Презентация на тему: 1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для

Реклама. Продолжение ниже
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для
1/49
Средняя оценка: 4.3/5 (всего оценок: 80)
Код скопирован в буфер обмена
Скачать (179 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации

1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для чисто механічного розв ’ язку задач певного класу. Характерні властивості алгоритму: Фінітність Масовість Дискретність Елементарність Результативність Детермінованість Для опису алгоритму вказуємо: – множину його початкових (вхідних) даних – множину вихідних даних, до яких належать результати роботи алгоритму.

Изображение слайда
1/1
2

Слайд 2

2 За допомогою алгоритму кожний конкретний результат отримується за скінченну кількість кроків із скінченної множини вхідних даних. До таких даних алгоритм застосовний. В деяких ситуаціях процес виконання алгоритму для певних вхідних даних продовжується необмежено. До таких даних алгоритм незастосовний. Кожний алгоритм  із множиною вхідних даних X та вихідних Y визначає часткову функцію f : Х → Y. Якщо  застосовний до d, то значення f ( d ) рівне  ( d ). Якщо  незастосовний до d, то f ( d ) невизначене. Такий алгоритм  обчислює функцію f.

Изображение слайда
1/1
3

Слайд 3

3 Функція алгоритмічно обчислювана (АОФ), якщо існує алгоритм, який її обчислює. Множина L алгоритмічно перелічна, якщо L є множиною значень деякої АОФ, тобто існує алгоритм, який перелічує елементи множини L і тільки їх. Множина L алгоритмічно розв'язна відносно множини U, якщо існує алгоритм, який дозволяє для кожного x  U визначати, x  L чи x  L.

Изображение слайда
1/1
4

Слайд 4

4 Відносний алгоритм ( алгоритм з оракулом ): на деяких кроках може звертатися до зовнішнього відносно алгоритму об ’ єкту – оракула. Видані оракулом відповіді –це дані, вироблені на таких кроках звертання. Функція алгоритмічно обчислювана відносно оракула , якщо існує алгоритм з оракулом , який її обчислює.

Изображение слайда
1/1
5

Слайд 5

5 Зв ’ язок алгоритмів та числень Поняття алгоритму можна звести до поняття числення в смислі зведення алгоритмічного процесу до процесу породження : кожний алгоритм можна трактувати як числення з такими ПВ, що виконання кожного із них відповідає виконанню одного кроку алгоритму. Поняття числення можна звести до поняття алгоритму в смислі зведення розгалуженого процесу породження до послідовного процесу переліку так, щоб алгоритм переліку відтворив усі породжені численням об’єкти і тільки їх.

Изображение слайда
1/1
6

Слайд 6

6 Теорія алгоритмів – розділ математики, що вивчає загальні властивості алгоритмів. Усвідомлення неможливості існування алгоритмів розв’язку низки масових проблем  необхідність математичного уточнення поняття алгоритму. Після сформування поняття алгоритму як нової та окремої сутності першочерговою стала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей – моделі для первісного поняття алгоритму (машини Тьюрінга, регістрові машини, нормальні алгоритми Маркова) – моделі для похідного поняття АОФ (  -означувані функції, частково рекурсивні функції та ін.).

Изображение слайда
1/1
7

Слайд 7

7 Доведено: кожна з відомих моделей задає (з точністю до кодування) один і той же клас функцій. Тому є всі підстави вважати, що кожна з таких моделей дає строге математичне уточнення інтуїтивного поняття АОФ. Таке твердження стосовно АОФ та строго визначеного класу частково рекурсивних функцій – теза Чорча (А.Чорч, 1936).

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8

8 МАШИНИ З НАТУРАЛЬНОЗНАЧНИМИ РЕГІСТРАМИ МНР є ідеалізованою моделлю комп ’ ютера. МНР складається з регістрів, вмістом яких є натуральні числа. Рег і стри позначаємо так: R 0, R 1,..., R n,... Вміст регістру R n позначимо ' R n. Конфігурація МНР – це послідовність (' R 0, ' R 1,..., ' R n,...) вмістів регістрів МНР МНР-програма – скінченна послідовність команд МНР Команди програми послідовно нумеруємо, починаючи з 1. А дреса команди – це номер команди в МНР-програмі I 1 I 2... I k – МНР - програма з командами I 1, I 2,..., I k | P | – д овжина ( кількість команд ) МНР - програми P

Изображение слайда
1/1
9

