Рабочая программа дисциплины Графы и алгоритмы Направление подготовки

Вид материала

Рабочая программа

Содержание Аннотация рабочей программы 1. Цели освоения дисциплины 2. Место дисциплины в структуре ООП бакалавриата 3. Компетенции обучающегося, формируемые в результате освоения дисциплины 4. Структура и содержание дисциплины Лабор. работа Контрольная работа Содержание отдельных разделов и тем Основные понятия. Классификация типов графов. Простейшие алгоритмы на графах и сетях. Связность и факторизации. Обходы графов. Планарность и раскраски. Перечисление и кодирование графов. Вопросы алгоритмической сложности. 5. Образовательные технологии 7. Учебно-методическое и информационное обеспечение дисциплины 8. Материально-техническое обеспечение дисциплины

Подобный материал:

• Рабочая программа дисциплины «теоретические основы теплотехники» Направление подготовки, 554.69kb.
• Рабочая программа дисциплины «Техническая термодинамитка» Направление подготовки, 804.99kb.
• Рабочая программа Наименование дисциплины Алгоритмы и методы компьютерной лингвистики, 210.54kb.
• Рабочая программа дисциплины Физика, ен. Ф. 03 направление подготовки, 491.56kb.
• Рабочая программа дисциплины «Компьютерная диагностика» Направление подготовки, 209.63kb.
• Рабочая программа дисциплины технические измерения и приборы Направление подготовки, 496.12kb.
• Рабочая программа дисциплины «Интегрированные системы проектирования и управления», 208.14kb.
• Рабочая программа дисциплины «Основы технологии машиностроения» Направление подготовки, 365.59kb.
• Рабочая программа дисциплины «Вычислительные машины, системы и сети» Направление подготовки, 231.13kb.
• Рабочая программа учебной дисциплины «психология» Направление подготовки, 808.24kb.

Приложение 3


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


Национальный исследовательский университет

Новосибирский государственный университет

Механико-математический факультет


УТВЕРЖДАЮ


_______________________


«_____»__________________201__ г.


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

Графы и алгоритмы


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


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


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

Бакалавр


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

Очная


Новосибирск 2010


^ Аннотация рабочей программы


Дисциплина «Графы и алгоритмы» является частью математического цикла ООП по направлению подготовки «», профиль «». Дисциплина реализуется на Механико-математическом факультете Национального исследовательского университета Новосибирский государственный университет кафедрой Программирования ММФ НИУ НГУ.

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

Дисциплина нацелена на формирование общекультурных компетенций ???, профессиональных компетенций ??? выпускника.

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

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

Общая трудоемкость дисциплины составляет 2,5 зачетных единиц, 92 академических часа. Программой дисциплины предусмотрены 34 часов лекционных и 18 часов практических занятий, а также 36 часов самостоятельной работы студентов. Остальное время – контроль в форме контрольной и зачета.


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

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

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


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

Дисциплина «Графы и алгоритмы» является частью математического цикла ООП по направлению подготовки «», профиль «».

Дисциплина «Графы и алгоритмы» опирается на следующие дисциплины данной ООП:

• Математическая логика (формализация методов рассуждений, логические связки, аксиоматические модели);
  
• Теория алгоритмов (понятие временной сложности алгоритма);
  
• Основы работы на ЭВМ (работа в среде Windows);
  
• Программирование I (принципы проектирования языков программирования высокого уровня, навыки реализации алгоритмов на ЯВУ, язык С, работа в среде Microsoft Visual Studio).
  

Результаты освоения дисциплины «Графы и алгоритмы» используются в следующих дисциплинах данной ООП:

• ???
  

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

• общекультурные компетенции: ???
  
• профессиональные компетенции: ???
  

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

иметь представление

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

знать

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

уметь

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

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

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

№ п/п	Раздел дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)					Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам)
				Лекция	^ Лабор. работа	Самост. работа	Контр. работа	Зачет
1	История развития теории графов.			2	2	0
2	Основные понятия. Классификация типов графов.			2	4	2
3	Классические алгоритмы на графах и сетях.			10	10	6
4	Связность и факторизации. Обходы графов.			10	10	4
5	Планарность и раскраски графов			6	6	4
6	Перечисление и кодирование графов. Вопросы алгоритмической сложности.			4	4	2
							2		^ Контрольная работа
								2	Зачет
				34	36	18	2	2

^ Содержание отдельных разделов и тем:

1. История развития теории графов.
   

Возникновение понятия графа. Графы как модели при решении задач. Задача Эйлера о кенигсбергских мостах. Задача Гамильтона. Исследования деревьев Кирхгофом и Кэли. Мультиграфы, ориентированные графы и сети. Алгоритмы на графах и сетях. Современное состояние развития теории графов.

2. ^ Основные понятия. Классификация типов графов.
   

