Жемчужины проектирования алгоритмов: функциональный подход (3000,00 руб.)

Стр.5

Стр.8

Стр.9

УДК 004.021+004.421 ББК 32.973-018 Б11 Б11 Ричард Бёрд Жемчужины проектирования алгоритмов: функциональный подход / Пер. с англ. В. Н. Брагилевского и А.М. Пеленицына. – М.: ДМК Пресс, 2015. — 330 с.: ил. ISBN 978-5-97060-161-7 В этой книге Ричард Бёрд представляет принципиально новый подход к проектированию алгоритмов, а именно проектирование посредством формального вывода. Основное содержание книги разделено на 30 коротких глав, называемых жемчужинами, в каждой из которых решается конкретная программистская задача. Эти задачи, некоторые из них абсолютно новые, происходят из таких разнообразных источников, как игры и головоломки, захватывающие комбинаторные построения и более традиционные алгоритмы сжатия данных и сопоставления строк. Каждая жемчужина начинается с постановки задачи, формулируемой на функциональном языке программирования Haskell, чрезвычайно мощном и в то же время лаконичном, позволяющем легко и просто выражать алгоритмические идеи. Новшество книги состоит в том, что каждое решение формально вычисляется из исходной постановки задачи посредством обращения к законам функционального программирования. Издание предназначено для программистов, увлекающихся функциональным программированием, студентов, аспирантов и преподавателей, интересующихся принципами проектирования алгоритмов, а также всех, кто желает приобрести и развить навыки рассуждений в эквациональном стиле применительно к программам и алгоритмам. УДК 004.021+004.421 ББК 32.973-018 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок всё равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несёт ответственности за возможные ошибки, связанные с использованием книги. ISBN 978-0-521-51338-8 (англ.) ISBN 978-5-97060-161-7(рус.) ○c Cambridge University Press ○c Перевод на русский язык, оформление, ДМК Пресс, 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