Слайд 9

9 Типи команд МНР Тип 1. Обнулення n - го регістру Z ( n ): ' R n :  0. Тип 2. Збільшення вмісту n - го регістру на 1 S ( n ): ' R n :  ' R n + 1. Тип 3. Копіювання вмісту регістру T ( m, n ): ' R n :  ' R m (' R m не змінюється ). Команди типів 1–3 – арифметичні. Наступник арифметичної команди – наступна команда програми Т и п 4.   Умовний перехід J ( m, n, q ): ' R n = ' R m,  перейти до q - ї команди, інакше виконувати наступну команда програми q – адреса переходу Крок МНР – виконання однієї команди МНР Саме МНР - програми є формальними моделями алгоритмів, поняття МНР використовується для опису функціонування МНР - програм.

Изображение слайда
1/1
10

Слайд 10

10 Виконання програми МНР починає з виконання першої команди Наступна для виконання команда програми – як описано вище Виконання програми завершується, якщо наступник відсутній ( номер наступної команди  номера останньої команди програми ). Фінальна конфігурація МНР – у момент завершення виконання програми Вона визначає результат роботи МНР - програми над даною початковою конфігурацією. P ( a 0, a 1,...)  : МНР - програма P не зупиняється при роботі над початковою конфігурацією ( a 0, a 1,...) P ( a 0, a 1,...)  : МНР - програма P зупиниться при роботі над поч. конфігурацією ( a 0, a 1,...) P ( a 0, a 1,...)  ( b 0, b 1,...): МНР - програма P при роботі над поч. конфігурацією ( a 0,   a 1,...) зупиняється з фінальною конфігурацією ( b 0, b 1,...)

Изображение слайда
1/1
11

Слайд 11

11 Кожна МНР - програма визначає однозначне відображення N N → N N, де N N   –  множина всіх нескінченних послідовностей нат. чисел. МНР - програми – фінітні об ’ єкти   МНР - програма в процесі виконання використовує тільки скінченну множину регістрів, усі вони явно вказані у МНР - програмі. Тому при розгляді відображень, заданих МНР - програмами, обмежимося скінченними послідовностями натуральних чисел. Надалі розглядаємо тільки скінченні конфігурації. Конфіг. ( a 0, a 1,..., a n, 0, 0,...), у якій ' R m = 0    m > n – с кінченна позначаємо ( a 0, a 1,..., a n ) Якщо МНР - програма P починає роботу над скінченною початковою конфігурацією, то в процесі виконання P МНР перебуватиме тільки в скінченних конфігураціях.

Изображение слайда
1/1
12

Слайд 12

12 МНР - програми P та Q еквівалентні, якщо вони визначають однакові відображення послідовностей натуральних чисел. Це означає: при роботі над однаковими початковими конфігураціями вони або обидві зупиняються з однаковими фінальними конфігураціями, або обидві не зупиняються МНР - програма P стандартна, якщо q    | P | + 1  команди вигляду J ( m, n, q ) Конкатенація стандартних МНР - програм P = І 1 I 2... I k та Q = I 1 I 2... I m – це стандартна МНР - програма I 1... I k I k +1... I k + m, де I k +1,..., I k + m – команди пр-ми Q, у яких  команда J ( m, n, q ) замінена командою J ( m, n, q + k ).

Изображение слайда
1/1
13

Слайд 13

13 МНР - програма P обчислює часткову n - арну функцію f  :   N n → N : f ( a 1, a 2,..., a n ) = b  P ( a 1, a 2,..., a n )  b. Пишемо P ( a 1, a 2,...)  b з амість P ( a 1, a 2,...)  ( b,...) – значення аргументів посл - но розміщуються в регістрах, поч-чи із R 0 – значення функції знімається з R 0. Еквівалентне визначення обчислюваності f : N n → N МНР - програмою P : – за умови ( a 1, a 2,..., a n )  D f та f ( a 1, a 2,..., a n ) = b P ( a 1, a 2,..., a n )  b ; – за умови ( a 1, a 2,..., a n )  D f маємо P ( a 1, a 2,..., a n ) . f   :   N n → N МНР - обчислювана, якщо існує МНР - програма, яка обчислює f.  МНР - програма обчислює безліч функцій нат. аргументів і значень Фіксуємо наперед арність функцій ( к-ть компонент початкових конфігурацій )   МНР - програма обчислює єдину функцію заданої арності

Изображение слайда
1/1
14

