Содержание.
Глава 1. Основы 14
1.1. Идеи 15
Блок-схемы 15
Псевдокод 17
Математические модели 18
1.2. Логика 20
Операторы 21
Булева алгебра 23
Таблицы истинности 25
Логика в вычислениях 29
1.3. Комбинаторика 31
Правило умножения 31
Перестановки 32
Перестановки без повторений 34
Комбинации 35
Правило суммирования 36
1.4. Вероятность 38
Подсчет количества возможных вариантов 38
Независимые (совместные) события 39
Несовместные события 40
Взаимодополняющие события 40
«Заблуждение игрока» 41
Более сложные вероятности 42
Подведем итоги 42
Полезные материалы 43
Глава 2. Вычислительная сложность 44
Надейтесь на лучшее, но готовьтесь к худшему 45
2.1. Оценка затрат времени 47
Понимание роста затрат 48
2.2. Нотация «О большое» 50
2.3. Экспоненциальное время 52
2.4. Оценка затрат памяти 54
Подведем итоги 55
Полезные материалы 56
Глава 3. Стратегия 57
3.1. Итерация 58
Вложенные циклы и степенные множества 59
3.2. Рекурсия 62
Рекурсия против итераций 63
3.3. Полный перебор 64
3.4. Поиск (перебор) с возвратом 67
3.5. Эвристические алгоритмы 71
«Жадные» алгоритмы 71
Когда жадность побеждает силу 73
3.6. Разделяй и властвуй 75
Разделить и отсортировать 75
Разделить и заключить сделку 80
Разделить и упаковать 82
3.7. Динамическое программирование 84
Мемоизация Фибоначчи 84
Мемоизация предметов в рюкзаке 85
Лучшая сделка снизу вверх 86
3.8. Ветви и границы 88
Верхние и нижние границы 88
Ветви и границы в задаче о рюкзаке 89
Подведем итоги 92
Полезные материалы 93
Глава 4. Данные 94
Абстракции 95
Тип данных 96
4.1. Абстрактные типы данных 96
Преимущества использования АТД 97
4.2. Общие абстракции 98
Примитивные типы данных 98
Стек 99
Очередь 100
Очередь с приоритетом 100
Список 101
Сортированный список 102
Множество 103
4.3. Структуры 104
Массив 104
Связный список 105
Двусвязный список 107
Массивы против связных списков 108
Дерево 109
Двоичное дерево поиска 112
Двоичная куча 115
Граф 117
Хеш-таблица 117
Подведем итоги 118
Полезные материалы 119
Глава 5. Алгоритмы 120
5.1. Сортировка 121
5.2. Поиск 124
5.3. Графы 125
Поиск в графах126
Раскраска графов 129
Поиск путей в графе 130
PageRank 133
5.4. Исследование операций 133
Задачи линейной оптимизации 134
Задачи о максимальном потоке в Сети 137
Подведем итоги 138
Полезные материалы 139
Глава 6. Базы данных 140
6.1. Реляционная модель 142
Отношения 142
Миграция схемы 145
SQL 146
Индексация 148
Транзакции 151
6.2. Нереляционная модель 152
Документные хранилища 152
Хранилища «ключ — значение» 154
Графовые базы данных 155
Большие данные 156
SQL против NoSQL 157
6.3. Распределенная модель 158
Репликация с одним ведущим 159
Репликация с многочисленными ведущими 159
Фрагментирование 160
Непротиворечивость данных 162
6.4. Географическая модель 163
6.5. Форматы сериализации 165
Подведем итоги 166
Полезные материалы 166
Глава 7. Компьютеры 167
7.1. Архитектура 168
Память 168
Процессор 171
7.2. Компиляторы 177
Операционные системы 181
Оптимизация при компиляции 182
Языки сценариев 183
Дизассемблирование и обратный инженерный анализ 184
Программное обеспечение с открытым исходным кодом 185
7.3. Иерархия памяти 186
Разрыв между памятью и процессором 187
Временная и пространственная локальность 188
Кэш L1 189
Кэш L2 189
Первичная память против вторичной 191
Внешняя и третичная память 193
Тенденции в технологии памяти 194
Подведем итоги 195
Полезные материалы 196
Глава 8. Программирование 197
8.1. Лингвистика 198
Значения 198
Выражения 198
Инструкции 200
8.2. Переменные 201
Типизация переменных 202
Область видимости переменных 202
8.3. Парадигмы 204
Императивное программирование 204
Декларативное программирование 207
Логическое программирование 213
Подведем итоги 214
Полезные материалы 214
Заключение 215
Приложения 217
I. Системы счисления 217
II. Метод Гаусса 219
III. Множества 220
IV. Алгоритм Кэдейна 222
