Теория графов

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

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

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

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

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

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

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

ЗАЙЦЕВА С. С.

ТЕОРИЯ ГРАФОВ

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

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

направление 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.

Виды и формы оценочных средств в период текущего контроля

№ темы	Устный опрос	Письменные работы	Информацинные системы и технологии	Итого количество баллов
ответ на семинаре	лабораторная работа	контрольная работа	Электронный практикум
Модуль 1
1.1	0-3	0-12			0-15
1.2	0-2	0-5		0-3	0-10
Всего	0-5	0-17		0-3	0-25
Модуль 2
2.1	0-2	0-5		0-3	0-10
2.2	0-2	0-4	0-4		0-10
2.3	0-2	0-5		0-3	0-10
Всего	0-6	0-14	0-4	0-6	0-30
Модуль 3
3.1	0-2	0-13			0-15
3.2	0-2	0-5		0-3	0-10
3.3	0-2	0-10	0-8		0-20
Всего	0-6	0-28	0-8	0-3	0-45
Итого	0-17	0-59	0-12	0-12	0-100

Таблица 3.

Планирование самостоятельной работы студентов

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

4.  Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами

№ п/п	Наименование обеспечиваемых (последующих) дисциплин	Темы дисциплины необходимые для изучения обеспечиваемых (последующих) дисциплин
1.1	1.2	2.1	2.2	2.3	3.1	3.2	3.3
1.	Дополнительные главы теории алгоритмов	+	+	+	+
2.	Курсовые и дипломные работы	+	+	+	+	+	+	+	+

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

Модуль 1

Тема1.1. Машинное представление графов и сетей.

Матрицы графов. Списки смежности. Структура Вирта.

Тема 1.2. Потоки в сетях.

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

Модуль 2

Тема 2.1. Паросочетания в двудольных графах.

Задача о наибольшем паросочетании. Алгоритм Хопкрофта-Карпа. Оценка сложности алгоритма Хопкрофта–Карпа.

Тема 2.2. Задача о назначениях.

Задача о назначениях. Венгерский алгоритм.

Тема2.3. Задача о разбиении на наименьшее число паросочетаний

Задача о разбиении на наименьшее число паросочетаний. Теорема Мендельсона-Далмеджа.

Модуль 3

Тема 3.1. Задача составления расписания.

Задача составления расписания.

Тема 3.2. Задача коммивояжера.

Метод ветвей и границ. Алгоритмы с гарантированной оценкой точности: минимальная вставка и остовный обход. Теоремы об оценки точности этих алгоритмов.

Тема 3.3. Общая схема стохастических алгоритмов.

Стохастический алгоритм решения задачи коммивояжера. Моделирование отжига.

6.  Планы семинарских занятий.

Не планируются

7.  Темы лабораторных работ (Лабораторный практикум).

Задания лабораторного практикума выполняются с использованием систем программирования на языках Borland Delphi, С/С++.

Тема1.1. Машинное представление графов и сетей.

Матрицы графов. Списки смежности. Структура Вирта.

Тема 1.2. Потоки в сетях.

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

Тема 2.1. Паросочетания в двудольных графах.

Задача о наибольшем паросочетании. Алгоритм Хопкрофта-Карпа.

Тема 2.2. Задача о назначениях.

Задача о назначениях. Венгерский алгоритм.

Тема2.3. Задача о разбиении на наименьшее число паросочетаний

Задача о разбиении на наименьшее число паросочетаний.

Тема 3.1. Задача составления расписания.

Задача составления расписания

Тема 3.2. Задача коммивояжера.

Метод ветвей и границ. Алгоритмы с гарантированной оценкой точности: минимальная вставка и остовный обход.

Тема 3.3. Общая схема стохастических алгоритмов.

Стохастический алгоритм решения задачи коммивояжера. Моделирование отжига.

Примерная тематика курсовых работ.

Не планируются.

8.  Учебно - методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины (модуля).

Контроль качества подготовки осуществляется путем проверки теоретических знаний и практических навыков с использованием

a) Текущей аттестации:

проверка промежуточных контрольных работ и прием лабораторных работ;

b) Промежуточной аттестации:

тестирование (письменное или компьютерное) по разделам дисциплины;

зачет в конце 3 семестра (к зачету допускаются студенты после сдачи всех лабораторных работ, решения всех задач контрольных работ и выполнения самостоятельной работы).

Текущий и промежуточный контроль освоения и усвоения материала дисциплины осуществляется в рамках рейтинговой (100-бальной) системы оценок.

Пример тестового задания по теме: «Машинное представление графов и сетей»:

PROCEDURE ONE (N: Integer; Beg: Massiv);

var UkZv: svqz;

BEGIN

For i:=1 to N do

begin

Write (' ',i,'...'); UkZv:=Beg[i];

If UkZv=Nil then WriteLn ('Пустой список!')

else begin While UkZv<>Nil do

begin

Write (UkZv^.Key:2,' * '); UkZv:=UkZv^.Sled

end;

