Введение в анализ алгоритмов (5000,00 руб.)

Стр.5

Стр.7

Стр.8

Стр.9

Стр.10

УДК 510.5 ББК 22.18я73 С60 С60 Введение в анализ алгоритмов / пер. с анг. А. В. Логунова. – М.: ДМК Пресс, 2019. – 278 с.: ил. Солтис М. ISBN 978-5-97060-696-4 Книга представляет собой краткое, но математически строгое введение в анализ различных алгоритмов с точки зрения доказывания их правильности. Вы ознакомитесь с основными свойствами линейных, ветвящихся и циклических алгоритмов и способами их проверки. Книга содержит большое количество теоретических задач и практических примеров на языке Python. Издание предназначено для студентов вузов, специалистов в области информатики и математики, а также широкого круга программистов и разработчиков. УДК 510.5 ББК 22.18я73 Original English language edition published by World Scientific Publishing Co. Pte. Ltd. Copyright Все права защищены. Любая часть этой книги не может быть воспроизведена в какой © 2018 by World Scientific Publishing Co. Pte. Ltd. Russian-language edition copyright © 2019 by DMK Press. All rights reserved. бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. ISBN 978-981-3235-90-8 (анг.) ISBN 978-5-97060-696-4 (рус.) Copyright © 2018 by World Scientific Publishing Co. Pte. Ltd. © Оформление, издание, перевод, ДМК Пресс, 2019

Стр.5

Содержание Предисловие ...........................................................................................................10 Глава 1. Предварительные условия ..................................................................13 1.1. Что такое правильность? ....................................................................................13 1.1.1. Сложность .....................................................................................................14 1.1.2. Деление .........................................................................................................15 1.1.3. Евклид ...........................................................................................................17 1.1.4. Палиндромы .................................................................................................18 1.1.5. Дальнейшие примеры .................................................................................20 1.2. Алгоритмы ранжирования .................................................................................21 1.2.1. Алгоритм PageRank ......................................................................................22 1.2.2. Стабильный брачный союз ..........................................................................24 1.2.3. Попарные сравнения ...................................................................................27 1.3. Ответы к избранным задачам ............................................................................29 1.4. Примечания .........................................................................................................35 Глава 2. Жадный алгоритм ...................................................................................37 2.1. Остовные деревья минимальной стоимости ....................................................37 2.2. Задания с предельными сроками и прибылями ...............................................44 2.3. Дальнейшие примеры и задачи .........................................................................47 2.3.1. Отсчитывание сдачи ....................................................................................47 2.3.2. Паросочетание с максимальным весом .....................................................48 2.3.3. Кратчайший путь .........................................................................................48 2.3.4. Коды Хаффмана ...........................................................................................51 Глава 3. Разделяй и властвуй ..............................................................................61 3.1. Сортировка слиянием .........................................................................................61 3.2. Умножение двоичных чисел ...............................................................................63 3.3. Алгоритм Савича .................................................................................................65 3.4. Дальнейшие примеры и задачи .........................................................................67 3.4.1. Расширенный алгоритм Евклида ................................................................67 3.4.2. Быстрая сортировка .....................................................................................68 3.4.3. Команда git bisect .........................................................................................68 2.4. Ответы к избранным задачам ............................................................................53 2.5. Примечания .........................................................................................................59 3.5. Ответы к избранным задачам ............................................................................69 3.6. Примечания .........................................................................................................70 Глава 4. Динамическое программирование ...................................................72 4.1. Задача о наибольшей монотонной подпоследовательности ...........................72 4.2. Задача кратчайшего пути для всех пар .............................................................73

Стр.7

