Дискретная математика. Лабораторные работы №№1-5. Для всех вариантов.

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

Постановка задачи
Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции (È, Ç, Í, \) с помощью алгоритма типа слияния. Допустима организация множеств в виде списка или в виде массива.
Работа программы должна происходить следующим образом:
1.На вход подаются два упорядоченных множества A и B (вводятся с клавиатуры, элементы множеств – буквы латинского алфавита)...
Описание входных данных программы и ее результатов
Входными данными являются конечные упорядоченные множества A и B. Множества хранятся в виде массива символов.
На вводе повторение символов допускается. Порядок символов произвольный. Ввод иных символов (не символов алфавита латиницы) считается ошибкой, о которой программа сообщает и требует нового ввода. Строчная и прописная буквы считаются одним и тем же символом (преобразуются в прописные при вводе).
После ввода множеств их элементы сортируются по возрастанию, повторяющиеся элементы удаляются...
Описание основных переменных, а также основных блоков и подпрограмм
Основные переменные:
A, B, C типа TSet – массивы символов (максимум до 50 элементов), A, B – исходные множества, С – результат операций объединения, пересечения, разности;
n, m, k типа integer – мощность множеств A, B, C.
В программе используются следующие функции...
Алгоритм решения задачи
Выводим на экран меню программы. Задаем начальные значения переменных n = m = 0.
На первом этапе программа предлагает ввести исходные множества A и В. При вводе проверяется ограничение элементов множества символами латинского алфавита. При этом не различается регистр букв, все элементы преобразуются в заглавные буквы. Если заданное множество содержит недопустимые элементы, предлагается ввести множество еще раз. Если все элементы входят в диапазон A..Z, массив сортируется по возрастанию, одинаковые элементы удаляются.
После ввода множеств A и В доступен выбор операции:
1 – ввести множества A и B (ввод новых множеств)...

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

Постановка задачи
Бинарное отношение R на конечном множестве A: RÍA2 – задано списком упорядоченных пар вида (a,b), где a,bÎA. Требования на множество – те же, что и раньше (в нем не должно встречаться повторяющихся элементов, кроме того, оно должно быть упорядочено по возрастанию). Программа должна определять свойства заданного отношения: рефлексивность, симметричность, антисимметричность, транзитивность. Проверку свойств выполнять по матрице бинарного отношения, сопровождая необходимыми пояснениями.
Работа программы должна происходить следующим образом:
1. На вход подается множество A из n элементов и список упорядоченных пар, задающий отношение R (мощность множества, элементы и пары вводятся с клавиатуры).
2. Результаты выводятся на экран (с необходимыми пояснениями) в следующем виде...
Описание входных данных программы и ее результатов
Входными данными является конечное упорядоченное множество A и список упорядоченных пар.
Мощность множества задается с клавиатуры и ограничена максимальным значением - 15 элементов.
При вводе элементов повторение символов допускается. Порядок символов произвольный. После ввода элементы сортируются по возрастанию, повторяющиеся элементы удаляются. Элементы свыше указанной мощности отбрасываются...
Описание основных переменных, а также основных блоков и подпрограмм
Основные переменные:
A типа TSet – массив символов (от 1 до 15 элементов) – исходное множество A;
num, n типа integer – мощность множества A,
m, S типа matrix – двухмерный массив (от 1 до 15 элементов) элементов типа byte – матрица бинарного отношения...
Алгоритм решения задачи
Вводим мощность множества A. Если она не превышает максимальное значение, предлагается ввести элементы множества. После ввода повторяющиеся элементы удаляются, элементы сортируются по возрастанию, лишние элементы отбрасываются. Элементы множества A выводятся на экран в упорядоченном виде.
Предлагается ввести список пар из элементов множества A, каждую пару в новой строке. Повтор пар не допускается.
Заканчивается ввод пар двойным нажатием Enter...

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

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

Лабораторная работа No 4.

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

Основные переменные:
B: TArray – массив элементов множества B / подмножеств (битовая шкала);
n – мощность множества B;
w: boolean – имеет значение true, когда производится запись в файл...

Алгоритм решения задачи
Алгоритм построения бинарного кода Грея:
Вход: n 3 0 – мощность множества.
Выход: последовательность кодов подмножеств B (битовая шкала).
1.Инициализация массива В и его выдача на печать.
2.В цикле по i (от 1 до 2 n –1):

Лабораторная работа No 5.

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

Описание основных переменных, а также основных блоков и подпрограмм
Основные переменные:
A: array of shortint – матрица смежности;
n: integer – количество вершин графа...

Алгоритм решения задачи
Для поиска компонент связности используется алгоритм обхода графа в глубину.
S[v] = true, если вершина уже была просмотрена, и false иначе.
(Изначально ни одна вершина еще не просмотрена, S[v] := false)...

Уважаемый слушатель, дистанционного обучения,
Оценена Ваша работа по предмету: Дискретная математика
Вид работы: Лабораторная работа
Оценка:Зачет
Дата оценки: .03.2013
Рецензия:Уважаемая
Бах Ольга Анатольевна