УТВЕРЖДАЮ. Алгоритмы на графах. 090401-ПОВ-з20.plx. Программное обеспечение вычислительной техники. 09.04.01 Информатика и вычислительная техника. Программное обеспечение вычислительной техники и автоматизированных систем. магистр. заочная. 216 часов/6 з.

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

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

ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ (НПИ) ИМЕНИ М. И. ПЛАТОВА»

УТВЕРЖДАЮ

Проректор по ОД ЮРГПУ (НПИ)

______________С. Н. Чеботарев

«____» ____________ 2020 г.

Б1. О. 02

Алгоритмы на графах

рабочая программа дисциплины (модуля)

Имя плана:

090401-ПОВ-з20. plx

Кафедра:

Программное обеспечение вычислительной техники

Специальность/н аправление подготовки:

09. 04. 01 Информатика и вычислительная техника

Специализация/ направленность (профиль):

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

Квалификация:

магистр

Форма обучения:

заочная

Год набора:

Общая трудоемкость:

216 часов/6 з. е.

Новочеркасск, 2020 г.

УП: 090401-ПОВ-з20. plx

докт. экон. наук, проф. Стрельцова Е. Д. _________________

Рабочая программа дисциплины (модуля) Алгоритмы на графах

разработана в соответствии с ФГОС ВО: Федеральный государственный образовательный стандарт высшего образования - магистратура по направлению подготовки 09. 04. 01 Информатика и вычислительная техника (приказ Минобрнауки России от 19. 09. 2017 г. № 918)

составлена на основании учебного плана, одобренного ученым советом факультета/института/института(филиала): Факультет информационных технологий и управления

23 июня 2020 г. протокол № 9.

Рабочая программа обсуждена на заседании кафедры

Программное обеспечение вычислительной техники

Протокол от __ __________ 2020 г. № __

Зав. кафедрой Гринченков Д. В. ___________________

УП: 090401-ПОВ-з20. plx

1. ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ (МОДУЛЯ)

Целью дисциплины «Алгоритмы на графах» является изучение магистрантами типовых задач, в которых предметная область имеет представление в форме графа, а также алгоритмов решения таких задач. В результате изучения дисциплины студент должен: знать области использования методов теории графов, понятия и теоретические основы теории графов, классические постановки задач теории графов, а также алгоритмы их решения; уметь реализовывать алгоритмы решения задач теории графов на различных языках программирования с использованием эффективных структур данных; владеть методами решения задач на графах, методами оценивания вычислительной сложности алгоритмов.

2. МЕСТО ДИСЦИПЛИНЫ (МОДУЛЯ) В СТРУКТУРЕ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ И ОБЪЕМ С РАСПРЕДЕЛЕНИЕМ ПО КУРСАМ

Цикл (раздел) ОП:

Б1. О

Связь с последующими дисциплинами (модулями), практиками, ВКР:

Технологическая (проектно-технологическая) практика

ОПК-8. 1, ОПК-8. 2, ОПК-8. 3, ОПК-7. 1, ОПК-7. 2, ОПК-7. 3, ОПК-6. 1, ОПК-6. 2, ОПК-6. 3, ОПК-5. 1, ОПК-5. 2, ОПК-5. 3, ОПК-4. 1, ОПК-4. 2, ОПК-4. 3, ОПК-3. 1, ОПК-3. 2, ОПК-3. 3, ОПК-2. 1, ОПК-2. 2, ОПК-2. 3, ОПК-1. 1, ОПК-1. 2, ОПК-1. 3, УК- 6. 1, УК-6. 2, УК-6. 3, УК-5. 1, УК-5. 2, УК- 5. 3, УК-4. 1, УК-4. 2, УК-4. 3, УК-3. 1, УК- 3. 2, УК-3. 3, УК-2. 1, УК-2. 2, УК-2. 3, УК- 1. 1, УК-1. 2, УК-1. 3

Сетевые технологии и промышленные протоколы

ОПК-1. 1, ОПК-1. 2, ОПК-1. 3, ОПК-6. 1, ОПК-6. 2, ОПК-6. 3, ОПК-7. 1, ОПК-7. 2, ОПК-7. 3

2. 3 Распределение часов дисциплины

Распределение часов дисциплины по курсам

Курс

Итого

Вид занятий

УП

Лекции

Лабораторные

Иная контактная работа

2, 95

Итого ауд.

Кoнтактная рабoта

10, 95

Сам. работа

196, 4