Слайд 14

14 Пр и клад 1. МНР - програма для функції x + y : 1) J (1,2,5) 2) S (0) 3) S (2) 4) J (0,0,1) Пр и клад 2. МНР - програма для функції x – y : 1) J (0,1,5) 2) S (1) 3) S (2) 4) J (0,0,1) 5) Т (2,0)

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15

15 Приклад 3. МНР - програма для всюди невизначеної функції : 1) J (0,0,1) Пр и клад 4. МНР - програма для функції [ x /2]: 1) J (0,2,7) 2) S (2) 3) J (0,2,7) 4) S (2) 5) S (1) 6) J (0,0,1) 7) Т (1,0)

Изображение слайда
1/1
16

Слайд 16

16 Приклад 5. МНР - програма для функції : 1) J (0,1,7) 2) J (0,2,6) 3) S (1) 4) S (2) 5) J (0,0,1) 6) Z (2) 7) Т (2,0)

Изображение слайда
1/1
17

Слайд 17

17 Приклад 6. МНР - програма для функції f ( x, y ) = x  y : 1) J (3,1,9) 2) J (0,2,6) 3) S (2) 4) S (4) 5) J (0,0,2) 6) Z (2) 7) S (3) 8) J (0,0,1) 9) Т (4,0)

Изображение слайда
1/1
18

Слайд 18

18 Нехай P – стандартна МНР - програма для n - арної функції f. Найбільший номер регістру, задіяного при обч - ні f, позначимо  ( P ). Для n - арної функції вважатимемо  ( P )  n  – 1. P [ k 1, k 2,..., k n  R ] позначимо МНР - програму, яка обчислює ту саму  f, що й МНР - програма  P, але за умови: – початкові значення аргументів занесені в регістри k 1,..., k n, – значення функції знімається з регістру R. Для обчисл - я f задіяно найбільше  ( P ) + 1 регістрів – з 0- го по  ( P )- й. МНР - програма P [ k 1, k 2,..., k n  R ] для вип. k 1  <  k 2  <...<  k n має вигляд T ( k i, i – 1), 1 < i  n Z ( k ), n  k   ( P ) P ' T (0, R ) P ' відрізняється від P тільки зміщенням адрес на  ( P ) 

Изображение слайда
1/1
19

Слайд 19

19 МАШИНИ ТЬЮРІНГА А. М.  Тюрінг, Е.Пост 1936 р. Варіанти МТ: багатострічкові, машини з еластичною стрічкою і т.  п. МТ – це ( Q, T, d, q 0, F ), де : – Q – скінченна множина внутрішніх станів ; – T – ск. алфавіт символів стрічки, символ порожньої клітини  T –  : Q  T → Q  T  { R, L,  } – функція переходів ; – q 0  Q – початковий стан ; – F  Q – множина фінальних станів. Функцію переходів задають ск. множиною команд одного з типів : qa  pbR qa  pbL qa  pb де p, q  Q, a, b  T,  Q  T. Вважаємо  тотальною    пар ( q, a )  D  неявно, не додаючи відп.команди qa  qa, вводимо довизначення  ( q, a ) = ( q, a, e )

Изображение слайда
1/1
20

Слайд 20

20 Неформально МТ: – скінченна пам ’ ять – розділена на клітини необмежена з обох боків стрічка – голівка читання - запису. У кожній клітині – єдиний символ   T, в   момент стрічка містить скінченну кількість символів    . Голівка читання - запису в    момент оглядає єдину клітину стрічки. Нехай МТ знаходиться в стані q та голівка читає символ a – при виконанні команди qa  pbR МТ переходить у стан p, замість a записує на стрічці b та зміщує голівку на 1 клітину направо – при виконанні команди qa  pb L – “ – “ – на 1 клітину наліво – при виконанні команди qa  pb – “ – “ – залишає голівку на місці.

Изображение слайда
1/1
21

Слайд 21

21 Конфігурація МТ – це слово xqy, де x, y  T *,   q  Q. Неформально : – на стрічці записано xy ( зліва і справа від xy можуть стояти тільки  ), – МТ знаходиться в стані q, – голівка читає 1- й символ підслова y. Конфігурація вигляду q 0 x – початкова Конфігурація вигляду xqy, де q  F – фінальна Після переходу фінальної конфігурації, МТ зупиняється. Нехай МТ знаходиться в конфіг. xcqay, де x, y  T *, a, c  T, q  Q. Після виконання команди qa  pbR МТ перейде до конфіг. xcbpy. Після виконання команди qa  pbL МТ перейде до конфіг. xpcby. Після виконання команди qa  pb МТ перейде до конфіг. xcpby.

