Наименование дисциплины: Алгоритмы на графахНаправление подготовки: 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 с. в) программное обеспечение и Интернет-ресурсы: программный комплекс «Сбалансированные бинарные деревья».