Часы на контроль

8, 65

Итого

2. 4. Виды контроля:

Экзамен

курс

3. ФОРМИРУЕМЫЕ КОМПЕТЕНЦИИ И ИНДИКАТОРЫ ИХ ДОСТИЖЕНИЯ

ОПК-2: Способен разрабатывать оригинальные алгоритмы и программные средства, в том числе с использованием современных интеллектуальных технологий, для решения профессиональных задач;

ОПК-2. 1: Знать: современные информационно-коммуникационные и интеллектуальные технологии, инструментальные среды, программно-технические платформы для решения профессиональных задач.

ОПК-2. 2: Уметь: обосновывать выбор современных информационно-коммуникационных и интеллектуальных технологий, разрабатывать оригинальные программные средства для решения профессиональных задач.

ОПК-2. 3: Владеть: методами разработки оригинальных программных средств, в том числе с использованием современных информационно-коммуникационных и интеллектуальных технологий, для решения профессиональных задач.

ОПК-6: Способен разрабатывать компоненты программно-аппаратных комплексов обработки информации и автоматизированного проектирования;

ОПК-6. 1: Знать: аппаратные средства и платформы инфраструктуры информационных технологий, виды, назначение, архитектуру, методы разработки и администрирования программно-аппаратных комплексов объекта профессиональной деятельности.

ОПК-6. 2: Уметь: анализировать техническое задание, разрабатывать и оптимизировать программный код для решения задач обработки информации и автоматизированного проектирования.

УП: 090401-ПОВ-з20. plx

стр. 4

ОПК-6. 3: Владеть: методами составления технической документации по использованию и настройке компонентов программно-аппаратного комплекса.

4. СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)

Наименование разделов и

тем /вид занятия/

Литература

Раздел 1. Введение в дисциплину. Основные понятия теории графов.

Введение. Цели и задачи дисциплины. Основные понятия и терминология теории графов. Числовые (метрические) характеристики графов. Алгоритм подсчёта степеней вершин графа. Структурные и комбинаторные свойства графов. Операции над графами. Способы представления графов в памяти компьютера. Списки смежности и матрица смежности. /Лек/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Исследование числовых характеристик и структурных свойств графов. /Лаб/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Самостоятельное изучение лекционного материала /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Дополнительные вопросы для самостоятельного изучения:

Применение графов для задач программирования, графы как модели программ, процессов, информационных структур. Граф, дополнительный к заданному графу. Самодополнительный граф. Алгоритм построения графа, дополнительного к заданному графу. Рёберный (линейный) граф. Алгоритм построения рёберного графа. Плоские и планарные графы. Задача о плоской укладке. Гамма -алгоритм. Алгоритм перечисления всех граней плоского графа. Алгоритм построения графа, двойственного к заданному плоскому графу. Изоморфизм графов. Алгоритм проверки изоморфности двух графов. Гомеоморфизм графов. Полиэдральные графы. Реализация графа в виде класса на языке С++. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 2. Подграфы. Покрытия и упаковки.

УП: 090401-ПОВ-з20. plx

стр. 5

Вершинные покрытия графа; минимальное и наименьшее вершинные покрытия. Алгоритмы решения задачи о наименьшем вершинном покрытии; эвристический «жадный» алгоритм. Независимые подмножества вершин; максимальное независимое множество вершин. Вершинное число независимости (число внутренней устойчивости) графа. Рёберные покрытия графа; минимальное и наименьшее рёберные покрытия. Независимые подмножества рёбер (паросочетания). Максимальное независимое множество рёбер и рёберное число независимости. Максимальное и совершенное паросочетания графа. Доминирующие множества вершин; минимальное и наименьшее доминирующие множества вершин. Число вершинного доминирования. Доминирующие множества рёбер; минимальное и наименьшее доминирующие множества рёбер. Число рёберного доминирования. Максимальные подмножества попарно смежных вершин; максимальные и наибольшие клики. Связь между понятиями «максимальное независимое множество вершин» и «максимальная клика». Связь между максимальным числом попарно смежных рёбер и максимальной кликой. /Лек/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Алгоритмы построения подграфов с заданными свойствами. Алгоритмы раскраски графов. /Лаб/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Самостоятельное изучение лекционного материала /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Дополнительные вопросы для самостоятельного изучения:

