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

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




Скачати 75.76 Kb.
НазваРабочая программа дисциплины (модуля) Теория графов
Дата конвертації07.02.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__г., протокол № ___.



Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації