18280

АЛГЕБРАЇЧНІ ОПЕРАЦІЇ І АЛГОРИТМИ

Лекция

Математика и математический анализ

Лекція 7 АЛГЕБРАЇЧНІ ОПЕРАЦІЇ І АЛГОРИТМИ Бінарні алгебраїчні операції та їх основні характеристики. Асоціативний і комутативний закони операції. Дистрибутивні закони що пов’язують дві операції. Операція обернена даній. Питання на самостійне опр...

Украинкский

2013-07-07

72.5 KB

15 чел.

Лекція 7

АЛГЕБРАЇЧНІ ОПЕРАЦІЇ І АЛГОРИТМИ

  1.  Бінарні алгебраїчні операції та їх основні характеристики.
  2.  Асоціативний і комутативний закони операції. Дистрибутивні закони, що пов’язують дві операції.
  3.  Операція обернена даній.

Питання на самостійне опрацювання

  1.  Поняття про алгоритми. Основні властивості алгоритмів.
  2.  Приклади алгоритмів, що зустрічаються в початковій школі.

  1.  Бінарні алгебраїчні операції та їх основні характеристики

Деякі види відношень, що вивчаються у різних математичних науках, називаються алгебраїчними операціями. Такими відношеннями, наприклад, є арифметичні операції, вивчення яких починається уже з перших років навчання у школі. Замість терміну "бінарна алгебраїчна операція" будемо користуватися терміном "операція" там, де це не приводить до непорозумінь.

Операцією на множині A називається відображення декартового квадрата множини A у множину A.

Операцією у множині або частковою операцією у множині A називається функція з декартового квадрата множини A у множину A. Позначатимемо операції символами * , , Τ , ^, ... . Якщо на множині A визначено операцію * і результат її застосування до елементів x і y, взятих у такому порядку, дає елемент z, то це записують x*y = z; елементи x і y називають компонентами операції, відповідно xпершою, y другою, а zрезультатом операції.

Операції над дійсними числами часто називають діями.

  1.  Асоціативний і комутативний закони операції.

Дистрибутивні закони, що пов’язують дві операції

Конкретні операції багато у чому відрізняються одна від іншої, але деякі з них мають і ряд спільних властивостей. Операція * на множині A називається:

1) асоціативною, якщо для довільних елементів x, y і z множини A має місце рівність

(x*y)*z = x*(y*z).

2) комутативною, якщо для довільних елементів x і y множини A має місце рівність

x*y = y*x.

Якщо операція * асоціативна на множині A, то при її виконанні можна опускати дужки, тобто замість (x*y)*z або x*(y*z) писати x*y*z, і поширити операцію на n компонент, де n ≥ 3 при умові, що порядок компонент не змінюється.

Якщо операції * і ○ визначені на множині A, то операція * називається:

1) дистрибутивною зліва відносно операції ○, якщо для довільних елементів x, y і z множини A має місце рівність x * (y ○ z) = (x * y) ○ (x * z);

2) дистрибутивною справа відносно операції ○, якщо для довільних елементів x, y і z множини A має місце рівність (y ○ z) * x = (y * x) ○ (z * x);

3) дистрибутивною відносно операції ○, якщо вона дистрибутивна справа і зліва.

Якщо операція * комутативна, то для її дистрибутивності відносно операції ○ достатньо розглядати лише одну з рівностей

x * (y ○ z) = (x * y) ○ (x * z),

(y ○ z) * x = (y * x) ○ (z * x).


Приклади
:

1) Операції множення та додавання дійсних чисел комутативні та асоціативні; операція множення дистрибутивна відносно додавання, але операція додавання недистрибутивна відносно множення, бо

2 + ( 3 × 4 ) ¹ ( 2 + 3 ) × ( 2 + 4 ).

2) Операція піднесення до степеня на множині натуральних чисел некомутативна і неасоціативна, бо

23 ¹ 32, (23)4 ¹ 2.

3) Операції перерізу і об'єднання множин комутативні, асоціативні та дистрибутивні одна відносно другої.

4) Операція віднімання множин некомутативна.

  1.  Операція обернена даній

Якщо на множині A визначена комутативна операція Τ і для довільних елементів a і b множини A існує єдиний елемент x такий, що

b Τ x = a, x Τb = a,

то цим самим на множині A задається операція ^ така, що

a ^ b = x.

У цьому випадку операція Τ називається оборотною на множині A, а операція ^ називається оберненою до операції Τ на множині A. Якщо операція ^ обернена до операції Τ на множині A, то за означенням для довільних елементів a і b множини A

b Τ (a ^ b) = (a ^ bΤ b = a.

У випадку, коли для деяких, але не для всіх, елементів a і b, порушується вимога існування або єдиності елемента x такого, що

b ^ x = a,

то говорять, що операція Τ оборотна у множині A, а операція ^ називається оберненою до операції Τ у множині A.

Наприклад:

1) Операція додавання є оборотною на множині цілих чисел Z і необоротною у множині натуральних чисел N. Оберненою операцією до додавання є операція віднімання.

2) Операція множення є оборотною на множині додатних раціональних чисел Q+ і оборотною у множині раціональних чисел Q. Оберненою до множення є операція ділення.

