Гид по Computer Science для каждого программиста, Спрингер В., 2020

Гид по Computer Science для каждого программиста, Спрингер В., 2020.

   Колосс на глиняных ногах — так можно назвать программиста без подготовки в области Computer Science. Уверенное владение основами позволяет «не изобретать велосипеды» и закладывать в архитектуру программ эффективные решения. Все это избавляет от ошибок и чрезмерных затрат на тестирование и рефакторинг.
Не беда, если вы чувствуете себя не у дел, когда другие программисты обсуждают аппроксимативный предел. Даже специалисты с опытом допускают ошибки из-за того, что подзабыли Computer Science.




Почему скорость имеет значение.
Современные компьютеры достаточно быстры, поэтому во многих случаях скорость алгоритма не особенно важна. Когда я нажимаю кнопку и компьютер реагирует за 1/25 секунды, а не за 1/100 секунды, эта разница для меня не имеет значения — с моей точки зрения, компьютер в обоих случаях реагирует мгновенно.

Но во многих приложениях скорость все еще важна, например, при работе с большим количеством объектов. Предположим, что у вас есть список из миллиона элементов, который необходимо отсортировать. Эффективная сортировка занимает одну секунду, а неэффективная может длиться несколько недель. Возможно, пользователь не захочет ждать, пока она закончится.

Мы часто считаем задачу неразрешимой, если не существует известного способа ее решения за разумные сроки, где «разумность» зависит от различных реальных факторов. Например, безопасность шифрования данных часто зависит от сложности разложения на множители (факторизации) больших чисел. Если я отправляю вам зашифрованное сообщение, содержимое которого нужно хранить в секрете в течение недели, то для меня не имеет значения, что злоумышлен ник перехватит это сообщение и расшифрует его через три года.

ОГЛАВЛЕНИЕ.
Введение.
Зачем нужна эта книга.
Чего вы не найдете в издании.
Дополнительные ресурсы.
От издательства.
Часть 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.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. Проблема остановки.
Послесловие.
Приложение А. Необходимая математика.
Приложение Б. Классические NР-полные задачи.
Б.1. SAT и 3-SAT.
Б.2. Клика.
Б.3. Кликовое покрытие.
Б.4. Раскраска графа.
Б.5. Гамильтонов путь.
Б.6. Укладка рюкзака.
Б.7. Наибольшее независимое множество.
Б.8. Сумма подмножества.

Купить .





Теги: учебник по программированию :: программирование :: Спрингер