Решение задач на тему "Готовые ответы на задания 1-7 | Дискретная математика ВШП"

Готовые ответы на задания. Задание было сдано и зачтено преподавателем в 2024 году. Ответ будет представлен в формате Word

Описание работы

Задание №1. (2 балла) Если A = {2,3,4,5,6,7,8} запишите бинарное отношение R = {(x,y) | x, y ? A, где x ? y}.
Задание №2. (2 балла) Доказать, что 43101+23101 делится на 66.
Задание №3. (2 балла) Решить уравнение в целых числах: 13x + 7y = 1.
Задание №4. (2 балла) Пусть U — множество всех действительных чисел. Постройте множество истинности для каждого из следующих предикатов: a) 2?25=0x2?25=0; b) 2+25=0x2+25=0; c) x2?6x+9=0.
Задание №5. (2 балла) Предикат P(x): «x есть простое число»; предикат Q(x): «x есть действительное число»; предикат T(x): «x меньше y». Запишите утверждение «для каждого числа x существует такое число y, что x меньше y», используя кванторы.

Задание №6. (4 балла) Задача Эйлера «О кёнигсбергских мостах»: в восемнадцатом веке город Кёнигсберг располагался на двух берегах реки Преголя, имеющей два острова, соединенных с берегами и между собой семью мостами. Можно ли пройти по всем семи мостам так, чтобы на каждом из них побывать по одному разу и вернуться к началу пути? Изобразите граф к решению задачи.

Задание №7.
(6 баллов) Классифицировать перечисленные ниже задачи по сложности (полиномиальные, экспоненциальные, NP-трудные, NP-полные):
а) сортировка чисел;
6) перечисление всех перестановок для и элементов множества;
в) нахождение эйлерова цикла в графе;
г) нахождение гамильтонова цикла в графе;
д) перечисление всех наборов переменных логической функции от п переменных;
е) нахождение минимального покрытия (столбцов строками) для бинарной матрицы; ж) поиск на графе в ширину;
3) поиск на графе в глубину;
и) задача коммивояжера;
к) вычисление n-го числа Фибоначчи;
л) определение хроматического числа графа;
м) определение цикломатического числа графа.