Наименование дисциплины: Алгоритмы на графах
Направление подготовки (специальность): 090301 Компьютерная безопасность
Специализация: Математические методы защиты информации
Квалификация (степень) выпускника: специалист
Форма обучения: очная
Автор: к. ф.-м. н., доцент, доцент кафедры компьютерной безопасности математических методов обработки информации О. П.
1. В курсе «Алгоритмы на графах» разбирается большое количество прикладных задач, которые решаются с помощью аппарата теории графов. Приводятся алгоритмы решения этих задач. Проводится анализ полученных результатов.
Целью преподавания дисциплины является формирование у студентов математической культуры, знакомство с аппаратом теории графов и основными алгоритмами на графах, примение известных алгоритмов для решения прикладных задач, задач поиска и кодирования, проведение анализа полученных результатов.
Задача курса познакомить студентов с современными методами построения и анализа алгоритмов.
В ходе изучения предмета студенты выполняют индивидуальные задания по решению прикладных задач, требующих модификации известных алгоритмов. Семестровый курс заканчивается зачетом.
2. Теория графов - важнейший математический инструмент, широко используемый в химии, генетике, исследовании операций, лингвистике, проектировании и кодировании. Непосредственное и детальное представление практических систем, таких, как распределительные сети и системы связи, приводит к графам большого размера, успешный анализ которых зависит от существования "хороших" алгоритмов. Поэтому в рамках курса уделяется большое внимание разработке и описанию эффективных алгоритмов, решающих практические задачи. Работа по этой проблематике значительно обогащает алгоритмическую культуру студентов, совершенствует технику написания программ, так как алгоритмы являются неиссякаемым источником задач любого уровня сложности. Знания и практические навыки, полученные из курса «Алгоритмы на графах», используются обучаемыми при изучении естественно-научных дисциплин, а также при разработке курсовых и дипломных работ.
Дисциплина относится к вариативной части блока С3.
3. В результате освоения дисциплины обучающийся должен:
Знать:
· основные способы представления графов в памяти компьютера;
· основные алгоритмы решения задач с помощью аппарата теории графов;
· понятие NP - полных задач, различные алгоритмы апроксимации ;
Уметь:
· использовать известные алгоритмы на графах для решения прикладных задач;
· применять полученные знания в различных предметных областях;
· представлять различные объекты с помощью графов.
Владеть:
· навыками алгоритмического мышления;
· навыками работы с компьютерами, с различными программными средами и оболочками;
· Навыками работы с документацией.
4. Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов.
5.Содержание дисциплины:
№ п/п | Раздел дисциплины |
1 | Введение в теорию графов. Начальные понятия. Способы представления графа в памяти ЭВМ. |
2 | Связность. Поиск в глубину. Отыскание всех двусвязных компонент графа. |
3 | Деревья. Построение минимального остовного дерева Алгоритм сортировки на основе бинарного дерева. |
4 | Алгоритмы поиска в деревьях( бинарные, АВЛ, красно-черные) |
5 | Методы поиска во внешней памяти на основе деревьев.(В-деревья) |
6 | Кратчайшие пути, поиск в ширину. |
7 | Независимость и покрытия. Наибольшие паросочетания. |
8 | Обходы. Эйлеровы и гамильтоновы графы. Задача коммивояжера. |
9 | Планарность. Раскраски. |
6. Учебно-методическое и информационное обеспечение дисциплины:
а) основная литература:
1. Алгоритмы: построение и анализ. М: МЦНМО, 2001, 19с.
2. , Полякова графов. Алгоритмы на графах:
учебное пособие/ Яросл. гос. ун-т. Ярославль, 20с.
3. Искусство программирования для ЭВМ. Т. 3.: Сортировка и поиск. М.: Вильямс. 20с.
б) дополнительная литература.
1. Алгоритмы и структуры данных. М.: Мир, 19с.
2. , , Тышкевич по теории графов. М.: Наука, 19с.
в) программное обеспечение и Интернет-ресурсы:
На сайте математического факультета имеются электронные варианты текстов учебных пособий и методических указаний.
