- •1. Основні поняття теорії множин (поняття порожньої множини, універсуму, способи завдання множин).
- •2.Основні операції над множинами.
- •3.Властивості операцій над множинами
- •4.Геометрична інтерпретація множин
- •5.Поняття підмножини, рівність множин.
- •6.Множина підмножин.
- •7.Алгебра множин.
- •8.Узагальнення операцій над множинами.
- •9.Декартовий добуток множин
- •10.Еквівалентність множин.
- •11.Поняття потужності множини.
- •12.Зчисленні та незчисленні множини.
- •13.Множини потужності континуума.
- •14.Поняття відношення
- •15.Поняття фактор – множини
- •16.Подання відношень за допомогою матриці і графа
- •17.Операції над відношеннями
- •18.Симетричне (обернене) відношення
- •19.Поняття композиції відношень
- •20.Властивості композиції відношень
- •26.Поняття функції та відображень.
- •27.Типи відображень
- •28.Поняття образу та праобразу
- •29.Основні властивості відображень
- •30.Відношення еквівалентності
- •31.Матриця та граф відношення еквівалентності
- •32.Відношення толерантності
- •33.Відношення нестрогого порядку
- •34.Відношення строгого порядку
- •35.Матриця та граф відношення нестрогого порядку
- •36.Матриця та граф відношення строгого порядку
- •37.Алгоритм побуд. Транзитивного замикання відношень(алг. Уоршалла)
- •38.Осн. Поняття реляційної алгебри
- •39.Булеві функції, способи задання булевої функції
- •40.Номери булевих функцій та інтерпретацій.Булеві ф-ї двох змінних.
- •41.Закони булевої алгебри
- •42.Поняття двоїстої та самодвоїстої функцій
- •43. Правило розкладаня булевої ф-ї за всіма або декількома змінними.
- •44.Поняття досконалої диз’юнктивної нормальної форми (дднф) та досконалої кон’юнктивної нормальної форми (дкнф).
- •45.Алгоритм переходу від таблиці істинності до дднф.
- •46.Поняття алгебри Жегалкіна, лінійні функції.
- •47.Правила мінімізації булевих функцій (карти Карно).
- •48. Понятя повних систем булевих функцій
- •49.Теорема Поста про повноту.
- •53.Поняття предикату, квантору
- •54. Закони у логіці предикатів
- •55.Алгоритм зведення вільної форми алгебри логіки предикатів до внф.
- •56. Закони математичної логіки першого ступеня. Поняття множини істинності предиката.
- •57.Основні поняття теорії графів (порядок, степені вершин, порожній граф, мультиграф, псевдо граф, орієнтований та неорієнтований граф).
- •58.Задання графа за допомогою матриці інцидентності
- •59.Задання графа за допомогою матриці суміжності
- •60.Задання графа за допомогою матриці Кірхгофа.
- •61. Локальні степені вершини графа.
- •62. Локальні степені вершини орграфа.
- •64. Операції над частинами графа.
- •65. Маршрути, ланцюги, цикли.
- •66. Ознаки зв’язності
- •67. Поняття дерева.
- •73. Поняття гамільтонових графів.
- •75. Поняття укладання графа. Пласкі та планарні графи.
- •76. Теорема. Ейлера та властивості планарного графа
- •77. Критерії планарності
- •80. Критичні графи
- •82. Алгоритм Форда-Беллмана д/знах. Макс. Шляху
- •83. Алгоритм Форда-Фалкерсона – знах. Макс. Потоку в мережі
- •84. Алгоритм Хафмана
- •90. Біном Ньютона. Поліномна формула
35.Матриця та граф відношення нестрогого порядку
Матриця: головна діагональ-1; Матриця не семетрична. Граф: петлі в усіх вершинах, вершини пов’язані дугами
36.Матриця та граф відношення строгого порядку
Матриця: головна діагональ-0; Матриця не семетрична. Граф: петлі в усіх вершинах, вершини пов’язані дугами, немає петель
37.Алгоритм побуд. Транзитивного замикання відношень(алг. Уоршалла)
I спосіб: 1) розглядаються поза діагональні елементи матриці. Якшо m(i,j) ≠0, то і-й рядок замінюється диз’юнкцією (лог.додавання) і-го та j-го рядків. 2) операції повторюються до тих пір, поки вигляд матриці не припинить змінюватись. II спосіб: 1) обчисл. матрицю композиції R2 = RoR 2) знаходимо лог. суму матриць: R2 = R2 vR 3) порывняємо R2 та R. Якщо R2 = R, то R2 – шукана матриця. Якшо R2 ≠ R, то R := R2 , повертаємося до п.1 і повторюємо процедуру.
38.Осн. Поняття реляційної алгебри
Теоретичні основи реляційної моделі баз даних були закладені Е.Коддом на початку 70-х років і спочатку дійсно мали чисто теоретичний характер. Сигнатура реляційної алгебри складається з 8-ми операцій.
Теоретико-множинні операції ,,\ – частково визначені.
Реляції R1(A1, … , An) і R2(B1, … , Bk) називаються сумісними, якщо: 1. у них однакова кількість атрибутів, тобто k = n; 2. кожному атрибуту першої реляції можна поставити у взаємно однозначну відповідність атрибут другої реляції, тобто існує таке бієктивне відображення
S:{1, … , k} {1, … , k}, що
N(Ai) = N(BS(i)), i = 1поділити k.
1-Об’єднання.
R1R2: в результуючу реляцію попадають всі кортежі першої і другої реляції без дублів.
2-Перетин.
R1R2: в результуючу реляцію попадають кортежі, присутні і в першій, і в другій реляції.
3-Різниця.
R1\R2: в результуючу реляцію попадають кортежі з R1, яких немає в R2.
4-Декартів добуток.:R1R2 – визначається для будь-яких реляцій. Ця операція може різко збільшити об’єм результату.
5-Проекція. Посилаючись на реляцію П (постачальник), запит “знайти прізвища всіх постачальників” може бути виражений так: П[прізв].
6-Операція θ - з’єднання (θ - join).
7-Операція θ - обмеження.
39.Булеві функції, способи задання булевої функції
Функція виду у – f(x1,x2,xn) аргументи хі і значення у якої належать множині В, називається n місною булевою функцією. Такі функції також називають логічними або перемикальними функціями. Змінні, які можуть приймати значення тільки з множини В, називаються логічними або булевими змінними. Самі значення 0 і 1 булевих змінних називають булевими константами. Булеві функції можуть бути задані трьома способами: за допомогою таблиці істинності (значеннями на кожній з інтерпретацій); порядковим номером, який має ця функція; аналітично (у вигляді формули).
40.Номери булевих функцій та інтерпретацій.Булеві ф-ї двох змінних.
Кожній функції привласнюють порядковий номер у вигляді натурального числа, двійковий код якого зображує стовпчик значень функції у таблиці істинності. Молодшим розрядом вважається самий нижчий рядок, а старшим – спмий верхній. Вказаний порядковий номер функції, де двійковий, так і десятковий, повністю визначає булаву функцію. Кожній інтерпретації булевої функції також привласнюється свій номер – значення двійкового коду, який зображує інтерпретація. Інтерпретація, що записана у верхньому рядку таблиці істинності, привласнюється номер 0, потім йде інтерпретація номер 1 тощо.