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

Автор: Белова Марина Владимировна

Дата публикации: 14.03.2016

Номер материала: 408

Рабочие программы
Математика
Без класса

МИНИСТЕРСТВО ОБРАЗОВАНИЯ ТВЕРСКОЙ ОБЛАСТИ

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

«ОСТАШКОВСКИЙ КОЛЛЕДЖ»

«СОГЛАСОВАНО»                                «УТВЕРЖДАЮ»

Директор филиала ООО «СИБОСС                 Зам.директора по УР ГБПОУ         

Девелопмент интернейшнл»                        «Осташковский колледж»

В Тверской области

__________________ Д.Б. Цветков                        _________________Е.А. Потоцкая        

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

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

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

2015

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

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

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

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

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

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

№1  от «31» августа  2015 г.

Рекомендована Экспертным советом по профессиональному образованию Федерального государственного учреждения Федерального института развития образования  (ФГУ ФИРО)

Заключение Экспертного совета № ____ от «___» ____________ 201   г.

© ГБПОУ «Осташковский колледж»

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


СОДЕРЖАНИЕ

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

1.1. Область применения программы.        

1.2.  Место дисциплины в структуре основной профессиональной образовательной программы:        

1.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины:        

1.4. Рекомендуемое количество часов на освоение программы дисциплины:        

2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ        

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

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

3. УСЛОВИЯ РЕАЛИЗАЦИИ УЧЕБНОЙ ДИСЦИПЛИНЫ        

3.1. Требования к минимальному материально-техническому обеспечению        

Аппаратные средства        

Программные средства        

3.2. Информационное обеспечение обучения        

4. КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ        


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

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

1.1. Область применения программы.

Программа учебной дисциплины является частью примерной основной профессиональной образовательной программы в соответствии с ФГОС по специальности СПО, входящим в состав укрупненной группы профессий 09.00.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

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

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

6

2

Запись матрицы достижимости и построение диаграммы Герца для ориентированного графа.

Решение задач на бинарные деревья.

Расчёт сетевого графика.

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

10

3

Работа с основной и дополнительной литературой. Подготовка отчетов по практическим работам.

Работа над индивидуальными проектами:

  • запись кода бинарного дерева;
  • восстановление по коду бинарного дерева;
  • построение бинарного дерева сортировки для заданной последовательности поступающих элементов.

Подготовка к итоговой аттестации.

ИТОГО

71

Для характеристики уровня освоения учебного материала используются следующие обозначения:

1. – ознакомительный (узнавание ранее изученных объектов, свойств);

2. – репродуктивный (выполнение деятельности по образцу, инструкции или под руководством)

3. – продуктивный (планирование и самостоятельное выполнение деятельности, решение проблемных задач)


3. УСЛОВИЯ РЕАЛИЗАЦИИ УЧЕБНОЙ ДИСЦИПЛИНЫ

3.1. Требования к минимальному материально-техническому обеспечению

Реализация учебной дисциплины требует наличия учебной лаборатории.

Технические средства обучения:

Аппаратные средства

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

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

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

Принтер — позволяет фиксировать на бумаге информацию, найденную и созданную студентом или преподавателем. Для многих школьных применений необходим или желателен цветной принтер. В некоторых ситуациях очень желательно использование бумаги и изображения большого формата.

Телекоммуникационный блок, устройства, обеспечивающие подключение к сети — дают доступ к российским и мировым информационным ресурсам, позволяют вести переписку с другими учебными заведениями

Устройства вывода звуковой информации — наушники для индивидуальной работы со звуковой информацией, громкоговорители с оконечным усилителем для озвучивания всего класса.

Устройства для ручного ввода текстовой информации и манипулирования экранными объектами — клавиатура и мышь (и разнообразные устройства аналогичного назначения).

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

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

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

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

Программные средства

Операционная система (графическая);

Файловый менеджер (в составе операционной системы или др.);

Антивирусная программа;

Интегрированное офисное приложение, включающее текстовый редактор, растровый и векторный графические редакторы, программу разработки презентаций и электронные таблицы;

