Новая книга была добавлена в корзину

Задача книги "Введение в анализ алгоритмов" проста: разобрать «идеи», лежащие в основе программ, и показать, как доказывать их правильность.
Как математически доказать, что заданный алгоритм делает то, что он должен делать? И почему это так важно?
Доказывается правильность классических алгоритмов: целочисленного деления, алгоритм Евклида, ранжирования, др. Помимо традиционных алгоритмов, таких как жадные алгоритмы, алгоритмы динамического программирования и алгоритмы «разделяй и властвуй», книга исследует также рандомизированные и онлайновые алгоритмы. Первые стали повсеместными из-за появления криптографии, а вторые необходимы во многих областях, начиная с операционных систем и заканчивая фондовым рынком.

Книга "Введение в анализ алгоритмов" усеяна задачами. Большинство задач теоретические, но многие требуют реализации алгоритма; для таких задач используется язык программирования Python 3. Несмотря на свою краткость, издание является математически строгим. Желательно предварительное знакомство с дискретной математикой.
Издание предназначено для студентов вузов, специалистов в области информатики и математики, а также широкого круга программистов и разработчиков.




Содержание книги Солтис М. "Введение в анализ алгоритмов"




Предисловие............................................................................................................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
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. Формальные доказательства правильности над ??2...................................141
7.3. Алгоритм Грама-Шмидта...................................................................................144
7.4. Гауссова редукция решетки...............................................................................144
7.5. Вычисление характеристического многочлена...............................................145
7.5.1. Алгоритм Чанки...........................................................................................145
7.5.2. Алгоритм Берковица...................................................................................146
7.5.3. Доказательство свойств характеристического многочлена.....................147
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.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