Geum.ru

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

Вид материалаДокументы

Содержание


Содержание дисциплины
Тематика рефератов, курсовых работ
Перечень вопросов к зачету
Подобный материал:
Построение и анализ комбинаторных алгоритмов

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


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


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

Общая трудоемкость дисциплины составляет 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
Приближенные алгоритмы
Жадный алгоритм как приближенный алгоритм. Задача о покрытии. Задача коммивояжера. Задача об упаковки в контейнеры.



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


  1. Анализ эффективности основных теоретико-числовых задач.
  2. Покрытие прямоугольника квадратами.
  3. Реализация рациональных чисел формулами.
  4. Сложность приближенного вычисления действительных чисел.
  5. Сложность задач на построение при помощи циркуля и линейки.
  6. Быстрые вычисления с целыми числами.
  7. Быстрые вычисления с многочленами.
  8. Быстрые вычисления с дробями.



ПЕРЕЧЕНЬ ВОПРОСОВ К ЗАЧЕТУ
  1. Сложность в худшем случае. Сложность в среднем. Анализ эффективности простейших алгоритмов сортировки.
  2. Сортировка слиянием, ее эффективность.
  3. Сортировка за линейное время.
  4. Метод динамического программирования.
  5. Представление графов. Поиск в ширину и глубину.
  6. Максимальный поток. Метод Форда – Фалкерсона.
  7. Жадные алгоритмы, примеры.



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


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

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

б) дополнительная литература:
  1. А.В. Ахо, Д.Э. Хопкрофт, Д.Д. Ульман Структуры данных и алгоритмы, М.: Вильямс, 2000.
  2. А. Левитин Алгоритмы. Введение в разработку и анализ, М.: Вильямс, 2006.
  3. Д. Макконелл Основы современных алгоритмов, М.: Техносфера, 2004.

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