Магазинов: 3, Цена: от 1439 руб. посмотреть все

В этой книге Ричард Бёрд представляет принципиально новый подход к проектированию алгоритмов, а именно проектирование посредством формального вывода. Основное содержание книги разделено на 30 коротких глав, называемых жемчужинами, в каждой из которых решается конкретная программистская задача. Эти задачи, некоторые из которых абсолютно новые, происходят из таких разнообразных источников, как игры и головоломки, захватывающие комбинаторные построения и более традиционные алгоритмы сжатия данных и сопоставления строк. Каждая жемчужина начинается с постановки задачи, формулируемой на функциональном языке программирования Haskell, чрезвычайно мощном и в то же время лаконичном, позволяющем легко и просто выражать алгоритмические идеи. Новшество книги состоит в том, что каждое решение формально вычисляется из исходной постановки задачи посредством обращения к законам функционального программирования. Издание предназначено для программистов, увлекающихся функциональным программированием, студентов, аспирантов и преподавателей, интересующихся принципами проектирования алгоритмов, а также всех, кто желает приобрести и развить навыки рассуждений в эквациональном стиле применительно к программам и алгоритмам.

  Book24 - 1439 руб.   Буквоед - 1439 руб.   Читай-Город - 1439 руб.

  Литрес - 399 руб.