Изображение слайда
1/1
22

Слайд 22

22 Кожна МТ задає деяке вербальне відображення T *→ T * : МТ М переводить u  T * у v  T *, якщо вона з початкової конфігурації q 0 u переходить до фінальної xqy, де q  F, xy =  v , ,    {  }*. При цьому 1- й та останній символи слова v відмінні від , або v  =  . МТ М переводить слово u в слово v : v = M ( u ). МТ M зациклюється при роботі над словом  u : починаючи роботу з початкової конфігурації q 0 u, M ніколи не зупиниться. Тоді M ( u ) невизначене. МТ M 1 та M 2 еквівалентні, якщо вони задають одне й те ж відображення. МТ детермінована, якщо функція  однозначна інакше МТ недетермінована

Изображение слайда
1/1
23

Слайд 23

23 Можна вважати, що F складається з єдиного фінального стану q *: Нехай M   =   ( Q, T, , q 0, F ). Візьмемо q *  Q. Тоді МТ M ’=   ( Q  { q *}, T,  ’, q 0, { q *}), де  ’=  { qa  q * a | q  F, a  T }, еквівалентна початковій машині M. Надалі – тільки детерміновані МТ з єдиним фінальним станом позначаємо їх ( Q, T, , q 0, q *). Конкретні МТ задаємо, указуючи множину команд початковий стан позначаємо q 0, фінальний – q *.

Изображение слайда
1/1
24

Слайд 24

24 МТ M обчислює часткову функцію f : N n → N, якщо вона –   слово вигляду переводить в у випадку ( x 1,..., x k )  D f – невизначене при ( x 1,..., x k )  D f . Функція обчислювана за Тьюрінгом, або МТ - обчислювана : існує МТ, яка її обчислює. К ожна МТ обчислює безліч функцій натуральних аргументів і значень Зафіксуємо наперед арність функцій    МТ обчислює єдину функцію заданої арності.

Изображение слайда
1/1
25

Слайд 25

25 Пр и клад 1. МТ, яка обчислює функцію x + y : q 0 |  q 1  R q 1 |  q 1 | R q 1 #  q *| q 0 #  q *  Приклад 2. МТ, яка обчислює функцію f ( x ) = sg ( x ): q 0  q *  q 0 |  q 1 | R q 1 |  q 1  R q 1  q *  Приклад 3. МТ, яка обчислює предикат " x парне ": q 0 |  q 1  R q 1 |  q 0  R q 0  q *| q 1  q * 

Изображение слайда
1/1
26

Слайд 26

26 Пр и клад 4. МТ, яка обчислює функцію x – y : q 0 |  q 1  R q 1 |  q 1 | R q 1 #  q 1 # R q 1  q 2  L q 2 |  q 3  L q 3 |  q 3 | L q 3 #  q 3 # L q 3  q 0  R q 2 #  q *| q 0 #  q 4  R q 4  q * 

Изображение слайда
1/1
27

Слайд 27

27 Приклад 5. МТ, яка кожне слово x  T* переводить у слово x # x, #  T q 0 t  q 0 tR для всіх t  T q 0  q 1 # L q 1 t  q 1 tL для всіх t  T q 1  q 2  R q 2 t  q t  R для всіх t  T q t p  q t pR для всіх t  T, p  T  {#} q t  q ' t tL для всіх t  T q ' t p  q ' t pL для всіх t  T, p  T  {#} q ' t  q 2 tR для всіх t  T q 2 #  q *#

Изображение слайда
1/1
28

Слайд 28

28 НОРМАЛЬНІ АЛГОРИТМИ МАРКОВА НА в алфавіті T – упорядкован f послідовність продукцій ( правил ) вигляду   або  , де ,     T * та   T,  T. Продукції вигляду   – фінальні. Кожен НА в алфавіті T задає деяке вербальне відображення T *→ T *  ( x ) – с лово, яке є результатом обробки слова x НА  Обробка слова x нормальним алгоритмом  – поетапно

Изображение слайда
1/1
29

Слайд 29

