Лабораторные работы №№1-5 по дисциплине: Дискретная математика. Вариант №2 (2-й семестр)

Лабораторная работа No1
Задание
Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции (, , , \\) с помощью алгоритма типа слияния. Допустима организация множеств в виде списка или в виде массива.
Работа программы должна происходить следующим образом:
1. На вход подаются два упорядоченных множества A и B (вводятся с клавиатуры, элементы множеств – буквы латинского алфавита).
2. После ввода множеств выбирается требуемая операция (посредством текстового меню, вводом определенного символа в ответ на запрос – выбор по желанию автора). Операции: вхождение AB, AB, AB, A\\B (дополнительно: B\\A, AB, BA).
3. Программа посредством алгоритма типа слияния определяет результат выбранной операции и выдает его на экран с необходимыми пояснениями. Одновременно с результатом на экране должны присутствовать и исходные множества.
4. Возврат на п.2 (выбор операции).
5. Завершение работы программы – из п.2 (например, по ESC).

Постановка задачи
Необходимо разработать программу, реализующую основные операции над множествами: объединение, пересечение, разница и симметричная разница.
За основу программы взять меню с выбором пункта нажатием клавиши. При вводе множества произвести проверку на принадлежность символов латинскому алфавиту, также исключить повторы. После ввода множества необходимо отсортировать.
Процедуры операций над множествами организовать на основе алгоритма типа слияния множеств.

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

Постановка задачи
Необходимо написать программу, определяющую свойства бинарного отношения на множестве A: RA2
Для этого необходимо разработать процедуры: ввода множества A, его сортировки, ввода множества R заданное списком упорядоченных пар. Для вычисления свойств разработать процедуры проверки матрицы бинарного отношения на рефлексивность, симметричность, антисимметричность, транзитивность.
Работу программы организовать с помощью меню, в котором необходимо предусмотреть следующие операции: ввод списка упорядоченных пар, вывод свойств отношения, добавление пары, удаление пары, выход из программы.

Лабораторная работа No3
Задание
Дано конечное множество A. Требуется сгенерировать все возможные перестановки его элементов в лексикографическом порядке. Требования к заданию множества – в нем не должно быть повторяющихся элементов, кроме того, удобнее использовать или только буквы, или только цифры.
Программа должна сначала упорядочить все элементы заданного множества по возрастанию (это первый – минимальный – набор), затем – посредством МИНИМАЛЬНО ВОЗМОЖНЫХ ПЕРЕСТАНОВОК! – сгенерировать последовательно возрастающие (лексикографически) наборы, вплоть до последнего, в котором все элементы упорядочены по убыванию.
Следует оценивать количество возможных перестановок и в случае, если они не поместятся на экран, выполнять их вывод в файл с выдачей на экран соответствующей информации для пользователя и выполнять поэкранный вывод с ожиданием нажатия клавиши.

Постановка задачи
Необходимо разработать программу, генерирующую перестановки множества. Мощность множества задается пользователем, таким образом нужно предусмотреть работу с динамическим массивом.
Процедуру перестановки реализовать по следующему алгоритму:
1) Выполняется проверка последнего (m-го) набора на наличие в его конце некоторого количества символов, упорядоченных по убыванию – пусть это символы ak+1...an.
Например: 3 5 2 6 4 1≥ – k=3, символы с 4-го по 6-й упорядочены по убыванию.
2) Если такое k найдено, то поменять местами k-й элемент и наименьший элемент из ak+1...an, больший этого ak.
В нашем примере это 2 и 4: 3 5 4 6 2 1≥ (это промежуточный набор).
3) После шага 2 упорядочить элементы с k+1-го до последнего по возрастанию. Получен очередной набор выдать его на печать.
3 5 4 1 2 6≥.
4) Если на шаге 1 ответ отрицательный, то поменять местами 2 последних элемента и выдать на печать полученный набор. После шага 3 было 3 5 4 1 2 6≥ выдать 3 5 4 1 6 2≥.
5) Если полученный набор не последний (упорядоченный по убыванию), то возврат на шаг 1. В противном случае конец работы.

Лабораторная работа No4
Задание
Задано целое положительное число n, которое представляет собой мощность некоторого множества. Требуется с минимальными трудозатратами генерировать все подмножества этого множества, для чего каждое последующее подмножество должно получаться из предыдущего путем добавления или удаления только одного элемента. Множество и все его подмножества представляются битовой шкалой. Для генерации использовать алгоритм построения бинарного кода Грея.
В качестве результата выводить построчно каждое из подмножеств (в виде битовой шкалы), сопровождая их порядковыми номерами. В случае большого количества результирующих строк (превышающего размер экрана) выполнять поэкранную выдачу, а также осуществлять их вывод в файл с выдачей на экран сообщения для пользователя – имя файла, его местонахождение...

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

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

Постановка задачи
Для реализации поставленной задачи необходимо разработать следующие процедуры: описание графа (ввод кол-ва вершин, определение ребер); подсчет количества компонент связанности графа, перечисление всех вершин, входящих в компоненту; редактирование графа (добавление/удаление ребер, изменение кол-ва вершин).

Все работы успешно зачтены!
В архиве 5 отчетов + программа по каждой работе.
Преподаватель: Бах О. А.