Колосс на rлиняных ногах - так можно назвать программиста без подготовки в области Coшputer Science. Уверенное владение основами позволяет «не изобретать велосипеды» и закладывать в архитектуру программ эффективные решения. Все это избавляет от ошибок и чрезмерных затрат на тестирование и рефакторинт. Не беда, если вы чувствуете себя не у дел, когда другие программисты обсуждают аппроксимативный предел. Даже специалисты с опытом допускают ошибки из-за того, что подзабыли Coшputer Science. Введение 10 Зачем нужна эта книга 10 Чего вы не найдете в издании 11 Дополнительные ресурсы 12 От издательства 13 Часть I Основы Computer Science 14 Глава 1. Асимптотическое время выполнения 15 1.1. Что такое алгоритм 15 1.2. Почему скорость имеет значение 17 1.3. Когда секунды (не) считаются 18 1.4. Как мы описываем скорость 21 1.5. Скорость типичных алгоритмов 22 1.6. Всегда ли полиномиальное время лучше? 26 1.7. Время выполнения алгоритма 28 1.8. Насколько сложна задача? 32 Глава 2. Структуры данных 33 2.1. Организация данных 33 2.2. Массивы, очереди и другие способы построиться 34 2.3. Связные списки 36 2.4. Стеки и кучи 39 2.5. Хеш-таблицы 43 2.6. Множества и частично упорядоченные множества 46 2.7. Специализированные структуры данных 50 Глава 3. Классы задач 51 Часть II Графы и графовые алгоритмы 60 Глава 4. Введение в теорию графов 61 4.1. Семь кенигсбергских мостов 61 4.2. Мотивация 63 4.3. Терминология 65 4.4. Представление графов 68 4.5. Направленные и ненаправленные графы 72 4.6. Циклические и ациклические графы 73 4.7. Раскраска графа 77 4.8. Взвешенные и невзвешенные графы 80 Глава 5. Структуры данных на основе графов 82 5.1. Двоичные деревья поиска 82 5.2. Сбалансированные деревья двоичного поиска 86 5.3. Кучи 87 Глава 6. Хорошо известные графовые алгоритмы 98 6.1. Введение 98 6.2. Поиск в ширину 99 6.3. Применение поиска в ширину 102 6.4. Поиск в глубину 103 6.5. Кратчайшие пути 106 Глава 7. Основные классы графов 111 7.1. Запрещенные подграфы 111 7.2. Планарные графы 112 7.3. Совершенные графы 115 7.4. Двудольные графы 117 7.5. Интервальные графы 118 7.6. Графы дуг окружности 120 Часть III Неграфовые алгоритмы 122 Глава 8. Алгоритмы сортировки 123 8.1. Малые и большие алгоритмы сортировки 124 8.2. Сортировки для малых наборов данных 126 8.3. Сортировка больших наборов данных 129 8.4. Сортировки без сравнения 133 Часть IV Методы решения задач 138 Глава 9. А если в лоб? 139 Глава 10. Динамическое программирование 142 10.1. Задача недостающих полей 142 10.2. Работа с перекрывающимися подзадачами 144 10.3. Динамическое программирование и кратчайшие пути 146 10.4. Примеры практического применения 148 Глава 11. Жадные алгоритмы 151 Часть V Теория сложности вычислений 154 Глава 12. Что такое теория сложности 155 Глава 13. Языки и конечные автоматы 158 13.1. Формальные языки 158 13.2. Регулярные языки 159 13.3. Контекстно свободные языки 170 13.4. Контекстно зависимые языки 176 13.5. Рекурсивные и рекурсивно перечислимые языки 177 Глава 14. Машины Тьюринга 179 14.1. Чисто теоретический компьютер 179 14.2. Построение машины Тьюринга 180 14.3. Полнота по Тьюрингу 182 14.4. Проблема остановки 182 Послесловие 184 Приложение А. Необходимая математика 187 Приложение Б. Классические NP-полные задачи 189 Б.1. SAT иЗ-SAT 189 Б.2. Клика 190 Б.З. Кликовое покрытие 190 Б.4. Раскраска графа 190 Б.5. Гамильтонов путь 191 Б.6. Укладка рюкзака 191 Б.7. Наибольшее независимое множество 191 Б.8. Сумма подмножества 191 Название: Гид по Computer Science для каждого программиста Автор: Спрингер Вильям Год: 2020 Жанр: программирование Серия: Библиотека программиста Издательство: Питер Язык: Русский Формат: pdf Качество: Отсканированные страницы + слой распознанного текста Страниц: 192 Размер: 11 MB Скачать Спрингер Вильям - Гид по Computer Science для каждого программиста (2020) Скачать с 2bay.org Скачать с Katfile.com Скачать с Oxy.cloud