29 Покладемо x 0 = x і скажемо: x 0 отримано з x після 0 етапів. Нехай x n отримано з x після n етапів. Тоді ( n +1)- й етап вик - ся так. Шукаємо першу за порядком   або   таку, що  – підслово x n. Застосуємо цю продукцію до x n – замінимо в x n найлівіше входження  на . Отримане слово позначимо x n +1. – застосована на ( n +1)- етапі продукція не фінальна  перехід до ( n +2)- етапу – ця продукція фінальна  після її застосування  зупиняється і  ( x ) = x n +1. – на ( n +1)- етапі жодна продукція  не застосовна до x n +1, тобто в  немає продукції, ліва частина якої – підслово слова x n +1   зупиняється,  ( x ) = x n. Якщо в процесі обробки x НА  не зупиняється на жодному етапі, то  ( x ) невизначене.

Изображение слайда
1/1
30

Слайд 30

30 НА називають нормальним алгоритмом над алфавітом T, якщо він є НА у деякому розширенні T '  T. НА над T задає T *→ T *, використовуючи допоміжні символи  T. Зупинка НА  над T при роботі над x  T * результативна, якщо вона відбулась на слові y  T *, інакше результат роботи  над x невизначений. НА  і  еквівалентні відносно алфавіту T, якщо    x  T * –  ( x )  та  ( x )  або –  ( x )  та  ( x )  та  ( x ) =  ( x )   НА над T існує еквівалентний йому відносно T НА в T  { s } із єдиним допоміжним s  T. Відомо, що вербальне відображення x     xx, x  T *, не може бути заданим жодним НА в алфавіті Т.

Изображение слайда
1/1
31

Слайд 31

31 НА  обчислює часткову функцію f : N n → N, якщо він –   слово вигляду переводить в у випадку ( x 1,..., x k )  D f – невизначене при ( x 1,..., x k )  D f . Функція обчислювана за Марковим, або НА - обчислювана : існує НА, який її обчислює. Кожний НА обчислює безліч функцій натур. аргументів і значень Зафіксуємо наперед арність функцій    НА обчислює єдину функцію заданої арності.

Изображение слайда
1/1
32

Слайд 32

32 Приклад 1. НА для функції f ( x, y ) = x + y : #  Приклад 2. НА для функції x – y : |#|  # #|  #| #  Приклад 3. НА для функції x /2 : #||  |# #|  #| #   #

Изображение слайда
1/1
33

Слайд 33

33 Приклад 4. НА, який задає а x b y  | x  y : а b  ba | | b  b | a  b  Приклад 5. НА для функції x  y : #  |  a  |  b   а b  ba | | b  b | a  b 

Изображение слайда
1/1
34

Слайд 34

34 Приклад 6. НА для : | a      a || a |      | |       |       | Приклад 7. НА для функції 2 х :  |  |  |  #  |# #   #  

Изображение слайда
1/1
35

Слайд 35

35 Приклад 8. НА, який    x  T * x     x R ( тут #  T ): # ab  b # a    a,   b  T ## a #  a ##    a  T ##   # Приклад 9. НА, який    x  T * x     xx ( тут #  Т ): ## a  a # a ##    a  Т # ab  b # a    a,   b  Т # a  a    a  Т ##   ##

Изображение слайда
1/1
36

Слайд 36

36 СИСТЕМИ ПОСТА. КОМБІНАТОРНІ СИСТЕМИ Канонічна система Поста над алфавітом T – це ФС ( T *, A, P ), у якої –множина аксіом A є скінченною підмножиною множини T * – множина ПВ P – із слів вигляду Тут  T, усі  k та  і – фіксовані слова з T *, усі S k  T, усі j i  {1,..., m }. Символи S k призначені для позначення довільних слів з T *. СП позначаємо P = ( T, A, P ). Множина P визначає на словах із T * відношення безп. виведення  Р :     Р  , якщо існує правило таке : для деяких u 1,....,   u m  T *    =    0 u 1  1...  m –1 u m  m та Рефлексивно - транзитивне замикання відношення  Р позн.  * Р     * Р   означає, що  отримане із  за допомогою правил з P.

Изображение слайда
1/1
37

Слайд 37

37 Слово  породжується системою Поста P, якщо     * Р   для деякої  A. Це записуємо P |–  і називаємо таке слово  теоремою СП P. Множину Th ( P )   =   {  T *|   P   |–  } назвемо множиною теорем СП P. Для задання СП достатньо вказати множину правил і множину аксіом. У випадку необхідності вказуємо й алфавіт T. Приклад 1. СП з A  = { a, b,  } та P  = { S  aSa, S  bSb } породжує всі слова - паліндроми в алфавіті { a, b } Множина X  T * породжувана за Постом, якщо: існують алфавіт T'  T і СП P   = ( T',   A,  P ) такі, що Th ( P )  ( T *) = X.