В 1990 году, когда журнал Journal of Functional Programming (JFP) только планировался к выходу, бывшие тогда редакторами Саймон Пейтон Джонс (Simon Peyton Jones) и Филипп Вадлер (Philip Wadler) попросили меня взяться за постоянную колонку под названием Функциональные жемчужины (Functional Pearls). Их идея заключалась в подражании чрезвычайно успешной серии эссе Джона Бентли (Jon Bentley) «Жемчужины программирования», которые публиковались в 80-е годы в журнале Communications of the ACM. Вот что Бентли писал о своих жемчужинах:
Как настоящие жемчужины вырастают из песчинок, раздражающих устриц, так и жемчужины программирования вырастают из реальных задач, мучающих программистов. Эти программы интересны, к тому же они учат важным программистским приёмам и фундаментальным принципам проектирования.
Мне кажется, что редакторы обратились именно ко мне, потому что я интересовался следующим подходом: я брал понятную, но неэффективную функциональную программу, выступавшую в роли спецификации к решаемой задаче, а затем посредством эквациональных рассуждений приходил к более эффективной версии. Одним из факторов, стимулирующих рост интереса к функциональным языкам в 90-е годы, было именно удобство применения эквациональных рассуждений. В самом деле, акроним в названии функционального языка GOFER, изобретённого Марком Джонсом (Mark Jones), отражает как раз эту идею. GOFER стал одним из языков, повлиявших на развитие языка Haskell, на котором основывается настоящая книга. Эквациональные рассуждения доминируют здесь над всем. Жемчужины проектирования алгоритмов: функциональный подход. За последние 20 лет в JFP и изредка на таких конференциях как International Conference of Functional Programming (ICFP) и Mathematics of Program Construction Conference (MPC) появилось около 80 жемчужин. Из них я написал примерно четверть, большая же часть написана другими. Темы этих жемчужин включают интересные выводы программ, новые структуры данных, а также маленькие, но элегантные встроенные в Haskell и ML предметно-ориентированные языки для конкретных приложений. Мне всегда были интересны алгоритмы и их проектирование. Отсюда название этой книги — Жемчужины проектирования алгоритмов: функциональный подход — вместо более общего Функциональные жемчужины. Многие, хотя и не все, жемчужины начинаются со спецификации на языке Haskell, а затем продолжаются выводом более эффективной реализации. При написании конкретно этих жемчужин мне хотелось выяснить, до какой степени проектирование алгоритма можно представить в виде традиционного в математике вычисления результата посредством применения общеизвестных принципов, теорем и законов. Хотя в математике вычисления обычно производятся для упрощения сложных выражений, в проектировании алгоритмов получается в точности наоборот: простые, но неэффективные программы преобразуются в более эффективные, но, возможно, неочевидные. Жемчужиной является не полученная в итоге программа, а скорее процесс её получения. Остальные жемчужины, в части из них совсем немного преобразований, посвящены попыткам дать простые объяснения некоторым интересным и довольно хитроумным алгоритмам. Объяснение идей, лежащих в основе алгоритма, при функциональном подходе оказывается гораздо проще, чем при императивном: составляющие алгоритм функции легче отделить, они коротки и отражают мощные вычислительные шаблоны. Жемчужины в этой книге, появлявшиеся прежде в JFP и других местах, были неоднократно отшлифованы. Собственно, многие не слишком сильно напоминают оригиналы. Даже при этом их несложно отшлифовать ещё лучше. Золотым стандартом красоты в математике считается книга Айгнера (Aigner) и Циглера (Ziegler) Proofs from The Book (третье издание, Springer, 2003), содержащая совершенные доказательства математических теорем. Я всегда рассматриваю эту книгу как идеал, к которому следует стремиться.
Примерно треть жемчужин новые. С некоторыми явно обозначенными исключениями жемчужины можно читать в любом порядке, хотя главы были упорядочены до некоторой степени по темам, таким как «разделяй и властвуй», жадные алгоритмы, полный перебор и т.п. В жемчужинах присутствует небольшое повторение материала, по большей части относящегося к свойствам используемых библиотечных функций или к более общим законам, таким как законы слияния для разнообразных свёрток. При необходимости читатель может обратиться к добавленному к книге короткому предметному указателю. Наконец, в этой книге собраны идеи многих людей. Некоторые жемчужины были изначально написаны в сотрудничестве с другими авторами. Я хотел бы поблагодарить Шэрон Кёртис (Sharon Curtis), Джереми Гиббонса (Jeremy Gibbons), Ральфа Хинзе (Ralf Hinze), Герэйнта Джонса (Geraint Jones) и Шин-Чень Му (Shin-Cheng Mu), моих соавторов, за щедрое разрешение переработать этот материал. Джереми Гиббонс прочитал окончательную версию черновика и сделал множество полезных предложений, направленных на улучшение изложения. Некоторые жемчужины досконально обсуждались на встречах исследовательской группы Algebra of Programming в Оксфорде. Хотя многие из недостатков и ошибок были исправлены, нет никаких сомнений в том, что при этом добавились новые. Помимо упомянутых ранее, я хотел бы выразить благодарность Стивену Дрейпу (Stephen Drape), Тому Харперу (Tom Harper), Дэниэлю Джеймсу (Daniel James), Джеффри Лейку (Jeffrey Lake), Менг Вонг (Meng Wang) и Николасу Ву (Nicholas Wu) за предложения по улучшению текста. Я также хотел бы поблагодарить Ламберта Мертенса (Lambert Meertens) и Уга де Мура (Oege de Moor) за плодотворное многолетнее сотрудничество. Наконец, я в долгу у Дэвида Транаха (David Tranah), моего редактора в издательстве Cambridge University Press, за содействие и поддержку, и в том числе за столь необходимые технические советы по подготовке окончательной версии.

Предисловие
1 Наименьшее отсутствующее число
2 Превосходная задача
3 Улучшаем седловой поиск
4 Задача о выборке
5 Сортировка попарных сумм
6 Делаем сотню
7 Строим дерево минимальной высоты
8 Распутываем жадные алгоритмы
9 Поиск знаменитостей
10 Удаляем повторы
11 Вовсе не максимальная сумма сегмента
12 Ранжируем суффиксы
13 Преобразование Барроуза-Уилера
14 Последний хвост
15 Все общие префиксы
16 Алгоритм Бойера-Мура
17 Алгоритм Кнута- Морриса-Пратта
18 Планирование в "Час пик"
19 Простой алгоритм решения судоку
20 Задача "Обратного отсчёта"
21 Хиломорфизмы и нексусы
22 Три способа вычисления определителей
23 Внутри выпуклой оболочки
24 Рациональное арифметическое
кодирование
25 Целочисленное арифметическое
кодирование
26 Алгоритм Шора-Вейта
27 Упорядоченная вставка
28 Бесцикловые функциональные алгоритмы
29 Алгоритм Джонсона-Троттера
30 Прядение паутины для чайников
Предметный указатель