ВУЗ:
ТЕОРИЯ АЛГОРИТМОВ
Объем - Недель -18 Лекции -36 Лабор -36 Контроль – экз.
Алгоритм: определение, свойства, примеры. Проблема алгоритмической раз-
решимости.
Мера сложности задачи. Временная и ленточная сложность задач. Асимптоти-
ческие соотношения. Анализ времени выполнения алгоритма.
Эффективность алгоритмов. Анализ рекурсивных программ. Решение рекур-
рентных соотношений.
Жадные алгоритмы. Эвристические методы. Алгоритмы локального поиска.
Задача коммивояжера.
Алгоритмы сортировки. Методы типа вставки, пузырька, метод фон Неймана.
Метод
Шелла, алгоритм быстрой сортировки (метод Хоара). Алгоритм иерархи-
ческой сортировки (метод Уильямса). Анализ временной сложности алгоритмов.
Алгоритмы на множествах. Построение всех подмножеств множества. Бинар-
ный поиск. Генерация всех n-элементных подмножеств множества в лексикогра-
фическом порядке. Алгоритм генерации перестановок элементов множества.
Временная сложность алгоритмов.
Списки, стеки, очереди. Различные реализации. Методы работы со списками
.
Структуры данных, основанные на хеш-таблицах. Алгоритмы хеширования.
Алгоритмы работы с деревьями. Алгоритм балансировки бинарного дерева.
AVL-деревья.
Алгоритмы на графах. Задачи о поиске кратчайших путей. Алгоритм Дейкст-
ры. Алгоритм Флойда-Уоршелла. Задача о кратчайшем остовном дереве. Алго-
ритмы Прима и Крускала. Анализ сложности алгоритмов. Уравнение динамиче-
ского программирования Беллмана
.
Некоторые задачи теории расписаний. Задача красильщика. Задача Джексона.
Задача о минимизации числа запоздавших работ (Мур) и алгоритм Ходжсона. За-
дача Джонсона о двух станках.
Алфавит и операции над словами. Нормальные алгоритмы Маркова.
Рекурсивные функции. Тезис Чёрча.
Машина Тьюринга (ТМ): структура, функциональная схема. Базисные машины
Тьюринга. Машины Тьюринга с полулентой. Композиция
и объединение ТМ.
Разветвление и итерация ТМ.
Тьюринговы алгоритмы. Тезис Тьюринга. Проблемы, алгоритмически нераз-
решимые по Тьюрингу. Универсальный алфавит машины. Проблема самоприме-
нимости ТМ. Универсальная машина Тьюринга.
Мера сложности задачи. Полиномиальная и недетерминированная полиноми-
альная сложность. NP-полнота.
Основная литература
1. А. Ахо, Д. Хопкрофт, Д. Ульман Структуры данных и алгоритмы. Пер
. с англ.
Учебное пособие. М.: Издательский дом "Вильямс", 2000.- 384 с.
Страницы
- « первая
- ‹ предыдущая
- …
- 2
- 3
- 4
- 5
- 6
- …
- следующая ›
- последняя »
