Главная > Документ


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

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

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

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

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

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

  • WolframMathWorld /

  • PlanetMath encyclopedia /encyclopedia

  • Wikipedia\, the free encyclopedia /wiki/Main_Page

3



Скачать документ

Похожие документы:

  1. Построение и анализ комбинаторных алгоритмов (дисциплина по выбору)

    Документ
    Построение и анализ комбинаторных алгоритмов (дисциплина по выбору) Преподаватель: Стеценко В.А., доцент кафедры ТИДМ, к.ф.-м.н. Структура и содержание дисциплины Общая трудоемкость дисциплины составляет 6 зачетных ...
  2. Построение и анализ алгоритмов

    Программа
    ... ., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. Пападимитриу Х., Стейглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: 1985 ...
  3. Аннотация дисциплины Деловой иностранный язык

    Задача
    ... языка для построения формальных моделей и алгоритмов обработки естественного ... предикатов и их комбинаторного перебора – исчисления, ... по направлению 220100 «Системный анализ и управление». Является дисциплиной по выбору. Целью преподавания дисциплины ...
  4. Подготовка магистра в сфере дошкольного И НАЧАЛЬНОГО образования Программы учебных дисциплин Допущено Учебно-методическим объединением по направлениям педагогического образования Министерства образования и науки РФ в качестве учебно-методических

    Документ
    ... (О.А.Ивашова) Дисциплины по выбору Методика внеклассной работы по дисциплинам естественно-математического ... построение: анализ, построение, доказательство, исследование. Построение треугольников. Обучение младших школьников геометрическим построениям по ...
  5. С б о р н и к примерных программ математических дисциплин цикла

    Пояснительная записка
    ... . Возможная тематика математических дисциплин по выбору (элективов) и факультативных дисциплин 1. Дополнительные главы математического анализа; 2. Дополнительные главы ...

Другие похожие документы..