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

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


Смотрите также:
Программа вступительного экзамена по математике и информационным технологиям направление 010500...
Математические модели и алгоритмы на графах с нестандартной достижимостью...
Математические модели и алгоритмы на графах с нестандартной достижимостью...
Рабочая программа дисциплины «теплофизика» Направление подготовки...
Рабочая программа дисциплины «теоретические основы теплотехники» Направление подготовки...
Рабочая программа дисциплины Физика, ен. Ф. 03 направление подготовки...
Рабочая программа учебной дисциплины «Правоведение» Направление подготовки...
Рабочая программа дисциплины технические измерения и приборы Направление подготовки...
Рабочая программа учебной дисциплины «Патентное право» Направление подготовки...
Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды...
Рабочая программа дисциплины «Интегрированные системы проектирования и управления» Направление...
Рабочая программа дисциплины «Вычислительные машины, системы и сети» Направление подготовки...



Загрузка...
скачать


Приложение 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. История развития теории графов.

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

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

Основные определения и обозначения, связанные с графами, орграфами и мультиграфами. Способы задания графов. Матрицы смежности и инцидентности, их свойства. Изоморфизм графов. Двудольные графы. Критерий двудольности графа. Леса и деревья. Эквивалентные определения дерева. Корневые и остовные деревья. Бинарные деревья. Хранение и поиск информации в бинарных деревьях. Добавление и удаление элементов. Деревья, сбалансированные по высоте (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.

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


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

  1. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность – М.: Мир, 1985.

  2. Кристофидес Н. Теория графов. Алгоритмический подход – М.: Мир, 1978.

  3. Дистель Р. Теория графов – Новосибирск: Изд-во ИМ СО РАН, 2002.


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

  • Ноутбук, медиа-проектор, экран.

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



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


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

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

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


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




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

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

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






Скачать 133,78 Kb.
оставить комментарий
Дата30.09.2011
Размер133,78 Kb.
ТипРабочая программа, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх