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

ТЕОРИЯ ГРАФОВ; ЕН. Ф.01.03 (Название дисциплины; индекс(ы) дисциплины в учебном(ых) плане(ах) для которых читается дисциплина. Для УМКД, предназначенных одновременно для нескольких направлений или специальностей указываются все их коды.)

Кафедра ЭИУ2-КФ «Компьютерные системы и сети» (сокращенное название обеспечивающей кафедры)

Доцент, к. т.н. , (Должность, ученая степень, Ф. И.О. разработчиков УМК, контактные телефоны, адрес электронной почты разработчика - при ее наличии)

Виды и объем занятий по дисциплине Виды занятий Объём занятий, час Всего 5 семестр Лекции 17 17 Семинары 17 17 Лабораторные работы - - Самостоятельная работа 2 2 Домашние задания 2 2 Подготовка к занятиям - - Курсовая работа - - Итого: 36 36 Проверка знаний: зачёт (Общая трудоемкость дисциплины в часах по семестрам, с перечислением всех видов занятий и соответствующего количества часов по учебному плану направления или специальности; форма отчетности по семестрам - экзамен, зачет, дифф. зачет)

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

Место дисциплины в образовательной программе 1. Предшествующие дисциплины (Приводится перечень дисциплин с указанием разделов (тем), усвоение которых студентами необходимо для изучения данной дисциплины.) Математика § Математический анализ § Аналитическая геометрия § Дискретная математика § Вычислительная математика Алгоритмические языки и программирование Теория автоматов 2. Является основой для дисциплин: (использование дисциплины в последующем образовательном процессе) Организация информационных систем. Организация ЭВМ и систем. Организация и планирование производства. Сети ЭВМ и телекоммуникации. Системы искусственного интеллекта. Моделирование. Теория информационных систем общего назначения.

Структура и ключевые понятия дисциплины: 1. Задачи паросочетания в графах (4 час.): основные понятия; теорема холла; паросочетание в двудольных графах; алгоритм нахождения максимального паросочетания в двудольном графе; паросочетание в произвольных графах; алгоритм нахождения максимального паросочетания в произвольном графе. 2. Задачи устойчивости и покрытия (8 час.): устойчивость, покрытия; выделение пустых подграфов; закон поглощения; нахождение всех полных подграфов; плотность графа; нахождение вершинного (реберного) числа внешней устойчивости. 3. Задачи теории графов (14 час.): раскраска вершин и ребер графа; основные понятия; теорема кёнига; хроматическое число; хроматический класс; свойство реберности; точный алгоритм раскраски вершин (ребер) графа; приближенный алгоритм раскраски вершин (ребер) графа; дифференцирование графов и мографов; матрица инцидентности; частотная матрица отношений; производная графа по событию. 4. Прикладная теория алгоритмов (12 час.): прикладная теория алгоритмов; задачи синтеза и анализа дискретных систем; синтаксическое эквивалентирование; эвристическое эквивалентирование; семантическое эквивалентирование; рефлексивная и проективная семантики; конструктивная семантика; характеризационный анализ; отношение подчинение; запрещенные фигуры; матроиды. (основные модули дисциплины и ее ключевые понятия в соответствии с образовательным стандартом)