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

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




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

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









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

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
















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

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

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


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

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

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


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



СОДЕРЖАНИЕ

HYPER13 TOC \o "1-3" \h \z \u HYPER14HYPER13 HYPERLINK \l "_Toc534482273" HYPER141. ПАСПОРТ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ HYPER13 PAGEREF _Toc534482273 \h HYPER144HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482274" HYPER141.1. Область применения программы. HYPER13 PAGEREF _Toc534482274 \h HYPER144HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482275" HYPER141.2. Место дисциплины в структуре основной профессиональной образовательной программы: HYPER13 PAGEREF _Toc534482275 \h HYPER144HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482276" HYPER141.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины: HYPER13 PAGEREF _Toc534482276 \h HYPER145HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482277" HYPER141.4. Рекомендуемое количество часов на освоение программы дисциплины: HYPER13 PAGEREF _Toc534482277 \h HYPER145HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482278" HYPER142. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ HYPER13 PAGEREF _Toc534482278 \h HYPER146HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482279" HYPER142.1. Объем учебной дисциплины и виды учебной работы HYPER13 PAGEREF _Toc534482279 \h HYPER146HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482280" HYPER142.2. Тематический план и содержание учебной дисциплины «Теория графов» HYPER13 PAGEREF _Toc534482280 \h HYPER147HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482281" HYPER143. условия реализации УЧЕБНОЙ дисциплины HYPER13 PAGEREF _Toc534482281 \h HYPER1410HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482282" HYPER143.1. Требования к минимальному материально-техническому обеспечению HYPER13 PAGEREF _Toc534482282 \h HYPER1410HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482283" HYPER14Аппаратные средства HYPER13 PAGEREF _Toc534482283 \h HYPER1410HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482284" HYPER14Программные средства HYPER13 PAGEREF _Toc534482284 \h HYPER1411HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482285" HYPER143.2. Информационное обеспечение обучения HYPER13 PAGEREF _Toc534482285 \h HYPER1412HYPER15HYPER15
HYPER13 HYPERLINK \l "_Toc534482286" HYPER144. Контроль и оценка результатов освоения УЧЕБНОЙ Дисциплины HYPER13 PAGEREF _Toc534482286 \h HYPER1414HYPER15HYPER15
HYPER15

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