Рабочая программа дисциплины Б3.ДВ12. Конструктивные описания графов и их приложения

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Нижегородский государственный педагогический университет

имени Козьмы Минина»

Факультет математики, информатики и физики

Кафедра информатики и информационных технологий

УТВЕРЖДАЮ

Проректор по учебно-

методической деятельности

__________

«__» _______20____г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Б3.ДВ12. Конструктивные описания графов и их приложения

Направление подготовки: 050100.62 Педагогическое образование

Профиль подготовки: Математика и информатика

Квалификация (степень) выпускника: бакалавр

Форма обучения: очная – 5 лет

Н. Новгород

2012 г.

Рабочая программа составлена на основе:

1.  Федерального государственного образовательного стандарта высшего профессионального образования по направлению 050100 Педагогическое образование, утвержденного «17» января 2011г., № 46.

2.  Учебного плана по направлению 050100.62 Педагогическое образование по профилю подготовки Математика и информатика, утвержденного «26» апреля 2012г.

Рабочая программа по дисциплине «Конструктивные описания графов и их приложения» принята на заседании кафедры «Информатики и информационных технологий», протокол № ___

от «___» ______________ 20___г.

Разработчик: д. ф.-м. н., профессор

СОГЛАСОВАНО

Зав. кафедрой «Информатики и информационных технологий»

_________________//

«____»_______________20__г.

СОГЛАСОВАНО

Зав. выпускающей кафедрой «Математического анализа,

теории и методики обучения математики»

_________________//

«____»_______________20__г.

СОГЛАСОВАНО

Директор библиотеки

_________________/ /

«____»_______________20__г.

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

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

Задачи дисциплины:

-  познакомить с основными понятиями конструктивных описаний графов;

-  рассмотреть конструктивные описания некоторых замкнутых классов графов;

-  познакомить с приложениями конструктивных описаний.

2.  Место дисциплины в структуре ООП ВПО

Дисциплина «Конструктивные описания графов и их приложения» относится к дисциплинам по выбору профессионального цикла (Б3.ДВ12).

Для освоения дисциплины студенты используют знания, умения и виды деятельности, сформированные в процессе освоения дисциплин «Дискретная математика» и «Теоретические основы информатики».

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

Процесс изучения дисциплины направлен на формирование следующих компетенций или их составляющих:

ОК-1 - владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения;

ОК-4 - способность применять методы математической обработки информации, теоретического и экспериментального исследования;

В результате освоения данной дисциплины студент должен:

Знать:

- основные понятия и представления конструктивных описаний графов;

- элементные и операционные базисы конструктивных описаний замкнутых классов всех графов, мультиграфов, обыкновенных графов, планарных и эйлеровых графов.

Уметь:

- анализировать конструктивные описания замкнутых классов графов;

- строить заданные графы по их конструктивным описаниям;

- применять конструктивные описания при решении прикладных задач на графах.

Владеть:

- основными приемами построения графов по заданным конструктивным описаниям;

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

Вид учебной работы	Всего зач. ед.	Всего часов	Семестр 9	Семестр 10
Общая трудоемкость дисциплины	2	72	36	36
Аудиторные занятия	32	16	16
(в т. ч. в активной и интерактивной форме)	6		6
Практические занятия	32	16	16
Самостоятельная работа	40	20	20
Вид итогового контроля	Зачет			Зачет

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

5.1. Тематический план

Раздел дисциплины	Количество часов	Итого по разделам дисциплины
Практические занятия	Самостоятельная работа
Введение	2	2	4
Раздел 1. Операции склейки	4	6	10
1.1 Основные свойства	2	3	5
1.2 Условия сохранения заданных свойств	2	3	5
Раздел 2. Конструктивные описания	10	12	22
2.1. Структура замкнутых классов графов	2	2	4
2.2. Все графы, мультиграфы, обыкновенные графы	2	2	4
2.3. Планарные графы	2	4	6
2.4. Эйлеровы и гамильтоновы графы	4	4	8
Раздел 3. Прикладные задачи	16	20	36
3.1. Кодирование графов	6	8	14
3.2. Размещение графов	10	12	22
Итого:	32	40	72

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

Введение. Использование конструктивных описаний при решении прикладных задач на графах.

Раздел 1. Операции склейки

1.1  Основные свойства.

Определение операций склейки. Зависимость результата от вида подграфов склейки, выбора и способа отождествления. Свойства графов, сохраняемые любыми операциями склейки.

1.2  Условия сохранения характеристических свойств графов.

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

Раздел 2. Конструктивные описания

2.1 Структура замкнутых классов графов.

Определения элементного и операционного базисов. Единственность элементного базиса. Число замкнутых классов.

