Книга с подробным описанием всевозможных алгоритмов, которые принято реализовывать на C++ в силу высоких требований к скорости и наращиванию мощности алгоритмов. Алгоритмы относятся к следующим предметным областям: машинное обучение и нейронные сети, статистика, криптография, оптимизация, перемножение матриц, хэширование, строковые алгоритмы, случайные леса, методы работы с числами, сортировка, кластеризация, графовые алгоритмы и другие темы, касающиеся программной инженерии. Затронуты вопросы командной разработки алгоритмов.
Книгу можно использовать как справочник по алгоритмам для программистов и исследователей и как учебное пособие для студентов соответствующих специальностей. Также будет полезна при подготовке к собеседованиям.
Желаю, чтобы мое желание не исполнилось.
Дуглас Хофштадтер
Профессия программиста неотделима от работы с алгоритмами и структурами данных. В идеале алгоритм должен быть корректным, легко понятным, применимым для решения разнообразных задач и при этом эффективным. В книге даны и объяснены реализации всевозможных алгоритмов, готовых к внедрению и не защищенных авторскими правами. Алгоритмы относятся к следующим предметным областям:
- статистические методы,
- числовые методы,
- программная инженерия,
- сортировка,
- хэширование,
- графовые алгоритмы,
- оптимизация,
- криптография,
- строковые алгоритмы,
- спектральная кластеризация,
- глубокое обучение,
- перемножение матриц
- случайные леса
и другим.
Важнейшая часть книги посвящена машинному обучению и отличается значительным теоретическим и академическим уклоном.
Каждая глава будет для вас небольшим открытием. Например, разобраны малоизученные практические аспекты выпуклой оптимизации, метода Монте-Карло и кластеризации при проектировании и усилении нейронных сетей. Затронуты вопросы командной разработки алгоритмов.
В зависимости от уровня вашей подготовки книга может послужить учебником или справочником, но на долгие годы останется для вас настольной.
Предисловие…………………………………………………………………………………………… 19
- С чего всё начинается………………………………………………………………………… 21
1.1. Введение………………………………………………………………………………………………………………………………. 21
1.2. Каким должен быть алгоритм?………………………………………………………………………………………….. 21
1.3. Логика принятия решений………………………………………………………………………………………………….. 23
1.4. Доказательство базовой правильности…………………………………………………………………………….. 25
1.5. Асимптотическая запись…………………………………………………………………………………………………….. 27
1.6. Машинные модели……………………………………………………………………………………………………………… 27
1.7. Рандомизированные алгоритмы………………………………………………………………………………………… 29
1.8. Измерение эффективности………………………………………………………………………………………………….. 29
1.9. Типы данных……………………………………………………………………………………………………………………….. 30
1.10. Эксперименты с алгоритмами…………………………………………………………………………………………. 32
1.11. Управление памятью………………………………………………………………………………………………………… 33
1.12. Оптимизация кода…………………………………………………………………………………………………………….. 34
1.13. Рекурсия…………………………………………………………………………………………………………………………….. 36
1.14. Стратегии вычислений……………………………………………………………………………………………………… 37
1.15. Выбор среди нескольких алгоритмов……………………………………………………………………………… 37
1.16. Создание параллельных алгоритмов……………………………………………………………………………… 38
1.17. Реализация алгоритмов……………………………………………………………………………………………………. 39
1.18. Рекомендуемые курсы для студентов, изучающих информатику………………………………… 40
1.19. Некоторые стратегии обучения………………………………………………………………………………………. 42
1.20. О проектах всей книги………………………………………………………………………………………………………. 43
1.21. Список рекомендуемой литературы……………………………………………………………………………….. 44
- Основы разработки программного обеспечения…………………………………. 45
2.1. Введение………………………………………………………………………………………………………………………………. 45
2.2. Обзор цикла разработки…………………………………………………………………………………………………….. 45
2.3. Требования………………………………………………………………………………………………………………………….. 46
2.4. Проектирование структуры компонентов………………………………………………………………………… 47
2.5. Проектирование отдельных компонентов и написание кода…………………………………………. 47
2.6. Шаблоны……………………………………………………………………………………………………………………………… 48
2.7. Управление ошибками……………………………………………………………………………………………………….. 52
2.8. Тестирование………………………………………………………………………………………………………………………. 54
2.9. Просмотр кода…………………………………………………………………………………………………………………….. 56
2.10. Релиз…………………………………………………………………………………………………………………………………… 56
2.11. Обслуживание…………………………………………………………………………………………………………………… 57
2.12. Оценка………………………………………………………………………………………………………………………………… 58
2.13. Следование формальному процессу……………………………………………………………………………….. 58
2.14. Управление данными пользователя………………………………………………………………………………… 59
2.15. Список рекомендуемой литературы……………………………………………………………………………….. 59
- Советы по вопросам карьерного роста ипрохождения собеседований.. 60
3.1. Введение………………………………………………………………………………………………………………………………. 60
3.2. Отклик на вакансию……………………………………………………………………………………………………………. 60
3.3. Составление резюме…………………………………………………………………………………………………………… 60
3.4. Поведенческие вопросы и собеседования………………………………………………………………………… 61
3.5. Технические собеседования………………………………………………………………………………………………. 63
3.6. Более сложные вопросы…………………………………………………………………………………………………….. 67
3.7. Собеседование по проектированию систем……………………………………………………………………… 68
3.8. Обсуждение предложения………………………………………………………………………………………………….. 68
3.9. Как красиво уйти с текущей работы?……………………………………………………………………………….. 69
3.10. Боритесь с самуспокоенностью………………………………………………………………………………………. 69
3.11. Советы по дополнительной подготовке………………………………………………………………………….. 70
3.12. Список рекомендуемой литературы……………………………………………………………………………….. 70
- Основы компьютерного права……………………………………………………………. 71
4.1. Введение………………………………………………………………………………………………………………………………. 71
4.2. Интеллектуальная собственность……………………………………………………………………………………… 71
4.3. Патенты……………………………………………………………………………………………………………………………….. 72
4.4. Коммерческие тайны………………………………………………………………………………………………………….. 73
4.5. Авторские права………………………………………………………………………………………………………………….. 74
4.6. Товарные знаки…………………………………………………………………………………………………………………… 75
4.7. Управление интеллектуальной собственностью……………………………………………………………… 76
4.8. Контракты……………………………………………………………………………………………………………………………. 76
4.9. Лицензии………………………………………………………………………………………………………………………………. 77
4.10. Трудовые соглашения………………………………………………………………………………………………………. 78
4.11. Конфиденциальность……………………………………………………………………………………………………….. 79
4.12. Киберпреступления………………………………………………………………………………………………………….. 80
4.13. Выступления в качестве свидетеля-эксперта…………………………………………………………………. 80
4.14. Советы по дополнительной подготовке………………………………………………………………………….. 81
4.15. Список рекомендуемой литературы……………………………………………………………………………….. 81
- Фундаментальные структуры данных………………………………………………… 82
5.1. Введение………………………………………………………………………………………………………………………………. 82
5.2. Вспомогательные функции………………………………………………………………………………………………… 82
5.3. Вектор………………………………………………………………………………………………………………………………….. 88
5.4. Блочный массив………………………………………………………………………………………………………………….. 92
5.5. Связанный список……………………………………………………………………………………………………………….. 93
5.6. Свободный список со сборкой мусора……………………………………………………………………………… 97
5.7. Стек…………………………………………………………………………………………………………………………………….. 101
5.8. Очередь………………………………………………………………………………………………………………………………. 102
5.9. Деревья………………………………………………………………………………………………………………………………. 105
5.10. Битовые алгоритмы………………………………………………………………………………………………………… 106
5.11. Набор битов…………………………………………………………………………………………………………………….. 109
5.12. Поиск объединения…………………………………………………………………………………………………………. 115
5.13. Примечания по реализации……………………………………………………………………………………………. 116
5.14. Комментарии…………………………………………………………………………………………………………………… 116
5.15. Советы по дополнительной подготовке……………………………………………………………………….. 117
5.16. Список рекомендуемой литературы……………………………………………………………………………… 117
- Генерация случайных чисел……………………………………………………………… 118
6.1. Введение…………………………………………………………………………………………………………………………….. 118
6.2. Краткий обзор теории вероятностей………………………………………………………………………………. 118
6.3. Генерация псевдослучайных чисел………………………………………………………………………………… 120
6.4. Класс генераторов псевдослучайных чисел Xorshift……………………………………………………. 122
6.5. Вихрь Мерсенна……………………………………………………………………………………………………………….. 123
6.6. Генератор MRG32k3a………………………………………………………………………………………………………. 123
6.7. Алгоритм RC4……………………………………………………………………………………………………………………. 125
6.8. Выбор генератора…………………………………………………………………………………………………………….. 126
6.9. Использование генератора………………………………………………………………………………………………. 127
6.10. Создание выборок из распределений……………………………………………………………………………. 127
6.11. Генерация выборок из дискретных распределений с ограниченным диапазоном…… 129
6.12. Генерация выборок из особых распределений……………………………………………………………. 133
6.13. Генерация случайных объектов……………………………………………………………………………………. 137
6.14. Генерация выборок из многомерных распределений………………………………………………….. 139
6.15. Метод Монте-Карло………………………………………………………………………………………………………. 140
6.16. Примечания по реализации……………………………………………………………………………………………. 146
6.17. Комментарии…………………………………………………………………………………………………………………… 147
6.18. Советы по дополнительной подготовке……………………………………………………………………….. 147
6.19. Список рекомендуемой литературы……………………………………………………………………………… 148
- Сортировка………………………………………………………………………………………. 149
7.1. Введение…………………………………………………………………………………………………………………………….. 149
7.2. Сортировка вставками……………………………………………………………………………………………………… 149
7.3. Быстрая сортировка…………………………………………………………………………………………………………. 150
7.4. Сортировка слиянием……………………………………………………………………………………………………….. 153
7.5. Целочисленная сортировка……………………………………………………………………………………………… 154
7.6. Векторная сортировка……………………………………………………………………………………………………… 155
7.7. Сортировка перестановкой……………………………………………………………………………………………… 158
7.8. Выбор…………………………………………………………………………………………………………………………………. 159
7.9. Множественный выбор…………………………………………………………………………………………………….. 160
7.10. Поиск………………………………………………………………………………………………………………………………… 161
7.11. Примечания по реализации……………………………………………………………………………………………. 161
7.12. Комментарии…………………………………………………………………………………………………………………… 162
7.13. Советы по дополнительной подготовке……………………………………………………………………….. 163
7.14. Список рекомендуемой литературы……………………………………………………………………………… 163
- Динамически сортируемые последовательности……………………………….. 164
8.1. Введение…………………………………………………………………………………………………………………………….. 164
8.2. Требования………………………………………………………………………………………………………………………… 164
8.3. Список с пропусками………………………………………………………………………………………………………… 165
8.4. Декартово дерево……………………………………………………………………………………………………………… 170
8.5. Итераторы деревьев………………………………………………………………………………………………………….. 176
8.6. Дополнения и варианты API……………………………………………………………………………………………. 178
8.7. Векторные ключи……………………………………………………………………………………………………………… 179
8.8. Расширение LCP для деревьев…………………………………………………………………………………………. 179
8.9. Префиксное дерево……………………………………………………………………………………………………………. 185
8.10. Тернарное декартово дерево…………………………………………………………………………………………. 186
8.11. Сравнение производительности……………………………………………………………………………………. 191
8.12. Примечания по реализации……………………………………………………………………………………………. 192
8.13. Комментарии…………………………………………………………………………………………………………………… 192
8.14. Советы по дополнительной подготовке……………………………………………………………………….. 194
8.15. Список рекомендуемой литературы……………………………………………………………………………… 194
- Хеширование……………………………………………………………………………………. 196
9.1. Введение…………………………………………………………………………………………………………………………….. 196
9.2. Хеш-функции……………………………………………………………………………………………………………………… 196
9.3. Универсальные хеш-функции………………………………………………………………………………………….. 200
9.4. Неуниверсальные хеш-функции………………………………………………………………………………………. 203
9.5. Скользящие хеш-функции………………………………………………………………………………………………… 205
9.6. Коллекция хеш-функций…………………………………………………………………………………………………… 206
9.7. Хеш-таблицы…………………………………………………………………………………………………………………….. 206
9.8. Цепочка хеш-таблиц…………………………………………………………………………………………………………. 206
9.9. Хеш-таблица с линейным зондированием……………………………………………………………………… 211
9.10. Оценка времени……………………………………………………………………………………………………………….. 215
9.11. Фильтр Блума………………………………………………………………………………………………………………….. 216
9.12. Примечания по реализации……………………………………………………………………………………………. 217
9.13. Комментарии…………………………………………………………………………………………………………………… 218
9.14. Советы по дополнительной подготовке……………………………………………………………………….. 219
9.15. Список рекомендуемой литературы……………………………………………………………………………… 219
- Приоритетные очереди……………………………………………………………………. 221
10.1. Введение………………………………………………………………………………………………………………………….. 221
10.2. API……………………………………………………………………………………………………………………………………. 221
10.3. Бинарная куча…………………………………………………………………………………………………………………. 221
10.4. Индексированные кучи…………………………………………………………………………………………………… 224
10.5. Примечания по реализации……………………………………………………………………………………………. 229
10.6. Комментарии…………………………………………………………………………………………………………………… 229
10.7. Список рекомендуемой литературы……………………………………………………………………………… 230
- Алгоритмы графов………………………………………………………………………….. 231
11.1. Введение………………………………………………………………………………………………………………………….. 231
11.2. Основы……………………………………………………………………………………………………………………………… 231
11.3. Представление графов……………………………………………………………………………………………………. 232
11.4. Поиск………………………………………………………………………………………………………………………………… 235
11.5. Примеры задач поиска…………………………………………………………………………………………………… 237
11.6. Минимальное остовное дерево……………………………………………………………………………………… 239
11.7. Кратчайшие пути……………………………………………………………………………………………………………. 240
11.8. Алгоритмы потока………………………………………………………………………………………………………….. 243
11.9. Двудольное сопоставление……………………………………………………………………………………………. 247
11.10. Устойчивое сопоставление………………………………………………………………………………………….. 248
11.11. Задача назначения……………………………………………………………………………………………………….. 249
11.12. Генерация случайных графов……………………………………………………………………………………… 250
11.13. Примечания по реализации…………………………………………………………………………………………. 251
11.14. Комментарии…………………………………………………………………………………………………………………. 251
11.15. Советы по дополнительной подготовке……………………………………………………………………… 252
11.16. Список рекомендуемой литературы…………………………………………………………………………… 252
- Разные алгоритмы и методы…………………………………………………………… 253
12.1. Введение………………………………………………………………………………………………………………………….. 253
12.2. Превращение статических структур данных в динамические……………………………………. 253
12.3. Обеспечение устойчивости структур данных……………………………………………………………… 254
12.4. Хранение кеша………………………………………………………………………………………………………………… 255
12.5. Вектор с k-битным размером слова………………………………………………………………………………. 258
12.6. Объединение множества на интервалах………………………………………………………………………. 259
12.7. Создание первых N простых чисел……………………………………………………………………………….. 259
12.8. Генерация всех возможных перестановок……………………………………………………………………. 260
12.9. Генерация всех возможных сочетаний…………………………………………………………………………. 261
12.10. Генерация всех подмножеств………………………………………………………………………………………. 262
12.11. Создание всех разделов……………………………………………………………………………………………….. 262
12.12. Генерация всех зависимых объектов………………………………………………………………………….. 263
12.13. Примечания по реализации…………………………………………………………………………………………. 263
12.14. Комментарии…………………………………………………………………………………………………………………. 263
12.15. Советы по дополнительной подготовке……………………………………………………………………… 264
12.16. Список рекомендуемой литературы…………………………………………………………………………… 264
- Алгоритмы для работы с внешней памятью……………………………………. 265
13.1. Введение………………………………………………………………………………………………………………………….. 265
13.2. Диски и файлы…………………………………………………………………………………………………………………. 265
13.3. Структура файла…………………………………………………………………………………………………………….. 268
13.4. Работа с файлами CSV…………………………………………………………………………………………………… 269
13.5. Модель ввода/вывода…………………………………………………………………………………………………….. 273
13.6. Вектор внешней памяти………………………………………………………………………………………………….. 277
13.7. Сортировка……………………………………………………………………………………………………………………… 280
13.8. Векторные структуры данных………………………………………………………………………………………. 282
13.9. Дерево B+………………………………………………………………………………………………………………………… 283
13.10. Комментарии…………………………………………………………………………………………………………………. 291
13.11. Советы по дополнительной подготовке……………………………………………………………………… 291
13.12. Список рекомендуемой литературы…………………………………………………………………………… 292
- Строковые алгоритмы…………………………………………………………………….. 293
14.1. Введение………………………………………………………………………………………………………………………….. 293
14.2. Поиск по одному шаблону…………………………………………………………………………………………….. 293
14.3. Поиск по нескольким шаблонам……………………………………………………………………………………. 296
14.4. Регулярные выражения…………………………………………………………………………………………………… 297
14.5. Расширенные шаблоны………………………………………………………………………………………………….. 299
14.6. Алгоритмы поиска расстояния между строками…………………………………………………………. 301
14.7. Обратный индекс…………………………………………………………………………………………………………….. 305
14.8. Суффиксный индекс………………………………………………………………………………………………………… 306
14.9. Синтаксическое дерево………………………………………………………………………………………………….. 310
14.10. Введение в краткие структуры данных………………………………………………………………………. 310
14.11. Примечания по реализации…………………………………………………………………………………………. 314
14.12. Комментарии…………………………………………………………………………………………………………………. 315
14.13. Советы по дополнительной подготовке……………………………………………………………………… 315
14.14. Список рекомендуемой литературы…………………………………………………………………………… 316
- Сжатие……………………………………………………………………………………………. 317
15.1. Введение………………………………………………………………………………………………………………………….. 317
15.2. Основные ограничения…………………………………………………………………………………………………… 317
15.3. Энтропия………………………………………………………………………………………………………………………….. 317
15.4. Битовый поток…………………………………………………………………………………………………………………. 318
15.5. Коды…………………………………………………………………………………………………………………………………. 320
15.6. Статические коды…………………………………………………………………………………………………………… 320
15.7. Коды Хаффмана……………………………………………………………………………………………………………… 324
15.8. Сжатие словаря………………………………………………………………………………………………………………. 328
15.9. Кодирование серий байтов……………………………………………………………………………………………. 331
15.10. Перемещение на передний план………………………………………………………………………………….. 332
15.11. Преобразование Берроуза — Уилера…………………………………………………………………………. 333
15.12. Примечания по реализации…………………………………………………………………………………………. 336
15.13. Комментарии…………………………………………………………………………………………………………………. 336
15.14. Советы по дополнительной подготовке……………………………………………………………………… 337
15.15. Список рекомендуемой литературы…………………………………………………………………………… 337
- Комбинаторная оптимизация………………………………………………………….. 338
16.1. Введение………………………………………………………………………………………………………………………….. 338
16.2. Теория сложности…………………………………………………………………………………………………………… 338
16.3. Типичные сложные задачи…………………………………………………………………………………………….. 340
16.4. Алгоритмы приближения……………………………………………………………………………………………….. 344
16.5. Эвристика жадного построения…………………………………………………………………………………….. 345
16.6. Ветвление и границы………………………………………………………………………………………………………. 346
16.7. Поиск крачайшего пути в пространстве с нижними границами…………………………………. 352
16.8. Локальный поиск…………………………………………………………………………………………………………….. 360
16.9. Применение локального поиска к некоторым задачам……………………………………………….. 366
16.10. Алгоритм имитации отжига…………………………………………………………………………………………. 370
16.11. Повторный локальный поиск………………………………………………………………………………………. 375
16.12. Генетические алгоритмы……………………………………………………………………………………………… 377
16.13. Анализ производительности………………………………………………………………………………………… 383
16.14. Подготовка данных для конкретной задачи………………………………………………………………. 384
16.15. Многоцелевая оптимизация…………………………………………………………………………………………. 384
16.16. Обработка ограничений………………………………………………………………………………………………. 385
16.17. Стохастические задачи………………………………………………………………………………………………… 390
16.18. Общие рекомендации……………………………………………………………………………………………………. 390
16.19. Примечания по реализации…………………………………………………………………………………………. 391
16.20. Комментарии…………………………………………………………………………………………………………………. 391
16.21. Советы по дополнительной подготовке……………………………………………………………………… 394
16.22. Список рекомендуемой литературы…………………………………………………………………………… 395
- Большие числа………………………………………………………………………………… 397
17.1. Введение………………………………………………………………………………………………………………………….. 397
17.2. Представление………………………………………………………………………………………………………………… 397
17.3. Сложение и вычитание…………………………………………………………………………………………………… 399
17.4. Операции сдвига……………………………………………………………………………………………………………… 400
17.5. Умножение………………………………………………………………………………………………………………………. 401
17.6. Деление……………………………………………………………………………………………………………………………. 402
17.7. Преобразование в десятичное число…………………………………………………………………………….. 404
17.8. Возведение в степень………………………………………………………………………………………………………. 404
17.9. Вычисление логарифма………………………………………………………………………………………………….. 405
17.10. Целочисленный квадратный корень…………………………………………………………………………… 405
17.11. Наибольший общий делитель……………………………………………………………………………………… 406
17.12. Модульная инверсия…………………………………………………………………………………………………….. 406
17.13. Проверка числа на простоту……………………………………………………………………………………….. 407
17.14. Рациональные числа…………………………………………………………………………………………………….. 408
17.15. Примечания по реализации…………………………………………………………………………………………. 410
17.16. Комментарии…………………………………………………………………………………………………………………. 410
17.17. Советы по дополнительной подготовке……………………………………………………………………… 411
17.18. Список рекомендуемой литературы…………………………………………………………………………… 411
- Вычислительная геометрия…………………………………………………………….. 412
18.1. Введение………………………………………………………………………………………………………………………….. 412
18.2. Расстояния……………………………………………………………………………………………………………………….. 412
18.3. VP-дерево…………………………………………………………………………………………………………………………. 413
18.4. k-d-дерево………………………………………………………………………………………………………………………… 417
18.5. Решение задач при большом числе измерений…………………………………………………………….. 422
18.6. Структуры данных для геометрических объектов………………………………………………………. 423
18.7. Точки………………………………………………………………………………………………………………………………… 423
18.8. Геометрические примитивы…………………………………………………………………………………………… 424
18.9. Выпуклая оболочка………………………………………………………………………………………………………… 425
18.10. Развертка плоскости…………………………………………………………………………………………………….. 426
18.11. Комментарии…………………………………………………………………………………………………………………. 427
18.12. Советы по дополнительной подготовке……………………………………………………………………… 428
18.13. Список рекомендуемой литературы…………………………………………………………………………… 428
- Обнаружение и исправление ошибок……………………………………………… 429
19.1. Введение………………………………………………………………………………………………………………………….. 429
19.2. Бинарные полиномы………………………………………………………………………………………………………. 429
19.3. Многочлены над конечными полями……………………………………………………………………………. 429
19.4. Обнаружение ошибок…………………………………………………………………………………………………….. 430
19.5. Каналы и коды………………………………………………………………………………………………………………… 432
19.6. Вычисление конечного поля………………………………………………………………………………………….. 434
19.7. Полиномы над элементами поля Галуа……………………………………………………………………….. 435
19.8. Коды Рида — Соломона………………………………………………………………………………………………… 438
19.9. Границы кодов минимального расстояния с фиксированным алфавитом………………… 442
19.10. Булевы матрицы……………………………………………………………………………………………………………. 443
19.11. Коды проверки на четность с низкой плотностью…………………………………………………….. 444
19.12. Примечания по реализации…………………………………………………………………………………………. 449
19.13. Комментарии…………………………………………………………………………………………………………………. 450
19.14. Советы по дополнительной подготовке……………………………………………………………………… 451
19.15. Список рекомендуемой литературы…………………………………………………………………………… 451
- Криптография…………………………………………………………………………………. 452
20.1. Введение………………………………………………………………………………………………………………………….. 452
20.2. Шифрование файлов………………………………………………………………………………………………………. 452
20.3. Длина ключа……………………………………………………………………………………………………………………. 454
20.4. Хранилище ключей…………………………………………………………………………………………………………. 455
20.5. Криптографическое хеширование………………………………………………………………………………… 456
20.6. Обмен ключами……………………………………………………………………………………………………………….. 456
20.7. Другие протоколы…………………………………………………………………………………………………………… 456
20.8. Примечания по реализации……………………………………………………………………………………………. 457
20.9. Комментарии…………………………………………………………………………………………………………………… 457
20.10. Совет по дополнительной подготовке………………………………………………………………………… 458
20.11. Список рекомендуемой литературы…………………………………………………………………………… 458
- Вычислительная статистика…………………………………………………………… 459
21.1. Введение………………………………………………………………………………………………………………………….. 459
21.2. Оценки……………………………………………………………………………………………………………………………… 459
21.3. Оценщики…………………………………………………………………………………………………………………………. 462
21.4. Поиск наиболее эффективных оценщиков……………………………………………………………………. 469
21.5. Некоторые особенности асимптотики………………………………………………………………………….. 473
21.6. Оценка нормальной CDF………………………………………………………………………………………………… 473
21.7. Оценка CDF T-распределения……………………………………………………………………………………….. 474
21.8. Подробнее о доверительных интервалах…………………………………………………………………….. 475
21.9. Границы среднего значения в конечной выборке………………………………………………………… 479
21.10. Доверительные интервалы для общих метрик местоположения……………………………… 481
21.11. Выпадающие значения и надежные выводы……………………………………………………………… 484
21.12. Функции оценок…………………………………………………………………………………………………………….. 486
21.13. Измерение времени выполнения алгоритма……………………………………………………………….. 487
21.14. Корреляционный анализ……………………………………………………………………………………………… 488
21.15. Начальная загрузка……………………………………………………………………………………………………… 490
21.16. Когда использовать начальную загрузку?…………………………………………………………………. 504
21.17. Проверка гипотез………………………………………………………………………………………………………….. 505
21.18. Сравнение тестов………………………………………………………………………………………………………….. 507
21.19. Эффективное использование тестов……………………………………………………………………………. 509
21.20. Валидация исследований…………………………………………………………………………………………….. 514
21.21. Сравнение совпадающих пар……………………………………………………………………………………… 515
21.22. Множественные сравнения………………………………………………………………………………………….. 517
21.23. Сравнение совпадающих кортежей……………………………………………………………………………. 519
21.24. Сравнение независимых выборок……………………………………………………………………………….. 520
21.25. Перестановочные тесты……………………………………………………………………………………………….. 522
21.26. Сравнение нескольких альтернатив в нескольких предметных областях………………. 526
21.27. Работа с данными расчета…………………………………………………………………………………………… 529
21.28. Тестирование различий в распределении………………………………………………………………….. 531
21.29. Сравнение данных с распределением………………………………………………………………………… 532
21.30. Сравнение распределений двух выборок…………………………………………………………………… 534
21.31. Анализ чувствительности…………………………………………………………………………………………….. 535
21.32. Последовательность Соболя……………………………………………………………………………………….. 537
21.33. Планирование экспериментов: основные идеи………………………………………………………….. 541
21.34. Марковская цепь Монте-Карло…………………………………………………………………………………… 544
21.35. Байесовские методы……………………………………………………………………………………………………… 547
21.36. Поиск лучшей альтернативы с помощью моделирования………………………………………… 549
21.37. Расчет размера выборки………………………………………………………………………………………………. 552
21.38. Анализ временных рядов……………………………………………………………………………………………… 553
21.39. Использование статистики на практике……………………………………………………………………… 565
21.40. Анализ решений……………………………………………………………………………………………………………. 567
21.41. Примечания по реализации…………………………………………………………………………………………. 569
21.42. Комментарии…………………………………………………………………………………………………………………. 570
21.43. Советы по дополнительной подготовке……………………………………………………………………… 576
21.44. Список рекомендуемой литературы…………………………………………………………………………… 578
- Численные алгоритмы: введение и матричная алгебра…………………… 582
22.1. Введение………………………………………………………………………………………………………………………….. 582
22.2. Арифметика с плавающей точкой…………………………………………………………………………………. 583
22.3. Ошибки при использовании арифметики с плавающей точкой………………………………….. 584
22.4. Ошибка приближения…………………………………………………………………………………………………….. 588
22.5. Показатели устойчивости и состояния…………………………………………………………………………. 589
22.6. Ошибка оптимизации……………………………………………………………………………………………………… 591
22.7. Другие общие темы…………………………………………………………………………………………………………. 593
22.8. Разработка надежного численного программного обеспечения……………………………….. 595
22.9. Матричная алгебра………………………………………………………………………………………………………… 599
22.10. Матричные нормы………………………………………………………………………………………………………… 602
22.11. LUP-разложение……………………………………………………………………………………………………………. 603
22.12. Разложение Холецкого…………………………………………………………………………………………………. 608
22.13. Ленточные матрицы……………………………………………………………………………………………………… 609
22.14. Решение тридиагональных матричных уравнений…………………………………………………… 611
22.15. Ортогональные преобразования…………………………………………………………………………………. 611
22.16. QR-разложение……………………………………………………………………………………………………………… 613
22.17. Собственные значения и собственные векторы симметричной матрицы……………….. 615
22.18. Разложение по сингулярным значениям (SVD)………………………………………………………….. 618
22.19. Собственные значения и собственные векторы асимметричной матрицы……………… 622
22.20. Разреженные матрицы………………………………………………………………………………………………….. 627
22.21. Итерационные методы для разреженных матриц……………………………………………………… 633
22.22. Итерационные методы для собственных значений…………………………………………………… 634
22.23. Введение в интервальную арифметику………………………………………………………………………. 636
22.24. Примечания по реализации…………………………………………………………………………………………. 639
22.25. Комментарии…………………………………………………………………………………………………………………. 639
22.26. Советы по дополнительной подготовке……………………………………………………………………… 642
22.27. Список рекомендуемой литературы…………………………………………………………………………… 642
- Численные алгоритмы: работа с функциями………………………………….. 645
23.1. Введение………………………………………………………………………………………………………………………….. 645
23.2. Быстрое преобразование Фурье……………………………………………………………………………………. 645
23.3. Интерполяция: общие идеи……………………………………………………………………………………………. 649
23.4. Полиномиальная интерполяция из существующих данных……………………………………….. 652
23.5. Полиномы Чебышева……………………………………………………………………………………………………… 655
23.6. Кусочная интерполяция…………………………………………………………………………………………………. 662
23.7. Сплайны — для работы с существующими данными…………………………………………………. 668
23.8. Сравнение методов интерполяции………………………………………………………………………………… 672
23.9. Интегрирование………………………………………………………………………………………………………………. 674
23.10. Многомерное интегрирование…………………………………………………………………………………….. 681
23.11. Оценка функции…………………………………………………………………………………………………………….. 685
23.12. Оценка производных…………………………………………………………………………………………………….. 685
23.13. Решение нелинейных уравнений и систем………………………………………………………………….. 691
23.14. Поиск всех корней в одномерном случае……………………………………………………………………. 707
23.15. Обыкновенные дифференциальные уравнения………………………………………………………….. 708
23.16. Решение жестких ОДУ………………………………………………………………………………………………….. 713
23.17. Краевые задачи для ОДУ…………………………………………………………………………………………….. 717
23.18. Уравнения с частными производными: некоторые размышления…………………………… 719
23.19. Некоторые выводы……………………………………………………………………………………………………….. 720
23.20. Примечания по реализации…………………………………………………………………………………………. 721
23.21. Комментарии…………………………………………………………………………………………………………………. 721
23.22. Советы по дополнительной подготовке……………………………………………………………………… 727
23.23. Список рекомендуемой литературы…………………………………………………………………………… 728
- Численная оптимизация…………………………………………………………………. 731
24.1. Введение………………………………………………………………………………………………………………………….. 731
24.2. Некоторые общие идеи…………………………………………………………………………………………………… 731
24.3. Минимизация унимодальной функции с одной переменной………………………………………. 732
24.4. Минимизация многомерных функций: введение и координатный спуск…………………… 735
24.5. Линейный поиск………………………………………………………………………………………………………………. 738
24.6. Алгоритмы линейного поиска……………………………………………………………………………………….. 742
24.7. Методы, не требующие вычисления производных……………………………………………………… 748
24.8. Негладкая минимизация…………………………………………………………………………………………………. 753
24.9. Глобальная минимизация………………………………………………………………………………………………. 756
24.10. Оптимизация в дискретном множестве……………………………………………………………………….. 770
24.11. Стохастическая оптимизация……………………………………………………………………………………… 772
24.12. Алгоритмы стохастической аппроксимации……………………………………………………………… 773
24.13. Линейное программирование………………………………………………………………………………………. 776
24.14. Некоторые соображения о нелинейном программировании……………………………………. 779
24.15. Примечания по реализации…………………………………………………………………………………………. 780
24.16. Комментарии…………………………………………………………………………………………………………………. 781
24.17. Советы по дополнительной подготовке……………………………………………………………………… 786
24.18. Список рекомендуемой литературы…………………………………………………………………………… 787
- Введение в машинное обучение………………………………………………………. 790
25.1. Введение………………………………………………………………………………………………………………………….. 790
25.2. Что такое машинное обучение?…………………………………………………………………………………….. 790
25.3. Математическое обучение…………………………………………………………………………………………….. 791
25.4. Прогнозирование и структурный вывод……………………………………………………………………….. 796
25.5. Оценка риска предиктора………………………………………………………………………………………………. 796
25.6. Источники риска……………………………………………………………………………………………………………… 799
25.7. Контроль сложности………………………………………………………………………………………………………. 800
25.8. Ошибка аппроксимации…………………………………………………………………………………………………. 802
25.9. Устойчивость…………………………………………………………………………………………………………………… 805
25.10. Оценка риска стратегии обучения………………………………………………………………………………. 806
25.11. Принятие решений и выбор модели…………………………………………………………………………….. 810
25.12. Общие стратегии выбора модели………………………………………………………………………………… 812
25.13. Смещение, дисперсия и бэггинг…………………………………………………………………………………… 813
25.14. Паттерны проектирования…………………………………………………………………………………………… 816
25.15. Подготовка данных………………………………………………………………………………………………………. 817
25.16. Масштабирование………………………………………………………………………………………………………… 819
25.17. Обработка пропущенных значений……………………………………………………………………………. 821
25.18. Выбор признаков………………………………………………………………………………………………………….. 821
25.19. Ядра……………………………………………………………………………………………………………………………….. 827
25.20. Обучение в реальном времени…………………………………………………………………………………….. 829
25.21. Работа с невекторными данными………………………………………………………………………………… 830
25.22. Масштабное обучение…………………………………………………………………………………………………. 830
25.23. Выводы………………………………………………………………………………………………………………………….. 832
25.24. Примечания по реализации…………………………………………………………………………………………. 833
25.25. Комментарии…………………………………………………………………………………………………………………. 833
25.26. Советы по дополнительной подготовке……………………………………………………………………… 839
25.27. Список рекомендуемой литературы…………………………………………………………………………… 840
- Машинное обучение: классификация…………………………………………….. 842
26.1. Введение………………………………………………………………………………………………………………………….. 842
26.2. Стратификация по метке класса……………………………………………………………………………………. 842
26.3. Оценка риска…………………………………………………………………………………………………………………… 844
26.4. Сведение мультикласса к двум классам……………………………………………………………………….. 848
26.5. Контроль сложности………………………………………………………………………………………………………. 851
26.6. Наивный классификатор Байеса…………………………………………………………………………………… 853
26.7. Ближайший сосед……………………………………………………………………………………………………………. 856
26.8. Дерево решений………………………………………………………………………………………………………………. 859
26.9. Механизм опорных векторов…………………………………………………………………………………………. 866
26.10. Линейный SVM……………………………………………………………………………………………………………… 868
26.11. Ядро SVM………………………………………………………………………………………………………………………. 873
26.12. Мультиклассовый нелинейный SVM………………………………………………………………………….. 878
26.13. Нейронная сеть……………………………………………………………………………………………………………… 880
26.14. Ансамбли рандомизации……………………………………………………………………………………………… 889
26.15. Обучение в реальном времени…………………………………………………………………………………….. 891
26.16. Бустинг…………………………………………………………………………………………………………………………… 894
26.17. Масштабное обучение…………………………………………………………………………………………………. 898
26.18. Экономичное обучение………………………………………………………………………………………………… 898
26.19. Несбалансированное обучение…………………………………………………………………………………… 903
26.20. Выбор признаков………………………………………………………………………………………………………….. 906
26.21. Сравнение классификаторов……………………………………………………………………………………….. 906
26.22. Примечания по реализации…………………………………………………………………………………………. 909
26.23. Комментарии…………………………………………………………………………………………………………………. 910
26.24. Советы по дополнительной подготовке……………………………………………………………………… 919
26.25. Список рекомендуемой литературы…………………………………………………………………………… 919
- Машинное обучение: регрессия………………………………………………………. 922
27.1. Введение………………………………………………………………………………………………………………………….. 922
27.2. Оценка риска…………………………………………………………………………………………………………………… 922
27.3. Управление сложностью………………………………………………………………………………………………… 924
27.4. Линейная регрессия………………………………………………………………………………………………………… 925
27.5. Регрессия лассо……………………………………………………………………………………………………………….. 926
27.6. Регрессия ближайших соседей………………………………………………………………………………………. 930
27.7. Дерево регрессии…………………………………………………………………………………………………………….. 931
27.8. Регрессия случайного леса…………………………………………………………………………………………….. 934
27.9. Нейронная сеть……………………………………………………………………………………………………………….. 935
27.10. Выбор признаков………………………………………………………………………………………………………….. 936
27.11. Сравнение производительности………………………………………………………………………………….. 936
27.12. Примечания по реализации…………………………………………………………………………………………. 937
27.13. Комментарии…………………………………………………………………………………………………………………. 938
27.14. Советы по дополнительной подготовке……………………………………………………………………… 941
27.15. Список рекомендуемой литературы…………………………………………………………………………… 942
- Машинное обучение: кластеризация………………………………………………. 943
28.1. Введение………………………………………………………………………………………………………………………….. 943
28.2. Постановка………………………………………………………………………………………………………………………. 943
28.3. Внешняя оценка………………………………………………………………………………………………………………. 945
28.4. Внутренняя оценка и выбор количества кластеров…………………………………………………….. 948
28.5. Расчет устойчивости………………………………………………………………………………………………………. 951
28.6. Кластеризация в евклидовом пространстве…………………………………………………………………. 953
28.7. Кластеризация в метрическом пространстве……………………………………………………………….. 957
28.8. Спектральная кластеризация………………………………………………………………………………………… 960
28.9. Эксперименты…………………………………………………………………………………………………………………. 964
28.10. Примечания по реализации…………………………………………………………………………………………. 964
28.11. Комментарии…………………………………………………………………………………………………………………. 965
28.12. Советы по дополнительной подготовке……………………………………………………………………… 969
28.13. Список рекомендуемой литературы…………………………………………………………………………… 969
- Машинное обучение: прочие задачи……………………………………………….. 971
29.1. Введение………………………………………………………………………………………………………………………….. 971
29.2. Обучение с подкреплением……………………………………………………………………………………………. 971
29.3. Функция, присваивающая значения……………………………………………………………………………… 972
29.4. Поиск часто встречающихся комбинаций предметов…………………………………………………. 974
29.5. Полуконтролируемое обучение…………………………………………………………………………………….. 975
29.6. Оценка плотности…………………………………………………………………………………………………………… 976
29.7. Обнаружение выпадающих значений…………………………………………………………………………… 976
29.8. Примечания по реализации……………………………………………………………………………………………. 977
29.9. Комментарии…………………………………………………………………………………………………………………… 977
29.10. Список рекомендуемой литературы…………………………………………………………………………… 978
- Отстойник: не слишком полезные алгоритмы и структуры данных.. 979
30.1. Введение………………………………………………………………………………………………………………………….. 979
30.2. Сортировка связанного списка……………………………………………………………………………………… 979
30.3. Частичная сортировка……………………………………………………………………………………………………. 981
30.4. Сжатое префиксное дерево……………………………………………………………………………………………. 981
30.5. Хеширование кукушкой…………………………………………………………………………………………………. 987
30.6. Немного приоритетных очередей…………………………………………………………………………………. 990
30.7. Младший общий предок (LCA) и запрос с минимальным диапазоном (RQM)…………. 996
30.8. Знаковый ранговый критерий Уилкоксона для двух выборок……………………………………. 997
30.9. Критерий Фридмана для согласованных выборок……………………………………………………… 998
30.10. MADS-подобный алгоритм оптимизации…………………………………………………………………… 999
30.11. Алгоритм классификации бустинга SAMME…………………………………………………………… 1000
30.12. Бустинг в задаче регрессии……………………………………………………………………………………….. 1001
30.13. Вероятностная кластеризация…………………………………………………………………………………… 1003
30.14. Иерархическая кластеризация………………………………………………………………………………….. 1007
30.15. Кластеризация на основе плотности………………………………………………………………………… 1010
30.16. Не представленные реализации………………………………………………………………………………… 1012
30.17. Советы по дополнительной подготовке……………………………………………………………………. 1013
30.18. Список рекомендуемой литературы…………………………………………………………………………. 1014
- Приложение: примечания о языке С++…………………………………………. 1015
31.1. Введение………………………………………………………………………………………………………………………… 1015
31.2. Путеводитель по литературе, посвященной C++……………………………………………………….. 1015
31.3. Советы по дополнительной подготовке……………………………………………………………………… 1015
31.4. Список рекомендуемой литературы…………………………………………………………………………… 1016
Предметный указатель……………………………………………………………………….. 1017
-
Реализация полезных алгоритмов на C++
2250 ₽
1755 ₽
