Оглавление
Благодарности............................................................................................................ 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
Оглавление  7
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
8  Оглавление
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
Оглавление  9
Глава 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
10  Оглавление
Глава 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