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




Скачать 56.71 Kb.
НазваниеПостроение и анализ комбинаторных алгоритмов
Дата27.11.2012
Размер56.71 Kb.
ТипДокументы
Построение и анализ комбинаторных алгоритмов

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


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


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

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

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



Похожие:

Построение и анализ комбинаторных алгоритмов iconПрограмма по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения
Эвм, вычислительной геометрии. Основным содержанием дисциплины является исследования и оценка сложности геометрических построений,...
Построение и анализ комбинаторных алгоритмов iconЛейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Мцнмо, 1999. Косовский Н. К. Основы теории элементарных алгоритмов
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: Мцнмо, 1999
Построение и анализ комбинаторных алгоритмов iconЛейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Мцнмо, 1999. Косовский Н. К. Основы теории элементарных алгоритмов
«Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»
Построение и анализ комбинаторных алгоритмов iconРешение комбинаторных задач методом полного перебора вариантов, знание приема умножения в комбинаторных задачах
Курс строится на индуктивной основе с привлечением элементов дедуктивных рассуждений. Теоретический материал курса излагается на...
Построение и анализ комбинаторных алгоритмов iconПоиск ключа в массиве. Анализ эффективности алгоритмов поиска
Целью работы является закрепление практических навыков по реализации алгоритмов поиска, а также анализ эффективности их работы
Построение и анализ комбинаторных алгоритмов iconАлгоритмы
Основы алгоритмизации. Понятие об алгоритме. Применение алгоритмов. Свойства алгоритмов. Типы алгоритмов: линейные, циклические,...
Построение и анализ комбинаторных алгоритмов iconСодержание, основные понятия
Понятие алгоритма, свойства алгоритмов. Использование алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...
Построение и анализ комбинаторных алгоритмов iconБилет №4
Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Способы описания алгоритмов....
Построение и анализ комбинаторных алгоритмов iconПлан-конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов и формы записи алгоритмов"
...
Построение и анализ комбинаторных алгоритмов iconРабочая программа дисциплины
Целями освоения дисциплины «Алгоритмы и анализ сложности» являются формирование устойчивого алгоритмического мышления у студентов,...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница