Реферат: Построение и анализ комбинаторных алгоритмов

Построение и анализ комбинаторных алгоритмов

(дисциплина по выбору)


Преподаватель: Стеценко В.А., доцент кафедры ТИДМ, к.ф.-м.н.


Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 6 зачетных единиц (216 часа).


Структура дисциплины


№ п/п

Наименование раздела дисциплины

Семестр

Виды учебной работы

(в академических часах)


Л


С


ПЗ


ЛБ


СР

1

Алгоритмы и их сложность

2

2







2

10

2

Основные методы сортировки

2

4







4

10

3

Перебор с возвратом

2

10







10

10

4

Теоретико-числовые алгоритмы

2

10





10

10

5

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

2

10





10

10

6

Основные алгоритмы на графах

3

20





10

20

7

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

3

8





4

10

8

Приближенные алгоритмы

3

8





4

10


^ Содержание дисциплины


№п/п

Наименование раздела дисциплины

Содержание раздела

(дидактические единицы)

1

Алгоритмы и их сложность

Сложность в худшем случае. Сложность в среднем. Примеры задач и алгоритмов. Полиномиальные алгоритмы.

2

Основные методы сортировки

Сортировка слиянием, быстрая сортировка, сортировка за линейное время.

3

Перебор с возвратом

Задача о n ферзях. Задача о гамильтоновом цикле. Задача о раскрашивании вершин графа. Задача о сумме подмножества. Метод ветвей и границ. Задача о назначениях. Задача о рюкзаке.

4

Теоретико-числовые алгоритмы

Наибольший общий делитель. Модулярная арифметика. Решение диофантовых уравнений. Степень элемента. Криптосистема RSA с открытым ключом. Проверка чисел на простоту.

5

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

Задача о числовом треугольнике. Когда применимо динамическое программирование? Оптимальная триангуляция выпуклого многоугольника. Задача о кафе. Перемножение нескольких матриц. Наибольшая общая подпоследовательность.

6

Основные алгоритмы на графах

Представление графов. Поиск в ширину и глубину. Сильно связные компоненты. Минимальные покрывающие деревья (Алгоритмы Крускала и Прима). Кратчайшие пути из одной вершины (Алгоритмы Беллмана–Форда и Дейкстры). Кратчайшие пути и умножение матриц (Алгоритм Флойда-Уоршолла). Максимальный поток. Метод Форда – Фалкерсона. Максимальное паросочетание в двудольном графе. Венгерский метод.

7

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

Задача о выборе заявок. Когда применим жадный алгоритм? Коды Хаффмена. Теоретические основы жадных алгоритмов.

8

Приближенные алгоритмы

Жадный алгоритм как приближенный алгоритм. Задача о покрытии. Задача коммивояжера. Задача об упаковки в контейнеры.



^ ТЕМАТИКА РЕФЕРАТОВ, КУРСОВЫХ РАБОТ



Анализ эффективности основных теоретико-числовых задач.

Покрытие прямоугольника квадратами.

Реализация рациональных чисел формулами.

Сложность приближенного вычисления действительных чисел.

Сложность задач на построение при помощи циркуля и линейки.

Быстрые вычисления с целыми числами.

Быстрые вычисления с многочленами.

Быстрые вычисления с дробями.



^ ПЕРЕЧЕНЬ ВОПРОСОВ К ЗАЧЕТУ

Сложность в худшем случае. Сложность в среднем. Анализ эффективности простейших алгоритмов сортировки.

Сортировка слиянием, ее эффективность.

Сортировка за линейное время.

Метод динамического программирования.

Представление графов. Поиск в ширину и глубину.

Максимальный поток. Метод Форда – Фалкерсона.

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



Учебно-методическое и информационное обеспечение дисциплины


а) основная литература:

Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Построение и анализ, М.: МЦНМО, 1999.

б) дополнительная литература:

А.В. Ахо, Д.Э. Хопкрофт, Д.Д. Ульман Структуры данных и алгоритмы, М.: Вильямс, 2000.

А. Левитин Алгоритмы. Введение в разработку и анализ, М.: Вильямс, 2006.

Д. Макконелл Основы современных алгоритмов, М.: Техносфера, 2004.

в) программное обеспечение и Интернет-ресурсы

WolframMathWorld http://mathworld.wolfram.com/

PlanetMath encyclopedia http://planetmath.org/encyclopedia

Wikipedia\, the free encyclopedia http://en.wikipedia.org/wiki/Main_Page