Точный (переборный) алгоритм решения задачи о наименьшем вершинном покрытии. Алгоритм построения наименьшего рёберного покрытия графа. Алгоритмы построения максимального паросочетания графа: эвристический «жадный» алгоритм; алгоритм Куна для двудольного графа; алгоритм Эдмондса, алгоритм Хопкрофта – Карпа. Эвристический «жадный» алгоритм построения наименьшего доминирующего множества вершин графа. Точный (переборный) алгоритм построения наименьшего доминирующего множества рёбер графа. Эвристический «жадный» алгоритм построения наименьшего доминирующего множества рёбер графа. Алгоритм Брона – Кербоша построения всех максимальных клик графа. Раскраски графа. Вершинная раскраска; минимальная вершинная раскраска; хроматическое число графа. «Жадный» алгоритм вершинной раскраски графа. Рёберная раскраска графа; минимальная рёберная раскраска; хроматический класс (индекс) графа. «Жадный» алгоритм рёберной раскраски графа.

/Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 3. Маршруты в графах.

УП: 090401-ПОВ-з20. plx

стр. 6

Основные понятия о маршрутах. Базовые алгоритмы обхода вершин графа. Обход вершин графа методом поиска в глубину (рекурсивная и итеративная реализации). Обход вершин графа методом поиска в ширину. Расстояние между вершинами графа, эксцентриситет вершины, диаметр, радиус, центр и периферия связного графа. Обхват и окружение графа. Эйлеровы цепи, эйлеровы циклы и эйлеровы графы. Задача о домино. Гамильтоновы пути, гамильтоновы циклы и гамильтоновы графы. Задача коммивояжёра. /Лек/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Маршруты в графах. /Лаб/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Самостоятельное изучение лекционного материала. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Дополнительные вопросы для самостоятельного изучения:

Алгоритм построения связных компонент графа. Проверка связного графа на двудольность. Алгоритм поиска всех простых циклов в графе. Алгоритм нахождения эйлеровой цепи в графе. Алгоритм нахождения гамильтонова цикла в графе. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 4. Связность графов.

Связные графы; компонента связности; достижимость вершин. Понятия вершинной и рёберной связностей. Вершинная связность. Вершинный разрез (вершинное разделяющее множество). Наименьшее вершинное разделяющее множество; Число вершинной связности. k-связный граф. Рёберная связность. Рёберное разделяющее множество. Наименьшее рёберное разделяющее множество. Число рёберной связности. Рёберно k- связный граф. Двусвязные (неразделимые) графы. Блоки. Точки сочленения (разделяющие / разрезающие вершины, шарниры) графа. Мосты (разрезающие ребра) графа. /Лек/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Связность графов. Поиск разделяющих вершин, мостов и блоков графа. /Лаб/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Самостоятельное изучение лекционного материала. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Дополнительные вопросы для самостоятельного изучения:

Алгоритм поиска разделяющих вершин, мостов и блоков графа. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 5. Ориентированные графы.

Основные понятия и терминология. Маршруты в орграфах. Турниры. Достижимость вершин орграфа. Обратный орграф. Сильно связные, односторонне связные и слабо связные орграфы. Компоненты сильной связности орграфа. Конденсация орграфа. Понятие метаграфа. /Лек/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

УП: 090401-ПОВ-з20. plx

стр. 7

Связность орграфов. Поиск всех сильных компонент орграфа. /Лаб/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Самостоятельное изучение лекционного материала. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Дополнительные вопросы для самостоятельного изучения:

Построение матрицы достижимостей орграфа с помощью алгоритма Флойда-Уоршелла. Алгоритм определения всех сильных компонент орграфа (алгоритм Косарайю-Шарира). /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 6. Ациклические графы.

Ациклические графы. Деревья. Остовное дерево и остовный лес графа и алгоритм их построения. Ациклические орграфы (Directed Acyclic Graph – DAG). Алгоритм проверки орграфа на ацикличность. Топологические упорядочения DAG. Алгоритмы топологической сортировки. Сети зависимостей (Dependency network). /Лек/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Построение остовного леса заданного графа. Получение всех топологических упорядочений заданного DAG. /Лаб/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Самостоятельное изучение лекционного материала. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Дополнительные вопросы для самостоятельного изучения:

Получение всех топологических упорядочений заданного DAG. Проверка заданной последовательности вершин DAG на топологическую упорядоченность. Представление DAG в ярусно-параллельной (уровневой) форме. Алгоритм Демукрона. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 7. Взвешенные графы.

