Учебной дисциплины «Теория графов» для направления 010100. 62 «Математика»

Вид материала

Документы

Содержание История возникновения и развития теории графов

Подобный материал:

• Программа дисциплины Спецкурс «Теория Галуа 1»  для направления 010100. 62 «Математика», 100.92kb.
• Учебной дисциплины «Теория игр и исследование операций» для направления 010100., 42.57kb.
• Программа дисциплины Спецкурс «Избранные главы дискретной математики»  для направления, 79.63kb.
• Программа дисциплины Спецкурс «Конфигурации гиперплоскостей: их комбинаторика, геометрия,, 94.05kb.
• Программа дисциплины Спецкурс «Многообразия флагов»  для направления 010100. 62 «Математика», 96.12kb.
• Программа дисциплины Спецкурс «Дополнительные главы теории чисел 2»  для направления, 149.76kb.
• Программа дисциплины Спецкурс «Дополнительные главы теории чисел 1»  для направления, 137.49kb.
• Программа дисциплины Спецкурс «Алгебраические кривые: по направлению к пространствам, 109.55kb.
• Программа дисциплины Дифференциальная геометрия и общая теория относительности  для, 218.93kb.
• Программа дисциплины История математики для направления 010100. 62 «Математика», 176.36kb.

Аннотация

программы учебной дисциплины «Теория графов»

для направления 010100.62 «Математика»

профиль «Вычислительная математика и информатика»


Общее количество часов – 144 ч. (4 зачетные единицы)

1. Цель и задачи дисциплины
   

Цель изучения дисциплины:

– формирование у студентов теоретических и методологических основ теории графов.

Задачи изучения дисциплины:

– расширение сферы компетенции студентов в теории графов;

– овладение студентами понятийно-терминологическим аппаратом теории графов;

– овладение приемами применение теории графов к решению прикладных задач.

2. Требования к уровню освоения содержания дисциплины
   

Процесс изучения дисциплины направлен на формирование следующих компетенций:

Общекультурные компетенции (ОК):

способность применять знания на практике (ОК-6);

умение находить, анализировать и контекстно обрабатывать научно-техническую информацию (ОК-10);

навыки работы с компьютером (ОК-12);

базовые знания в областях информатики и современных информационных технологий, навыки использования программных средств и навыки работы в компьютерных сетях, умение создавать базы данных и использовать ресурсы Интернет (ОК-13).


Профессиональные компетенции (ПК):

определение общих форм, закономерностей и инструментальных средств отдельной предметной области (ПК-1);

самостоятельное построение алгоритма и его анализ (ПК-11);

глубокое понимание сути точности фундаментального знания (ПК-13);

владение методом алгоритмического моделирования при анализе постановок математических задач (ПК-19);

владение методами математического и алгоритмического моделирования при анализе теоретических проблем и задач (ПК-21);

владение проблемно-задачной формой представления математических знаний (ПК-22);

владение проблемно-задачной формой представления естественнонаучных знаний (ПК-23);

умение самостоятельно математически корректно ставить естественно-научные и инженерно-физические задачи (ПК-25);

обретение опыта самостоятельного различения типов знания (ПК-26).


В результате изучения дисциплины студент должен:

иметь базовые знания в области теории графов (определение графа, виды графов, способы задания графов, раскраска графов, циклы и пути в графах, алгоритмы на графах), необходимые для успешного изучения математических и теоретико-информационных дисциплин, решения задач, возникающих в профессиональной сфере; экономических и физических задач; задач, возникающих в информатике.

уметь: формулировать и доказывать теоремы, применять методы теории графов для решения математических задач, построения и анализа моделей экономики, физики и информатики, самостоятельно решать классические задачи.

владеть: навыками практического использования современного математического инструментария для решения и анализа задач экономики, физики и информатики.

3. Содержание дисциплины. Основные разделы
   

История возникновения и развития теории графов: задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой.

Основные понятия и определения:

– понятие графа, основные определения (вершины, ребра, дуги, ориентированные и неориентированные графы, простой граф, петли, кратные ребра, виды графов, подграфы и дополнения, операции над графами и т.д.);

– маршруты, цепи, пути, циклы;

– связность, компоненты связности.

Эйлеровы и гамильтоновы графы: эйлеров путь, эйлеров цикл, гамильтонов путь, гамильтонов цикл.

Планарность графов, деревья:

– планарные графы, формула Эйлера, критерий планарности;

– понятие дерева, характеризация деревьев, алгоритм построения.

Раскраска: раскраска графов, вершинная k-раскраска, задача о раскрашивании карт, ее связь с вершинной раскраской графа.

Представление графов в компьютере: матрица смежности, матрица инцидентности, списки смежности.

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

– обходы графов (в ширину и глубину (рекурсивная и нерекурсивная реализация));

– алгоритмы, основанные на алгоритмах обхода (нахождение компонент связности, поиск кратчайших путей);

– алгоритмы нахождения кратчайших путей от выделенной вершины (алгоритм Форда-Беллмана, Дейкстры, алгоритм Флойда).

Потоки в сетях: понятие сети, понятие потока в сети, алгоритм Форда-Фолкерсона для сети с одним источником и одним стоком.