WriteLn end end END;

Процедура предназначена для :

1. Вывода структуры смежности для графа, заданного ортогональными списками

2. Вывода структуры смежности для графа, заданного структурой Вирта

3. Вывода содержимого списков смежности

Пример лабораторного задания по теме: «Машинное представление графов и сетей»:

1. Реализовать граф как класс на основе структуры Вирта. Методы:

­  добавление и удаление вершины;

­  добавление и удаление ребра (дуги);

­  ориентирование (неориентирование).

2.  Реализовать процедуры преобразования структуры Вирта во все динамические и матричные (смежность, инцидентность, достижимость) структуры. Реализовать интерфейс для всех представлений.

Вопросы к зачёту:

1.  Представление графов с помощью матриц. Основные недостатки. 

2.  Представление графов с помощью списков смежности. Описание типа. 

3.  Представление графов с помощью ортогональных списков смежности. Описание типа. 

4.  Представление графов с помощью структуры Вирта. Описание типа. 

5.  Представление графов с помощью модифицированной структуры Вирта. Описание типа. 

6.  Построение списков смежности, моделирующих ориентированный граф, вывод их на экран, добавление и удаление дуг. 

7.  Построение ортогональных списков смежности, моделирующих ориентированный граф. Вывод на экран структуры ортогональных списков смежности, добавление и удаление дуг, добавление и удаление вершин. 

8.  Построение динамической структуры Вирта, моделирующей ориентированный граф. Вывод на экран его структуры, добавление и удаление ребер, добавление и удаление вершин. 

9.  Построение модифицированной структуры Вирта, моделирующий ориентированный граф, вывод ее на экран и добавление ребер. 

10.  Задача о потоке в сети с ограничениями снизу.

11.  Задача о потоке минимальной стоимости. Транспортная задача.

12.  Критерий µ-оптимальности потока.

13.  Прямой алгоритм построения потока минимальной стоимости.

14.  Двойственный алгоритм построения потока минимальной стоимости.

15.  Паросочетания в двудольных графах. Теорема Бержа. Связь понятий паросочетания и потока в соответствующей цепи. Модификация алгоритма Форда-Фалкерсона для построения наибольшего паросочетания.

16.  Алгоритм Хопкрофта-Карпа. Основные процедуры этого алгоритма.

17.  Оценка сложности алгоритма Хопкрофта-Карпа.

18.  Задача о назначениях. Основные леммы.

19.  Венгерский алгоритм решения задачи о назначениях.

20.  Задача о разбиении на наименьшее число паросочетаний. Теорема Мендельсона-Далмеджа и алгоритм разбиения на наименьшее число паросочетаний.

21.  Задача составления учебного расписания.

22.  Задача коммивояжера. Алгоритмы с гарантированной оценкой точности.

23.  Метод ветвей и границ, схема для задачи коммивояжера.

24.  Моделирование отжига.

9.  Образовательные технологии.

Сочетание традиционных образовательных технологий в форме лекций, компьютерных лабораторных работ и проведение контрольных мероприятий (контрольных работ, промежуточного тестирования, зачёта).

аудиторные занятия:

лекционные и компьютерные лабораторные занятия; на лабораторных занятиях контроль осуществляется при сдаче лабораторного задания в виде программы (на одном из используемых языков программирования) и пояснительной записки к задаче. В течение семестров студенты выполняют задачи, указанные преподавателем к каждому занятию.

активные и интерактивные формы:

компьютерное моделирование и анализ результатов при выполнении лабораторных работ;

внеаудиторные занятия:

выполнение дополнительных заданий разного типа и уровня сложности при выполнении лабораторных работ, подготовка к аудиторным занятиям, изучение отдельных тем и вопросов учебной дисциплины в соответствии с учебно-тематическим планом, составлении конспектов. Подготовка индивидуальных заданий: выполнение самостоятельных и контрольных работ, подготовка ко всем видам контрольных испытаний: текущему контролю успеваемости и промежуточной аттестации; индивидуальные консультации.

10.  Учебно-методическое и информационное обеспечение дисциплины (модуля).

10.1.  Основная литература:

1.  Асанов  оптимизация . -Екатеринбург: УралHАУКА, 1998.

2.  и др. Алгоритмы: построение и анализ - М.: МЦМНО, 2001. 

3.  Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 

10.2.  Дополнительная литература:

1.  Искусство программирования на ЭВМ. М.: Мир, 1978. Т.3: Поиск и сортировка. 

2.  Алгоритмы: построение и анализ. М.: Изд-во «Вильямс», 2005.

3.  . Теория графов. Алгоритмический подход. – М.: Мир, 1978.

11.  Технические средства и материально-техническое обеспечение дисциплины (модуля).

При освоении дисциплины для проведения лекционных занятий нужны учебные аудитории, оснащённые мультимедийным оборудованием, для выполнения лабораторных работ необходимы классы персональных компьютеров с набором базового программного обеспечения разработчика - системы программирования на языках Borland Delphi, С/С++.