Генерация всех разбиений множества
МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный технический университет радиотехники, электроники и автоматики"
МГТУ МИРЭА
Факультет Информационных технологий
(наименование кафедры)
Утверждаю
Заведующий
кафедрой ______________________
« » _____________ 2012г.
ЗАДАНИЕ
На выполнение курсовой работы
По дисциплине «Дискретная математика»
СтудентПолинко Сергей ДмитриевичГруппа ИВБ-3-11
1.Тема«Курсовая работа по дискретной математике за I курс»
2. Исходные данные:
3. Перечень вопросов, подлежащих разработке, и обязательного графического материала:
1, 2, 3, 4, 5 задания сопровождаются обязательным графическим материалом.
4. Срок представления к защите курсовой работы: до «»________2012г.
Задание на курсовую работу выдал «» _________2012г.Подпись руководителя
Антик М.И.
Задание на курсовую работу получил «» _________2012г.Подпись исполнителя
Полинко С.Д.
№1. Выяснить взаимное расположение множеств D,E,F, если A,B,C–произвольные подмножества U. Указать расположение множеств на карте Карно. Для каждого множества написать минимальную дизьюнктивную формулу.
D: BΔC+( A* ( C \ B ) )
E: B+C
F: ( B* C ) + ( ( A \ C ) \ B )
B Δ C ( A* ( C \ B ) )
B Δ C +( A * ( C \ B ) )
|
|
|
B C
B + C
B * C ( A \ C ) \ B
B * C + ( A \ C ) \ B
FDE
Минимизированные:
D: ( B \ C ) * ( ( C \ B ) \ A)
E: B+C
F: ( B * C ) + ( A * B * C )
№2. Проверить, что для любых множеств A,B,Cвыполнение включенияαвлечет выполнение включенияβ.
α : B \ CA
β : B C +( B * A )
α : ( b * c )+ a = b +1 c +2 a
β : b +5 c +4( b *3 a )
| a | b | c | 1 | 2 | 3 | 4 | 5 | α | β |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
α< = >β
№3. Для произвольных множеств A,B,H проверить, является ли выполнение включения α необходимым и достаточным условием выполнения равенстваβ.
A + B α H H \ A =β( AΔ H ) + ( B \ A )
α: a + b + h β: ( h * a ) = ( ( h * a ) + ( b * a ) ) + ( b * a )
( a *1 b ) +2 h ( h *3 a ) =9 ( ( h *4 a ) +6 ( a *5 b ) ) +8 ( b *7 a )
| a | b | h | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | α | β |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
|
|
|
β ->α, является.
№4. Выяснить, верно ли равенство α для произвольныхA, B, C.
α: B * ( A \ C ) = ( B * ( A + C ) ) * ( B * C )
α : b *2( a *1 c ) = ( b *4 ( a +3 c ) ) *6 ( b *5 c )
| a | b | c | 1 | 2 | 3 | 4 | 5 | 6 | 2 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
2 <> 6 => для произвольныхA,B иCравенство α не верно
| Террористический акт |
| Кол-во пострадавших |
| Место терр. акта |
| Ф.И.О. террористов |
| Код уголовного дела*к2 |
№5. Террористы и террористические акты
| Террорист |
| Ф.И.О.*к1 |
| Возраст |
| Происхождение |
Генерация подмножеств для заданного множества.
//Генерация подмножеств заданного множества
|
|
|
//сограниченным числом элементов
#include<iostream>
usingstd::cin;
usingstd::cout;
intmain()
{
//Ввод размера множества
int n;
cin>> n;
if(n<=0)
return 0;
//Ввод предела размера подмножества
intsize;
cin>> size;
if(size<=0 || size>n)
return 0;
//Созданиеивводмножества
int *A = new int[n];
for(int l=0;l<n;l++)
cin>> A[l];
//Создание массива для кода Грея
short *B = new short[n];
for(int l=0;l<n;l++)
B[l]=0;
//Генерация всех подмножеств
int i=0,p,j,count;
do
{
//Подсчет количества элементов в подмножестве
count=0;
for(int l=0;l<n;l++)
if(B[l]==1)
count++;
//Вывод подмножества, если количество его элементов равно size
if(count==size)
{
for(int l=0;l<n;l++)
|
|
|
{
if(B[l]==1)
cout<< A[l] << ' ';
}
cout<< '\n';
}
//Генерация следующего кода Грея
i++;
p=0;
j=i;
while (j%2==0)
{
j=j/2;
p++;
}
if(p<n)
B[p]=1-B[p];
}
while (p<n);
delete[] B;
delete[] A;
return 0;
}
Генерация всех разбиений множества
//Генерация всех разбиений множества
#include<iostream>
usingstd::cin;
usingstd::cout;
//Вывод разбиения на экран
//a - исходное множество
//b - разбиение
voidPrintPartition(int size, int *a, int* b)
{
//Проверка на существование массивов
if(a==NULL || b==NULL)
return;
//Вычисляем количество подмножеств в данном разбиении
int blocks=1;
for(inti=0;i<size;i++)
if(b[i]>blocks)
blocks=b[i];
//Выводим каждое подмножество
for(int i=0;i<blocks;i++)
{
for(int j=0;j<size;j++)
if(b[j]==i+1)
cout<< a[j] << ' ';
if(i!=blocks-1)
cout<< "| ";
}
cout<< '\n';
}
//Помещает в элемент массива b с номером pos элементы от 1 до max
//и для каждого значения вызывает сама себя для следующей позиции массива
//а - исходное множество
//size - размер множества
void Partition(intpos, int max, int size, int *a, int *b)
{
//Проверка на существование массивов
if(a==NULL || b==NULL)
return;
//Если достигнут конец массива, то вывести разбиение
if(pos>=size)
{
PrintPartition(size,a,b);
return;
}
//Цикл по всем возможным вариантам для данной позиции массива
for(inti=0;i<max;i++)
{
b[pos]=i+1;
//Переход к следующей позиции массива
//При этом, если данная позиция достигла максимума, то максимум следующей увеличивается на 1
if(i+1==max)
Partition(pos+1,max+1,size,a,b);
else
Partition(pos+1,max,size,a,b);
}
}
intmain()
{
//Ввод размера множества
int n;
cin>> n;
if(n<=0)
return 0;
//Вводмножества
int *A = new int[n];
for(inti=0;i<n;i++)
cin>> A[i];
cout<< '\n';
int *B = new int[n];
//Генерация разбиений
//Начальное значение: нулевой элемент массива, максимальный индекс - 1
Partition(0,1,n,A,B);
delete[] A;
delete[] B;
return 0;
}
Дата добавления: 2018-04-05; просмотров: 864; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!