Библиотека программиста - Springer William / Спрингер Вильям - A Programmer's Guide to Computer Science / Гид по Computer Science, расширенное издание [2021, PDF/EPUB, RUS]

Введение ...............................................................................11
Зачем нужна эта книга .......................................................11
Чего вы не найдете в издании ............................................12
Дополнительные ресурсы ...................................................13
Что дальше ........................................................................14
От издательства .................................................................14
Часть I. Основы Computer Science
Глава 1. Асимптотическое время выполнения ...................... 16
1.1. Что такое алгоритм ....................................................16
1.2. Почему скорость имеет значение ...............................18
1.3. Когда секунды (не) считаются ....................................19
1.4. Как мы описываем скорость .......................................22
1.5. Скорость типичных алгоритмов ..................................23
1.6. Всегда ли полиномиальное время лучше? ..................27
1.7. Время выполнения алгоритма ....................................29
1.8. Насколько сложна задача? .........................................33
Глава 2. Структуры данных .................................................. 34
2.1. Организация данных ..................................................34
2.2. Массивы, очереди и другие способы построиться .......35
2.3. Связные списки ..........................................................37
2.4. Стеки и кучи ..............................................................39
2.5. Хеш-таблицы ..............................................................43
2.6. Множества и частично упорядоченные множества .....47
2.7. Специализированные структуры данных ....................50
Глава 3. Классы задач .......................................................... 51
Часть II. Графы и графовые алгоритмы
Глава 4. Введение в теорию графов ..................................... 60
4.1. Семь кенигсбергских мостов .......................................60
4.2. Мотивация .................................................................62
4.3. Терминология ............................................................64
4.4. Представление графов ...............................................67
4.5. Направленные и ненаправленные графы ...................71
4.6. Циклические и ациклические графы ..........................72
4.7. Раскраска графа .........................................................75
4.8. Взвешенные и невзвешенные графы ..........................79
Глава 5. Структуры данных на основе графов ...................... 80
5.1. Двоичные деревья поиска ..........................................80
5.2. Сбалансированные деревья двоичного поиска ...........84
5.3. Кучи ...........................................................................85
Глава 6. Хорошо известные графовые алгоритмы ................. 96
6.1. Введение ....................................................................96
6.2. Поиск в ширину..........................................................97
6.3. Применение поиска в ширину ..................................100
6.4. Поиск в глубину .......................................................101
6.5. Кратчайшие пути .....................................................104
Глава 7. Основные классы графов ...................................... 109
7.1. Запрещенные подграфы ...........................................109
7.2. Планарные графы ....................................................110
7.3. Совершенные графы ................................................113
7.4. Двудольные графы ...................................................115
7.5. Интервальные графы ...............................................116
7.6. Графы дуг окружности .............................................117
Часть III. Неграфовые алгоритмы
Глава 8. Алгоритмы сортировки ......................................... 120
8.1. Малые и большие алгоритмы сортировки .................121
8.2. Сортировки для малых наборов данных ...................123
8.3. Сортировка больших наборов данных ......................126
8.4. Сортировки без сравнения .......................................130
Часть IV. Методы решения задач
Глава 9. А если в лоб? ........................................................ 136
Глава 10. Динамическое программирование ...................... 139
10.1. Задача недостающих полей ....................................139
10.2. Работа с перекрывающимися подзадачами .............141
10.3. Динамическое программирование
и кратчайшие пути .................................................143
10.4. Примеры практического применения ......................145
Глава 11. Жадные алгоритмы ............................................. 148
Часть V. Теория сложности вычислений
Глава 12. Что такое теория сложности ............................... 152
Глава 13. Языки и конечные автоматы ............................... 155
13.1. Формальные языки ................................................155
13.2. Регулярные языки ..................................................156
13.3. Контекстно свободные языки .................................166
13.4. Контекстно зависимые языки .................................173
13.5. Рекурсивные и рекурсивно перечислимые языки ...174
Глава 14. Машины Тьюринга .............................................. 175
14.1. Чисто теоретический компьютер ............................175
14.2. Построение машины Тьюринга ...............................176
14.3. Полнота по Тьюрингу .............................................177
14.4. Проблема остановки ..............................................178
Часть VI. Доказательства
Глава 15. Приемлемые доказательства .............................. 180
15.1. Введение в доказательства ....................................180
15.2. Терминология .......................................................181
Глава 16. Методы доказательства ..................................... 184
16.1. Конструктивное доказательство, доказательство
методом исчерпывания вариантов .........................184
16.2. Доказательство от противного ..............................185
16.3. Доказательство методом индукции ........................187
16.4. Доказательство на основе закона контрапозиции ..191
Глава 17. Сертификаты ...................................................... 192
Часть VII. Безопасность и конфиденциальность
Глава 18. Введение в безопасность .................................... 196
18.1. Конфиденциальность ............................................196
18.2. Целостность ...........................................................198
18.3. Доступность ..........................................................198
18.4. Цели ......................................................................199
Глава 19. Введение в криптографию ................................. 200
19.1. Современная криптография ...................................201
19.2. Терминология .......................................................202
19.3. Абсолютно безопасный обмен данными .................203
19.4. Квантовое распределение ключей .........................205
Глава 20. Криптографическая система с открытым ключом 207
20.1. Использование открытого и закрытого ключей ......207
20.2. Алгоритм RSA .........................................................209
20.3. Соображения производительности ........................211
Глава 21. Аутентификация пользователя ........................... 213
Часть VIII. Аппаратное и программное
обеспечение
Глава 22. Аппаратные абстракции ..................................... 218
22.1. Физическое хранилище ..........................................218
22.2. Данные и методы ввода/вывода .............................221
22.3. Память ...................................................................223
22.4. Кэш ........................................................................225
22.5. Регистры ................................................................226
Глава 23. Программные абстракции ................................... 228
23.1. Машинный код и язык ассемблера ........................228
23.2. Низкоуровневые языки программирования ............229
23.3. Высокоуровневые языки программирования .........229
Глава 24. Компьютерная арифметика ................................. 231
24.1. Битовый сдвиг .......................................................232
24.2. Битовые И и ИЛИ ..................................................233
24.3. Битовое НЕ ............................................................235
24.4. Битовое исключающее ИЛИ ...................................235
Глава 25. Операционные системы ..................................... 237
25.1. Управление процессами ........................................237
25.2. Управление хранилищем .......................................241
25.3. Ввод/вывод ............................................................246
25.4. Безопасность .........................................................247
Глава 26. Распределенные системы .................................. 250
26.1. Ложные допущения относительно
распределенных вычислений ................................251
26.2. Коммуникация ........................................................254
26.3. Синхронизация и согласованность .........................255
Глава 27. Встроенные системы .......................................... 257
Глава 28. Сети и Интернет ................................................. 260
28.1. Уровни протоколов ................................................261
28.2. Протоколы TCP/IP и UDP .......................................264
28.3. Доставка сообщения .............................................265
28.4. Алгоритмы маршрутизации ...................................267
Глава 29. Базы данных ....................................................... 269
29.1. Реляционные базы данных (РБД) ...........................269
29.2. Иерархические базы данных (ИБД) ........................272
Часть IX. Углубленные темы
Глава 30. Основная теорема о рекуррентных соотношениях ..................................................... 274
Глава 31. Амортизированное время выполнения ................ 278
Глава 32. Расширяющееся дерево ...................................... 280
34.1. Концепции .............................................................280
32.2. Zig ........................................................................282
32.3. Zig-zig ....................................................................282
32.4. Zig-zag ...................................................................282
Глава 33. Декартово дерево .............................................. 284
Глава 34. Искусственный интеллект .................................. 287
34.1. Типы искусственного интеллекта ..........................287
34.2. Подобласти ИИ ......................................................291
34.3. Примеры ...............................................................293
Глава 35. Квантовые вычисления ....................................... 294
35.1. Физика ..................................................................295
35.2. Теоретические соображения ..................................295
35.3. Практические соображения ...................................296
Послесловие ..........................................................................297
Приложения
Приложение A. Необходимая математика ......................... 300
Приложение Б. Классические NP-полные задачи .............. 302
Б.1. SAT и 3-SAT ..............................................................302
Б.2. Клика .......................................................................303
Б.3. Кликовое покрытие ..................................................303
Б.4. Раскраска графа .......................................................303
Б.5. Гамильтонов путь .....................................................304
Б.6. Укладка рюкзака ......................................................304
Б.7. Наибольшее независимое множество .......................304
Б.8. Сумма подмножества ...............................................304