Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Елементи теорії множин
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Математика
Група:
ПМ-21
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут прикладної математики
і фундаментальних наук
Кафедра прикладної математики
Лабораторна робота № 1
“Елементи теорії множин”
Тема: множини та операції над ними.
Мета: навчитись оперувати множинами, виконувати над ними операції задопомогою засобів ЕОМ.
Теоретичні відомості:
Множини є основними об’єктами вивчення у дискретній математиці. Множина – це невпорядкована сукупність об’єктів, які називають елементами множини. Елементами можна вважати довільні об’єкти, які можуть бути названі або означені задопомогою правила, що задає належність до множин.
Множину можна зберігати в пам’яті як масив. Типові операції над множинами – об’єднання, перетин, перевірка приналежності елемента множині – реалізуються з допомогою засобів алгоритмічної мови або процедур обробки масивів (в мові Паскаль передбачені дані типу множина (SET) та дії над ними).
Нехай задані дві множини X і Y. Побудуємо всі можливі пари (x, y) такі, що x(X, y(Y. Отримана таким шляхом множина пар називається прямим добутком множин X і Y і позначається X(Y. Будь-яка підмножина множини X(Y називається відношенням R на X(Y. Якщо (x, y) (R, то будемо говорити, що “x знаходиться у відношенні R до y” і записують xRy.
Відношення R ( A(A називається транзитивним, якщо з xRy і yRz випливає xRz для всіх x, y, z ( A.
k-ту степінь відношення R на множині A можна задати рекурсивно.
ab тоді і тільки тоді, коли aRb.
ab для k>1 тоді і тільки тоді, коли існує c(A таке, що aRc і cb для a, b(A.
Відношення - називається транзитивним: ab тоді і тільки тоді, якщо знайдеться таке k, що ab для a і b, які належать даній множині.
Відношення називається транзитивним замиканням відношення R на множині A.
Для знаходження матриці транзитивного замикання відношення R на множині A зі скінченою кількістю елементів можна скористуватиси формулою:
де M – матриця, що задає відношення R на множині A, яка мітить n елементів.
Завдання:
10. Побудувати процедуру обчислення матриці транзитивного замикання.
Код програми(С++):
#include <iostream>
#define m
using namespace std;
void In_Matrix(int A[m][m], int n);
void Out_Matrix(int A[m][m], int n);
void Null_Matrix(int A[m][m]);
void Multiply_Matrix(int A[m][m], int B[m][m], int C[m][m]);
void Pow_Matrix(int A[m][m], int As[m][m], int s);
void Union_Matrix(int A[m][m], int B[m][m], int C[m][m]);
void Transitive_Matrix(int A[m][m], int B[m][m], int n);
void main()
{
int n, M[m][m], Mt[m][m];
cout<<"Ob4uslennja matruci tranzutuvnogo zamukannnja vidnowennja R na mnozhuni A."<<endl;
cout<<"Vvedit' kil'kist' elementiv mnozhunu A:"<<endl;
cout<<"n = "; cin>>n;
cout<<"Vvedit' elementu matruci M, w4o zadae vidnowennja R na mnozhuni A:"<<endl;
In_Matrix(M, n);
Transitive_Matrix(M, Mt, n);
cout<<endl<<"Matrucja M:"<<endl;
Out_Matrix(M, n);
cout<<endl<<"Matrucja M+, w4o zadae tranzutuvne zamukannja vidnowennja R na mnozhuni A:"<<endl;
Out_Matrix(Mt, n);
}
void In_Matrix(int A[m][m], int n)
{
Null_Matrix(A);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
cout<<"M["<<i + 1<<","<<j + 1<<"] = ";
go: cin>>A[i][j];
if ((A[i][j] != 0)&&(A[i][j] != 1))
{
cout<<"Elementu matruci - luwe nyli abo odunuci!"<<endl;
goto go;
}
}
}
void Out_Matrix(int A[m][m], int n)
{
for(int i = 0; i < n; i++)
{
cout<<endl<<endl;
for(int j = 0; j < n; j++)
cout<<A[i][j]<<"\t";
}
cout<<endl;
}
void Null_Matrix(int A[m][m])
{
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
{
A[i][j] = 0;
}
}
void Multiply_Matrix(int A[m][m], int B[m][m], int C[m][m])
{
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
{
C[i][j] = 0;
for(int k = 0; k < m; k++)
C[i][j] += (A[i][k] * B[k][j]);
if (C[i][j] != 0) C[i][j] = 1;
}
}
void Pow_Matrix(int A[m][m], int As[m][m], int s)
{
int R[m][m];
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
if (i == j)
As[i][j] = 1;
else
As[i][j] = 0;
if (s != 0)
for(int k = 0; k < s; k++)
{
Multiply_Matrix(A, As, R);
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
As[i][j] = R[i][j];
}
}
void Union_Matrix(int A[m][m], int B[m][m], int C[m][m])
{
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
if (A[i][j] || B[i][j]) C[i][j] = 1;
else C[i][j] = 0;
}
void Transitive_Matrix(int M[m][m], int Mt[m][m], int n)
{
int Rez1[m][m], Rez2[m][m];
Null_Matrix(Rez2);
for(int k = 1; k <= n; k++)
{
Pow_Matrix(M, Rez1, k);
Union_Matrix(Rez2, Rez1, Mt);
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
Rez2[i][j] = Mt[i][j];
}
}
Результати програми:
Ob4uslennja matruci tranzutuvnogo zamukannnja vidnowennja R na mnozhuni A.
Vvedit' kil'kist' elementiv mnozhunu A:
n = 3
Vvedit' elementu matruci M, w4o zadae vidnowennja R na mnozhuni A:
M[1,1] = 0
M[1,2] = 1
M[1,3] = 1
M[2,1] = 0
M[2,2] = 1
M[2,3] = 0
M[3,1] = 1
M[3,2] = 0
M[3,3] = 0
Matrucja M:
0 1 1
0 1 0
1 0 0
Matrucja M+, w4o zadae tranzutuvne zamukannja vidnowennja R na mnozhuni A:
1 1 1
0 1 0
1 1 1
Перевірка:
Висновок:
Я ознайомився з елементами теорії множин, операціями над множинами, властивостями відношень і реалізацію операцій над множинами засобами мови C++.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора