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

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. Задача о максимальном потоке в сети.

Основные понятия и результаты. Разрез в сети, пропускная способность разреза, f - дополняющая цепь, теорема Форда – Фалкерсона. Алгоритм Форда – Фалкерсона.

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

Паросочетания в графах. Алгоритм Хопкрофта - Карпа. Задача о полном паросочетании. Алгоритм Куна.

Тема 3.3. Гамильтоновы циклы.

Гамильтонов цикл наименьшего веса. Задача коммивояжёра. Алгоритм решения задачи коммивояжёра с гарантированной оценкой точности. Решение задачи коммивояжёра методом ветвей и границ.

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

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

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

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

Модуль 1

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

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

Тема 1.2. Поиск в графах.

Поиск в ширину. Деревья поиска в ширину. Поиск в глубину.

Модуль 2

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

Минимальный покрывающий остов. Алгоритм Прима. Алгоритм Краскала.

Тема 2.2. Кратчайшие пути из одной вершины.

Дерево кратчайших расстояний. Релаксация. Случай неотрицательных весов. Алгоритм Дейкстры.

Тема 2.3. Кратчайшие пути для всех пар вершин.

Задача построения матрицы кратчайших расстояний. Алгоритм Флойда-Уоршалла.

Модуль 3

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

Основные понятия и результаты. Разрез в сети, пропускная способность разреза, f - дополняющая цепь, теорема Форда – Фалкерсона. Алгоритм Форда – Фалкерсона.

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

Паросочетания в графах. Алгоритм Хопкрофта - Карпа. Задача о полном паросочетании. Алгоритм Куна.

Тема 3.3. Гамильтоновы циклы.

Гамильтонов цикл наименьшего веса. Задача коммивояжёра. Алгоритм решения задачи коммивояжёра с гарантированной оценкой точности. Решение задачи коммивояжёра методом ветвей и границ.

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

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

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

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

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. Гамильтоновы пути и циклы. Алгоритм нахождения всех гамильтоновых циклов в графе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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