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



Скачать 75.76 Kb.
Дата06.07.2013
Размер75.76 Kb.
ТипРабочая программа
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Томский государственный университет
УТВЕРЖДАЮ
Декан факультета информатики

Сущенко С.П.

"" декабря 2010 г.

Рабочая программа дисциплины (модуля)
Теория графов

Направление подготовки
010300 Фундаментальная информатика и информационные технологии

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

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


Томск

2010


1. Цели освоения дисциплины
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов.

2. Место дисциплины в структуре ООП бакалавриата
Раздел образовательной программы: Б.3. Профессиональный цикл. Базовая часть.

Для изучения курса необходимо знание следующих дисциплин:

- дискретная математика.

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

- знать теорию множеств, теорию отношений, теорию булевых алгебр.

Знания и умения, полученные в ходе освоения данной дисциплины (модуля), понадобятся при изучении таких последующих дисциплин ООП, как:

- алгоритмы и анализ сложности;

- основы программирования;

- базы данных;

- методы оптимизации и исследование операций;

- интеллектуальные системы;

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

- теория систем и системный анализ.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля) Теория графов
Курс «Теория графов» способствует выработке у студента следующих компетенций:
- знание основных понятий и методов теории графов;

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

4. Структура и содержание дисциплины (модуля) «Теория графов»

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






п/п

Раздел

Дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)

Формы текущего контроля успеваемости (по неделям семестра)

Форма промежуточной аттестации (по семестрам)













всего

лекции

сем

самостоятельная работа




1

Основные определения

2

1-2

12

4




8




2

Связность графов

2

3-4

12

4




8




3

Цикломатика графов

2

5-6

18

4

4

10

Тест

4

Потоки в сетях

2

7-8

14

4




10




5

Экстремальные части графов

2

9-10

18

4

4

10

Тест


6

Задачи раскраски вершин и ребер графа

2

11-12

12

4




8

Тест

7

Алгоритмы

2

13-14

11

4




7




8

Применение графов для задач программирования

2

15-16

11

4




7

Тест

ИТОГО










108

32

8

68

Экзамен



Лекционный курс

Тема 1. Основные определения.


Способы задания графов. Типы графов.

Тема 2. Связность графов.


Маршруты, цепи, циклы. Алгоритмы нахождения кратчайших цепей. Обходы графа. Эйлеровы цепи и циклы, гамильтоновы цепи и циклы.

Тема 3. Цикломатика графов.


Цикломатическое число. Деревья, каркасы. Алгоритмы нахождения каркасов. Нахождение фундаментальных циклов. Цикломатическая матрица, матрица разрезов.

Тема 4. Потоки в сетях.


Алгоритм Форда – Фалкерсона нахождения максимального потока в сети.

Тема 5. Экстремальные части графов.


Максимальные и наибольшие полные, пустые подграфы, паросочетания. Минимальные и наименьшие покрытия. Алгоритмы нахождения экстремальных частей.

Тема 6. Задачи раскраски вершин и ребер графа.


Проблема четырех красок. Алгоритмы минимальной раскраски.

Тема 7. Алгоритмы.

Алгоритмы решения задач на взвешенных графах.

Тема 8. Применение графов для задач программирования.


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

Самостоятельная работа студентов по дисциплине организуется в следующих формах:

- самостоятельное изучение основного теоретического материала, ознакомление с дополнительной литературой, Интернет-ресурсами;

В качестве учебно-методического обеспечения самостоятельной работы используется основная и дополнительная литература по предмету, Интернет-ресурсы, материал лекций, указания, выданные преподавателем при проведении семинарских занятий.

Текущий контроль успеваемости проводится по результатам ежемесячных контрольных работ по текущим темам.
7. Учебно-методическое и информационное обеспечение дисциплины (модуля) «Теория графов»
а) основная литература:

  1. Лекции по теории графов/ Емеличев В.А. и др. – Наука, Гл. ред. физ-мат. лит., 1990.

  2. Зыков А.А. Основы теории графов. – М., Наука, Гл. ред. физ-мат. лит., 1987.

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

  4. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000.

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

  1. Липский В. Комбинаторика для программистов. – М., Мир, 1977.

  2. Свами М., Тхуласириман К. Графы, сети и алгоритмы. – М., Мир, 1984.

  3. Берж К.. Теория графов и ее применения. – М., Изд-во иностр. лит., 1962.




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



Требуется обеспечение литературой, которую в достаточном объеме может предложить книжный фонд Научной библиотеки Томского госуниверситета и факультета информатики.

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

Рецензент: д.физ-мат.н., профессор О. А. Змеев.

Программа одобрена на заседании Ученого Совета Факультета информатики
от «___»_________201__г., протокол № ___.

Похожие:

Рабочая программа дисциплины (модуля) Теория графов Направление подготовки iconРабочая программа дисциплины "Теория конечных графов и ее приложения" Направление подготовки 010300. 62 «фиит»
Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные...
Рабочая программа дисциплины (модуля) Теория графов Направление подготовки iconРабочая программа дисциплины (модуля) Этнология (Наименование дисциплины (модуля) Направление подготовки
Целью изучения курса «этнология» является формирование систематизированных знаний у студентов по данной отрасли науки
Рабочая программа дисциплины (модуля) Теория графов Направление подготовки iconРабочая учебная программа дисциплины (модуля) Теория вероятностей и математическая статистика Направление подготовки 080100 Экономика
Дисциплина «Теория вероятностей и математическая статистика» входит в базовую часть математического и естественнонаучного цикла подготовки...
Рабочая программа дисциплины (модуля) Теория графов Направление подготовки iconРабочая программа дисциплины (модуля) трудовое право направление подготовки: юриспруденция Профиль подготовки

Рабочая программа дисциплины (модуля) Теория графов Направление подготовки iconРабочая программа дисциплины (модуля) Агроэкология Направление подготовки 022000 Экология и природопользование
Целью освоения дисциплины (модуля) «Агроэкология» является знакомство студентов с основами организации и функционирования преобразованных...
Рабочая программа дисциплины (модуля) Теория графов Направление подготовки iconРабочая программа дисциплины (модуля) История налогов и налогообложения Направление подготовки Экономика

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

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

Рабочая программа дисциплины (модуля) Теория графов Направление подготовки iconРабочая программа дисциплины (модуля) Основы биогеографии Направление подготовки
Министерство природных ресурсов рф, другие природоохранные ведомства и учреждения
Рабочая программа дисциплины (модуля) Теория графов Направление подготовки iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Разместите кнопку на своём сайте:
ru.convdocs.org


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