Geum.ru

Алгоритмы на графах

Вид материалаДокументы
Подобный материал:
Наименование дисциплины: Алгоритмы на графах

Направление подготовки: 010200 Математика и компьютерные науки

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

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

Автор: к.ф.–м.н , доцент, доцент кафедры компьютерной безопасности и математических методов обработки информации О.П.Якимова.


1. Целями освоения дисциплины «Алгоритмы на графах» являются: формирование у студентов математической культуры, знакомство с аппаратом теории графов и основными алгоритмами на графах, примение известных алгоритмов для решения прикладных задач, задач поиска и кодирования, проведение анализа полученных результатов.


2. Дисциплина «Алгоритмы на графах» относится к части цикла Б3.  важнейший математический инструмент, широко используемый в проектировании, кодировании, исследовании операций, химии, генетике, лингвистике. Непосредственное и детальное представление практических систем, таких, как распределительные сети и системы связи, приводит к графам большого размера, успешный анализ которых зависит от существования "хороших" алгоритмов. Поэтому в рамках курса уделяется большое внимание разработке и описанию эффективных алгоритмов, решающих практические задачи. Работа по этой проблематике значительно обогащает алгоритмическую культуру студентов, совершенствует технику написания программ, так как алгоритмы являются неиссякаемым источником задач любого уровня сложности. Знания и практические навыки, полученные из курса «Алгоритмы на графах», используются обучаемыми при изучении естественно-научных дисциплин, а также при разработке курсовых и дипломных работ.


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


Знать:

-основные способы представления графов в памяти компьютера;

-основные алгоритмы решения задач с помощью аппарата теории графов;

-основные NP- полные задачи на графах и различные алгоритмы апроксимации применяемые для их решения;

Уметь:

-использовать известные алгоритмы на графах для решения прикладных задач;

-применять полученные знания в различных предметных областях;

-представлять различные объекты с помощью графов.


Владеть:

-навыками алгоритмического мышления;

-навыками работы с компьютерами, с различными программными средами и оболочками;

-навыками работы с документацией.


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


5. Содержание дисциплины:


№ п/п
Раздел дисциплины

1
Введение в теорию графов. Начальные понятия. Способы представления графа в памяти ЭВМ.

2
Связность. Поиск в глубину. Отыскание всех двусвязных компонент графа.

3
Деревья. Построение минимального остовного дерева (алгоритмы Краскала и Прима).

4
Алгоритмы поиска в деревьях (бинарные, АВЛ, красно-черные: построение дерева, поиск по дереву, удаление из дерева, анализ трудоемкости).

5
Методы поиска во внешней памяти на основе деревьев (В-деревья).

6
Кратчайшие пути, поиск в ширину ( алгоритмы Дейкстры и Флойда).

7
Независимость и покрытия. Наибольшие паросочетания.

8
Обходы. Эйлеровы и гамильтоновы графы. Задача коммивояжера.

9
Планарность. Критерии планарности (без доказательства). Алгоритм укладки графа на плоскости.

10
Раскраски. Задача составления расписаний, распре-деления оборудования. Алгоритм последовательной раскраски. Раскраска планарных графов.



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


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

1. Дольников В.Л., Полякова О.П. Теория графов. Алгоритмы на графах: учебное пособие/ Яросл. гос. ун-т. Ярославль, 2003. 116 с.


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

1. Емеличев Е.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 385 с.

2. Кнут Д. Искусство программирования для ЭВМ. Т. 3.: Сортировка и поиск. М.: Вильямс. 2004. 903 с.


в) программное обеспечение и Интернет-ресурсы:

программный комплекс «Сбалансированные бинарные деревья».