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

МИНИСТЕРСТВО образования Тверской области
гОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ уЧРЕЖДЕНИЕ «осташковский КОЛЛЕДЖ»




«СОГЛАСОВАНО» «утверждаю»
Директор филиала ООО «СИБОСС Зам.директора по УР ГБПОУ
Девелопмент интернейшнл» «Осташковский колледж»
В Тверской области
__________________ Д.Б. Цветков _________________Е.А. Потоцкая

«31» августа 2015 г. «31» августа 2015 г.









ПРОГРАММа УЧЕБНОЙ ДИСЦИПЛИНЫ

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
















2015
Программа учебной дисциплины разработана на основе Федеральных государственных образовательных стандартов (далее – ФГОС) по профессиям среднего профессионального образования (далее СПО) 09.02.03 «Программирование в компьютерных сетях»

Организация-разработчик: ГБПОУ «Осташковский колледж»

Разработчики:
Белова М.В., преподаватель ГБПОУ «Осташковский колледж»


Рекомендована Предметной цикловой методической комиссией

Протокол заседания предметной цикловой методической комиссии
№1 от «31» августа 2015 г.

Рекомендована Экспертным советом по профессиональному образованию Федерального государственного учреждения Федерального института развития образования (ФГУ ФИРО)
Заключение Экспертного совета № ____ от «___» ____________ 201 г.


© ГБПОУ «Осташковский колледж»
© Белова М.В. преподаватель ГБПОУ «Осташковский колледж»



СОДЕРЖАНИЕ

13 TOC \o "1-3" \h \z \u 1413 LINK \l "_Toc534482273" 141. ПАСПОРТ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ 13 PAGEREF _Toc534482273 \h 1441515
13 LINK \l "_Toc534482274" 141.1. Область применения программы. 13 PAGEREF _Toc534482274 \h 1441515
13 LINK \l "_Toc534482275" 141.2. Место дисциплины в структуре основной профессиональной образовательной программы: 13 PAGEREF _Toc534482275 \h 1441515
13 LINK \l "_Toc534482276" 141.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины: 13 PAGEREF _Toc534482276 \h 1451515
13 LINK \l "_Toc534482277" 141.4. Рекомендуемое количество часов на освоение программы дисциплины: 13 PAGEREF _Toc534482277 \h 1451515
13 LINK \l "_Toc534482278" 142. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ 13 PAGEREF _Toc534482278 \h 1461515
13 LINK \l "_Toc534482279" 142.1. Объем учебной дисциплины и виды учебной работы 13 PAGEREF _Toc534482279 \h 1461515
13 LINK \l "_Toc534482280" 142.2. Тематический план и содержание учебной дисциплины «Теория графов» 13 PAGEREF _Toc534482280 \h 1471515
13 LINK \l "_Toc534482281" 143. условия реализации УЧЕБНОЙ дисциплины 13 PAGEREF _Toc534482281 \h 14101515
13 LINK \l "_Toc534482282" 143.1. Требования к минимальному материально-техническому обеспечению 13 PAGEREF _Toc534482282 \h 14101515
13 LINK \l "_Toc534482283" 14Аппаратные средства 13 PAGEREF _Toc534482283 \h 14101515
13 LINK \l "_Toc534482284" 14Программные средства 13 PAGEREF _Toc534482284 \h 14111515
13 LINK \l "_Toc534482285" 143.2. Информационное обеспечение обучения 13 PAGEREF _Toc534482285 \h 14121515
13 LINK \l "_Toc534482286" 144. Контроль и оценка результатов освоения УЧЕБНОЙ Дисциплины 13 PAGEREF _Toc534482286 \h 14141515
15

1. ПАСПОРТ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ
Теория графов
1.1. Область применения программы.
Программа учебной дисциплины является частью примерной основной профессиональной образовательной программы в соответствии с ФГОС по специальности СПО, входящим в состав укрупненной группы профессий 09.02.00 Информатика и вычислительная техника, по направлению подготовки: 09.02.03 Программирование в компьютерных системах.
Программа учебной дисциплины может быть использована:
- в дополнительном профессиональном образовании по программе повышения квалификации при наличии начального профессионального образования по профессии оператор ЭВМ;
- в профессиональной подготовке и переподготовке работников в области гуманитарных наук и сферы обслуживания, при наличии среднего образования технического профиля или высшего профессионального образования нетехнического профиля.

1.2. Место дисциплины в структуре основной профессиональной образовательной программы:
дисциплина входит в математический и общий естественнонаучный цикл.
Материал дисциплины «Теория графов» используется при изучении дисциплин:
- «Основы программирования»;
- «Архитектура компьютерных систем»;
- «Базы данных»;
- «Теория вероятностей и математическая статистика»;
- «Теория алгоритмов»;
- «Технология разработки программных продуктов».

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

