Контрольная и Лабораторные работы 1-3 по дисциплине: Дискретная математика. Вариант №20

Вариант No20

Контрольная работа

No1 Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна. а) A\((AB)(AC)) = (A\B)\C  б) (AB)(CB) = (AC)B.

No2 Даны два конечных множества: А={a,b,c}, B={1,2,3,4}; бинарные отношения P1 AB, P2 B2. Изобразить P1, P2 графически. Найти P = (P2P1)–1. Выписать области определения и области значений всех трех отношений: P1, P2, Р. Построить матрицу [P2], проверить с ее помощью, является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным. P1 = {(a,2),(a,4),(a,3),(c,1),(c,2),(c,3)}; P2 = {(1,1),(1,4),(2,3),(3,3),(4,1),(4,3),(4,4)}.

No3 Задано бинарное отношение P; найти его область определения и область значений. Проверить по определению, является ли отношение Pрефлексивным, симметричным, антисимметричным, транзитивным.
P Z2, P = {(x,y) | y x – 2}.

No4 Доказать утверждение методом математической индукции: 13 + 23 + 33 + ... + n3 = n2·(n+1)2/4.

No5 Бригада из восьми взломщиков одновременно выходит на грабеж трех разных магазинов. Сколькими способами они могут разделиться, если в каждой группе должно быть не менее 2 человек? Сколькими способами их после задержания могут рассадить по четырем одинаковым камерам (не менее чем по одному в каждую)?

No6 Сколько существует положительных трехзначных чисел: а) делящихся на числа 9, 21 или 30? б) делящихся ровно на одно из этих трех чисел?

No7 Найти коэффициенты при a=x2·y6·z2, b=x4·y·z, c=x4·y8 в разложении (5·x2+2·y2+3·z)6.

No8 Найти последовательность {an}, удовлетворяющую рекуррентному соотношению an+2 – 3·an+1 – 28·an = 0 и начальным условиям a1=15, a2=17.

No9 Орграф задан матрицей смежности. Необходимо:  
а) нарисовать граф;  
б) выделить компоненты сильной связности;  
в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл). 1
0
1
1
0
1 0
0
0
0
0
1 1
0
0
1
0
1 1
0
0
0
0
0 0
0
1
1
1
1 0
0
1
0
1
0

No10 Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса;  
б) кратчайшее расстояние от вершины v2 до остальных вершин графа, используя алгоритм Дейкстры.

=============================================
=============================================

Лабораторная работа 1

Отношения и их свойства
Бинарное отношение R на конечном множестве A: RA2 – задано списком упорядоченных пар вида (a,b), где a,bA. Требования на множество – в нём не должно встречаться повторяющихся элементов, кроме того, оно должно быть упорядочено по возрастанию. Если введённое пользователем множество не соответствует этим требованиям, программа должна автоматически привести его к необходимому виду. Программа должна построить матрицу бинарного отношения и определить его свойства: ре-флексивность, антирефлексивность, симметричность, антисимметричность, транзитивность (по ма-териалам главы 1, п.1.3). Проверку свойств выполнять по матрице, сопровождая необходимыми по-яснениями.
Работа программы должна происходить следующим образом:
1. На вход подаётся множество A из n элементов и список упорядоченных пар, задающий отношение R (мощность множества, элементы и пары вводятся с клавиатуры).
2. Результаты выводятся на экран (с необходимыми пояснениями) в следующем виде:  
а) матрица бинарного отношения размера nn; 
б) список свойств данного отношения.
В матрице отношения строки и столбцы должны быть озаглавлены (элементы исходного мно-жества, упорядоченного по возрастанию).
3. После вывода результатов предусмотреть возможность изменения заданного бинарного отноше-ния либо выхода из программы.
Это изменение может быть реализовано различными способами. Например, вывести на экран список пар (с номерами) и по команде пользователя изменить что-либо в этом списке (удалить какую-то пару, добавить новую, изменить имеющуюся), после чего повторить вычисления, вы-брав соответствующий пункт меню. Другой способ – выполнять редактирование непосредствен-но самой матрицы отношения, после чего также повторить вычисления. Возможным вариантом является автоматический пересчёт – проверка свойств отношения – после изменения любого элемента матрицы.
Дополнительно: предусмотреть не только изменение отношения, но и ввод нового множества (размер нового множества может тоже быть другим).

=============================================

Лабораторная работа 2

Генерация подмножеств
Задано целое положительное число n, которое представляет собой мощность некоторого множества. Требуется с минимальными трудозатратами генерировать все подмножества этого множества, для чего каждое последующее подмножество должно получаться из предыдущего путем добавления или удаления только одного элемента. Множество и все его подмножества представляются битовой шкалой. Для генерации использовать алгоритм построения бинарного кода Грея.
В качестве результата выводить построчно каждое из подмножеств (в виде битовой шкалы), сопровождая их порядковыми номерами. В случае большого количества результирующих строк (превышающего размер экрана) выполнять поэкранную выдачу, а также осуществлять их вывод в файл с выдачей на экран сообщения для пользователя – имя файла, его местонахождение...
Алгоритм построения бинарного кода Грея
Вход: n 0 – мощность множества.
Выход: последовательность кодов подмножеств B (битовая шкала).
1. Инициализация массива В и его выдача на печать.
2. В цикле по i (от 1 до 2 n –1):
 а) Определение элемента для добавления или удаления: p:=Q(i);
 б) Добавление или удаление элемента B[p]:=1–B[p];
 в) Вывод очередного подмножества – массива B.
Функция Q(i) определяется как число, на единицу превышающее количество «2» в разложении числа i на множители. Очевидно, что для нечётных i значение этой функции равно 1, т.е. для нечётного i значение будет менять крайний правый бит шкалы (нумерация справа налево от 1), а для i, равных степени 2, будет «включаться» бит, соответствующий этой степени 2 (например, для 4 – 3-й бит, для 8 – 4-й бит, ...).
Пример: Выполнение алгоритма для n=3. Дополнительно: множество {a,b,c}.
i p  B   Дополнительно множества
  0 0 0   
1 1 0 0 1   {с}
2 2 0 1 1   {b,c}
3 1 0 1 0   {b}
4 3 1 1 0   {a,b}
5 1 1 1 1   {a,b,c}
6 2 1 0 1   {a,c}
7 1 1 0 0   {a}
Дополнительно:
Предоставить пользователю возможность задать исходное множество путём перечисления его элементов. Упорядочить это множество, сопоставить ему битовую шкалу. При выводе каждой строки битовой шкалы на экран в той же строке указывать конкретное подмножество, соответствующее этой шкале.

=============================================

Лабораторная работа 3

Поиск компонент связности графа

Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е. изменять исходный граф без выхода из программы. Предусмотреть также возможность изменения количества вершин.
При выполнении работы разрешается (даже рекомендуется!) использовать матрицу бинарных отношений из лабораторной работы No1.
Вход программы: число вершин графа и матрица смежности.
Выход: разбиение множества вершин на подмножества, соответствующие компонентам связности.
Дополнительно:
Заданный граф рассматривать как ориентированный. Выполнять поиск компонент сильной связности.

=============================================

Оценка: Отлично
Дата оценки: 07.10.2023г.

Помогу с вашим вариантом, другой работой, дисциплиной или онлайн-тестом.
E-mail: sneroy20@gmail.com
E-mail: ego178@mail.ru