Теория графов: учебная программа учреждения образования по учебной дисциплине для специальности: 6-05-0533-11 Прикладная информатика. Рег. № 1733/б.

Abstract

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Цели и задачи учебной дисциплины Учебная дисциплина «Теория графов» знакомит студентов с основами этой теории, а также с алгоритмами решения задач на графах. В программу дисциплины включены как классические разделы теории графов, так и прикладные аспекты этой теории (независимость и доминирование в графах, паросочетания, обходы графов, раскраски). Учебная дисциплина также знакомит слушателя с важными открытиями в алгоритмической теории графов. При этом предпочтение при изложении материала отдается наиболее простым для понимания алгоритмам, которые наглядно демонстрируют ту или иную идею. Приводятся примеры прикладных задач, которые могут быть сформулированы и решены в теоретико-графовых терминах. Цель преподавания учебной дисциплины состоит в ознакомлении студентов с теоретическими основами теории графов и ее алгоритмическими аспектами, формирование у студентов современного математического кругозора, овладение навыками построения и анализа теоретико-графовых моделей прикладных задач. Задачи учебной дисциплины: 1. Ознакомление студентов с основными понятиями и фактами теории графов, и связями между ними. 2. Обучение методам нахождения ключевых структурных и числовых характеристик графов. 3. Ознакомление с методами построения и анализа теоретико-графовых моделей прикладных задач. Место учебной дисциплины в системе подготовки специалиста с высшим образованием. Учебная дисциплина относится к модулю «Дискретная математика и алгоритмы» государственного компонента. Программа составлена с учетом межпредметных связей с учебными дисциплинами. Основой для изучения учебной дисциплины являются дисциплины государственного компонента «Алгебра и теория чисел», модуля «Высшая математика», «Дискретная математика и математическая логика» модуля «Дискретная математика и алгоритмы». Знания, полученные в учебной дисциплине, используются при изучении дисциплины государственного компонента «Алгоритмы и структуры данных» модуля «Дискретная математика и алгоритмы».