Колосс на глиняных ногах — так можно назвать программиста без подготовки в области Computer Science. Уверенное владение основами позволяет «не изобретать велосипеды» и закладывать в архитектуру программ эффективные решения. Всё это избавляет от ошибок и чрезмерных затрат на тестирование и рефакторинг. Не беда, если вы чувствуете себя не у дел, когда другие программисты обсуждают аппроксимативный предел. Даже специалисты с опытом допускают ошибки из-за того, что подзабыли Computer Science.
Author(s): Вильям Спрингер
Series: Библиотека программиста
Edition: 1
Publisher: Питер
Year: 2021
Language: Russian
Commentary: Vector PDF
Pages: 304
City: СПб.
Tags: Data Structures; Problem Solving; Graph Theory; Dynamic Programming; Graph Algorithms; Hash Functions; Discrete Mathematics; Turing Machine; Greedy Algorithms; Algorithm Analysis; Regular Languages; Brute Force; State Machines; Computer Science; Algorithm Complexity; Sorting Algorithms; Formal Languages; Context-free Languages; Context-sensitive Languages
Зачем нужна эта книга
Чего вы не найдете в издании
Дополнительные ресурсы
Что дальше
От издательства
Часть I. Основы Computer Science
Глава 1. Асимптотическое время выполнения
1.1. Что такое алгоритм
1.2. Почему скорость имеет значение
1.3. Когда секунды (не) считаются
1.4. Как мы описываем скорость
1.5. Скорость типичных алгоритмов
1.6. Всегда ли полиномиальное время лучше?
1.7. Время выполнения алгоритма
1.8. Насколько сложна задача?
Глава 2. Структуры данных
2.1. Организация данных
2.2. Массивы, очереди и другие способы построиться
2.3. Связные списки
2.4. Стеки и кучи
2.5. Хеш-таблицы
2.6. Множества и частично упорядоченные множества
2.7. Специализированные структуры данных
Глава 3. Классы задач
Часть II. Графы и графовые алгоритмы
Глава 4. Введение в теорию графов
4.1. Семь кенигсбергских мостов
4.2. Мотивация
4.3. Терминология
4.4. Представление графов
4.5. Направленные и ненаправленные графы
4.6. Циклические и ациклические графы
4.7. Раскраска графа
4.8. Взвешенные и невзвешенные графы
Глава 5. Структуры данных на основе графов
5.1. Двоичные деревья поиска
5.2. Сбалансированные деревья двоичного
поиска
5.3. Кучи
Глава 6. Хорошо известные графовые алгоритмы
6.1. Введение
6.2. Поиск в ширину
6.3. Применение поиска
в ширину
6.4. Поиск в глубину
6.5. Кратчайшие пути
Глава 7. Основные классы графов
7.1. Запрещенные подграфы
7.2. Планарные графы
7.3. Совершенные графы
7.4. Двудольные графы
7.5. Интервальные графы
7.6. Графы дуг окружности
Часть III. Неграфовые алгоритмы
Глава 8. Алгоритмы сортировки
8.1. Малые и большие алгоритмы сортировки
8.2. Сортировки для малых наборов данных
8.3. Сортировка больших наборов данных
8.4. Сортировки без сравнения
Часть IV. Методы решения задач
Глава 9. А если в лоб?
Глава 10. Динамическое программирование
10.1. Задача недостающих полей
10.2. Работа с перекрывающимися подзадачами
10.3. Динамическое программирование и кратчайшие пути
10.4. Примеры практического применения
Глава 11. Жадные алгоритмы
Часть V. Теория сложности вычислений
Глава 12. Что такое теория сложности
Глава 13. Языки и конечные автоматы
13.1. Формальные языки
13.2. Регулярные языки
13.3. Контекстно свободные языки
13.4. Контекстно зависимые языки
13.5. Рекурсивные и рекурсивно перечислимые языки
Глава 14. Машины Тьюринга
14.1. Чисто теоретический компьютер
14.2. Построение машины Тьюринга
14.3. Полнота по Тьюрингу
14.4. Проблема остановки
Часть VI. Доказательства
Глава 15. Приемлемые доказательства
15.1. Введение в доказательства
15.2. Терминология
Глава 16. Методы доказательства
16.1. Конструктивное доказательство, доказательство методом исчерпывания вариантов
16.3. Доказательство методом индукции
16.4. Доказательство на основе закона контрапозиции
Глава 17. Сертификаты
Часть VII.Безопасность и конфиденциальность
Глава 18. Введение в безопасность
18.1. Конфиденциальность
18.2. Целостность
18.3. Доступность
18.4. Цели
Глава 19. Введение в криптографию
19.1. Современная криптография
19.2. Терминология
19.3. Абсолютно безопасный обмен данными
19.4. Квантовое распределение ключей
Глава 20. Криптографическая система с открытым ключом
20.1. Использование открытого и закрытого ключей
20.2. Алгоритм RSA
20.3. Соображения производительности
Глава 21. Аутентификация пользователя
Часть VII.Аппаратное и программное обеспечение
Глава 22. Аппаратные абстракции
22.1. Физическое хранилище
22.2. Данные и методы ввода/вывода
22.3. Память
22.4. Кэш
22.5. Регистры
Глава 23. Программные абстракции
23.1. Машинный код и язык ассемблера
23.2. Низкоуровневые языки программирования
23.3. Высокоуровневые языки программирования
Глава 24. Компьютерная арифметика
24.1. Битовый сдвиг
24.2. Битовые И и ИЛИ
24.3. Битовое НЕ
24.4. Битовое исключающее ИЛИ
Глава 25. Операционные системы
25.1. Управление процессами
25.2. Управление хранилищем
25.3. Ввод/вывод
25.4. Безопасность
Глава 26. Распределенные системы
26.1. Ложные допущения относительно распределенных вычислений
26.2. Коммуникация
26.3. Синхронизация и согласованность
Глава 27. Встроенные системы
Глава 28. Сети и Интернет
28.1. Уровни протоколов
28.2. Протоколы TCP/IP и UDP
28.3. Доставка сообщения
28.4. Алгоритмы маршрутизации
Глава 29. Базы данных
29.1. Реляционные базы данных (РБД)
29.2. Иерархические базы данных (ИБД)
Часть VIII. Углубленные темы
Глава 30. Основная теорема о рекуррентных соотношениях
Глава 31. Амортизированное время выполнения
Глава 32. Расширяющееся дерево
34.1. Концепции
32.2. Zig
32.3. Zig-zig
32.4. Zig-zag
Глава 33. Декартово дерево
Глава 34. Искусственный интеллект
34.1. Типы искусственного интеллекта
34.2. Подобласти ИИ
34.3. Примеры
Глава 35. Квантовые вычисления
35.1. Физика
35.2. Теоретические соображения
35.3. Практические соображения
Приложения
Приложение А. Необходимая математика
Приложение Б. Классические NP-полные задачи
Б.1. SAT и 3-SAT
Б.2. Клика
Б.3. Кликовое покрытие
Б.4. Раскраска графа
Б.5. Гамильтонов путь
Б.6. Укладка рюкзака
Б.7. Наибольшее независимое множество
Б.8. Сумма подмножества