В результате освоения дисциплины обучающийся должен знать:
понятие неориентированного графа и основные определения, связанные с ним;
алгоритм фронта волны в графе;
методику выделения компонент связности в графе;
понятие моста и разделяющей вершины;
понятие расстояния между вершинами в графе и методику его нахождения;
понятие эксцентриситета вершины, радиуса графа, диаметра графа, центральной вершины;
понятие двудольного графа, методику проверки графа на двудольность, понятие полного двудольного графа;
понятие эйлерова графа, теорему Эйлера, методику нахождения эйлерова цикла в эйлеровом графе;
понятие гамильтонова графа;
понятие плоского графа; соотношение между количествами вершин, рёбер и граней в плоском графе; простейшие примеры неплоских графов;
понятие дерева, свойства деревьев;
понятие ориентированного графа (орграфа) и основные определения, связанные с ним;
понятие достижимости вершин в орграфе, методика записи матрицы достижимости орграфа;
понятие бесконтурного орграфа, теорема о существовании источника и стока в бесконтурном орграфе;
понятие бинарного дерева;
кодирование бинарных деревьев
1.4. Рекомендуемое количество часов на освоение программы дисциплины:
максимальной учебной нагрузки обучающегося 71 час, в том числе:
обязательной аудиторной учебной нагрузки обучающегося 51 час;
самостоятельной работы обучающегося 20 часов.
2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
2.1. Объем учебной дисциплины и виды учебной работы
Вид учебной работы
Количество часов

Максимальная учебная нагрузка (всего)
71

Обязательная аудиторная учебная нагрузка (всего)
51

в том числе:


практические работы
12

Самостоятельная работа обучающегося (всего)
20

в том числе:


реферат, доклад, сообщение
10

индивидуальные проекты
10

Итоговая аттестация в форме дифференцированного зачёта


2.2. Тематический план и содержание учебной дисциплины «Теория графов»

Наименование разделов и тем
Содержание учебного материала, лабораторные работы и практические занятия, самостоятельная работа обучающихся
Объем часов
Уровень освоения

1
2
3
4

Раздел 1. Неориентированные графы.
1
Понятие неориентированного графа. Способы задания графа. Матрица смежности.
22
2


2
Путь в графе. Цикл в графе. Связный граф. Компоненты связности графа.




3
Степень вершины. Теорема о сумме степеней вершин графа.




4
Полный граф; формула количества рёбер в полном графе.




5
Алгоритм фронта волны в графе. Мосты и разделяющие вершины (точки сочленения).




6
Радиус и диаметр графа. Центральные вершины.




7
Двудольные графы. Методика проверки графа на двудольность. Полный двудольный граф.




8
Изоморфные графы. Методика проверки пары графов на изоморфность.




9
Эйлеровы графы. Теорема Эйлера (критерий эйлеровости графа). Методика нахождения эйлерова цикла в эйлеровом графе. Гамильтоновы графы.




10
Плоские графы. Грани плоской укладки плоского графа. Соотношения между количествами вершин, рёбер и граней в плоском графе. Примеры неплоских графов.




11
Графы с цветными ребрами. Свойства полных графов с цветными ребрами.




Практические работы
6
2


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




Самостоятельная работа
10
3


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



Раздел 2. Ориентированные графы.
1
Понятие ориентированного графа (орграфа). Способы задания орграфа. Матрица смежности для орграфа. Степень входа и степень выхода вершины. Источник. Сток. Ориентированный путь. Ориентированный цикл (контур).
17

2



2
Понятие достижимости одной вершины из другой вершины в орграфе. Множество достижимости вершины. Матрица достижимости.




3
Эквивалентность (взаимодостижимость) вершин в орграфе. Классы эквивалентных вершин. Диаграмма Герца. Сильносвязный орграф.




4
Бесконтурные орграфы. Теорема о существовании источника и стока в бесконтурном орграфе.




5
Понятие ориентированного дерева. Понятие бинарного дерева. Дисбаланс вершины в бинарном дереве. Кодирование бинарных деревьев.




6
Парадоксы «голосования с предпочтением». Отношения. Свойства отношений. Отношение эквивалентности. Отношение порядка. Определение графа.




7
Отношение эквивалентности. Отношение порядка. Определение графа.




8
Сетевой график. Критический путь.




9
Сетевой график. Резервы времени.





Приложенные файлы

  • doc Graf
    Размер файла: 191 kB Загрузок: 0