Введение в анализ алгоритмов

                  Майкл Солтис



Введение в анализ алгоритмов

                         Michael Soltys
                     California State University Channel Islands, USA



   An Introduction to the
    Analysis of Algorithms



                 3rd Edition





NEW JERSEY • LONDON • SINGAPORE • BEIJING • SHANGHAI • HONG KONG • TAIPEI • CHENNAI • TOKYO

             Майкл Солтис
   Калифорнийский университет Нормандские острова



     Введение
в анализ алгоритмов





                     Москва, 2019

УДК  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 (анг.)        Copyright © 2018 by World Scientific Publishing Co.
                                         Pte. Ltd.
ISBN 978-5-97060-696-4 (рус.)        ©  Оформление, издание, перевод, ДМК Пресс, 2019

Посвящается моей семье

Содержание




Предисловие............................................................................................................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
2.4. Ответы к избранным задачам.............................................................................53
2.5. Примечания..........................................................................................................59

Глава 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
3.5. Ответы к избранным задачам.............................................................................69
3.6. Примечания..........................................................................................................70

Глава 4. Динамическое программирование....................................................72
4.1. Задача о наибольшей монотонной подпоследовательности............................72
4.2. Задача кратчайшего пути для всех пар..............................................................73

                                                         Содержание    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
4.7. Ответы к избранным задачам.............................................................................86
4.8. Примечания..........................................................................................................90

Глава 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
6.5. Дальнейшие задачи...........................................................................................128
6.6. Ответы к избранным задачам...........................................................................129
6.7. Примечания........................................................................................................134

Глава 7. Алгоритмы в линейной алгебре.........................................................138
7.1. Введение.............................................................................................................138
7.2. Гауссово исключение..........................................................................................138
   7.2.1. Формальные доказательства правильности над
7.3. Алгоритм Грама-Шмидта...................................................................................1447.4. Гауссова редукция решетки...............................................................................144Ժ2...................................141
7.5. Вычисление характеристического многочлена...............................................145
   7.5.1. Алгоритм Чанки...........................................................................................145
   7.5.2. Алгоритм Берковица...................................................................................146
   7.5.3. Доказательство свойств характеристического многочлена.....................147

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
8.6. Ответы к избранным задачам...........................................................................195
8.7. Примечания........................................................................................................205

Глава 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

                                                         Содержание    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
9.5. Ответы к избранным задачам...........................................................................242
9.6. Примечания........................................................................................................261

Библиография........................................................................................................263
Предметный указатель........................................................................................269

Предисловие




                                                Ах, если бы он чуть поменьше знал, на                                             сколько лучше он мог бы научить неиз                                      меримо большему!
                                                 Чарльз Диккенс [Dickens (1854)], стр. 7

  Эта книга представляет собой краткое введение в анализ алгоритмов с точки
зрения доказывания правильности алгоритма. Приведенная выше цитата относится к г-ну Чадомору, карикатуре на учителя из «Тяжелых времен» Чарльза Диккенса, который душит умы своих учеников слишком большим объемом информации. Мы избежим ошибки Чадомора и возведем краткость в добродетель.
  Наша тема заключается в следующем: как математически, без бремени чрезмерного формализма, доказывать, что заданный алгоритм делает то, что он должен делать? И почему это так важно? По словам К. А. Р. Хоара:
    Что касается фундаментальной науки, то мы до сих пор точно не знаем, как
    доказывать правильность программ. Нам требуется довольно много устой     чивого прогресса в этой области, который можно было бы предвидеть, и ряд
     прорывов, когда люди внезапно обнаруживают, что, оказывается, существует
    простой способ сделать то, что всеми до сих пор считалось слишком трудным1.
  Инженеры по программному обеспечению знают много примеров того, когда
дела принимают ужасный оборот из-за программных ошибок; их конкретными
фаворитами являются следующие два из них2. Отключение электроэнергии на
северо-востоке Америки летом 2003 года было вызвано программным дефектом
в системе энергоуправления; сигнал тревоги, который должен был сработать, так
и не сработал, что привело к цепочке событий, кульминацией которых стало каскадное отключение электроэнергии. Ариан 5, полет 501, первый полет ракеты
4 июня 1996 г., закончился взрывом на 40-й секунде полета; этот убыток в размере
500 млн долл. был вызван переполнением при конвертации 64-разрядного числа
с плавающей запятой в 16-разрядное целое число со знаком.
  Когда Ричард А. Кларк, бывший национальный координатор по безопасности,
спросил Эда Аморосо, руководителя подразделения по сетевой безопасности
AT&T Network Security, что нужно сделать в отношении уязвимостей в киберинфраструктуре США, Аморосо сказал:
    Программное обеспечение – это большая часть проблемы. Мы должны пи    сать программное обеспечение, которое имеет гораздо меньше ошибок и яв    ляется гораздо безопасным3.


1  Из интервью с К. А. Р. Хоаром, разработчиком алгоритма «быстрой сортировки», в [Shus   tek (2009)].
2  Эти два примера взяты из публикации [van Vliet (2000)], где можно найти еще много
  примеров впечатляющих провалов.
3  См. стр. 272 в [Clarke и Knake (2011)].