Гид по Computer Science для каждого программиста

Description

Колосс на глиняных ногах – так можно назвать программиста без подготовки в области Computer Science. Уверенное владение основами позволяет «не изобретать велосипеды» и закладывать в архитектуру программ эффективные решения. Всё это избавляет от ошибок и чрезмерных затрат на тестирование и рефакторинг. Не беда, если вы чувствуете себя не у дел, когда другие программисты обсуждают аппроксимативный предел. Даже специалисты с опытом допускают ошибки из-за того, что подзабыли Computer Science. Эта книга будет вам живым помощником в освоении и повторении самых насущных вопросов компьютерных наук: • типы и структуры данных; • алгоритмы; • графы; • теория сложности; • приемы эффективного решения задач. Оглавление Введение Зачем нужна эта книга Чего вы не найдете в издании Дополнительные ресурсы От издательства Часть 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. Проблема остановки Послесловие Приложение А. Необходимая математика Приложение Б. Классические NP-полные задачи Б.1. SAT иЗ-SAT Б.2. Клика Б.З. Кликовое покрытие Б.4. Раскраска графа Б.5. Гамильтонов путь Б.6. Укладка рюкзака Б.7. Наибольшее независимое множество Б.8. Сумма подмножества