Контрольные вопросы
Что называется матрицей бинарного отношения и как она строится?
Дайте определение верхнего и нижнего среза элемента. Объясните способ задания бинарного отношения верхними или нижними срезами.
Как построить верхний и нижний срез элемента по матрице бинарного отношения?
Дайте определения свойств бинарного отношения и объясните алгоритмы проверки выполнения свойств по матрице бинарного отношения.
Задание для лабораторной работы.
Написать программу, которая строит матрицу бинарного отношения R варианта, определенного на множестве X и выводит её на печать. По построенной матрице:
построить срезы бинарного отношения для элементов, заданных в варианте;
проверить выполнение либо нарушение свойств бинарного отношения, заданных в варианте.
Построение среза бинарного отношения по элементу x и проверку свойства бинарного отношения оформить в виде в виде функций.
Текст программы и результат её работы оформить в отчёт.
Лабораторная работа № 4 комбинаторные алгоритмы
Цель работы: изучение комбинаторных объектов, алгоритмов их генерации и применение данных алгоритмов к решению задач.
Теоретические сведения
Приведём эффективные алгоритмы, генерирующие основные комбинаторные объекты.
Размещения с повторениями.
Данный алгоритм генерирует наиболее общий класс размещений с повторениями, когда i-ый элемент размещения выбирается из своего множества Xi . Генерация выполняется в лексикографическом порядке.
Используемые обозначения:
A – массив, содержащий размещение;
x – массив, содержащий минимальные значения элементов размещения;
y – массив, содержащий максимальные значения элементов размещения;
k – количество элементов в размещении.
{
i
:=
k
;
for
( j
=
)Aj
:=
xj
;
while ( i 1 )
{ вывод массива A;
i := k ;
while ( Ai = yi ) i := i 1;
if ( i 1) { Ai := Ai +1;
for
( j
=
)Aj
:=
xj
;
}
}
}
Перестановки без повторений.
Данный алгоритм генерирует перестановки без повторений в антилексикографическом порядке. При генерации используется рекурсивная функция.
Используемые обозначения:
P – массив, содержащий перестановку;
n – количество элементов в перестановке;
– поменять местами переменные.
reverse ( m )
{ i :=1; j := m ;
while ( i <j ) { Pi Pj ;
i :=i +1; j :=j 1;
}
}
Antilex ( m )
{ if ( m =1) вывод массива P ;
else
for ( i
=
)
{ Antilex ( m 1);
if (i < m )
{ Pi Pm ;
reverse ( m 1);
}
}
}
{
for ( i
=
)Pi
:=
i
;
Antilex ( n );
}
Сочетания без повторений.
Генерация сочетаний без повторений так же, как и размещений с повторениями, выполняется в лексикографическом порядке.
Используемые обозначения:
С – массив, содержащий сочетание;
k – количество элементов в сочетании;
n – количество элементов в исходном множестве.
{
for
( i
=
)Ci
:=
i
;
p :=k ;
while ( p 1)
{ вывод массива C;
if ( Ck = n ) p := p 1;
else p :=k ;
if
( p
1)
for
( i
=
)
Ci := Cp + i – p +1;
}
}
Размещения без повторений.
При генерации размещений без повторений используется комбинация двух алгоритмов: генерация сочетаний без повторений и перестановок без повторений. Для этого в алгоритме генерации сочетаний без повторений вместо печати сгенерированной комбинации выполняется генерация всех её перестановок (так как размещения отличаются от сочетаний тем, что в них учитывается порядок выбранных элементов). При реализации этого алгоритма сначала в массиве С генерируется сочетание, затем, вместо вывода массива С, его элементы копируются в массив P и вызывается рекурсивная процедура генерации перестановок.