Классические задачи Computer Science на языке Python

Благодарности.............................................................................................................12

Об этой книге..............................................................................................................14
Торговые марки..................................................................................................14
Форум этой книги................................................................................................14
Об авторе....................................................................................................................15
Об иллюстрации на обложке.......................................................................................16
От издательства..........................................................................................................18
Введение.....................................................................................................................19
Почему именно Python.........................................................................................20
Что такое классическая задача программирования.............................................20
Какие задачи представлены в этой книге............................................................21
Для кого эта книга..............................................................................................22
Версии Python, хранилище исходного кода и аннотации типов............................22
Никакой графики и пользовательских интерфейсов — только стандартная библиотека..23
Книги этой серии.................................................................................................24
Глава 1. Простые задачи............................................................................................25
1.1. Ряд Фибоначчи....................................................................................................25
1.1.1. Первый вариант рекурсии.........................................................................25
1.1.2. Использование базовых случаев...............................................................27
1.1.3. Спасение — в мемоизации........................................................................29
1.1.4. Автоматическая мемоизация.....................................................................30
1.1.5. Будьте проще, Фибоначчи!.......................................................................30
1.1.6. Генерация чисел Фибоначчи с помощью генератора.................................31
1.2. Простейшее сжатие.............................................................................................32
1.3. Невскрываемое шифрование...............................................................................37
1.3.1. Получение данных в заданной последовательности..................................38
1.3.2. Шифрование и дешифрование..................................................................39
1.4. Вычисление числа π............................................................................................41
1.5. Ханойские башни................................................................................................42
1.5.1. Моделирование башен..............................................................................42
1.5.2. Решение задачи о ханойских башнях........................................................44
1.6. Реальные приложения.........................................................................................46
1.7. Упражнения.........................................................................................................47
Глава 2. Задачи поиска..............................................................................................48
2.1. Поиск ДНК...........................................................................................................48
2.1.1. Хранение ДНК...........................................................................................48
2.1.2. Линейный поиск.......................................................................................50
2.1.3. Бинарный поиск........................................................................................51
2.1.4. Параметризованный пример.....................................................................54
2.2. Прохождение лабиринта.....................................................................................56
2.2.1. Создание случайного лабиринта................................................................57
2.2.2. Мелкие детали лабиринта.........................................................................58
2.2.3. Поиск в глубину........................................................................................59
2.2.4. Поиск в ширину........................................................................................63
2.2.5. Поиск по алгоритму A*.............................................................................67
2.3. Миссионеры и людоеды.......................................................................................73
2.3.1. Представление задачи..............................................................................74
2.3.2. Решение...................................................................................................76
2.4. Реальные приложения.........................................................................................78
2.5. Упражнения........................................................................................................78
Глава 3. Задачи с ограничениями...............................................................................80
3.1. Построение структуры для задачи с ограничениями............................................81
3.2. Задача раскраски карты Австралии.....................................................................85
3.3. Задача восьми ферзей.........................................................................................88
3.4. Поиск слова........................................................................................................91
3.5. SEND + MORE = MONEY......................................................................................94
3.6. Размещение элементов на печатной плате..........................................................96
3.7. Реальные приложения.........................................................................................97
3.8. Упражнения........................................................................................................98
Глава 4. Графовые задачи..........................................................................................99
4.1. Карта как граф....................................................................................................99
4.2. Построение графовой структуры.......................................................................102
4.2.1. Работа с Edge и Graph.............................................................................106
4.3. Поиск кратчайшего пути....................................................................................108
4.3.1. Пересмотр алгоритма поиска в ширину...................................................108
4.4. Минимизация затрат на построение сети...........................................................110
4.4.1. Работа с весами......................................................................................110
4.4.2. Поиск минимального связующего дерева................................................114
4.5. Поиск кратчайших путей во взвешенном графе.................................................121
4.5.1. Алгоритм Дейкстры.................................................................................121
4.6. Реальные приложения.......................................................................................126
4.7. Упражнения......................................................................................................127
Глава 5. Генетические алгоритмы............................................................................128
5.1. Немного биологической теории.........................................................................128
5.2. Обобщенный генетический алгоритм.................................................................130
5.3. Примитивный тест.............................................................................................137
5.4. SEND + MORE = MONEY, улучшенный вариант..................................................140
5.5. Оптимизация сжатия списка..............................................................................143
5.6. Проблемы генетических алгоритмов..................................................................146
5.7. Реальные приложения.......................................................................................147
5.8. Упражнения......................................................................................................148
Глава 6. Кластеризация методом k-средних..............................................................149
6.1. Предварительные сведения...............................................................................150
6.2. Алгоритм кластеризации k-средних...................................................................152
6.3. Кластеризация губернаторов по возрасту и долготе штата................................158
6.4. Кластеризация альбомов Майкла Джексона по длительности............................163
6.5. Проблемы и расширения кластеризации методом k-средних.............................165
6.6. Реальные приложения.......................................................................................166
6.7. Упражнения......................................................................................................166
Глава 7. Простейшие нейронные сети...................................................................... 167
7.1. В основе — биология?....................................................................................... 168
7.2. Искусственные нейронные сети......................................................................... 170
7.2.1. Нейроны................................................................................................. 170
7.2.2. Слои....................................................................................................... 171
7.2.3. Обратное распространение..................................................................... 172
7.2.4. Ситуация в целом................................................................................... 176
7.3. Предварительные замечания............................................................................. 176
7.3.1. Скалярное произведение........................................................................ 177
7.3.2. Функция активации................................................................................. 177
7.4. Построение сети................................................................................................ 179
7.4.1. Реализация нейронов.............................................................................. 179
7.4.2. Реализация слоев................................................................................... 180
7.4.3. Реализация сети..................................................................................... 182
7.5. Задачи классификации...................................................................................... 185
7.5.1. Нормализация данных............................................................................ 186
7.5.2. Классический набор данных радужной оболочки.................................... 187
7.5.3. Классификация вина............................................................................... 190
7.6. Повышение скорости работы нейронной сети.................................................... 192
7.7. Проблемы и расширения нейронных сетей........................................................ 193
7.8. Реальные приложения....................................................................................... 195
7.9. Упражнения...................................................................................................... 196
Глава 8. Состязательный поиск................................................................................ 197
8.1. Основные компоненты настольной игры............................................................ 197
8.2. Крестики-нолики............................................................................................... 199
8.2.1. Управление состоянием игры в крестики-нолики.................................... 200
8.2.2. Минимакс................................................................................................ 203
8.2.3. Тестирование минимакса для игры в крестики-нолики............................ 206
8.2.4. Разработка ИИ для игры в крестики-нолики............................................ 208
8.3. Connect Four...................................................................................................... 209
8.3.1. Подключите четыре игровых автомата.................................................... 209
8.3.2. ИИ для Connect Four................................................................................ 214
8.3.3. Улучшение минимакса с помощью альфа-бета-отсечения....................... 215
8.4. Другие улучшения минимакса........................................................................... 217
8.5. Реальные приложения....................................................................................... 218
8.6. Упражнения...................................................................................................... 218
Глава 9. Другие задачи............................................................................................ 220
9.1. Задача о рюкзаке.............................................................................................. 220
9.2. Задача коммивояжера....................................................................................... 226
9.2.1. Наивный подход..................................................................................... 226
9.2.2. Переходим на следующий уровень.......................................................... 230
9.3. Мнемоника для телефонных номеров................................................................ 231
9.4. Реальные приложения....................................................................................... 234
9.5. Упражнения...................................................................................................... 234
Приложение A. Глоссарий....................................................................................... 236
Приложение Б. Дополнительные ресурсы............................................................... 242
Б.1. Python............................................................................................................... 242
Б.2. Алгоритмы и структуры данных......................................................................... 243
Б.3. Искусственный интеллект.................................................................................. 244
Б.4. Функциональное программирование................................................................. 245
Б.5. Полезные проекты с открытым исходным кодом для машинного обучения........ 245
Приложение В. Коротко об аннотациях типов......................................................... 247
В.1. Что такое аннотации типов............................................................................... 247
В.2. Как выглядят аннотации типа........................................................................... 248
В.3. Почему полезны аннотации типов..................................................................... 249
В.4. Каковы недостатки аннотаций типов................................................................. 251
В.5. Источники дополнительной информации........................................................... 252