Елементи теорії множин. Лабораторна робота з Математика. Робота № 110139

Елементи теорії множин

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра прикладної математики

Інформація про роботу

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Математика

Група:

ПМ-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++.

Лабораторна робота Математика

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись