Введение.................................................................................9
Зачем нужна эта книга .........................................................9
Чего вы не найдете в издании............................................10
Дополнительные ресурсы...................................................11
От издательства ......................................................................12
Часть I. Основы Computer Science
Глава 1. Асимптотическое время выполнения ........................14
1.1. Что такое алгоритм....................................................14
1.2. Почему скорость имеет значение ...............................16
1.3. Когда секунды (не) считаются....................................17
1.4. Как мы описываем скорость .......................................20
1.5. Скорость типичных алгоритмов..................................21
1.6. Всегда ли полиномиальное время лучше? ..................25
1.7. Время выполнения алгоритма ....................................27
1.8. Насколько сложна задача? .........................................31
Глава 2. Структуры данных ....................................................32
2.1. Организация данных ..................................................32
2.2. Массивы, очереди и другие способы построиться.......33
2.3. Связные списки..........................................................35
2.4. Стеки и кучи ..............................................................38
2.5. Хеш-таблицы..............................................................42
2.6. Множества и частично упорядоченные
множества..................................................................45
2.7. Специализированные структуры данных ....................49
Глава 3. Классы задач............................................................50
Часть II. Графы и графовые алгоритмы
Глава 4. Введение в теорию графов.......................................60
4.1. Семь кенигсбергских мостов.......................................60
4.2. Мотивация .................................................................62
4.3. Терминология ............................................................64
4.4. Представление графов...............................................67
4.5. Направленные и ненаправленные графы ...................71
4.6. Циклические и ациклические графы ..........................72
4.7. Раскраска графа.........................................................76
4.8. Взвешенные и невзвешенные графы..........................79
Глава 5. Структуры данных на основе графов ........................81
5.1. Двоичные деревья поиска..........................................81
5.2. Сбалансированные деревья двоичного поиска ...........85
5.3. Кучи...........................................................................86
Глава 6. Хорошо известные графовые алгоритмы...................97
6.1. Введение....................................................................97
6.2. Поиск в ширину..........................................................98
6.3. Применение поиска в ширину ..................................101
6.4. Поиск в глубину .......................................................102
6.5. Кратчайшие пути .....................................................105
Глава 7. Основные классы графов........................................110
7.1. Запрещенные подграфы...........................................110
7.2. Планарные графы ....................................................111
7.3. Совершенные графы ................................................114
7.4. Двудольные графы...................................................116
7.5. Интервальные графы ...............................................117
7.6. Графы дуг окружности .............................................119
Часть III. Неграфовые алгоритмы
Глава 8. Алгоритмы сортировки ...........................................122
8.1. Малые и большие алгоритмы сортировки.................123
8.2. Сортировки для малых наборов данных ...................125
8.3. Сортировка больших наборов данных ......................128
8.4. Сортировки без сравнения .......................................132
Часть IV. Методы решения задач
Часть V. Теория сложности вычислений
Глава 12. Что такое теория сложности.................................154
Глава 13. Языки и конечные автоматы.................................157
13.1. Формальные языки...................................................157
13.2. Регулярные языки....................................................158
13.3. Контекстно свободные языки ...................................169
13.4. Контекстно зависимые языки ...................................175
13.5. Рекурсивные и рекурсивно перечислимые языки......176
Глава 14. Машины Тьюринга................................................178
14.1. Чисто теоретический компьютер..............................178
14.2. Построение машины Тьюринга.................................179
14.3. Полнота по Тьюрингу...............................................181
14.4. Проблема остановки ................................................181
Послесловие .......................................................................183
Приложение A. Необходимая математика ...........................186
Приложение Б. Классические NP-полные задачи ................188
Б.1. SAT и 3-SAT..............................................................188
Б.2. Клика.......................................................................189
Б.3. Кликовое покрытие ..................................................189
Б.4. Раскраска графа.......................................................189
Б.5. Гамильтонов путь.....................................................190
Б.6. Укладка рюкзака ......................................................190
Б.7. Наибольшее независимое множество .......................190
Б.8. Сумма подмножества ...............................................190
Глава 9. А если в лоб?..........................................................138
Глава 10. Динамическое программирование ........................141
10.1. Задача недостающих полей .....................................141
10.2. Работа с перекрывающимися подзадачами ..............143
10.3. Динамическое программирование
и кратчайшие пути...................................................145
10.4. Примеры практического применения .......................147
Глава 11. Жадные алгоритмы...............................................150