УДК 004.021+004.421
ББК 32.973-018
Б11
Б11
Бёрд, Ричард.
Жемчужины проектирования алгоритмов: функциональный подход.
С примерами на языке Haskell / Р. Бёрд ; пер. с англ. В. Н. Брагилевского,
А. М. Пеленицына. — 2-е изд., эл. — 1 файл pdf : 331 с. — Москва :
ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe
Digital Editions 4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-89818-555-8
В этой книге Ричард Бёрд представляет принципиально новый подход к проектированию
алгоритмов, а именно проектирование посредством формального вывода.
Основное содержание книги разделено на 30 коротких глав, называемых жемчужинами,
в каждой из которых решается конкретная программистская задача.
Эти задачи, некоторые из них абсолютно новые, происходят из таких разнообразных
источников, как игры и головоломки, захватывающие комбинаторные построения
и более традиционные алгоритмы сжатия данных и сопоставления строк.
Каждая жемчужина начинается с постановки задачи, формулируемой на функциональном
языке программирования Haskell, чрезвычайно мощном и в то же
время лаконичном, позволяющем легко и просто выражать алгоритмические идеи.
Новшество книги состоит в том, что каждое решение формально вычисляется из
исходной постановки задачи посредством обращения к законам функционального
программирования.
Издание предназначено для программистов, увлекающихся функциональным
программированием, студентов, аспирантов и преподавателей, интересующихся
принципами проектирования алгоритмов, а также всех, кто желает приобрести и
развить навыки рассуждений в эквациональном стиле применительно к программам
и алгоритмам.
УДК 004.021+004.421
ББК 32.973-018
Электронное издание на основе печатного издания: Жемчужины проектирования
алгоритмов: функциональный подход. С примерами на языке Haskell / Р. Бёрд ; пер. с англ.
В. Н. Брагилевского, А. М. Пеленицына. — Москва : ДМК Пресс, 2015. — 330 с. — ISBN
978-5-97060-161-7. — Текст : непосредственный.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими
бы то ни было средствами без письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических ошибок все
равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений.
В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских
прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.
ISBN 978-5-89818-555-8
© Cambridge University Press
© Перевод на русский язык, оформление,
ДМК Пресс, 2015
Стр.5
Оглавление
Предисловие
1 Наименьшее отсутствующее число
2 Превосходная задача
3 Улучшаем седловой поиск
4 Задача о выборке
5 Сортировка попарных сумм
6 Делаем сотню
7 Строим дерево минимальной высоты
8 Распутываем жадные алгоритмы
9 Поиск знаменитостей
10 Удаляем повторы
11 Вовсе не максимальная сумма сегмента
12 Ранжируем суффиксы
13 Преобразование Барроуза–Уилера
14 Последний хвост
15 Все общие префиксы
9
12
19
24
35
42
49
58
68
75
84
94
101
115
128
139
Стр.8
8
Жемчужины проектирования алгоритмов: функциональный подход
16 Алгоритм Бойера—Мура
17 Алгоритм Кнута—Морриса—Пратта
18 Планирование в «Час пик»
19 Простой алгоритм решения судоку
20 Задача «Обратного отсчёта»
21 Хиломорфизмы и нексусы
22 Три способа вычисления определителей
23 Внутри выпуклой оболочки
24 Рациональное арифметическое кодирование
25 Целочисленное арифметическое кодирование
26 Алгоритм Шора—Вейта
27 Упорядоченная вставка
28 Бесцикловые функциональные алгоритмы
29 Алгоритм Джонсона—Троттера
30 Прядение паутины для чайников
Предметный указатель
145
156
166
178
189
202
215
224
236
247
262
274
287
298
306
326
Стр.9