ТЕМЫ ДИСКРЕТКА

Лектор – Олейник Т.А.

Информация о процедуре проведения и содержании экзамена по ДМ в

2022-23 уч. г.

1. Порядок проведения экзамена

Экзамен проводится в очной форме. Порядок проведения экзамена следующий. Студент готовит в письменной форме ответы к заданиям (время подготовки 60), после чего преподаватель проверяет написанное и устно беседует со студентом.

2. Структура билета и оценивание

Билет экзамена состоит из двух частей.

Часть 1 - практическая (на умение решать типовые задачи). Она состоит из двух задач (см. образец экзаменационного билета), а именно:

Задача 1 на свойства бинарных отношений и представление бинарных отношений ориентированными графами.

Задача 2 на представление булевых функций схемами функциональных элементов. Часть 2 – теоретическая. Она состоит из четырех вопросов.

Приответенапервыетривопросатребуетсясформулироватьопределения,привести формулировки утверждений и иллюстрирующие примеры.

При ответе на четвертый вопрос требуется доказать какое-либо теоретическое утверждение.

Требуемый объем и глубина изложения материала соответствуют текстам лекций, размещенным в ресурсах дисциплины в ОРИОКС (или, что то же, в электронном курсе Moodle «ВМ-1 - Дискретная математика (01.03.04, #807)»), а также видео лекциям Олейник Т.А.

Первые три вопроса включают материал, который изложен в текстах лекций в разделах «Базовые понятия и утверждения». Четвертый вопрос включает материал, который изложен в текстах лекций в разделе «Теоретические обоснования и примеры».

Вопрос 1 формулируется в рамках одной из тем 3-7 (нумерация тем та же, что и в семестровом плане, и в электронном курсе Moodle).

Вопрос 2 формулируется в рамках одной из тем 8 -12. Вопрос 3 формулируется в рамках одной из тем 13 -16.

Вопрос 4 формулируется в рамках одной из тем, затронутых в первых трех вопросах Ниже в таблице приведено максимальное число баллов, которое можно получить за

выполнение заданий:

Ниже приводится образец билета экзамена. После него приведена дополнительная информация по содержанию второй части билета.

1

Лектор – Олейник Т.А.

3. Образец экзаменационного билета

по курсу «Дискретная математика»

Часть I

1. Пусть A 1,2,3,4 . Задать с помощью графа бинарное отношение , заданное на множестве A условием x y 3x 2y (изобразить диаграмму, выписать матрицу смежности). Является ли отношение рефлексивным, симметричным, антисимметричным, транзитивным, отношением эквивалентности, отношением порядка?

2. Построить схему из функциональных элементов , , , реализующую функцию f (x, y,z) (x yz) (x z).

Часть II

1. Сформулируйте определение функции, двойственной данной. Используя определение, найдите двойственные функции ко всем функциям одной переменной. Сформулируйте принцип двойственности для формул над произвольной системой функций. Задайте формулой какую-нибудь функцию f над множеством , , ,0 (в

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

2. Какой подграф графа называется остовом? Что такое матрица Кирхгофа? Как с помощью этой матрицы найти число остовов в связном неодноэлементном обыкновенном графе с занумерованными вершинами? Найдите с помощью матрицы Кирхгофа число остовов, а также изобразите сами остовы для графа G с вершинами v1,v2,v3 и ребрами

e1 v1v2 , e2 v1v3 , e3 v2v3 .

3.Что такое поток в сети? Что называют величиной потока? Какой поток называют максимальным? Что называют разрезом в сети. Что такое пропускная способность разреза? Какой разрезназываютминимальным?Изобразитепроизвольную сеть содним источником

иодним стоком. Задайте на этой сети какой-нибудь поток, укажите величину этого потока. Задайтенаэтой сетикакой-нибудьразрезинайдитепропускнуюспособность этогоразреза.

4.Докажите Лемму 1 о связи между величиной потока в сети и величинами потоков, текущих через разрез.

4. Темы теоретических вопросов к экзамену по ДМ

(с подробной расшифровкой)

Тема 3. Булевы функции и способы их задания. Булев вектор. Функции алгебры логики

(булевы функции). Задание булевых функций таблицей истинности и вектором значений. Элементарные булевы функции одной и двух переменных. Формулы над множеством

2

Лектор – Олейник Т.А.

функций, задание функций формулами, равносильные формулы. Доказательство равносильности формул с использованием таблиц истинности. Основные равносильности над множеством { , ,¬,0,1}. Упрощение формул методом равносильных преобразований. Фиктивные и существенные переменные, равные функции, алгоритм удаления и введения фиктивных переменных.

Тема 4. Представление булевых функций формулами специального вида.

Двойственная функция. Принцип двойственности. Разложение булевой функции по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ). Совершенная конъюнктивнаянормальнаяформа(СКНФ).Представлениебулевой функции ввидеСДНФ и СКНФ. Полином Жегалкина, представление булевой функции полиномом Жегалкина.

Тема 5. Минимизация дизъюнктивных нормальных форм. Элементарная конъюнкция,

ранг элементарной конъюнкции. Дизъюнктивная нормальная форма (ДНФ), сложность ДНФ. Минимальная ДНФ. Импликанта, простая импликанта. Сокращенная ДНФ. Тупиковая ДНФ. Представление булевой функции в виде сокращенной, тупиковой и минимальной ДНФ.

Тема 6. Классы Поста и замыкание. Функции, сохраняющие 0. Функции, сохраняющие 1. Самодвойственные функции. Монотонные функции. Линейные функции. Классы Поста. Замыкание системы булевых функций.

Тема 7. Полнота системы булевых функций. Понятие полной системы. Теорема о полноте двух систем. Лемма о функции, сохраняющей 0. Лемма о функции, сохраняющей 1. Лемма о самодвойственной функции. Лемма о монотонной функции. Критерий полноты системы булевых функций (теорема Поста). Базисы.

Тема 8. Неориентированные графы: первичные понятия. Граф, его вершины и ребра.

Смежные вершины. Кратные ребра, петли. Инцидентные вершины и ребра. Степени вершин. Висячие и изолированные вершины. Лемма о рукопожатиях. Диаграмма графа. Изоморфные графы. Специальные виды графов: обыкновенные, полные, двудольные, полные двудольные графы. Матрица смежности и матрица инцидентности. Подграф. Операции над графами: объединение, пересечение, декартово произведение.

Тема 9. Циклы и мосты, цикломатическое число. Фундаментальная система циклов графа. Пути, цепи, циклы на графе. Отношение достижимости (связности), компоненты связности графа. Мосты графа, связь между мостами и циклами. Цикломатическое число графа. Линейное пространство циклов. Алгоритм построения фундаментальной системы циклов.

Тема 10. Деревья. Дерево, лес, их характеристические свойства. Остовы графа. Число остовов в графе с занумерованными вершинами. Алгоритм Краскала отыскания минимального остова. Кодирование деревьев.

Тема 11. Планарность. Укладка графов в трехмерном пространстве. Укладка графа на плоскости. Планарныеграфы. Связь между числом вершин, ребер и граней плоского графа. Гомеоморфные графы. Критерии планарности. Алгоритм укладки графа на плоскости.

Тема 12. Обходы графов. Эйлеровы цикл и цепь, критерии их существования. Алгоритм построения эйлерова цикла. Гамильтоновы цикл и цепь. Задача коммивояжера. Раскраска графов. Раскраска графа. Хроматическое число графа. Критерий бихроматичности. Раскраска плоских графов.

Тема 13. Ориентированные графы: первичные понятия. Ориентированный граф

(орграф). Диаграмма орграфа. Изоморфные орграфы. Матрицы смежности и

3

Лектор – Олейник Т.А.

инцидентности орграфа. Ориентированные пути, цепи, циклы. Слабая и сильная связность. Орграф и его элементы. Изоморфные орграфы. Матрицы смежности и инцидентности орграфа. Пути, цепи, циклы на орграфе. Слабая и сильная связность орграфа. Понятие ориентированного дерева. Графы и бинарные отношения.

Отыскание кратчайших путей на графе. Постановка задачи об отыскании кратчайших путей в сети. Алгоритм Дейкстры, его обоснование.

Тема 14. Задача о максимальном потоке в сети. Сеть. Поток в сети. Величина потока.

Максимальный поток. Дополняющая цепь. Разрез в сети. Минимальный разрез. Алгоритм Форда – Фалкерсона. Обоснование алгеритма (Леммы 1,2,3 и теорема Форда-Фалкерсона).

Тема 15. Паросочетания в двудольных графах. Алгоритм поиска в ширину на ориентированных графах. Паросочетания: наибольшее, максимальное, совершенное. Задача о поиске наибольшего парососчетания в двудольном графе: постановка и алгоритм решения задачи. Задача о поиске совершенного паросочетания минимального веса (задача о назначениях): постановка и алгоритм решения задачи.

Тема 16. Схемы их функциональных элементов. Схема из функциональных элементов.

Входы, функциональные элементы, выходы схемы. Сложность схемы. Глубина вершины. Функции, реализуемые в вершинах схемы. Функции, реализуемые схемой. Проблема анализа и проблема синтеза схем.

Упорядоченная бинарная диаграмма решений. Упорядоченная бинарная диаграмма решений (УБДР). Сток, внутренняя вершина. Сложность УБДР. Минимальная УБДР. Сокращенная УБДР. Правило сокращения. Правило слияния. Построение сокращенной УБДР для функции, заданной таблицей и формулой.

4