Изображение слайда
1/1
38

Слайд 38

38 ФС вигляду ( T *, A, P ), у яких мн-на аксіом A – скінченна підмножина T *, а ПВ мають вигляд , називають комбінаторними. СП є комбінаторними системами досить загального вигляду. Правило gS  Sh називається правилом у нормальній формі. СП, усі правила якої – у нормальній формі, – нормальна СП Правило Sg  hS називається правилом в антинормальній формі. СП, усі правила якої – в антинормальній формі, – антинормальна СП. Кожна породжувана за Постом множина може бути породжена нормальною системою Поста. Те саме вірно й для антинормальних систем Поста.

Изображение слайда
1/1
39

Слайд 39

39 Напівтуевська система – це система Поста, усі правила якої мають вигляд S 1  S 2  S 1  S 2. Система Туе – це система Поста, усі правила якої мають вигляд S 1  S 2  S 1  S 2, причому   правила S 1  S 2  S 1  S 2 існує симетричне йому S 1  S 2  S 1  S 2. Якщо кожну пару симетричних правил системи Туе об ' єднувати в одне, то отримаємо комбінаторні системи, які називають екваційними численнями. Для екваційних числень правила записують у вигляді   .

Изображение слайда
1/1
40

Слайд 40

40 Окремим випадком СП можна вважати породжувальні, або формальні граматики, різноманітні класи яких вивчаються в програмуванні. Поняття формальної граматики тісно пов ’ язане з поняттям напівтуевських систем. При визначенні формальних граматик явно вказують основний ( термінальний ) алфавіт T, допоміжний ( нетермінальний ) алфавіт T N, єдину аксіому s  ( T N )* і правила виведення, які записують у вигляді , де ,   ( T  T N )*. Формальні граматики записують у вигляді G = ( T, T N, s, P ). Формальна граматика є системою Поста в алфавіті T  T N, усі правила якої мають вигляд S 1  S 2  S 1  S 2, а множина аксіом складається з єдиного слова s. Мова L ( G ), породжувана формальн ою граматик ою G, визначається як множина всіх теорем такої СП, які є словами термінального алфавіту.

Изображение слайда
1/1
41

Слайд 41

41 Класифікація формальних граматик за Хомським. ФГ, у якій немає обмежень на правила виведення, – граматика типу 0. ФГ, у якій для ПВ виконується умова |  |    |  |, називається нескоротною, або граматикою типу 1. ПВ для граматик типу 1 можна звести до  A   , де A  T N , . Такі ФГ називають також контекстними, контекстно - чутливими, або БС - граматиками. ФГ, у якій ПВ мають вигляд A , де A  T N, – граматикаою типу 2. Такі ФГ називають також безконтекстними, або контекстно - вільними, або КВ - граматиками. ФГ, у якій ПВ вигляду A  xB або A  x, де A  T N та x  T, – праволінійна. ФГ, у якій ПВ вигляду A  Bx або A  x, де A  T N та x  T, – ліволінійна. Праволінійні та ліволінійні грамматики утв. клас граматик типу 3. Такі граматики називають регулярними, або скінченно - автоматними.

Изображение слайда
1/1
42

Слайд 42

42 Наведеним класам граматик відповідають певні класи алгоритмічних машин ( автоматів ), які задають такі самі класи мов. Граматикам типу 0 відповідають недетерміновані МТ. Граматикам типу 1 відповідають лінійно - обмежені автомати – недетерміновані МТ, які не збільшують довжину робочої стрічки. Граматикам типу 2 відповідають автомати з магазинною пам’яттю, або магазинні автомати Граматикам типу 3 відповідають скінченні автомати.

Изображение слайда
1/1
43

Слайд 43