Звуковой редактор;

Оборудование лаборатории и рабочих мест лаборатории:

  • персональные компьютеры с лицензионным программным обеспечением, объединенных в сеть (15 компьютеров);  
  • рабочее место преподавателя, оборудованное ЭВМ.

3.2. Информационное обеспечение обучения

Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы

Основная

  1. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. –   М.: Вузовская книга, 2007.
  2. Новиков Ф.А.  Дискретная математика для программистов.  – СПб.:  Питер, 2010.
  3. Сирота А.И., Худак Ю.И.   Дискретная математика. Москва Издательство МИРЭА 2010:
  4. Харири Ф.   Теория графов М., УРСС 2008  
  5. Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Основания информатики.–М.:Мир; Бином. Лаборатория знаний, 2009.
  6. Ландо С.К.  Лекции о производящих функциях. – Изд. 3–е.– М.: МЦНМО, 2010
  7. Свами М., Тхулалираман К. Графы, сети и алгоритмы. М: Мир, 2011.
  8. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов — М.: Высш. школа, 2011

Дополнительная

  1. Акимов О.Е.  Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2010.
  2. Гаврилов Г.П., Сапоженко А.А.  Задачи и упражнения по дискретной математике.  – М.: Высшая школа, 2010.
  3. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2009.

Интернет-ресурсы

  1. http://iit.metodist.ru - Информатика  - и информационные технологии: cайт лаборатории информатики МИОО
  2. http://www.intuit.ru - Интернет-университет информационных технологий (ИНТУИТ.ру)
  3. http://www.osp.ru - Открытые системы: издания по информационным технологиям


4. КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ

Контроль и оценка результатов освоения учебной дисциплины осуществляется преподавателем в процессе проведения практических работ, тестирования, а также выполнения обучающимися индивидуальных заданий, проектов, исследований.

Результаты обучения

(освоенные умения, усвоенные

знания)

Формы и методы контроля и оценки результатов обучения

1

2

Знание:

  • понятия неориентированного графа и основных определений, связанных с ним;
  • алгоритма фронта волны в графе;
  • методики выделения компонент связности в графе;

Умение:

выделять компоненты связности в графе 

Оценка устного и письменного опроса

Оценка выполнения практических работ

Оценка результатов:

  • практических работ;

- внеаудиторной самостоятельной работы (по выбору: доклад, сообщение, реферат, презентация, индивидуальный проект)

Знание:

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

Умение:

проверять, является ли данный граф двудольным

Оценка устного и письменного опроса

Оценка выполнения практических работ

Оценка результатов:

  • практических работ;

- внеаудиторной самостоятельной работы (по выбору: доклад, сообщение, реферат, презентация, индивидуальный проект)

Знание:

  • понятия эйлерова графа, теоремы Эйлера, методики нахождения эйлерова цикла в эйлеровом графе;
  • понятия гамильтонова графа;
  • понятия плоского графа; соотношения между количествами вершин, рёбер и граней в плоском графе; простейших примеров неплоских графов;

Умение:

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

Оценка устного и письменного опроса

Оценка выполнения практических работ

Оценка результатов:

  • практических работ;

- внеаудиторной самостоятельной работы (по выбору: доклад, сообщение, реферат, презентация, индивидуальный проект)

Знание:

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

Умение:

строить бинарное дерево сортировки для заданной последовательности поступающих элементов.

Оценка устного и письменного опроса

Оценка выполнения практических работ

Оценка результатов:

  • практических работ;

- внеаудиторной самостоятельной работы (по выбору: доклад, сообщение, реферат, презентация, индивидуальный проект)

Результат контрольной работы

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

Процент результативности (правильных ответов)

Качественная оценка индивидуальных образовательных достижений

балл (отметка)

вербальный аналог

90 ÷ 100

5

отлично

80 ÷ 89

4

хорошо

70 ÷ 79

3

удовлетворительно

менее 70

2

не удовлетворительно

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