96

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

ID: 206154
Дата закачки: 21 Января 2020
Продавец: nik200511 (Напишите, если есть вопросы)
    Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Word, TurboPascal
Сдано в учебном заведении: ДО СИБГУТИ

Описание:
Лабораторная работа 1.

Отношения и их свойства

Бинарное отношение R на конечном множестве A: RA2 – задано списком упорядоченных пар вида (a,b), где a,bA. Требования на множество – в нём не должно встречаться повторяющихся элементов, кроме того, оно должно быть упорядочено по возрастанию. Если введённое пользователем множество не соответствует этим требованиям, программа должна автоматически привести его к необходимому виду. Программа должна построить матрицу бинарного отношения и определить его свойства: рефлексивность, антирефлексивность, симметричность, антисимметрич-ность, транзитивность (по материалам главы 1, п.1.3). Проверку свойств выполнять по матрице, сопровождая необходимыми пояснениями.
Работа программы должна происходить следующим образом:
1. На вход подаётся множество A из n элементов и список упорядоченных пар, задающий отноше-ние R (мощность множества, элементы и пары вводятся с клавиатуры).
2. Результаты выводятся на экран (с необходимыми пояснениями) в следующем виде:  
а) матрица бинарного отношения размера nn; 
б) список свойств данного отношения.
В матрице отношения строки и столбцы должны быть озаглавлены (элементы исходного мно-жества, упорядоченного по возрастанию).
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).
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е. изменять исходный граф без выхода из программы. Предусмотреть также возможность изменения количества вершин.
При выполнении работы разрешается (даже рекомендуется!) использовать матрицу бинарных отношений из лабораторной работы №1.
Вход программы: число вершин графа и матрица смежности.
Выход: разбиение множества вершин на подмножества, соответствующие компонентам связности.
Дополнительно:
Заданный граф рассматривать как ориентированный. Выполнять поиск компонент сильной связности.



Комментарии: май 2019, зачтено без замечаний

в программе указано имя автора

Размер файла: 187,7 Кбайт
Фаил: (.rar)
-------------------
Обратите внимание, что преподаватели часто переставляют варианты и меняют исходные данные!
Если вы хотите, чтобы работа точно соответствовала, смотрите исходные данные. Если их нет, обратитесь к продавцу или к нам в тех. поддержку.
Имейте ввиду, что согласно гарантии возврата средств, мы не возвращаем деньги если вариант окажется не тот.
-------------------

Скачать

Добавить в корзину

Занесено в корзину

    Скачано: 51         Коментариев: 0

Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них.
Опять не то? Мы можем помочь сделать!

Некоторые похожие работы:

Лабораторные работы №1,2,3 по дисциплине: Дискретная математика. Для всех вариантов
Дискретная математика. Лабораторная работа 1 (2019). Для всех вариантов.
Дискретная математика. Лабораторная работа 3 (2019). Для всех вариантов.
Дискретная математика. Лабораторная работа 2 (2019). Для всех вариантов.
Дискретная математика. Лабораторные работы №№1-5. Для всех вариантов.
Дискретная математика. Лабораторные работы №1-5. Вариант №5.(подходит для всех вариантов)
Ещё искать по базе с такими же ключевыми словами.