43 Обчислюваність функції за Постом означає породжуваність за Постом її графіка. Функція f   :  N n → N обчислювана за Постом, якщо множина породжувана за Постом Пр и клад 2. Система Поста для функції x + y : A = {##}; P = { X # Y # R  X |# Y # R |, X # Y # R  X # Y |# R | }. Приклад 3. Система Поста для функції f ( x, y ) = x–y : A = {##}; P = { X # Y # R  X |# Y # R |, X # Y # R |  X # Y |# R }.

Изображение слайда
1/1
44

Слайд 44

44 Пр и клад 4. Система Поста для функції f ( x, y ) = x  y : A = {##}; P = { X # Y # R  X |# Y # RY, X # Y # R  X # Y |# RX }. Пр и клад 5. Система Поста для функції f ( x ) = x 2 : A = {#}; P = { X # R  X |# R ХХ |}.

Изображение слайда
1/1
45

Слайд 45

45 Приклад 6. Система Поста для функції f ( x ) = x 2 – 2 x : A = {#, ||#}; P = { X |# R  X ||# RXX |}. Треба врахувати, що f (1) . Приклад 7. Система Поста для функції f ( x ) = x 3 : A = {  }; P = { X  Q  R  X |  QXX |  RQQQXXX |, X  Q  R  X # R }. Для обчислення f ( x +1) = ( x +1) 3 = f ( x )+3 x 2 +3 х +1 потрібне  x 2, тому теоремами СП мають також бути коди трійок ( x,   x 2,   x 3 ). Однак теоремами в алфавіті {|,   #} можуть бути тільки коди елементів графіка f ( x ), тому для кодування трійок ( x,   x 2,   x 3 ) використано .

Изображение слайда
1/1
46

Слайд 46

46 Приклад 8. Система Поста для функції f ( x ) = x !: A = {#|}; P = { X # F  X |  F , S  F  A  B  M  S  F  A |  B  MB, S  F  A  B  M  S  F  A  B |  MA, S  F  S  F  M  S # M }. До теорем СП належать коди п’ятірок ( x +1,   x !,  a,  b,  ab ), для їх кодування використано . З кодів п’ятірок ( x +1, x !, x +1, x !, ( x +1)  x !) можна вивести закодовані в алфавіті {|, #} коди пар ( x +1, ( x +1)!).

Изображение слайда
1/1
47

Слайд 47

47 Приклад 9. Система Поста для функції A = {  }; P = { X  X | , QS |  Q  R  QS |  QRR |  R |, X  X  R  X # R, X  XS |  R |  X # R }. До теорем СП належать коди трійок ( x, r 2, r ), для їх код - ня вик-но . З кодів трійок ( x,   x,  r ) та ( x,   ( r +1) 2,  r +1) за умови r 2     х  < ( r  + 1) 2 можна вивести закодовані в алфавіті {|, #} коди пар ( x, r ).

Изображение слайда
1/1
48

Слайд 48

48 Основна література 1. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983. 2. Клини С. Математическая логика. – М.: Наука, 1973. 3. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М., 1975. 4. Лісовик Л.П., Шкільняк С.С. Теорія алгоритмів. – К., 2003. 5. Мальцев А.И. Алгоритмы и рекурсивные функции. – М., 1965. 6. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. – К., 2008. 7. Нікітченко М.С., Шкільняк С.С. Основи математичної логіки. – К., 200 6 8. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М., 1972 9. Шкільняк С.С. Теорія алгоритмів: приклади і задачі. – К., 2003. 10. Шкільняк С.С. Математична логіка: приклади і задачі. – К., 200 7.

Изображение слайда
1/1
49

Последний слайд презентации: 1 ТЕОРІЯ АЛГОРИТМІВ Алгоритм – скінченна множину точно визначених правил для

49 Додаткова література 1. Д.Гильберт, П.Бернайс. Основания математики. Т.1, Т.2. – М., 1982. 2. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра, языки, программирование.– К., 1974. 3. Ю.В.Капітонова, С.Л.Кривий, О.А.Летичевський, Г.М.Луцький, М.К.Печурін. Основи дискретної математики. – К., 2002. 4. Лисовик Л.П., Редько В.Н. Алгоритмы и формальные системы. – К., 1981. 5. Манин Ю.И. Доказуемое и недоказуемое. – М., 1979. 6. Манин Ю.И. Вычислимое и невычислимое. – М., 1980. 7. Мендельсон Э. Введение в математическую логику. – М., 1976. 8. Непейвода Н.Н.. Прикладная логика. – Новосибирск: НГУ, 2000. 9. Справочная книга по математической логике (под ред. Дж.Барвайса). Ч.1– 4. – М., 1982–1983. 10. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М., 1987. 11. Шенфилд Дж. Математическая логика. – М.: Наука, 1975.

Изображение слайда
1/1
Реклама. Продолжение ниже