Презентація на тему «Теорія алгоритмів»
![Презентація на тему «Теорія алгоритмів» - Слайд #1 Презентація на тему «Теорія алгоритмів» - Слайд #1](http://cdn.gdz4you.com/files/slides/fb4/ed77915db49cc00d73cf5a0da66925cf.jpeg)
Математичні основи
теорії алгоритмів
![Презентація на тему «Теорія алгоритмів» - Слайд #2 Презентація на тему «Теорія алгоритмів» - Слайд #2](http://cdn.gdz4you.com/files/slides/fb5/4e9d013f20582a8bc03e13a78e4876d4.jpeg)
Пізнання завжди шукало способи опису алгоритмів. І застосовуючи природну мову пізнання – математикові, необхідно визначити у ній ті цеглинки, з яких дослідники створили ці прекрасно величні будови – Алгоритми, а заодно і їх теорію й аналіз. Основними математичними складової теорії алгоритмів виявилися теорія множин, математична логіка й теорія графів. Тому іноді теорію алгоритмів іменують як теорію алгоритмів і вирахувань ( у нашім курсі ми її називаємо «Теорія алгоритмів і математична логіка» ) і розділяють на дві частини. Перша - загальна теорія, що має справу з будовою алгоритмів і вирахувань самих по собі. Друга являє собою прикладну теорію, що має справу із проблемами, пов'язаними із практичними застосуваннями алгоритмів і виникаючими в різних областях математики.
![Презентація на тему «Теорія алгоритмів» - Слайд #3 Презентація на тему «Теорія алгоритмів» - Слайд #3](http://cdn.gdz4you.com/files/slides/fb6/98319696130262affe5dc482a14b4332.jpeg)
2.1 Асимптотичний аналіз функцій
При аналізі поводження функції трудомісткості алгоритму часто використовують прийняті в математику асимптотичні позначення, що дозволяють показати швидкість росту функції, маскуючи при цьому конкретні коефіцієнти.
Така оцінка функції трудомісткості алгоритму називається складністю алгоритму й дозволяє визначити переваги у використанні того або іншого алгоритму для більших значень розмірності вихідних даних.
В асимптотичному аналізі прийняті наступні позначення:
Оцінка (тетта)
Нехай f(n) і g(n) - додатні функції аргументу, n ≥1 (кількість об'єктів на вході й кількість операцій - додатні числа), тоді:
![Презентація на тему «Теорія алгоритмів» - Слайд #4 Презентація на тему «Теорія алгоритмів» - Слайд #4](http://cdn.gdz4you.com/files/slides/fb7/2ec93880ca1029c57fabe14ccc873e6f.jpeg)
Оцінка (тетта)
f(n) = (g(n)), якщо існують такі додатні с1, с2, n0, що:с1 * g(n) ≤ f(n) ≤ c2 * g(n), при n > n0
![Презентація на тему «Теорія алгоритмів» - Слайд #5 Презентація на тему «Теорія алгоритмів» - Слайд #5](http://cdn.gdz4you.com/files/slides/fb8/0db9cf7ccf9216629763601798d48ea5.jpeg)
Звичайно говорять, що при цьому функція g(n) є асимптотичною точною оцінкою функції f(n), тому що по визначенню функція f(n) не відрізняється від функції g(n) з точністю до постійного множника.
Відзначимо, що з f(n) = (g(n)) слідує, що g(n) = (f(n)).
Приклади:
1) f(n)=4*n2+n*lnn+174 – f(n)= (n2);
2) f(n)= (1) – запис означає, що f(n) або дорівнює константі, не рівної нулю, або f(n) обмежена константою на ∞: f(n) = 7+1/n = (1).
2 Оцінка О (О велике)
На відміну від оцінки , оцінка О вимагає тільки, що б функція f(n) не перевищувала g(n), починаючи з n > n0, з точністю до постійного множника:
![Презентація на тему «Теорія алгоритмів» - Слайд #6 Презентація на тему «Теорія алгоритмів» - Слайд #6](http://cdn.gdz4you.com/files/slides/fb9/4b8cbfc38b1c439cc456bd80f619c6f4.jpeg)
Оцінка О (О велике)
c > 0, n0 > 0 : 0 ≤ f(n) ≤ c * g(n),
n > n0.
![Презентація на тему «Теорія алгоритмів» - Слайд #7 Презентація на тему «Теорія алгоритмів» - Слайд #7](http://cdn.gdz4you.com/files/slides/fba/5eeb90daebefdb908dfa94b2a588e3c8.jpeg)
Взагалі, запис O(g(n)) позначає клас функцій, таких, що всі вони ростуть не швидше, ніж функція g(n) з точністю до постійного множника, тому іноді говорять, що g(n) мажорує функцію f(n).
Наприклад, для всіх функцій:
f(n)=1/n, f(n)= 12, f(n)=3*n+17, f(n)=n*Ln(n), f(n)=6* n2+24*n+77 буде справедлива оцінка О(n2)
Указуючи оцінку О є зміст указувати найбільше «близьку» мажоруючи функцію, оскільки, наприклад, для f(n)= n2 справедлива оцінка О(n2), однак вона не має практичного змісту.
3. Оцінка Ω(Омега)
На відміну від оцінки О, оцінка є оцінкою знизу – тобто визначає клас функцій, які ростуть не повільніше, ніж g(n) з точністю до постійного множника:
![Презентація на тему «Теорія алгоритмів» - Слайд #8 Презентація на тему «Теорія алгоритмів» - Слайд #8](http://cdn.gdz4you.com/files/slides/fbb/8e889b987095bcc46f6608b178ab7e74.jpeg)
Оцінка Ω(Омега)
c > 0, n0 >0 : 0 ≤ c * g(n) ≤ f(n)
![Презентація на тему «Теорія алгоритмів» - Слайд #9 Презентація на тему «Теорія алгоритмів» - Слайд #9](http://cdn.gdz4you.com/files/slides/fbc/f2e65e87d311bb8861aacffea5a6e92e.jpeg)
Наприклад, запис Ω(n*Ln(n)) позначає клас функцій, які ростуть не повільніше, ніж g(n) = n*Ln(n), у цей клас попадають всі поліноми зі ступенем більшої одиниці, так само як і всі статечні функції з підставою більшим одиниці.
Асимптотичне позначення О віднесемо до підручника Бахмана по теорії простих чисел (Bachman, 1892), позначення , уведені Д. Кнутом (Donald Knuth).
В асимптотичному аналізі алгоритмів розроблені спеціальні методи одержання асимптотичних оцінок, особливо для класу рекурсивних алгоритмів. Очевидно, що оцінка є більше кращої, чим оцінка О. Знання асимптотики поводження функції трудомісткості алгоритму, його складності, дає можливість робити прогнози на вибір більше раціонального з погляду трудомісткості алгоритму для великих розмірностей вихідних даних.
![Презентація на тему «Теорія алгоритмів» - Слайд #10 Презентація на тему «Теорія алгоритмів» - Слайд #10](http://cdn.gdz4you.com/files/slides/fbd/d60a32128d7abd680090e1aa7c8e7b03.jpeg)
2.2 Елементи теорії множин, відношення, функції і перетворення, алгебраїчні структури.
Те, що Георг Кантор своєю теорією множин зробив революцію в математиці, загальновідомо. Поняття множини належить до числа первісних математичних понять і може бути пояснено тільки за допомогою прикладів. У сучасній математиці поняття множини вважається одним з основних, з його починається виклад традиційних математичних дисциплін і побудова нових математичних теорій.
Теорія множин була створена в основному працями математиків XIX століття Її сучасні положення викладені в літературі по дискретній математиці.
Поняття множини вводиться на аксіоматичному рівні, аналогічно тому, як у математику – крапка, в інформатиці -інформація, а саме: “Множина є багато чого, мислиме як єдине”(Г.Кантор), тобто множина як «поєднання в одне ціле об'єктів, помічених нашою інтуїцією або думкою».
Опускаючи елементарні операції і властивості, діаграми Ейлера-Венна, приведемо схему подальшого розвитку поняття множини .
![Презентація на тему «Теорія алгоритмів» - Слайд #11 Презентація на тему «Теорія алгоритмів» - Слайд #11](http://cdn.gdz4you.com/files/slides/fbe/201ad9c1924982bd8abb1fcd33771a32.jpeg)
2.2 Елементи теорії множин, відношення, функції і перетворення, алгебраїчні структури.
Те, що Георг Кантор своєю теорією множин зробив революцію в математиці, загальновідомо. Поняття множини належить до числа первісних математичних понять і може бути пояснено тільки за допомогою прикладів. У сучасній математиці поняття множини вважається одним з основних, з його починається виклад традиційних математичних дисциплін і побудова нових математичних теорій.
Теорія множин була створена в основному працями математиків XIX століття Її сучасні положення викладені в літературі по дискретній математиці.
Поняття множини вводиться на аксіоматичному рівні, аналогічно тому, як у математику – крапка, в інформатиці -інформація, а саме: “Множина є багато чого, мислиме як єдине”(Г.Кантор), тобто множина як «поєднання в одне ціле об'єктів, помічених нашою інтуїцією або думкою».
Опускаючи елементарні операції і властивості, діаграми Ейлера-Венна, приведемо схему подальшого розвитку поняття множини .
![Презентація на тему «Теорія алгоритмів» - Слайд #12 Презентація на тему «Теорія алгоритмів» - Слайд #12](http://cdn.gdz4you.com/files/slides/fbf/23b3162d514eb0b74ba829a63d8cee37.jpeg)
Нагадаємо,що при доказі тотожностей у теорії множин, діаграми Эйлера-Венна служать лише графічною ілюстрацією, а основним методом доказу є метод двох включень. Наприклад, потрібно довести, що A Δ B = (A B)/(AB). Доведемо методом двох включень.
Фіксуємо довільно елемент x . Нехай x (А Δ В) . Тоді, відповідно до визначення симетричної різниці х (АВ) (ВА) . Це означає, що х (АВ) або х (ВА) . Якщо х (АВ) , то х А и x В , тобто х (A B) і при цьому x (A B) . Якщо ж х (ВА), то х B і x А, звідкіля х (A B) і при цьому x (A B) . Отже, у будь-якому випадку з x (А Δ В) випливає х (A B) і x (A B), тобто x (A B)/(A B).
![Презентація на тему «Теорія алгоритмів» - Слайд #13 Презентація на тему «Теорія алгоритмів» - Слайд #13](http://cdn.gdz4you.com/files/slides/fc0/8f91731deb1f100448d2e02d80c0e9d4.jpeg)
Скорочений запис вищенаведеного доказу з використанням логічної символіки виглядає так:
Тим найперше включення, тобто включення A Δ B (A B)/(A B), установлено.
Покажемо зворотне включення, тобто включення (A B)/(A B) A Δ B. Запис доказу зворотного включення з використанням логічної символіки виглядає так:
Обоє включення мають місце, отже тотожність доведена.
![Презентація на тему «Теорія алгоритмів» - Слайд #14 Презентація на тему «Теорія алгоритмів» - Слайд #14](http://cdn.gdz4you.com/files/slides/fc1/14d3fd79d051f1028293ad6e69b264af.jpeg)
Звертаємо увагу на те, що при доказі тотожностей методом двох включень рекомендується скрупульозно проводити доказ обох включень. Можливі приклади того, що „зворотний" доказ є не зовсім точним оберненням „прямого".
Повернемося до запропонованої схеми. Відповідно до неї, основною операцією для множин є операція декартового добутку, що надалі породжує поняття :відношення, бінарні відношення і функції.
![Презентація на тему «Теорія алгоритмів» - Слайд #15 Презентація на тему «Теорія алгоритмів» - Слайд #15](http://cdn.gdz4you.com/files/slides/fc2/7e276815edbf21e19317468c01c46905.jpeg)
Властивості бінарних відношень на схемі докладно описані. Зупинимося на функціональних відношеннях.
Визначення 2.1. Бінарним відношенням між елементами множин А і В називається будь-яка підмножина R множини декартового добутку . Якщо А=В, то відношення називається бінарним відношенням на А. Позначається – xRy.
Визначення 2.2. Відношення f на називається функцією з А в В і позначається f:А→В , якщо для кожного ttіснує єдиний елемент такий, що (a,b) f. Функція f: називається також відображенням; при цьому говорять, що f відображає А в В. Якщо , то множина f (Е)={b:f(a)=b для деякого a з E} називається образом множини E. Якщо , то множина
f -1 (F)={a:f(a) F} називається прообразом множини F.
![Презентація на тему «Теорія алгоритмів» - Слайд #16 Презентація на тему «Теорія алгоритмів» - Слайд #16](http://cdn.gdz4you.com/files/slides/fc3/27561a36bc00ccf9cdd8179f9cc51e12.jpeg)
Властивості бінарних відношень на схемі докладно описані. Зупинимося на функціональних відношеннях.
Визначення 2.1. Бінарним відношенням між елементами множин А і В називається будь-яка підмножина R множини декартового добутку . Якщо А=В, то відношення називається бінарним відношенням на А. Позначається – xRy.
Визначення 2.2. Відношення f на називається функцією з А в В і позначається f:А→В , якщо для кожного ttіснує єдиний елемент такий, що (a,b) f. Функція f: називається також відображенням; при цьому говорять, що f відображає А в В. Якщо , то множина f (Е)={b:f(a)=b для деякого a з E} називається образом множини E. Якщо , то множина
f -1 (F)={a:f(a) F} називається прообразом множини F.
![Презентація на тему «Теорія алгоритмів» - Слайд #17 Презентація на тему «Теорія алгоритмів» - Слайд #17](http://cdn.gdz4you.com/files/slides/fc4/b03024e43c74dc860029412d40bede33.jpeg)
Подальше дослідження властивостей і операцій на множинах приводить до поняття алгебраїчних структур.
Якщо в минулих століттях і на початку XX століття алгебра вивчала досить обмежене число алгебраїчних структур, то зараз можна дати дуже загальне визначення алгебри – а саме: наука про властивості множин, на яких визначена та або інша система операцій і відношень. В розвиток такого погляду на алгебру уніс великий вклад академік А.И. Мальцев. Зокрема, він увів поняття алгебраїчної системи, що і є підтемою даного розділу. Завдяки роботам А.И. Мальцева стало зрозуміло, що алгебра і математична логіка – дві тісно зв'язані між собою дисципліни.
![Презентація на тему «Теорія алгоритмів» - Слайд #18 Презентація на тему «Теорія алгоритмів» - Слайд #18](http://cdn.gdz4you.com/files/slides/fc5/0238bf8be49f536abc8f6670b766caa7.jpeg)
Визначення 2.3. n-арним (n-містним) відношенням на множині A називається підмножина n-ого декартового ступеня An множини A.
Визначення 2.4. n-арною (n-містною) алгебраїчною операцією (або просто операцією), визначеною на множині A називається n-містна функція f: An → A.
Число n для n-арної операції f (n-арного відношення r) називається арносттю операції f (відношення r) і позначається n(f) (n(r)). Арності відносин – це числа більше нуля. Арність операцій – це числа більші або рівні нулеві. Операції арности 0 являють собою функції з областю визначення, що складає з одного елемента (n-ки довжини 0) і ототожнюються зі значенням функції.
Для унарних операцій ми будемо використовувати префіксну і постфіксну нотацію, а для бінарних – як правило інфіксну.
![Презентація на тему «Теорія алгоритмів» - Слайд #19 Презентація на тему «Теорія алгоритмів» - Слайд #19](http://cdn.gdz4you.com/files/slides/fc6/93302061249673dd7f2ec70a5b364ccd.jpeg)
Визначення 2.3. n-арним (n-містним) відношенням на множині A називається підмножина n-ого декартового ступеня An множини A.
Визначення 2.4. n-арною (n-містною) алгебраїчною операцією (або просто операцією), визначеною на множині A називається n-містна функція f: An → A.
Число n для n-арної операції f (n-арного відношення r) називається арносттю операції f (відношення r) і позначається n(f) (n(r)). Арності відносин – це числа більше нуля. Арність операцій – це числа більші або рівні нулеві. Операції арности 0 являють собою функції з областю визначення, що складає з одного елемента (n-ки довжини 0) і ототожнюються зі значенням функції.
Для унарних операцій ми будемо використовувати префіксну і постфіксну нотацію, а для бінарних – як правило інфіксну.
![Презентація на тему «Теорія алгоритмів» - Слайд #20 Презентація на тему «Теорія алгоритмів» - Слайд #20](http://cdn.gdz4you.com/files/slides/fc7/1313145840584d15ba050f01320f458f.jpeg)
Визначення 2.3. n-арним (n-містним) відношенням на множині A називається підмножина n-ого декартового ступеня An множини A.
Визначення 2.4. n-арною (n-містною) алгебраїчною операцією (або просто операцією), визначеною на множині A називається n-містна функція f: An → A.
Число n для n-арної операції f (n-арного відношення r) називається арносттю операції f (відношення r) і позначається n(f) (n(r)). Арності відносин – це числа більше нуля. Арність операцій – це числа більші або рівні нулеві. Операції арности 0 являють собою функції з областю визначення, що складає з одного елемента (n-ки довжини 0) і ототожнюються зі значенням функції.
Для унарних операцій ми будемо використовувати префіксну і постфіксну нотацію, а для бінарних – як правило інфіксну.
![Презентація на тему «Теорія алгоритмів» - Слайд #21 Презентація на тему «Теорія алгоритмів» - Слайд #21](http://cdn.gdz4you.com/files/slides/fc8/749ac3ae6fd9c18874888e142504be5c.jpeg)
Визначення 2.3. n-арним (n-містним) відношенням на множині A називається підмножина n-ого декартового ступеня An множини A.
Визначення 2.4. n-арною (n-містною) алгебраїчною операцією (або просто операцією), визначеною на множині A називається n-містна функція f: An → A.
Число n для n-арної операції f (n-арного відношення r) називається арносттю операції f (відношення r) і позначається n(f) (n(r)). Арності відносин – це числа більше нуля. Арність операцій – це числа більші або рівні нулеві. Операції арности 0 являють собою функції з областю визначення, що складає з одного елемента (n-ки довжини 0) і ототожнюються зі значенням функції.
Для унарних операцій ми будемо використовувати префіксну і постфіксну нотацію, а для бінарних – як правило інфіксну.
![Презентація на тему «Теорія алгоритмів» - Слайд #22 Презентація на тему «Теорія алгоритмів» - Слайд #22](http://cdn.gdz4you.com/files/slides/fc9/db439584591c98a7017b2aaf37ff0f88.jpeg)
Визначення 2.3. n-арним (n-містним) відношенням на множині A називається підмножина n-ого декартового ступеня An множини A.
Визначення 2.4. n-арною (n-містною) алгебраїчною операцією (або просто операцією), визначеною на множині A називається n-містна функція f: An → A.
Число n для n-арної операції f (n-арного відношення r) називається арносттю операції f (відношення r) і позначається n(f) (n(r)). Арності відносин – це числа більше нуля. Арність операцій – це числа більші або рівні нулеві. Операції арности 0 являють собою функції з областю визначення, що складає з одного елемента (n-ки довжини 0) і ототожнюються зі значенням функції.
Для унарних операцій ми будемо використовувати префіксну і постфіксну нотацію, а для бінарних – як правило інфіксну.
![Презентація на тему «Теорія алгоритмів» - Слайд #23 Презентація на тему «Теорія алгоритмів» - Слайд #23](http://cdn.gdz4you.com/files/slides/fca/fa1479a3062038290ebe553c7d037a7b.jpeg)
Визначення 2.3. n-арним (n-містним) відношенням на множині A називається підмножина n-ого декартового ступеня An множини A.
Визначення 2.4. n-арною (n-містною) алгебраїчною операцією (або просто операцією), визначеною на множині A називається n-містна функція f: An → A.
Число n для n-арної операції f (n-арного відношення r) називається арносттю операції f (відношення r) і позначається n(f) (n(r)). Арності відносин – це числа більше нуля. Арність операцій – це числа більші або рівні нулеві. Операції арности 0 являють собою функції з областю визначення, що складає з одного елемента (n-ки довжини 0) і ототожнюються зі значенням функції.
Для унарних операцій ми будемо використовувати префіксну і постфіксну нотацію, а для бінарних – як правило інфіксну.
![Презентація на тему «Теорія алгоритмів» - Слайд #24 Презентація на тему «Теорія алгоритмів» - Слайд #24](http://cdn.gdz4you.com/files/slides/fcb/dc6fcd6e98b8d3ac37d50b53b932599d.jpeg)
Визначення 2.3. n-арним (n-містним) відношенням на множині A називається підмножина n-ого декартового ступеня An множини A.
Визначення 2.4. n-арною (n-містною) алгебраїчною операцією (або просто операцією), визначеною на множині A називається n-містна функція f: An → A.
Число n для n-арної операції f (n-арного відношення r) називається арносттю операції f (відношення r) і позначається n(f) (n(r)). Арності відносин – це числа більше нуля. Арність операцій – це числа більші або рівні нулеві. Операції арности 0 являють собою функції з областю визначення, що складає з одного елемента (n-ки довжини 0) і ототожнюються зі значенням функції.
Для унарних операцій ми будемо використовувати префіксну і постфіксну нотацію, а для бінарних – як правило інфіксну.
![Презентація на тему «Теорія алгоритмів» - Слайд #25 Презентація на тему «Теорія алгоритмів» - Слайд #25](http://cdn.gdz4you.com/files/slides/fcc/dcc54a3916dc22280eadecb1a6eba61c.jpeg)
Визначення 2.3. n-арним (n-містним) відношенням на множині A називається підмножина n-ого декартового ступеня An множини A.
Визначення 2.4. n-арною (n-містною) алгебраїчною операцією (або просто операцією), визначеною на множині A називається n-містна функція f: An → A.
Число n для n-арної операції f (n-арного відношення r) називається арносттю операції f (відношення r) і позначається n(f) (n(r)). Арності відносин – це числа більше нуля. Арність операцій – це числа більші або рівні нулеві. Операції арности 0 являють собою функції з областю визначення, що складає з одного елемента (n-ки довжини 0) і ототожнюються зі значенням функції.
Для унарних операцій ми будемо використовувати префіксну і постфіксну нотацію, а для бінарних – як правило інфіксну.
![Презентація на тему «Теорія алгоритмів» - Слайд #26 Презентація на тему «Теорія алгоритмів» - Слайд #26](http://cdn.gdz4you.com/files/slides/fcd/6f4d39bae2a0f54b1d8dddadc99d9b86.jpeg)
На закінчення цього розділу представимо загальну схему взаємозв'язків від теорії множин та системою класифікацій загальної алгебри, що починається з поняття категорії як сукупності однотипних математичних структур (об'єктів) і відображень (морфізмів) між ними. У категорії множин об'єктами є множини; морфізмами – їх відображення друг у друга; множення морфізмів збігається із суперпозицією або послідовним виконанням відображень; одиничними морфізмами є тотожні відображення множин у себе. У категорії бінарних відношень над категорією множин об'єктами виступають довільні множини; морфізмами – бінарні відношення; множення морфізмів є множення бінарних відношень.
![Презентація на тему «Теорія алгоритмів» - Слайд #27 Презентація на тему «Теорія алгоритмів» - Слайд #27](http://cdn.gdz4you.com/files/slides/fce/b445b19a34b33eb3cd156f4d89e77050.jpeg)