Примерный вариант экзаменационной работы
Описание файла
PDF-файл из архива "Примерный вариант экзаменационной работы", который расположен в категории "". Всё это находится в предмете "дискретные модели" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Примерный вариант экзаменационной работыЗадача 1 (3 балла). Доказать равенство ∼ (x̄ · ȳ) = (∼ x) · ȳ.Задача 2 (3 балла). Подсчитать число попарно неизоморфных деревьев, в которыхровно 6 ребер и ровно 3 висячие вершины. Изобразить все такие деревья.Задача 3 (3 балла). Выяснить, задается ли полиномом по модулю 4 функция f (x) =J0 (x) + 3J3 (x) ∈ P4 .
Ответ обосновать.Задача 4 (3 балла). Какое наименьшее число ребер надо удалить из полного графа K5 ,чтобы вершины оставшегося графа можно было раскрасить в 4 цвета? Изобразить этотчетырехцветный граф и раскраску его вершин.Задание 5 (3 балла). Дать определение числа Рамсея R(m, n). Чему равно числоR(m, 1)?Задание 6 (3 балла). Сформулировать теорему о представлении функций k-значнойлогики во 2-й форме. Записать во 2-й форме функцию f (x) = min(3x2 , 2x3 ) ∈ P5 .Задание 7 (3 балла).
Сформулировать теорему о числе остовных деревьев полногопомеченного графа. Восстановить остовное дерево полного графа K5 по коду этого дерева(1, 4, 4).Задание 8 (3 балла). Сформулировать теорему о наибольшем числе ребер в графе сp вершинами без треугольников. Изобразить граф с 7 вершинами без треугольников и снаибольшим числом ребер.Задание 9 (4 балла). Сформулировать и доказать теорему Янова.Задание 10 (4 балла). Задается ли полиномом по модулю 36 функцияf (x, y) = 24x2 y 3 + 5J15 (x) ∈ P36 ?Ответ обосновать..
