Вопросы к экзамену

Жадные алгоритмы

Жадные алгоритмы: идея, пример (алгоритм Краскала). Матроиды: определение, свойства. Схема жадного алгоритма на матроиде. [ДМП]

Критерий точности жадных алгоритмов — теорема Радо-Эдмондса [ДМП]. Приближенные жадные алгоритмы [Кузюрин, глава 2].

Стратегия "Разделяй и властвуй"

Стратегия "разделяй и властвуй", на примере алгоритма сортировки слиянием.

Оценка сложности рекурсивных алгоритмов, анализ рекуррентных соотношений (частный случай). Анализ рекуррентных соотношений общего вида, случай мультиптикативной функции d. Рекурсивный алгоритм перемножения целых чисел.[ПАВА, СДА]

Сортировка. Оценка средней сложности сортировки. Сортировка деревом (с доказательством корректности и с оценкой сложности). Быстрая сортировка (с оценкой сложности в среднем и в худшем случае). Порядковые статистики.[ПАВА, СДА]

Динамическое программирование

Идея динамического программирования (на примере задачи нахождения чисел Фибоначчи). Задача о рюкзаке [LNOA]. Задача определения оптимального порядка вычисления произведения матриц [ПАВА, LNOA]. Задача о наибольшей подстроке [451lect]. Задача о построении оптимального дерева поиска [ПАВА, LNOA].

Методы решения сложных задач

Алгоритмы локального поиска — идея, общая схема, применение (итерационные эвристические алгоритмы, отсечение ветвей в МВГ). Задача о размещении блоков. Задачи об оптимальной нумерации, о размыкании контуров и об экспертных оценках.

Литература

ДМП Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2000.
ПАВА Ахо А., Хопкрофт Д., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1978.
СДА Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. - М.: Вильямс, 2000.
Кузюрин Кузюрин Н.Н. Курс лекций "Сложность комбинаторных алгоритмов"
http://discopal.ispras.ru/ru.lectures.htm
LNOA Ian Parberry. Lecture Notes On Algorithm Analysis and Computational Complexity (англ.)
http://hercule.csci.unt.edu/ian/books/free/
451lect David Mount "Design and Analysis of Computer Algorithms" (англ.)
http://www.cs.umd.edu/~mount/451/
Сайт создан в системе uCoz