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

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

Реферативная работа включает:

1. Изложение теории по теме.

2. Изложение содержательных примеров по теме (применение алгоритмов для решения конкретных задач).

Содержание реферативной работы и ее объем согласовывается с преподавателем на консультациях.

Защита реферативной работы является необходимым условием получения баллов.

Реферативная работа оценивается по следующим критериям:

1) Полнота и качество изложения теоретического материала по теме.

2) Полнота и качество изложения содержательных примеров по теме.

3) Понимание изложенного материала (выявляется в процессе защиты реферативной работы).

Комплект КИМ к коллоквиуму (экзамену) модуля 2

Вопросы к коллоквиуму (экзамену)

Для подготовки к сдаче экзамена по модулю 2 на базовом уровне вместо списка вопросов студенту выдается программа промежуточной аттестации курса «Дискретная математика», Модуль 2 «Теория графов». Задания билета составляются в точном соответствии с этой программой и базовыми частями лекций (в свою очередь написанными в точном соответствии с этой программой). Электронные варианты лекций выдаются студентам в начале изучения модуля. При сдаче коллоквиума на базовом уровне проверяется знание теоретических фактов, способность иллюстрировать теоретические понятия и утверждения на примерах, а также умение решать типовые упражнения, аналогичные тем, которые приведены в электронном варианте лекций.

Для подготовки к сдаче коллоквиума по модулю 2 на повышенном уровне студенту выдается: (а) программа промежуточной аттестации курса повышенного уровня «Дискретная математика», Модуль 2 «Теория графов», (б) список вопросов, составленный в соответствии рабочей программой курса повышенного уровня «Дискретная математика», Модуль 2 «Теория графов».

Вопросы к коллоквиуму по курсу «Дискретной математики», Модуль 2

1. Неориентированный граф: определение, элементы, локальные характеристики. Диаграмма графа. Лемма о рукопожатиях. Изоморфные графы. Обыкновенные, полные, двудольные графы. Матрицы смежности и инцидентности неориентированного графа. Подграфы, виды подграфов. Операции над графами: пересечение, объединение, удаление вершины, удаление ребра. Дизъюнктное разбиение графа.
2. Пути, цепи и циклы на графе. Лемма о простой цепи. Отношение достижимости. Компоненты связности. Число связности графа.
3. Мосты и циклы графа. Теорема о мостах. Теорема о мостах и циклах.
4. Цикломатическое число графа. Теорема о знаке цикломатического числа.
5. Определение и основные свойства деревьев. Теорема о характеристических свойствах деревьев. Следствие их нее. Понятие о лесе.
6. Остовы графа. Число остовов обыкновенного графа. Отыскание числа остовов с помощью матрицы Кирхгофа.
7. Минимальный остов. Задача о построении минимального остова. Алгоритм Краскала (без доказательства).
8. Кодирование деревьев. Бинарный код и код из натуральных чисел (кодирование и декодирование).
9. Укладки графов в трехмерном пространстве и на плоскости. Планарные графы. Теорема о плоских графах. Формула Эйлера для плоских графов.
10. Доказательство непланарности графов и . Критерии планарности (без доказательства).
11. Обходы графов. Эйлеров цикл и эйлерова цепь на графе. Критерии существования эйлерового цикла и эйлеровой цепи на графе (теорема об эйлеровых циклах, теорема об эйлеровых цепях). Алгоритм построения эйлерового цикла и эйлеровой цепи на графе. Понятие о гамильтоновом цикле и гамильтоновой цепи.
12. Раскраска графов. Хроматическое число. Утверждения о хроматических числах графа. Критерий бихроматичности графа.
13. Фундаментальная система циклов: пространство циклов графа, базис пространствоа циклов. Алгоритм построения фундаментальной системы циклов.
14. Ориентированные графы: определение, элементы. Изоморфные орграфы. Матрицы смежности и инцидентности ориентированных графов. Ориентированные пути, цепи, циклы на орграфе. Связные и сильно связные орграфы. Ориентированные деревья.
15. Задача о поиске кратчайших путей в сети. Алгоритм Дейкстры.
16. Потоки в сетях. Постановка задачи о поиске максимального потока. Алгоритм Форда-Флакерсона. Его обоснование: три леммы и теорема Форда-Фалкерсона.
17. Схемы из функциональных элементов в базисе . Реализация булевых функций с помощью схем из функциональных элементов.
18. Упорядоченная бинарная диаграмма решений. Сложность УБДР. Минимальная УБДР. Построение минимальных УБДР функции относительно заданного порядка переменных: правило удалении вершин, правило слияния, сокращенная УБДР, алгоритм построения сокращенной УБДР. Построение сокращенной УБДР по формулам.