Глава 1. Введение
1.1 Понятие алгоритма Упражнения 1.1
1.2 Основы решения алгоритмической задачи. Понимание задачи. Определение возможностей вычислительного устройства. Выбор между точным или приближенным методом решения задачи. Выбор подходящих структур данных . Методы проектирования алгоритмов. Методы представления алгоритмов. Оценка корректности алгоритма. Анализ алгоритма. Кодирование алгоритма. Упражнения 1.2
1.3 Важные типы задач. Сортировка. Поиск. Обработка строк. Задачи из теории графов. Комбинаторные задачи. Геометрические задачи. Численные задачи. Упражнения 1.3
1.4 Базовые структуры данных Линейные структуры данных Графы. Деревья. Множества и словари. Упражнения 1.4. Резюме
Глава 2. Основы анализа эффективности алгоритмов
2.1 Основы анализа. Оценка размера входных данных. Единицы измерения времени выполнения алгоритма. Порядок роста. Эффективность алгоритма в разных случаях. Повторение пройденного. Упражнения 2.1
2.2 Асимптотические обозначения и основные классы эффективности. Нестрогое введение. О-обозначение. Ω-обозначение. Θ-обозначение
Полезные свойства сделанных асимптотических обозначений. Использование пределов для сравнения порядка роста двух функций. Основные классы эффективности. Упражнения 2.2
2.3 Математический анализ нерекурсивных алгоритмов. Упражнения 2.3
2.4 Математический анализ рекурсивных алгоритмов. Упражнения 2.4
2.5 Пример: числа Фибоначчи. Явная формула для определения n-го элемента. последовательности чисел Фибоначчи. Алгоритмы вычисления чисел Фибоначчи. Упражнения 2.5
2.6 Эмпирический анализ алгоритмов. Упражнения 2.6. Визуализация алгоритмов. Резюме
Глава 3. Метод грубой силы
3.1 Сортировка выбором и пузырьковая сортировка. Сортировка выбором. Пузырьковая сортировка. Упражнения 3.1
3.2 Последовательный поиск и поиск подстрок методом грубой силы. Последовательный поиск. Поиск подстроки. Упражнения 3.2
3.3 Задачи поиска пары ближайших точек и вычисления выпуклой оболочки с использованием грубой силы. Поиск пары ближайших точек. Поиск выпуклой оболочки. Упражнения 3.3
3.4 Исчерпывающий перебор. Задача коммивояжера. Задача о рюкзаке. Задача о назначениях
Упражнения 3.4. Резюме
Глава 4. Метод декомпозиции
4.1 Сортировка слиянием. Упражнения 4.1
4.2 Быстрая сортировка. Упражнения 4.2
4.3 Бинарный поиск. Упражнения 4.3
4.4 Обход бинарного дерева. Упражнения 4.4
4.5 Умножение больших целых чисел и алгоритм умножения матриц Штрассена. Умножение больших целых чисел. Алгоритм Штрассена для умножения матриц. Упражнения 4.5.
4.6 Решение задач о паре ближайших точек и о выпуклой оболочке методом декомпозиции. Задача о паре ближайших точек. Задача о выпуклой оболочке. Упражнения 4.6. Резюме
Глава 5. Метод уменьшения размера задачи
5.1 Сортировка вставкой. Упражнения 5.1
5.2 Поиск в глубину и поиск в ширину. Поиск в глубину. Поиск в ширину. Упражнения 5.2
5.3 Топологическая сортировка. Упражнения 5.3
5.4 Алгоритмы генерации комбинаторных объектов. Генерация перестановок. Генерация подмножеств. Упражнения 5.41
5.5 Алгоритмы с использованием уменьшения на постоянный множитель. Задача поиска фальшивой монеты. Умножение по-русски. Задача Иосифа. Упражнения 5.5
5.6 Алгоритмы с переменным уменьшением размера. Вычисление медианы и задача выбора. Интерполяционный поиск. Поиск и вставка в бинарное дерeво поиска. Упражнения 5.6. Резюме
Глава 6. Метод преобразования
6.1 Предварительная сортировка. Упражнения 6.1
6.2 Метод исключения Гаусса. LU-разложение и другие приложения. Вычисление обратной матрицы. Вычисление определителя. Упражнения 6.2
6.3 Сбалансированные деревья поиска. AVL-деревья . 2-3-деревья. Упражнения 6.3
6.4 Пирамиды и пирамидальная сортировка. Понятие пирамиды. Пирамидальная сортировка. Упражнения 6.4
6.5 Схема Горнера и возведение в степень. Схема Горнера. Бинарное возведение в степень. Упражнения 6.5
6.6 Приведение задачи. Вычисление наименьшего общего кратного. Подсчет путей в графе. Приведение задач оптимизации. Линейное программирование. Приведение к задачам о графах. Упражнения 6.6. Резюме
Глава 7. Пространственно-временной компромисс
7.1 Сортировка подсчетом. Упражнения 7.1
7.2 Улучшение входных данных в поиске подстрок. Алгоритм Хорспула. Алгоритм Бойера-Мура. Упражнения 7.2
7.3 Хеширование. Открытое хеширование (раздельные цепочки). Закрытое хеширование (открытая адресация). Упражнения 7.3
7.4 В-деревья. Упражнения 7.4. Резюме
Глава 8. Динамическое программирование
8.1 Вычисление биномиальных коэффициентов. Упражнения 8.1
8.2 Алгоритмы Воршалла и Флойда. Алгоритм Воршалла
Алгоритм Флойда поиска кратчайших путей между всеми парами вершин. Упражнения 8.2
8.3 Оптимальные бинарные деревья поиска. Упражнения 8.3
8.4 Задача о рюкзаке и функции с запоминанием. Функции с запоминанием. Упражнения 8.4. Резюме
Глава 9. Жадные методы
9.1 Алгоритм Прима. Упражнения 9.1
9.2 Алгоритм Крускала. Не пересекающиеся подмножества и алгоритмы поиска объединений. Упражнения 9.2
9.3 Алгоритм Дейкстры. Упражнения 9.3
9.4 Деревья Хаффмана. Упражнения 9.4. Резюме
Глава 10. Ограничения мощи алгоритмов
10.1 Доказательства нижних границ. Тривиальные нижние границы. Информационно-теоретические доказательства. Доказательство "от противника"
Приведение задачи. Упражнения 10.1
10.2 Деревья принятия решения. Деревья принятия решения для алгоритмов сортировки. Деревья принятия решения для поиска в отсортированном массиве. Упражнения 10.2
10.3 Р, NP и NP-полные задачи. Р и NP-задачи. NР-полные задачи. Упражнения 10.3
10.4 Численные алгоритмы. Упражнения 10.4. Резюме
Глава 11. Преодоление ограничений
11.1 Поиск с возвратом. Задача о n ферзях. Задача о гамильтоновом цикле. Задача о сумме подмножества. Общие замечания. Упражнения 11.1
11.2 Метод ветвей и границ. Задача о назначениях. Задача о рюкзаке. Задача коммивояжера. Упражнения 11.2
11.3 Приближенные алгоритмы для iVP-сложных задач. Приближенный алгоритм для решения задачи коммивояжера . Приближенные алгоритмы для задачи о рюкзаке . Упражнения 11.3
11.4 Алгоритмы для решения нелинейных уравнений. Метод деления пополам. Метод секущих. Метод Ньютона. Упражнения 11.4. Резюме. Эпилог
Приложение А. Формулы, использующиеся при анализе алгоритмов. Свойства логарифмов. Комбинаторика. Важные формулы суммирования. Правила работы с суммами. Приближение суммы определенным интегралом. Формулы для округлений снизу и сверху. Разное
Приложение Б. Краткое руководство по рекуррентным соотношениям. Последовательности и рекуррентные соотношения. Методы решения рекуррентных соотношений. Распространенные типы рекуррентных соотношений в анализе алгоритмов
Список технической литературы
Указания к упражнениям
Предметный указатель
Добавить комментарий