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



Скачать 132.95 Kb.
Дата08.10.2012
Размер132.95 Kb.
ТипРабочая программа


Приложение 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. Материально-техническое обеспечение дисциплины

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

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



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

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

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

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

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



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

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

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



Похожие:

Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconРабочая программа учебной дисциплины «коллоидная химия» Направление подготовки: 240100 Химическая технология
Квалификация (степень) выпускника: бакалавр, специальное звание «бакалавр техники и технологий»
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconРабочая программа дисциплины Философия Направление подготовки 011800 Радиофизика Квалификация (степень) выпускника Бакалавр
Дисциплина цикла гсэ. Специальные требования к входным знаниям, умениям и компетенциям студента не предусматриваются
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconУчебный план разработан в соответствии с фгос впо по направлению подготовки 200100 «Приборостроение»
...
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconНаправление подготовки 022000 – Экология и природопользование Профиль – Экология Степень (квалификация) выпускника – бакалавр
Институте естественных и социально-экономических наук (иесэн) с 2011 г на основе опыта подготовки по специальностям Экология (с 1993...
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconНаправление подготовки 020400 – Биология Профиль – Общая биология Степень (квалификация) выпускника – бакалавр
Подготовка по данному направлению реализуется в Институте естественных и социально-экономических наук (иесэн) с 2011 г на основе...
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconРабочая программа дисциплины математика Направление подготовки 080200. 62 Менеджмент Профиль подготовки
Рабочая программа предназначена для преподавания дисциплины математика базовой части математического и естественнонаучного цикла...
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconНаправление подготовки 050100 – Педагогическое образование Профиль – География Степень (квалификация) выпускника – бакалавр
Педагогическое образование, профиль География. Обучение проводится по очной (дневной) и заочной формам
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconНаправление подготовки 050100 – Педагогическое образование Профиль – Биология Степень (квалификация) выпускника – бакалавр
Педагогическое образование, профиль Биология. Обучение проводится по очной (дневной) и заочной формам
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconПрограмма учебной дисциплины «технический и групповой анализ топлив» Направление подготовки: 240100 Химическая технология
Квалификация (степень) выпускника: бакалавр, специальное звание «бакалавр техники и технологий»
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника iconРабочая программа дисциплины Корпоративный менеджмент Направление подготовки 080200 Менеджмент Профиль подготовки
Рабочая программа предназначена для преподавания дисциплины по выбору профессионального цикла ( В. Дв. 1) студентам очной и заочной...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org