Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей))

Рекомендовано МССН

«Информатика»


Программка


Наименование дисциплины: Теория конечных графов


Рекомендуется для направления (ий) подготовки (специальности (ей))

080500 «Бизнес-информатика»

(указываются код и наименования направления (ий)

подготовки (специальности (ей) и/либо профилей (специализаций)

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

(указывается квалификация (степень) выпускника в согласовании с ФГОС)


1. Цели и задачки дисциплины:

Основной целью освоения дисциплины является исследование традиционной теории конечных графов, также применение способов теории конечных графов в прикладных задачках. Курс «Теория конечных Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) графов» носит теоретический и практический нрав.

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

^ 2. Место дисциплины в структуре Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) ООП:

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

Цикл, к которому относится Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) дисциплина: вариативная часть проф цикла Б.3.

Требования к входным познаниям и умениям: нужна математическая подготовка в границах школьной программки.

^ Знать Главные понятия и способы теории множеств.

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


Дисциплины, для которых данная дисциплина является предыдущей: Модели на гиперграфах, Введение в управление инфокоммуникациями, Проектирование корпоративных систем, Прикладные задачки ТМО.


^ 3. Требования к результатам освоения дисциплины:

    Процесс исследования дисциплины «Теория Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) конечных графов» ориентирован на формирование последующих компетенций: ОК: 1, ПК: 19, 20

    (указываются в согласовании с ФГОС ВПО)

В итоге Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) исследования дисциплины «Теория конечных графов» студент должен:

    Знать:

    Уметь:

Обладать:



^ 4. Объем дисциплины и виды учебной работы

Общая трудозатратность дисциплины составляет Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) ____4_______ зачетных единиц.


Вид учебной работы

Всего часов

Семестры







3










^ Аудиторные занятия (всего)

54

54

-

В том числе:







-

Лекции

36

36

-

Практические занятия (ПЗ)

-

-

-

Семинары (С)

-

-

-

Лабораторные работы (ЛР)

18

18

-

^ Самостоятельная работа (всего)

90

90

-

В том числе:

-

-

-

Курсовой проект (работа)

-

-

-

Расчетно-графические работы

-

-

-

Реферат

-

-

-

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

-

-

-

Самостоятельная проработка дополнительного материала

90

90

-

Вид промежной аттестации (зачет, экзамен)




экзамен

-

Общая трудозатратность час


144

144

-

зач. ед.

4

4

-


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

5.1. Содержание разделов дисциплины

№ п/п

Наименование раздела дисциплины

Содержание раздела

1.

Элементы теории графов

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


2.

Методы на графах

Метод Краскала. Метод Прима. Метод Дейкстры. Метод нахождения Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) эйлерова цикла в графе. Метод построения кратчайшего пути от фиксированной верхушки до всех других вершин в направленном графе, случай неотрицательных весов ребер.

3.

Потоки в сетях

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


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

№ п/п

Наименование обеспе-чиваемых (последую-щих) дисциплин

№ № разделов данной дисциплины, нужных для исследования обеспечиваемых (следующих) дисциплин







1

2

3

1.

Модели на гиперграфах

+

+

+

2.

Введение в управление инфокоммуникациями

+

+

+

3.

Моделирование информационных процессов







+

4.

Прикладные задачки ТМО

+




+

5.

Курсовая работа

+

+

+

^ 5.3. Разделы Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) дисциплин и виды занятий

№ п/п

Наименование раздела дисциплины

Лекц.

Практ.

зан.

Лаб.

зан.

Семин

СРС

Все-го

час.

1.

Элементы теории графов

12

0

6

0

30

48

2.

Методы на графах

12

0

6

0

30

48

3.

Потоки в сетях

12

0

6

0

30

48







36




18




90

144


^ 6. Лабораторный практикум

№ п/п

№ раздела дисциплины

Наименование лабораторных работ

Трудо-емкость

(час.)

1.

Элементы теории графов Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей))

Разбор главных понятий и определений на неориентированных и нацеленных графах. Матрицы смежности и матрицы инцидентности для неориентированных и нацеленных графов. Поиск маршрутов, цепей и циклов для графов. Нахождение связных компонент в графе. Метрические Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) свойства графов. Эйлеровы графы. Эйлеровы пути и циклы. Нахождение кратчайших путей в направленном графе

6

2.

Методы на графах

Метод Краскала. Метод Прима. Метод Дейкстры. Метод нахождения эйлерова цикла в графе. Метод построения кратчайшего пути от Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) фиксированной верхушки до всех других вершин в направленном графе, случай неотрицательных весов ребер. Построение матрицы связности (достижимости для графа). Метод Уоршалла-Флойда.

6

3.

Потоки в сетях

Прикладные модели и задачки. Оценка структурных компонент графа Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)). Задачка о наивысшем потоке и о наименьшем разрезе в сети. Наибольший поток в транспортной сети. Задачка на нахождение «узких» мест в сети. Задачка о потоке малой цены.

6










18

^ 7. Практические занятия (семинары) не Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) предусмотрены

8. Примерная тема курсовых проектов (работ)____ не предусмотрены

9. Учебно-методическое и информационное обеспечение дисциплины:

а) основная литература

  1. Гайдамака Ю.В., Зарипова Э.Р., Кокотчикова М.Г., Севастьянов Л.А. «Лекции по дискретной арифметике. Часть II. Комбинаторика Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)). Теория конечных графов». Учебное пособие. // М.: Изд-во РУДН, 2008.

  2. Харари Фрэнк.Теория графов / Харари Фрэнк ; Пер. с англ. В.П.Козырева; Под ред. Г.П.Гаврилова. - 4-е изд. - М. : URSS : Либроком, 2009. - 296 с Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)).

  3. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. «Лекции по теории графов». Изд.2, испр., Изд-во Либроком, 2009.

  4. Муромцев В.В. «Некоторые методы на графах». Учебное пособие, Белгород Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)): Изд. БелГТАСМ, 2000.- 64 с.


б) дополнительная литература

  1. Зыков А. А. Базы теории графов. — М.: «Вузовская книга», 2004. — С. 664

  2. Кирсанов М.Н. «Графы в MAPLE» Пособие по дискретной арифметике для студентов институтов. М: Физматлит, 2007.

в) программное обеспечение Maple Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)), MatLab, SciLab, MathCad, Mathematica

г) базы данных, информационно-справочные и поисковые системы____________________ http://vuz.exponenta.ru/PDF/book/GrMaple.pdf

^ 10. Материально-техническое обеспечение дисциплины: Москва, ул. Орджоникидзе, д.3, корп. 1. учебные лаборатории кафедры Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) систем телекоммуникаций:

^ 11. Методические советы по организации исследования дисциплины:

На освоение дисциплины отводится 1 семестр. В качестве итогового контроля познаний предусмотрен экзамен.

Для текущего контроля Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) успеваемости и промежной аттестации студентов рекомендуется использовать вопросы и задания подобные перечисленным ниже:

Типовые задачки для промежного контроля познаний:

  1. Отыскать эксцентриситет, поперечник и радиус графа.

  2. Составить матрицу смежности и Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) матрицу инцидентности для графа.

  3. Выстроить малое покрывающее дерево для графа по методу Краскала.

  4. Задачка на применение метода Дейкстры.

  5. Задачка на применение метода Уоршалла-Флойда.

  6. Поиск эйлерова цикла в графе.