Минимальное остовное дерево взвешенного графа (minimum spanning tree – MST). Построение MST с помощью обобщенного алгоритма обхода графа (алгоритма поиска с кратчайшим выбором (shortest- first search – SFS)). Кратчайшие пути в графах и орграфах. Дерево кратчайших путей (shortest-paths tree – SPT). Различия между SPT и MST. /Лек/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Построение минимального остовного дерева взвешенного графа. Построение дерева кратчайших путей взвешенного графа. /Лаб/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Самостоятельное изучение лекционного материала. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

УП: 090401-ПОВ-з20. plx

стр. 8

Дополнительные вопросы для самостоятельного изучения:

Классические алгоритмы построения MST: обобщенный алгоритм, алгоритм Борувки, алгоритм Краскала, алгоритм Ярника (Прима, Дейкстры)). Построение SPT с помощью унивесального релаксационного алгоритма Форда. Варианты реализации алгоритма Форда при использовании в качестве «мешка» стека, очереди и приоритетной очереди. Алгоритм Дейкстры. Алгоритм Беллмана-Шимбела. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 8. Потоки в сетях.

Потоки в сетях. Потоковые сети. Определение потока. Разрезы. Задача о максимальном потоке. Алгоритм Форда–Фалкерсона. /Лек/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Определение максимального потока сети. /Лаб/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Самостоятельное изучение лекционного материала. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 9. Комбинаторная оптимизация в задачах на графах.

Дополнительные вопросы для самостоятельного изучения:

Комбинаторная оптимизация в задачах на графах. Основные комбинаторные соотношения для задач на графах. Оценка мощности множества допустимых решений. Алгоритмы перечисления (перебора) решений. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 10. Применение эволюционных алгоритмов к решению задач на графах.

Дополнительные вопросы для самостоятельного изучения:

Применение эволюционных алгоритмов к решению задач на графах. Общие сведения об эволюционных алгоритмах. Особенности кодирования решений в задачах на графах. Генетический алгоритм и генетические операторы для задач на графах. /Ср/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

Раздел 11. Иная контактная работа

Групповые консультации с преподавателем во время лабораторно-экзаменационной сессии. /ИКР/

Групповая консультация перед экзаменом. /ИКР/

Сдача экзамена. /ИКР/

Раздел 12. Контроль

Самостоятельная работа по подготовке к экзамену во время лабораторно-экзаменационной сессии. /Экзамен/

Л1. 1 Л1. 2 Л1. 3Л2. 1 Л2. 2Л3. 1 Л3. 2 Л3. 3 Л3. 4

5. ФОНД ОЦЕНОЧНЫХ СРЕДСТВ

5. 1. Контрольные вопросы для текущего контроля успеваемости

Не предусмотрены.

5. 2. Контрольные вопросы для промежуточной аттестации

Тема 1

1. Для произвольной вершины заданного графа построить её замкнутую окрестность.

2. Пояснить понятия: «простой граф», «мультиграф», «псевдограф» и привести примеры.

3. Пояснить понятия: «пустой (нулевой) граф», «тривиальный граф», «полный граф» и привести их обозначения и примеры.

4. Пояснить понятия: «граф-цикл», «граф-цепь», «граф-колесо» и привести их обозначения и примеры.

5. Пояснить понятия: «двудольный граф (биграф)», «полный двудольный граф», «звезда», «клешня», «дерево» и привести их обозначения и примеры.

6. Пояснить понятия: «дополнительный граф», «самодополнительный граф» и привести их примеры.

7. Что такое рёберный (линейный) граф. Для заданного графа построить его рёберный граф.

8. Что такое «регулярный (однородный) граф»? Привести примеры кубических графов и графов четвёртой степени.

9. Пояснить понятия: «плоский граф», «планарный граф» и привести примеры. Привести примеры непланарных графов. Формулировка теоремы Понтрягина-Куратовского.

10. Пояснить понятие «грань» плоского графа. Формула Эйлера. Граф, двойственный к плоскому графу. Самодвойственные плоские графы. Привести примеры.

11. Пояснить понятие изоморфности графов. Привести примеры изоморфных графов.

12. В чём смысл операций «подразбиение (подразделение) ребра» и «устранение подразбиения»? Привести примеры.

13. В чём смысл операций «слияние (отождествление) вершин» и «стягивание ребра»? Привести примеры.

14. Пояснить понятие гомеоморфности графов. Привести примеры гомеоморфных графов.

15. Способы представления графов в памяти компьютера.

Тема 2

16. Перечислите четыре задачи о минимальных покрытиях графа.