Основные определения и обозначения, связанные с графами, орграфами и мультиграфами. Способы задания графов. Матрицы смежности и инцидентности, их свойства. Изоморфизм графов. Двудольные графы. Критерий двудольности графа. Леса и деревья. Эквивалентные определения дерева. Корневые и остовные деревья. Бинарные деревья. Хранение и поиск информации в бинарных деревьях. Добавление и удаление элементов. Деревья, сбалансированные по высоте (AVL-деревья) и по весу. Точки сочленения, мосты и блоки графа. Вершинная и реберная связность. Характеризация двусвязных графов. Взаимное расположение двух блоков в графе. Дерево блоков и точек сочленения. Независимые множества вершин и ребер графа. Вершинные и реберные покрытия, факторы и паросочетания. Числовые параметры, связанные с независимостью и покрытиями, их свойства. Теорема Галлаи.

3. ^ Простейшие алгоритмы на графах и сетях.

Поиск по графу в ширину и глубину. Дерево поиска. Связь поиска в ширину с нахождением кратчайших цепей. Модифицированный алгоритм поиска в глубину. Поиск блоков в связном графе. Нахождение минимального остова: алгоритмы Примы и Краскала. Кратчайшие пути во взвешенных орграфах. Алгоритмы Дейкстры и Флойда-Уоршелла. Сети и потоки в сетях. Задача о максимальном потоке. Остаточные сети, дополняющие пути и разрезы. Теорема и обобщенный алгоритм Форда-Фалкерсона. Анализ работы алгоритма в случае целых и рациональных пропускных способностей. Случай иррациональных пропускных способностей. Пример Форда и Фалкерсона. Метод кратчайших путей.

4. ^ Связность и факторизации. Обходы графов.

Наборы непересекающихся цепей, соединяющих два подмножества вершин графа (орграфа). Вершинная и реберная теоремы Менгера. Критерии вершинной и реберной k-связности графов (теорема Уитни). Обходы графов. Эйлеровы и гамильтоновы графы. Теорема Эйлера и алгоритм Флери. Достаточные условия гамильтоновости. Теоремы Дирака и Оре. Гамильтоновы циклы и задача коммивояжера. Наибольшие паросочетания и чередующиеся цепи. Характеризация наибольших паросочетаний в терминах чередующиеся цепей. Паросочетания, покрывающие долю двудольного графа. Связь с системами различных представителей и теоремой Холла. Теоремы Кенига о числе реберной независимости двудольного графа и (0,1)-матрицах. Алгоритм поиска наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе. Задача о назначениях. Критерий Татта существования 1-фактора в произвольном графе. Теоремы Петерсена о 2-факторах.

5. ^ Планарность и раскраски.

Плоские и планарные графы. Нормальные карты и эйлеровы многогранники. Формула Эйлера и ее следствия. Критерий планарности Понтрягина-Куратовского. Алгоритм укладки графа на плоскости. Понятие геометрически двойственного графа. Раскраски вершин графов. Простейшие оценки хроматического числа. Теорема Брукса. Хроматические полиномы, их свойства. Нерешенные задачи о хроматических полиномах. Раскраски планарных графов и карт. Теорема о четырех красках. Доказательство теоремы о пяти красках. Вопросы 3-раскрашиваемости планарных графов. Теоремы Грецша и Грюнбаума. Реберные раскраски графов и мультиграфов. Теоремы Визинга и Шэннона. Хроматический индекс двудольного графа. Интервальные раскраски. Связь с задачами теории расписаний. Предписанные раскраски. Теорема Томассена о предписанной 5-раскрашиваемости плоских графов.

6. ^ Перечисление и кодирование графов. Вопросы алгоритмической сложности.

Перечисление и кодирование графов. Проблема изоморфизма. Кодирование деревьев. Код Прюфера. Теорема Кэли о числе помеченных деревьев. Классы труднорешаемых задач на графах. Классы P, NP и NPC. Связь между задачами “Клика” и “Выполнимость”. NP-полнота задач “Изоморфный подграф”, “Независимость’’, “Вершинное покрытие’’, “Гамильтонов цикл”, “Гамильтонова цепь”, “3-раскрашиваемость”.


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

Лекционные занятия, семинарские занятия, самостоятельная исследовательская работа, информационные технологии.


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


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

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

1. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов – М.: Наука, 1990.
   
2. Харари Ф. Теория графов – М.: УРСС, 2003.
   
3. Косточка А. В. Дискретная математика. Часть 2 – Новосибирск: НГУ, 2001.
   

4. Кормен Т., Лейзерсон Ч., Ривест Р. – Алгоритмы: построение и анализ // М.: МЦНМО, 2001.
   

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

1. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность – М.: Мир, 1985.
   
2. Кристофидес Н. Теория графов. Алгоритмический подход – М.: Мир, 1978.
   
3. Дистель Р. Теория графов – Новосибирск: Изд-во ИМ СО РАН, 2002.
   

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

• Ноутбук, медиа-проектор, экран.
  
• Программное обеспечение для демонстрации слайд-презентаций.
  

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


Автор: Глебов Алексей Николаевич

к.ф.-м.н., ст. препод. ММФ НГУ

с.н.с. ИМ СО РАН


Рецензент (ы)


Программа одобрена на заседании

(Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет)

от ___________ года, протокол № ________