Кафедра информационных технологий, 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Кафедра информационных технологий,



ГОУВПО

“Воронежская государственная технологическая академия”

 

Кафедра информационных технологий,

Моделирования и управления

 

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические указания к лабораторным занятиям

по дисциплине "Математика",

раздел "Дискретная математика"

 

Для бакалавров,

Обучающихся по направлениям

230400 – "Информационные системы и технологии",

230700 – "Прикладная информацика"

Дневной и сокращенной формы обучения

 

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

СПОСОБЫ ЗАДАНИЯ И СВОЙСТВА БИНАРНЫХ ОТНОШЕНИЙ

Задание. Написать программу, которая строит матрицу бинарного отношения R варианта, определенного на множестве X и выводит её на печать. По построенной матрице:

a) построить срезы бинарного отношения для элементов, заданных в варианте;

b) проверить выполнение либо нарушение свойств бинарного отношения, заданных в варианте.

Построение среза бинарного отношения по элементу x оформить в виде процедуры, проверку свойства бинарного отношения – в виде функции, выдающей логический результат.

X = {2, 3, 5, 6, 7, 10, 12, 13, 14, 17, 18, 20} – для нечетных вариантов,

X = {1, 3, 4, 5, 6, 8, 9, 11, 12, 15, 16, 17, 18} – для четных вариантов.

 

Методические указания к выполнению работы.

Множество X,на котором задано бинарное отношение, определить как типизированную константу, являющуюся одномерным массивом, количество элементов множества – символьной константой. Построенное бинарное отношение и срезы варианта должны быть сохранены в двумерных массивах. Для возможности передачи массива и матрицы в качестве параметров в процедуру и функции определить соответствующие типы.

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

Параметрами-значениями этой процедуры должны быть номер элемента, для которого строится срез, и количество элементов множества; параметрами-константами – множество, на котором определено бинарное отношение, и матраца бинарного отношения; параметр-переменная – строящийся верхний или нижний срез. Например

procedure v_srez(k,n:byte; const X:mas; const R:matr; var G:matr);

В теле процедуры необходимо проверить k -ую строку (для нижних срезов) или k -ый столбец (для верхних срезов) матрицы бинарного отношения. Если элемент матрицы равен 1, то в матрицу срезов необходимо записать соответствующий элемент множества X. Заполнение матрицы срезов выполняется по строкам для любого среза, пропуски элементов в строке не допускаются, поэтому вводится счетчик элементов среза. На печать выводятся только построенные срезы, печать можно выполнять параллельно с заполнением матрицы срезов.

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

function refleks(const R:matr; n:byte):boolean;

Так как проверяемое свойство должно быть выполнено для всех элементов или пар элементов или троек элементов, то вначале результату функции присваивается значение true, а затем проверяется нарушение соответствующего свойства. Если условие нарушается хотя бы один раз, то функция принимает значение false.

 


Варианты заданий

1.

a) нижние срезы четных элементов;

b) антисимметричность и слабая полнота.

 

2.

a) верхние срезы элементов, номера которых четны;

b) асимметричность и полнота.

 

3.

a) нижние срезы элементов, номера которых нечетны;

b) антирефлексивность и негатранзитивность.

 

4.

a) верхние срезы нечетных элементов;

b) рефлексивность и транзитивность.

 

5.

a) нижние срезы элементов, кратных 3;

b) симметричность и полнота.

 

6.

a) верхние срезы элементов, номера которых являются удвоенными четными;

b) слабая полнота и транзитивность.

 

7.

a) нижние срезы элементов, номера которых кратны 3;

b) антисимметричность и негатранзитивность.

 

8.

a) верхние срезы элементов, которые являются удвоенными четными;

b) асимметричность, слабая полнота.

 

9.

a) нижние срезы элементов, не превышающих 10;

b) полнота, антисимметричность.

 

10.

a) верхние срезы элементов, номера которых являются удвоенными нечетными;

b) симметричность, рефлексивность, антирефлексивность.

 

11.

a) нижние срезы элементов, для которых i +1 кратно 3;

b) антисимметричность и слабая полнота.

 

 

12.

a) верхние срезы элементов, которые являются удвоенными нечетными;

b) асимметричность и полнота.

 

13.

a) нижние срезы элементов, не меньших 10;

b) антирефлексивность и негатранзитивность.

 

14.

a) верхние срезы элементов, меньших ;

b) рефлексивность и транзитивность.

 

15.

a) нижние срезы элементов, для которых i +2 кратно 3;

b) симметричность и полнота.

 

16.

a) верхние срезы четных элементов;

b) слабая полнота и транзитивность.

 

17.

a) нижние срезы элементов, номера которых четны;

b) антисимметричность и негатранзитивность

 

18.

a) верхние срезы элементов, номера которых нечетны;

b) асимметричность, слабая полнота.

 

19.

a) нижние срезы нечетных элементов;

b) полнота, антисимметричность.

 

20.

a) верхние срезы элементов, кратных 3;

b) симметричность, рефлексивность, антирефлексивность.

 

21.

a) нижние срезы элементов, номера которых являются удвоенными четными;

b) антисимметричность и слабая полнота.

 

22.

a) верхние срезы элементов, номера которых кратны 3;

b) асимметричность и полнота.

 

 

23.

a) нижние срезы элементов, которые являются удвоенными четными;

b) антирефлексивность и негатранзитивность.

 

24.

a) верхние срезы элементов, не превышающих 10;

b) рефлексивность и транзитивность.

 

25.