17. Перечислите четыре задачи об упаковках графа.

18. Привести краткое изложение эвристического «жадного» алгоритма построения наименьшего вершинного покрытия.

19. Как связаны алгоритм построения максимального паросочетания и алгоритм построения наименьшего рёберного покрытия графа?

20. Как связаны «рёберное число независимости», «число рёберного покрытия» и «вершинное число независимости»? Привести пример.

21. Привести краткое изложение эвристического «жадного» алгоритма построения максимального паросочетания графа.

22. Основная идея алгоритма Куна (построение максимального паросочетания в двудольном графе).

23. Основная идея алгоритма Эдмондса (построение максимального паросочетания в произвольном графе).

24. Основная идея алгоритма Хопкрофта – Карпа (построение максимального паросочетания в двудольном графе).

25. Привести краткое изложение эвристического «жадного» алгоритма построения наименьшего доминирующего множества вершин графа.

26. Привести краткое изложение эвристического «жадного» алгоритма построения наименьшего доминирующего множества рёбер графа.

27. Основная идея алгоритма Брона – Кербоша (построение всех максимальных клик графа).

28. Как связаны «максимальное подмножество попарно смежных рёбер» и «максимальная клика»? Привести пример.

29. Поясните термины «k-раскраска графа», «k-цветный граф» и «k-хроматический граф». Привести пример.

30. Привести краткое изложение эвристического «жадного» алгоритма вершинной раскраски графа.

31. Пояснить связь между хроматическим классом (индексом) графа и максимальной степенью графа. Привести пример.

32. Формулировка теоремы Кёнига.

33. Формулировка теоремы Визинга и следствия из этой теоремы.

34. Привести краткое изложение эвристического «жадного» алгоритма рёберной раскраски графа.

Тема 3

35. Основная идея DFS-стратегии (стратегии обхода вершин графа методом поиска в глубину). Привести пример и построить для него дерево поиска в глубину.

36. Основная идея рекурсивного алгоритма поиска в глубину.

37. Основная идея итеративного алгоритма поиска в глубину с использованием стека.

38. Основная идея итеративного алгоритма поиска в глубину без использованием стека.

39. Основная идея BFS-стратегии (стратегии обхода вершин графа методом поиска в ширину). Привести пример и построить для него дерево поиска в ширину.

40. Основная идея алгоритма проверки связного графа на двудольность с использованием BFS-стратегии. Привести пример.

41. Пояснить понятие «граф без треугольников». Привести пример.

42. Основная идея алгоритма поиска всех простых циклов в графе.

43. Пояснить понятия: «эйлеров граф» и «полуэйлеров граф». Привести примеры.

44. Основная идея алгоритма нахождения эйлеровой цепи в графе.

45. Пояснить понятие «гамильтонов граф». Привести примеры.

46. Основная идея рекурсивного алгоритма полного перебора с возвратами для нахождения гамильтонова цикла в графе.

47. Задача коммивояжёра и гамильтоновы циклы в графе.

УП: 090401-ПОВ-з20. plx

Тема 4

48. Пояснить понятие «вершинно k-связный (или просто k-связный)» граф. Привести примеры односвязных и двусвязных графов.

49. Пояснить понятие «рёберно k-связный (или просто k-связный)» граф. Привести примеры рёберно односвязных и рёберно двусвязных графов.

50. Основная идея алгоритма поиска разделяющих вершин, мостов и блоков графа.

Тема 5

51. Пояснить понятие «турнир». Привести все турниры для орграфа из 3 вершин.

52. Пояснить понятие «достижимость вершин» в орграфе. Что такое матрица достижимостей? Привести пример.

53. Построение матрицы достижимостей с помощью алгоритма Флойда-Уоршелла. Привести пример.

54. Матричный способ определения сильных компонент орграфа. Привести пример.

55. Основная идея алгоритма Косарайю-Шарира (определения всех сильных компонент орграфа). Привести пример.

Тема 6

56. Основная идея алгоритмов построения остовного дерева графа. Привести пример.

57. Основная идея алгоритма проверки орграфа на ацикличность.

58. Основная идея алгоритма получения всех топологических упорядочений заданного ациклического орграфа.

59. Основная идея алгоритма Демукрона для представления заданного ациклического орграфа в ярусно-параллельной (уровневой) форме.

Тема 7

60. Задача построения минимального остовного дерева. Основная идея её решения с помощью обобщенного алгоритма обхода графа.

