Решение задач «Решить 3 темы (в каждой по 3-5 задач)»,
Дискретная математика в Санкт-Петербурге

ВАРИАНТ 7 (смотрите в файле) 1. «ТЕОРИЯ МНОЖЕСТВ» Постановка задачи: 1. Изобразить множества на диаграмме Эйлера-Венна 2. Определить, какими свойствами обладают соответствия, и привести содержательные примеры. 3. Определить, какими свойствами обладают отношения, и объяснить почему. Является ли это отношение отношением порядка? Отношением эквивалентности? 4. Для заданных частично-упорядоченных множеств найти минимальный, максимальный, наименьший, наибольший элементы, а также sup(B) и inf(B). 2. «АЛГЕБРА ЛОГИКИ» Постановка задачи: 1. Доказать что функции являются (или не являются) тавтологиями. Использовать два способа (с помощью таблицы истинности и с помощью законов алгебры логики). 2. Для заданного выражения найти СКНФ и СДНФ. Использовать два способа (с помощью таблицы истинности и с помощью законов алгебры логики). 3. Для заданного выражения найти МДНФ. Использовать два способа (с помощью метода Квайна и с помощью карт Вейча-Карно ). 3. «ГРАФЫ» Постановка задачи: 1. Упорядочить элементы орграфа (привести к ярусно параллельной форме) В отчете привести исходный граф, матрицу смежности вершин, упорядоченный граф. 2. Определить ядро для орграфа. В отчете привести исходный граф, матрицу смежности вершин, решение с указанием множеств вершин внутренней и внешней устойчивости, ядра графа. Объяснить полученные результаты. 3. Определить клику для неориентированного графа. Для определения клики взять граф из задания 2 , не учитывая направления дуг. В отчете привести исходный граф, матрицу смежности вершин, решение c указанием множеств вершин, образующих клику графа. Объяснить полученные результаты. 4. Найти минимальный путь в графе от а до f или g (в зависимости от числа вершин), используя метод Дейкстры. В отчете привести исходный граф, матрицу смежности вершин с метками, решение с указание длины пути. 5. Найти минимальный по весу остов. В отчете привести исходный граф, матрицу смежности вершин, решение, остов графа.