a) нижние срезы элементов, номера которых являются удвоенными нечетными;

b) симметричность и полнота.

 

26.

a) верхние срезы элементов, для которых i +1 кратно 3;

b) слабая полнота и транзитивность.

 

27.

a) нижние срезы элементов, которые являются удвоенными нечетными;

b) антисимметричность и негатранзитивность

 

28.

a) верхние срезы элементов, не меньших 10;

b) асимметричность, слабая полнота.

 

29.

a) нижние срезы элементов, больших ;

b) полнота, антисимметричность.

 

30.

a) верхние срезы элементов, для которых i +2 кратно 3;

b) симметричность, рефлексивность, антирефлексивность.

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

КОМБИНАТОРНЫЕ АЛГОРИТМЫ

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

Если решение не единственное, то вывод комбинаций осуществлять в файл. Во время генерации производить подсчет общего числа сгенерированных вариантов и число вариантов, удовлетворяющих условию задачи, и вывести эти значения на экран.

 

Разгадка числовых ребусов.

В числовых ребусах зашифровывают некоторое арифметическое действие, буквами обозначают цифры. Разным цифрам соответствуют разные буквы. Требуется разгадать, какая цифра скрывается за каждой буквой. Это возможно, если воспользоваться программой генерации размещений без повторений.

Пример. ТОРГ ´ Г = ГРОТ. Имеем 4 различных цифры: Т, О, Р, Г. Следовательно, необходимо сгенерировать 4-размещения из 10 (всего 10 цифр), т.е. массив а[1], …, а[4], удовлетворяющий следующим условиям:

1) а[1] ¹ 0, а[4] ¹ 0 – т.к. число не может начинаться с 0.

2) а[1]×1000 + а[2]×100 + а[3]×10 + а[4] = а[4]×1000 + а[3]∙100 + а[2]∙10 + а[1] – это запись зашифрованного действия.

В процессе генерации каждое полученное сочетание проверяют на выполнение перечисленных условий и отбирают подходящие. В общем случае решений может быть несколько. В данном примере ТОРГ = 1089 (1089×9 = 9801).

Варианты заданий

1. Написать программу разгадки числового ребуса

П Ч Ё Л К А * 7 = Ж Ж Ж Ж Ж Ж

2. Написать программу разгадки числового ребуса

П Р О П: О = Р Ц И Я

3. Написать программу разгадки числового ребуса

С С С Р = Р Ф

4. Написать программу разгадки числового ребуса

(М + О + С + К + В + А) 4 = М О С К В А

5. Написать программу разгадки числового ребуса

6. Написать программу разгадки числового ребуса

С А Р = А Т О В

7. Написать программу генерации m -последовательностей 0 и 1, удовлетворяющих обоим требованиям:

1) число единиц должно быть чётно (включая 0 единиц);

2) число нулей должно быть не меньше числа единиц.

8. Написать программу генерации m -последовательностей 0 и 1, удовлетворяющих обоим требованиям:

1) число единиц должно быть не меньше m / 2 - 2;

2) хотя бы 2 единицы шли подряд.

9. Написать программу генерации m -последовательностей 0 и 1, удовлетворяющих обоим требованиям:

1) число нулей должно быть не больше m / 2 + 2;

2) никакие 2 нуля не шли подряд.

10. Написать программу генерации m -последовательностей 0 и 1, удовлетворяющих обоим требованиям:

1) число нулей должно быть нечётно;

2) число нулей должно быть меньше числа единиц не больше, чем на 3.

11. Написать программу генерации m -последовательностей 0 и 1, удовлетворяющих обоим требованиям:

1) никакие 3 единицы не стоят рядом;

2) число единиц превосходит число нулей.

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

Варианты заданий

По таблице смежности построить списки инцидентности неориентированного графа и подсчитать степени его вершин.

По таблице рёбер построить списки инцидентности ориентированного графа и подсчитать полустепени его вершин.

По таблице смежности построить списки инцидентности ориентированного графа и подсчитать полустепени его вершин.

По таблице рёбер построить списки инцидентности неориентированного графа и подсчитать степени его вершин.

По таблице смежности построить списки инцидентности неориентированного графа, записи в каждом списке упорядочить по возрастанию номеров вершин.

По таблице рёбер построить списки инцидентности неориентированного графа, записи в каждом списке упорядочить по убыванию номеров вершин.

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

По таблице рёбер построить списки инцидентности ориентированного графа, записи в каждом списке упорядочить по возрастанию номеров вершин.

По таблице смежности построить списки инцидентности неориентированного графа, удалить из графа все рёбра, начинающиеся и заканчивающиеся в вершинах n1, n2, n3 или n4.

По таблице рёбер построить списки инцидентности ориентированного графа, добавить рёбра с началом в вершинах, кратных 2, и концом в вершинах, кратных 5.

По таблице рёбер построить списки инцидентности ориентированного графа, удалить из графа вершины с номерами n1 и n2.

По таблице смежности построить списки инцидентности ориентированного графа, добавить рёбра с началом в вершинах n1, n2 и n3 и концом в вершинах n3, n4 и n5.

По таблице рёбер построить списки инцидентности неориентированного графа, удалить из графа все рёбра, обе вершины которых кратны 3.

 

ГОУВПО

“Воронежская государственная технологическая академия”

 

Кафедра информационных технологий,

Моделирования и управления

 

ДИСКРЕТНАЯ МАТЕМАТИКА



Поделиться:


Последнее изменение этой страницы: 2017-01-19; просмотров: 375; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.221.46.132 (0.08 с.)