Дискретная оптимизация (стр. 1 )

РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

Государственное образовательное учреждение

высшего профессионального образования

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Институт математики, естественных наук и информационных технологий

Кафедра программного обеспечения

ЗАЙЦЕВА С. С.

ДИСКРЕТНАЯ ОПТИМИЗАЦИЯ

Учебно-методический комплекс.

Рабочая программа для студентов очной формы обучения,

направление 090900.62 «Информационная безопасность»,

профиль подготовки: «Безопасность распределённых систем».

Тюменский государственный университет

2011

Зайцева оптимизация. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направление 090900.62 «Информационная безопасность»,профиль подготовки: «Безопасность распределённых систем».Тюмень, 2011, 11 стр.

Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки.

Рабочая программа дисциплины «Дискретная оптимизация» опубликована на сайте ТюмГУ: http://www. ***** [электронный ресурс] / Режим доступа: свободный.

Рекомендовано к изданию кафедрой программного обеспечения. Утверждено проректором по учебной работе Тюменского государственного университета.

ОТВЕТСТВЕННЫЙ РЕДАКТОР: , д. п.н., профессор.

© Тюменский государственный университет, 2011.

© , 2011.

1. Пояснительная записка:

1.1. Цели и задачи дисциплины

Дисциплина «Дискретная оптимизация» посвящена построению математических моделей практических задач; изучению классических алгоритмов решения оптимизационных задач на графах и сетях с применением различных приемов программирования; построению новых и модификации и комбинации известных алгоритмов для решения конкретных задач; оценке эффективности указанных алгоритмов.

Цели дисциплины:

- дать навыки постановки и решения задач оптимизации на графах;

- научить выбору адекватных алгоритмов для решения вышеуказанных задач;

- отработать умения по программной реализации алгоритмов на персональном компьютере.

1.2. Место дисциплины в структуре ООП бакалавриата

Дисциплина «Дискретная оптимизация» входит в часть дисциплин по выбору цикла естественно-научных дисциплин Федерального государственного образовательного стандарта высшего профессионального образования (ФГОС ВПО) по направлению «Информационная безопасность». Для её успешного изучения необходимы знания и умения, приобретенные в результате освоения разделов дискретной математики и программирования.

Знания, полученные при изучении дискретной оптимизации необходимы как при проведении теоретических исследований в различных областях математики, так и при решении практических задач из разнообразных прикладных областей, таких как программирование, математическая экономика, математическая лингвистика, обработка и передача данных, распознавание образов, криптография и др.

1.3. Компетенции выпускника ООП бакалавриата, формируемые в результате освоения данной ООП ВПО.

В результате изучения дисциплины «Дискретная оптимизация» цикла естественно-научных дисциплин по выбору по направлению подготовки 090900.62 «Информационная безопасность» с квалификацией (степенью) «бакалавр» в соответствии с целями основной образовательной программы и задачами профессиональной деятельности, указанными в ФГОС ВПО, выпускник должен обладать следующими компетенциями:

Профессиональными компетенциями:

· умением демонстрировать определение общих форм, закономерностей, инструментальных средств для данной дисциплины (ПК-1);

· умением понять поставленную задачу (ПК-2);

· умением на основе анализа увидеть и конкретно сформулировать результат (ПК-5).

В результате освоения дисциплины обучающийся должен:

· Знать: основные алгоритмы на графах;

· Уметь: применять алгоритмический аппарат для решения прикладных задач; 

· Владеть: навыками применения языков программирования и средств дискретной оптимизации.

2. Структура и трудоемкость дисциплины.

Семестр 3. Форма промежуточной аттестации зачёт. Общая трудоемкость дисциплины составляет 2 зачетных единицы - 72 часа.

3. Тематический план.

Таблица 1.

Тематический план

№	Тема	недели семестра	Виды учебной работы и самостоятельная работа, в час.	Итого часов по теме	Из них в интерактивной форме	Итого количество баллов
Лекции	Лабораторные занятия	Самостоятельная работа
1	2
Модуль 1
1.1	Машинное представление графов и сетей.	1-4	4	4	8	16	4	0-15
1.2	Поиск в графах.	5-6	2	2	4	8	2	0-10
Всего:	6	6	12	24	6	0-25
Модуль 2
2.1	Задача построения минимального остова.	7-8	2	2	4	8	2	0-10
2.2	Кратчайшие пути из одной вершины.	9-10	2	2	4	8	2	0-10
2.3	Кратчайшие пути для всех пар вершин.	11-12	2	2	4	8	2	0-10
Всего:	6	6	12	24	6	0-30
Модуль 3
3.1	Задача о максимальном потоке в сети.	13-14	2	2	4	8	2	0-15
3.2	Задача о наибольшем паросочетании.	15-16	2	2	4	8	2	0-10
3.3	Гамильтоновы циклы.	17-18	2	2	4	8	2	0-20
Всего:	6	6	12	24	6	0-45
	Итого (часов, баллов):		18	18	36	72	18	0-100
	Из них часов в интерактивной форме			9	9		18

Таблица 2.