Содержание  7 4.2.1. Алгоритм Беллмана–Форда ........................................................................75 4.3. Простая задача о рюкзаке...................................................................................75 4.3.1. Задача о рассредоточенном рюкзаке .........................................................78 4.3.2. Общая задача о рюкзаке ..............................................................................79 4.4. Задача выбора мероприятий..............................................................................79 4.5. Задания с указанием предельных сроков, длительностей и прибылей ..........82 4.6. Дальнейшие примеры и задачи .........................................................................83 4.6.1. Задача суммирования сплошной подпоследовательности ......................83 4.6.2. Перетасовка ..................................................................................................84 Глава 5. Онлайновые алгоритмы........................................................................92 5.1. Задача доступа к списку .....................................................................................92 5.2. Замещение страниц ............................................................................................97 5.2.1. Замещение страниц по требованию ...........................................................98 5.2.2. Первым вошел/первым вышел (FIFO) ......................................................100 5.2.3. Наименее недавно использованная страница (LRU) ...............................100 5.2.4. Маркировочные алгоритмы ......................................................................103 5.2.5. Сброс при заполнении (FWF) ....................................................................105 5.2.6. Наибольшее расстояние вперед (LFD) ......................................................105 5.3. Ответы к избранным задачам ..........................................................................109 5.4. Примечания .......................................................................................................112 Глава 6. Рандомизированные алгоритмы ......................................................113 6.1. Идеальное паросочетание ................................................................................114 6.2. Сопоставление с образцом ...............................................................................117 6.3. Проверка простоты ...........................................................................................119 6.4. Шифрование с публичным ключом .................................................................122 6.4.1. Обмен ключами Диффи–Хеллмана ..........................................................122 6.4.2. Криптосистема Эль-Гамаля .......................................................................124 6.4.3. Криптосистема RSA ....................................................................................127 4.7. Ответы к избранным задачам ............................................................................86 4.8. Примечания .........................................................................................................90 6.5. Дальнейшие задачи ..........................................................................................128 6.6. Ответы к избранным задачам ..........................................................................129 6.7. Примечания .......................................................................................................134 Глава 7. Алгоритмы в линейной алгебре ........................................................138 7.1. Введение ............................................................................................................138 7.2. Гауссово исключение .........................................................................................138 7.2.1. Формальные доказательства правильности над �2 ..................................141 7.3. Алгоритм Грама-Шмидта ..................................................................................144 7.4. Гауссова редукция решетки ..............................................................................144 7.5. Вычисление характеристического многочлена ..............................................145 7.5.1. Алгоритм Чанки ..........................................................................................145 7.5.2. Алгоритм Берковица ..................................................................................146 7.5.3. Доказательство свойств характеристического многочлена ....................147

Стр.8

8  Содержание 7.6. Ответы к избранным задачам ..........................................................................152 7.7. Примечания .......................................................................................................154 Глава 8. Вычислительные основы ....................................................................155 8.1. Введение ............................................................................................................155 8.2. Алфавиты, строки и язык .................................................................................155 8.3. Регулярные языки .............................................................................................156 8.3.1. Детерминированный конечный автомат .................................................156 8.3.2. Недетерминированные конечные автоматы ...........................................159 8.3.3. Регулярные выражения .............................................................................162 8.3.4. Алгебраические законы для регулярных выражений .............................165 8.3.5. Свойства замыкания в регулярных языках ..............................................166 8.3.6. Сложность преобразований и принятия решений ..................................167 8.3.7. Эквивалентность и минимизация автоматов ..........................................167 8.3.8. Нерегулярные языки ..................................................................................169 8.3.9. Автоматы на членах ...................................................................................171 8.4. Контекстно-свободные языки ..........................................................................172 8.4.1. Контекстно-свободные грамматики .........................................................172 8.4.2. Магазинные автоматы ...............................................................................174 8.4.3. Нормальная форма Хомского ....................................................................176 8.4.4. Алгоритм CYK ............................................................................................178 8.4.5. Лемма о накачке для контекстно-свободных языков .............................179 8.4.6. Дальнейшие замечания по нормальной форме Хомского ......................180 8.4.7. Другие грамматики ....................................................................................181 8.5. Машины Тьюринга ...........................................................................................181 8.5.1. Недетерминированные машины Тьюринга .............................................182 8.5.2. Варианты кодирования .............................................................................184 8.5.3. Разрешимость .............................................................................................184 8.5.4. Тезис Черча–Тьюринга ..............................................................................185 8.5.5. Неразрешимость ........................................................................................186 8.5.6. Редукции .....................................................................................................188 8.5.7. Теорема Райса .............................................................................................189 8.5.8. Задача соответствий Поста ........................................................................189 8.5.9. Неразрешимые свойства контекстно-свободных языков .......................194 Глава 9. Математическая основа ......................................................................208 9.1. Индукция и инвариантность ............................................................................208 9.1.1. Индукция ....................................................................................................208 9.1.2. Инвариантность .........................................................................................211 9.2. Теория чисел ......................................................................................................212 9.2.1. Простые числа ............................................................................................213 9.2.2. Модулярная арифметика ...........................................................................213 9.2.3. Теория групп ..............................................................................................214 9.2.4. Приложения теории групп к теории чисел ..............................................216 8.6. Ответы к избранным задачам ..........................................................................195 8.7. Примечания .......................................................................................................205

Стр.9

Содержание  9 9.3. Отношения ........................................................................................................217 9.3.1. Замыкание ..................................................................................................218 9.3.2. Отношение эквивалентности ....................................................................220 9.3.3. Частичные порядки ....................................................................................221 9.3.4. Решетки ......................................................................................................223 9.3.5. Теория неподвижных точек.......................................................................224 9.3.6. Рекурсия и неподвижные точки ................................................................227 9.4. Логика ................................................................................................................229 9.4.1. Пропозициональная логика ......................................................................230 9.4.2. Первопорядковая логика ...........................................................................235 9.4.3. Арифметика Пеано ....................................................................................239 9.4.4. Формальная верификация ........................................................................239 Библиография .......................................................................................................263 Предметный указатель .......................................................................................269 9.5. Ответы к избранным задачам ..........................................................................242 9.6. Примечания .......................................................................................................261

Стр.10