Типовые вопросы для Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) итогового контроля познаний:

  1. Неориентированный граф. Определение. Смежность ребер и вершин. Инцидентность. Изоморфизм.

  2. Аксиома о четности вершин в конечном графе. Определения полного графа и подграфа.

  3. Определение маошрута, замкнутого маршрута. Определение цепи и обычной Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) цепи. Определение дерева. Аксиома о количестве ребер в дереве с n верхушками.

  4. Связный неориентированный граф. Аксиома о связности графа.

  5. Определение орграфа. Смежность в орграфе. Положительная и отрицательная инцидентность в орграфе. Положительная и отрицательная степени Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) вершин в орграфе.

  6. Определение пустого графа. Определение изолированной верхушки. Определение ормаршрута и замкнутого ормаршрута. Определение пути и обычного пути. Определение контура.

  7. Определение сильносвязного графа. Определение орграфа. Определение симметричного и смешанного графов Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)).

  8. Определение эксцентриситета, поперечника и радиуса в графе. Центр графа.

  9. Матрица смежности и инцидентности для неорграфа. Перечень смежности. Матрица весов.

  10. Матрица смежности и инцидентности для орграфа.

  11. Аксиома о числе ормаршрутов длины n меж Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) 2-мя верхушками орграфа.

  12. Построение малого покрывающего дерева по методу Краскала. Метод.

  13. Построение наибольшего покрывающего дерева по методу Краскала. Метод.

  14. Определение псевдографа и мультиграфа. Определение плоского графа.

  15. Построение малого покрывающего дерева по методу Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) Прима. Метод.

  16. Построение наибольшего покрывающего дерева по методу Прима. Метод

  17. Поиск маршрута и меньшей длины по методу Дейкстры. Метод.

  18. Задачка о кенигсбергских мостах. Определение эйлерова цикла и эйлерова графа. Определение эйлерова пути Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) и метод получения эйлерова пути из эйлерова цикла.

  19. Аксиома о четности степеней в эйлеровом графе.

  20. Поиск эйлерова цикла в графе. Метод.

  21. Поиск малых расстояний меж всеми парами вершин по методу Уоршалла-Флойда Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)). Метод.

  22. Сопоставление алгоритмов Дейкстры и Уоршалла-Флойда. Сходства и различия алгоритмов.

  23. Задачка построения транзитивного замыкания бинарного дела. Определение бинарного дела. Определение транзитивного замыкания. Матрица достижимости (связности).

  24. Построение транзитивного замыкания для графа. Метод Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)).

  25. Особенности i-той строчки и i-столбца для Метода Уоршалла-Флойда. Подтверждение.

  26. Особенности i-той строчки и i-столбца для Метода поиска транзитивного замыкания. Подтверждение.

  27. Определение потока в графе. Условия существования потока в Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) графе. Правила расскрашивания дуг графа для поиска увеличивающей цепи. Определение прямых и оборотных дуг.

  28. Повышение потока в графе по увеличивающей цепи. Метод.

  29. Поиск наибольшего потока в графе. Метод.

  30. Поиск потока малой цены Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)). Метод.

  31. Поиск рационального маршрута почтальона для орграфа. Метод.

  32. Определение гамильтонова цикла и гамильтоновой цепи.

  33. Гамильтоновы и эйлеровы графы. Сходства и различия гамильтонова и эйлерова циклов.

  34. Три достаточных аспекта существования гамильтоновых циклов в Программа наименование дисциплины: Теория конечных графов Рекомендуется для направления (ий) подготовки (специальности (ей)) неорграфе.

  35. Поиск гамильтонова цикла в орграфе. Метод с упрощением

Разработчики:

Ст. педагог каф. систем телекоммуникаций Э.Р. Зарипова

Должность, заглавие кафедры, инициалы, фамилия

Заведующий кафедрой систем телекоммуникаций К. Е. Самуйлов

заглавие кафедры, инициалы, фамилия

programma-mezhdunarodnogo-festivalya-gorodov-pobratimov-permi-mi-vmeste-17-sentyabrya-vtornik.html
programma-mezhdunarodnogo-foruma-starshee-pokolenie-27-marta.html
programma-mezhdunarodnogo-kinofestivalya-turisticheskih-filmov-zolotaya-vershina.html