Обернена операція ^, очевидно, не є новою незалежною операцією: вона є похідною від операції Τ.

Елемент e Î A називається нейтральним елементом відносно операції Τ, визначеної на множині A, якщо

" a Î A: aΤe = a Ù eΤa = a.

Число 0 є нейтральним елементом відносно операції додавання цілих чисел, а число 1 – відносно їх множення.

Порожня множина Æ є нейтральним елементом відносно операції об'єднання множин, а універсальна множина U – відносно операції перерізу всіх її підмножин.

Множина може і не містити нейтрального елемента відносно операції, яка визначена на ній. Наприклад, у множині парних цілих чисел визначена операція множення, але число одиниця, як нейтральний елемент відносно множення, у ній не міститься.

Симетричною різницею довільних множин A і B (позначається A¸B) називається множина, яка складається з тих і тільки тих елементів, які належать одній і тільки одній з множин A чи B. Операція над множинами, при якій кожній парі множин A і B ставиться у відповідність їх симетрична різниця A¸B, називається симетричним відніманням множин.

На кругах Ейлера результат симетричного віднімання множин зобразиться так, як на мал. 1, де його заштриховано.

A¸B

Мал. 1.

По аналогії дамо означення симетричної різниці більше як двох множин. Симетричною різницею множин A1, A2, A3, ..., An (n ≥ 3) називається множина, яка складається з тих і тільки тих елементів, які належать одній і тільки одній з множин A1, A2, A3, ..., An, і позначається ¸(A1, A2, A3, ..., An).

На кругах Ейлера симетрична різниця трьох множин A, B і C зобразиться так, як показано на мал. 2, де вона заштрихована. А тепер розглянемо (A¸B)¸C і зобразимо результат виконання операції за допомогою кругів Ейлера (мал. 3).

¸(A, B, C) – 

Мал. 2.

A¸B –             (A¸B)¸C – 

Мал. 3.

Порівнюючи мал. 2 і мал. 3, дійдемо висновку, що

¸(ABC¹ (A ¸ B¸ C,

тобто результат терарної операції не збігається з результатом бінарної операції, яка виконується над трьома компонентами.

Питання на самостійне опрацювання

  1.  Поняття про алгоритми. Основні властивості алгоритмів

Одним з найбільших досягнень математики XX ст. є створення теорії алгоритмів. Назва науки – теорія алгоритмів – говорить про те, що предметом її вивчення є алгоритм. Термін "алгоритм" походить від латинської форми написання імені узбецького математика IX ст. Мухаммед бен Муса аль-Хорезмі, який сформулював правила виконання арифметичниих операцій над числами у десятковій системі числення. Поняття алгоритму у його загальному виді належить до числа неозначуваних понять математики.

Під алгоритмом розуміють точне керівництво (точний опис, правило) про виконання у певному порядку системи операцій, не обов'язково математичних, необхідних для виконання деякої роботи або розв'язування задачі певного класу. Не завжди точне керівництво буде алгоритмом, а лише тоді, коли воно має такі властивості:

1. Дискретність – алгоритм повинен розчленовуватися на скінченну кількість кроків, які мають бути результативними.

2. Елементарність кроків – правила отримання кожного наступного результату на основі попередніх повинні бути зрозумілими для виконавця, не обов'язково людини.

3. Детермінованість – на кожному кроці отримується результат, який однозначно визначається даними або отриманими попередньо результатами.

4. Направленість – повинна існувати вказівка, що розуміти під результатом алгоритму, коли на деякому кроці із попередніх даних результат не отримується.

5. Масовість – алгоритм повинен застосовуватися до різних задач певного класу.

  1.  
    Приклади алгоритмів, що зустрічаються в початковій школі

Алгоритми задаються по-різному, зокрема: формулами, таблицями, словесно, графічно.

У процесі навчання учні знайомляться з багатьма алгоритмами. Одними із перших таких алгоритмів є, наприклад, алгоритми виконання арифметичних операцій у десятковій системі числення.

Побудова алгоритму для розв'язування будь-якої задачі з довільної галузі людської діяльності вимагає від людини глибоких знань у цій галузі. На пошуки алгоритму розв'язування деяких задач учені затрачають багато часу. Але коли алгоритм створений, то розв'язування задач за готовим алгоритмом не вимагає ніяких інших розумових операцій, крім тих, що пов'язані з строгим виконанням кроків алгоритму. Тому його виконавцем може бути і машина. Зважаючи на це, для математики важливе не знання алгоритму, а його побудова і доведення, що за допомогою нього розв'язується будь-яка задача з певного класу. Алгоритми є важливою частиною кожної науки, але ними не вичерпується її зміст.

Не для кожного класу задач можна побудувати алгоритм. Наприклад, не існує алгоритму побудови за допомогою циркуля і лінійки квадрата, площа якого рівна площі заданого круга.

Зауваження . У початковій школі термін "алгоритм" не використовується, замість нього часто вживається термін "правило". Цей термін має різні значення, зокрема, його використовують як синонім понять "означення", "теорема", "аксіома" та "алгоритм". Учитель початкової школи повинен знати, в якому розумінні вжито термін "правило", бо від цього залежить методика його вивчення.