61. Основная идея алгоритма Борувки для построения минимального остовного дерева. Привести пример.

62. Основная идея алгоритма Краскала для построения минимального остовного дерева. Привести пример.

63. Основная идея алгоритма Ярника (Прима, Дейкстры) для построения минимального остовного дерева. Привести пример.

64. В чём различие между деревьями кратчайших путей и минимальными остовными деревьями? Привести пример.

65. Основная идея универсального релаксационного алгоритма Форда (построение дерева кратчайших путей). Привести пример.

66. Основная идея алгоритма Дейкстры (построение дерева кратчайших путей). Привести пример.

67. Основная идея алгоритма Беллмана-Шимбела (построение дерева кратчайших путей). Привести пример.

Тема 8

68. Основная идея алгоритма Форда–Фалкерсона (определение максимального потока сети). Привести пример.

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

5. 3. Темы и вопросы для оценивания плановых работ

Учебным планом не предусмотрены

6. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)

6. 1. Рекомендуемая литература

Гаврилов Г. П., Сапоженко А. А.. Задачи и упражнения по дискретной математике: учебное пособие]. - Москва: Физматлит, 2005. - 416 с.

Князьков В. С., Волченская Т. В.. Введение в теорию графов [Электронный ресурс]:. - Москва: Интернет- Университет Информационных Технологий (ИНТУИТ), 2008. - 69 с. – Режим доступа: http: //biblioclub. ru/index. php? page=book& id=234135

Дехтярь М. И.. Основы дискретной математики [Электронный ресурс]: курс лекций. - Москва: Национальный Открытый Университет «ИНТУИТ», 2016. - 184 с. – Режим доступа: http: //biblioclub. ru/index. php? page=book& id=428981

Таланов А. В., Алексеев В. Е.. Графы и алгоритмы [Электронный ресурс]:. - Москва: Национальный Открытый Университет «ИНТУИТ», 2016. - 154 с. – Режим доступа: http: //biblioclub. ru/index. php? page=book& id=428827

Костюкова Н. И.. Комбинаторные алгоритмы для программистов [Электронный ресурс]:. - Москва: Национальный Открытый Университет «ИНТУИТ», 2016. - 217 с. – Режим доступа: http: //biblioclub. ru/index. php? page=book& id=429067

Костюкова Н.. Графы и их применение [Электронный ресурс]: курс лекций. - Москва: Национальный Открытый Университет «ИНТУИТ», 2016. - 148 с. – Режим доступа: http: //biblioclub. ru/index. php? page=book& id=429066

Быкова В. В.. Комбинаторные алгоритмы: множества, графы, коды [Электронный ресурс]: учебное пособие. - Красноярск: Сибирский федеральный университет (СФУ), 2015. - 152 с. – Режим доступа: http: //biblioclub. ru/index. php? page=book& id=435666

Седжвик Р.. Алгоритмы на С++ [Электронный ресурс]:. - Москва: Национальный Открытый Университет «ИНТУИТ», 2016. - 1773 с. – Режим доступа: http: //biblioclub. ru/index. php? page=book& id=429164

УП: 090401-ПОВ-з20. plx

Асанов М. О., Баранский В. А.. Дискретная математика: графы, матроиды, алгоритмы [Электронный ресурс]:. - Санкт-Петербург: Лань, 2010. - 368 с. – Режим доступа: https: //e. lanbook. com/books/element. php? pl1_cid=25& pl1_id=536

6. 3. Лицензионное и свободно распространяемое программное обеспечение в том числе отечественного производства

DevC++

Microsoft Visual Studio 2015 Professional

Microsoft Office 2010, 2013, 2016 Professional

Microsoft Windows 7, Microsoft Windows 8, Microsoft Windows 10

6. 4. Перечень профессиональных баз данных и информационных справочных систем

Электронно-библиотечная система " Лань"

Электронно-библиотечная система " Университетская библиотека ONLINE"

Научно-техническая библиотека ЮРГПУ (НПИ)

Научная электронная библиотека " eLibrary"

7. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)

Аудитория 102ЛК - Учебная аудитория для занятий лекционного типа, семинарского типа, помещение для самостоятельной работы обучающихся, курсового проектирования (выполнения курсовых работ), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, лаборатория: Специализированная мебель: Стол – 13; стул - 25; Доска-1.; ПК - 7 шт.;

© helpiks.su При использовании или копировании материалов прямая ссылка на сайт обязательна.