Теоретический минимум по Computer Science. Все что нужно программисту и разработчику

Предисловие.............................................................................................. 11

Эта книга для меня?...........................................................................12
Но разве computer science не только для ученых?..............................13
Глава 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