Назвіть відношення, одержане в результаті операції з’єднання Фірма-продукція-телефон.
3. Виберіть два варіанти виконання операції проекції до відношення Фірма-продукція-телефон. За якими атрибутами ви робили проекції?
4. Виконайте обмеження відношення Фірма-продукція-телефон за умови:
а) Продукція = меблі;
б) Продукція = матеріали для ремонту, Місто = Харків;
в) Місто = Одеса.
Як змінюється число кортежів і (або) атрибутів відношення під час виконання вивчених нами операцій. Розгляньте кожну операцію окремо.
Розділ З
Алгебраїчні структури
Алгебраїчні операції та їх властивості
Унарна операція, бінарна операція, п арна операція, операнд, записи infix, prefix, postfix, таблиця Келі, кому та ти вніс ть, асоціативність, дистрибутивність, одиниця, обернений елемент, операції додавання та множення за модулем.
Поняття алгебраїчної структури включає визначену множину об’єктів та операцій над цими об’єктами. Оскільки практично в будь-якій задачі обробки даних за допомогою комп’ютера виділяється множина самих даних і операції, які застосовні до цих даних, очевидно, що при цьому формуються визначені алгебраїчні структури. Ми вже знайомі з алгебраїчними структурами на множині натуральних, цілих і дійсних чисел, на множинах та відношеннях. Розглянемо такі алгебраїчні структури, як півгрупи, моноїди і групи, що, зокрема, використовуються для перетворення рядків символів і беруть участь у формуванні більш складних структур — кілець і йолів. Ці поняття є базовими для загальної та лінійної алгебри, використовуються під час роботи з матрицями, при кодуванні інформації та обробці даних.
Визначення
Операцією на множині S називається функція f, яка є відображенням виду S" -> S, п є N, де S" — декартів добуток S х S Х...Х S, в який S входить п разів.
У цьому визначенні є два важливих моменти. По-перше, оскільки операція є функцією, то результат застосування операції визначено однозначно. Тому даний упорядкований набір з п елементів множини S функція f переводить тільки в один елемент із S. По-друге, операція замкнена (див. п. 4.8) на S у тому розумінні, що область визначення та область значень операції лежать у S" і S відповідно.
Стверджують, що операція S" —> S має порядок п або є п арною операцією. Частіше зустрічається ситуація, коли порядок дорівнює 1 або 2. Операції виду S S називають унарними, а операції S2 —> S називають бінарними. Елементи упорядкованого набору з п елементів в області визначення Sn називають операндами. Операції звичайно позначають символами, що називають операторами. У випадку унарних операцій звичайно символ оператора ставлять перед або над операндом.
Приклади.Прикладами унарних операцій є операція зміни знаку (-) на множині дійсних чисел JR(-2,678; - 56), операція зведення до степеня (наприклад, до квадрату) на множині R: 562, 7*. В алгебрі множин прикладом унарної операції є операція доповнення множин. Бінарними операціями на множині дійсних чисел R є арифметичні операції — додавання, віднімання, множення, ділення (+, -, *, /). В алгебрі множин бінарними є операції — об’єднання (и), перетин (п), різниця (\).
Операції записують одним з трьох способів. У першому випадку оператор ставиться між операндами (infix), у другому — перед операндами (prefix) і у третьому — після операндів (postfix). Розглянемо три варіанти запису бінарної операції арифметичного виразу а + Ь.
infix: а + Ь, prefix'. 4-ab, postfix: ab-\-.
Відповідно до більшості математичних текстів ми будемо використовувати позначення infix. Форми запису postfix і prefix мають ту перевагу, що не потребують дужок при визначенні порядку обчислень складних виразів, і це робить їх особливо зручними для автоматичної обробки. Вони часто використовуються для представлення виразів у пам’яті
Алгоритм обчислення значень виразу, що записаний у формі postfix, виглядає так:
6.При перегляді запису зліва направо виконується перша знайдена операція, якій безпосередньо передує достатня для неї кількість операндів.
7.На місці виконаної операції і використаних для цього операндів у рядок записується результат виконання операції.
8.Повертаємося до кроку 1.
Приклад. Нехай є вираз, який у стандартній звичній для нас /л/ілг-формі виглядає так:
14-2*3 +(4 + 5* (6 + 7)).
Результат переведення його до postfix буде таким:
123 * + 4567 + * + +.
Обчислимо тепер значення виразу, використовуючи наведений алгоритм:
ретині рядку а, і стовпця ah є елемент Ta6™"u£tJjJlx ® а,, — а, ® aj.
Приклад. Нехай операція ® визначена на множині {а, Ь, с) за допомогою таблиці 3.1.
Отже, а ® Ь = а, Ь ® Ь = а, с ® Ь = Ь, ...
Очевидно, що використання таблиць має велике значення, оскільки деякі операції, з якими доводиться мати справу в комп’ютерній математиці, не придатні для словесного завдання.
Наведемо важливі властивості, які можуть мати операції.
