Теория конечных графов и ее приложения

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

РОССИЙСКОЙ ФЕДЕРАЦИИ

Саратовский государственный университет имени

______________________________________________________________

(Наименование института, факультета)

УТВЕРЖДАЮ

___________________________

"__" __________________20__ г.

Рабочая программа дисциплины

Теория конечных графов и ее приложения

Направление подготовки

010300 Фундаментальная информатика и информационные

технологии

Профиль подготовки

Информатика и компьютерные науки

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

Бакалавр

Форма обучения

очная

(очная, заочная)

Саратов,

2011 год

1. Цели освоения дисциплины.

Целями освоения дисциплины «Теория конечных графов и ее приложения» являются: знакомство с фундаментальными понятиями и математическим аппаратом теории графов для последующего их использования; изучение основных задач теории графов и методов их решения, формирование навыков эффективно применять графовые алгоритмы для решения прикладных задач, использовать современные инструментальные и вычислительные средства для реализации графовых алгоритмов.

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

Данная учебная дисциплина входит в раздел «Естественнонаучный цикл. Вариативная часть» ФГОС-3. Читается в 3 семестре. Для успешного осовения дисциплины необходимы компетенции, сформированные в ходе изучения курсов «Теоретическая информатика», «Дискретная математика», «Основы программирования».

Для успешного освоения данного курса обучающийся должен

знать:

-  базовые структуры и алгоритмы компьютерной обработки данных;

-  понятия связных структур, способы их задания;

-  понятия отношения, свойства отношений;

-  методы анализа алгоритмов;

уметь:

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

-  использовать для решения практических задач такие структуры данных как матрицы, связные списки, массивы списков;

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

3 Компетенции обучающегося, формируемые в результате освоения дисциплины:

способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат, фундаментальные концепции и системные методологии, международные и профессиональные стандарты в области информационных технологий, способность использовать современные инструментальные и вычислительные средства (в соответствии с профилем подготовки) (ПК-4)

способность профессионально владеть базовыми математическими знаниями и информационными технологиями, эффективно применять их для решения научно-технических задач и прикладных задач, связанных с развитием и использованием информационных технологий (ПК-8)

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

знать: основные понятия теории графов, основные алгоритмы на графах и методы их решения;

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

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

4. Структура и содержание дисциплины.

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

№ п/п	Раздел дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) Лек Лаб Сам	Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам)
1	Введение в теорию графов	3	1	2	2	4		Опрос (проводится по контрольным вопросам 1-13)
2	Обходы графов	3	2-3	4	6	2		Выполнение заданий на сайте school. *****, acm. *****/univer
3	Деревья	3	4-5	4	2	2		Реферат (проект)
4	Ориентированные графы	3	6-7	4	4	4		Проверка индивидуальных заданий
5	Глобальный анализ графов	3	8-11	8	6	6		Проверка индивидуальных заданий
6	Разрезания и раскраска графов	3	12-13	4	2	4		Контрольная работа
7	Оптимизационные задачи на графах	3	14-16	6	12	8		Выполнение заданий на сайте acm. *****/univer
8	Прикладные задачи теории графов	3	17-18	4	2	6		Контрольная работа
	Промежуточная аттестация							Экзамен
	Итого			36	36	36		36

Введение в теорию графов

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

Обходы графов

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

Деревья

Понятие дерева, характеризация деревьев. Покрывающее дерево, алгоритм построения.

Ориентированные графы

Классификация путей в бесконтурных графах. Достижимость и сильная связность. База орграфа. Турниры.

Глобальный анализ графов

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

Разрезания и раскраска графов

Понятие разреза. Задача о разрезании графа. Разрезание различных видов графов. Понятие раскраски, правильно раскраски, хроматиеческого числа. Задача о вершинной раскраске, о раскраске граней, их связь. Оценка хроматического числа для некоторых видов графов. Хроматический многочлен.

Оптимизационные задачи на графах

Поиск кратчайших путей. Алгоритмы Форда-Беллмана, Флойда, Дейкстры, поиск пути в бесконтурном графе. Задача о потоке. Задача о каркасе минимального веса. Задача коммивояжера. Сетевое планирование.

Прикладные задачи теории графов

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

На лабораторных занятиях студенты получают индивидуальные задания, связанные с тематикой соответствующей занятию недели и пример которых приведен в разделе 6 настоящей программы. Задания выполняются в компьютерном классе с использованием программного обеспечения, указанного в разделе 8. Результатом выполнения индивидуального задания является программный код.

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

При проведении занятий по данному курсу используются следующие активные и интерактивные формы: организация временных творческих коллективов при работе над рефератом, учебным проектом, организация дискуссий и обсуждений спорных вопросов, использование метода мозгового щтурма, организация конкурса проектов и задач, использование мультимедийных презентаций, тестирование на сайте course. *****, использование системы дистанционной поддержки занятий на сайтах school. ***** и course. *****, разработанных сотрудниками факультета компьютерных наук и информационных технологий, Центра олимпиадной подготовки программистов, Центра непрерывной подготовки IT-специалистов.

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

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

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

, Евстигнеев в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003.

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

1. Замятин и сети. - Екатеринбург: Изд-во Урал. ун-та, 2004.

2. Костюкова и их применение. Комбинаторные алгоритмы для программистов. - М.: Интернет-Ун-т Информ. Технологий: БИНОМ. Лаб. знаний, 2007 .

в) программное обеспечение и Интернет-ресурсы

·  Образовательный сайт course. *****.

·  Портал обучения информатике и программированию school. *****.

·  Алгоритмы и фундаментальное программирование в СГУ http://acm. *****/univer

·  , Таланов и алгоритмы. Сайт интернет университета информационных технологий. [Электронный ресурс]. URL:

http://www. *****/department/algorithms/gaa/ (дата обращения 25.01.2011).

·  Костюкова и их применение. Сайт интернет университета информационных технологий. [Электронный ресурс]. URL:

http://www. *****/department/algorithms/graphsuse/ (дата обращения 25.01.2011).

Программное обеспечение: пакет офисных приложений для работы с файлами в формате Microsoft Word 97/2003, Microsoft Excel 97/2003, веб-браузер.

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

·  лекционная аудитория с мультимедийным оборудованием с выходом в Интернет,

·  компьютерные классы с программным обеспечением, рассчитанные на обучение группы студентов из 8 – 12 человек, удовлетворяющие санитарно-гигиеническим требованиям под управлением операционной системы Microsoft Windows XP с подключением к Internet;

·  Пакет Microsoft Office, Microsoft Visual Studio 2008.

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и Примерной ООП ВПО по направлению 010300 Фундаментальная информатика и информационные технологии и профилю подготовки Информатика и компьютерные науки.

Автор доцент

___________

Программа одобрена на заседании кафедры информатики и программирования от «14»февраля 2011 года, протокол

Заведующий кафедрой информатики и программирования, доцент	___________
Декан факультета КНиИТ, доцент	___________