2.2 Все графы, мультиграфы, обыкновенные графы.

Элементные и операционные базисы замкнутых классов всех графов, мультиграфов и обыкновенных графов. Счетность порождающих базисов замкнутого класса обыкновенных графов.

2.3  Планарные графы.

Элементные и операционные базисы замкнутого класса планарных графов при различных ограничениях на операции склейки.

2.4  Эйлеровы и гамильтоновы графы.

Элементные и операционные базисы. Планарные эйлеровы графы. Избыточность конструктивных описаний гамильтоновых графов.

Раздел 3. Прикладные задачи

3.1  Кодирование графов.

Экономное кодирование (s, r)-деревьев и k-деревьев.

3.2  Размещение графов.

Построение минимальных нумераций вершин деревьев.

5.3. Разделы дисциплины и связь с формируемыми компетенциями

Наименование компетенций	№ разделов дисциплины, участвующих в формировании компетенций
1	2	3
ОК-1	+		+
ОК-4	+	+	+

6. Образовательные технологии

Технологии проблемного обучения, интерактивные технологии

6.1. Темы занятий в активной и интерактивной форме

1. Элементные и операционные базисы замкнутых классов всех графов, мультиграфов и обыкновенных графов – 2 ч.

2. Эйлеровы и гамильтоновы графы – 4 ч.

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

7.1. Основная литература:

1.  Бурков описания планарных и эйлеровых графов // Вестник Нижегородского государственного университета. Математика. 2010, № 5(1). С. 165-170.

2.  Иорданский построения в теории графов // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.) / Под ред. . Нижний Новгород: Изд-во Нижегородского госуниверситета. 2011. С. 183-187.

3.  Иорданский описания и экономное кодирование графов // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. 2000. Вып.1(22). С. 88-93.

4.  , , Тышкевич по теории графов.- М.: УРСС, 2009. – 384с.

5.  Иорданский нумерации вершин графов // Математические вопросы кибернетики. 2001. Вып.10. С. 83-102.

7.2. Дополнительная литература:

6.  Иорданский описания графов // Дискретный анализ и исследование операций. 1996. Т. 3. № 4. С. 35-63.

7.  Иорданский графов: методические указания. – Н. Новгород: НГПУ, 2000. – 12с.

8. Иорданский описания и экономное кодирование графов: методические разработки. – Н. Новгород: НГПУ, 1998. – 18с.

7.3. Базы данных, информационно-справочные и поисковые системы:

www. biblioclub. ru	ЭБС «Университетская библиотека онлайн»
www. elibrary. ru	Научная электронная библиотека
www. ebiblioteka. ru	Универсальные базы данных изданий

8. Материально-техническое обеспечение дисциплины

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

9. Контроль и оценка результатов освоения дисциплины

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

Наименование компетенции	Показатель оценки сформированности компетенции	№ разделов дисциплины, участвующих в формировании компетенций
1	2	3
ОК -1 - владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения
	Знает: - основные понятия и представления конструктивных описаний графов; Умеет: - анализировать конструктивные описания замкнутых классов графов	Тест		Выступление на занятии
ОК-4 – способность применять методы математической обработки информации, теоретического и экспериментального исследования
	Знает: - элементные и операционные базисы конструктивных описаний замкнутых классов всех графов, мультиграфов, обыкновенных графов, планарных и эйлеровых графов Умеет: - анализировать конструктивные тивные описания замкнутых классо классов графов; - строить заданные графы по их конструктивным описаниям; - применять конструктивные описания при решении прикладных задач на графах. Владеет: - основными приемами построения графов по заданным конструктивным описаниям;	Выступление на занятии	Практическое задание	Практическое задание

Контрольные вопросы к зачету

1. Операции склейки и их свойства.

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

3. Условия сохранения операциями склейки отсутствия кратных ребер.

4. Конструктивное описание замкнутого класса всех графов.

5. Конструктивное описание замкнутого класса мультиграфов.

6. Конструктивные описания замкнутого класса обыкновенных графов.

7. Условия сохранения операциями склейки свойства планарности.

8. Элементные и операционные базисы планарных графов.

9. Условия сохранения операциями склейки свойства эйлеровости.

10. Элементные и операционные базисы эйлеровых графов.

11. Условия сохранения операциями склейки свойства гамильтоновости.

12. Элементные и операционные базисы гамильтоновых графов.

13. Определение k-дерева.

13. Алгоритмы экономного кодирования помеченных и непомеченных k-деревьев.

14. Определение минимальной нумерации.

15. Определение плоской нумерации.

16. Алгоритм построения минимальной плоской нумерации вершин дерева.