Основні алгоритмічні теорії

Размещено на http://www.allbest.ru/

Основні алгоритмічні теорії

Вступ

Теорія алгоритмів (ТА) виникла з внутрішньої потреби математики. Математична логіка, метаматематика, алгебра, геометрія і аналіз залишаються і сьогодні однією з основних областей застосування теорії алгоритмів. Інша область її застосування появилася в 40-х роках ХХ-го століття -- при створенні ефективних (перш за все швидкодіючих) електронних обчислювальних машин (ЕОМ). Поява ЕОМ особливо сприяла розвиткові тих розділів ТА, що мали яскраво виражену прикладну спрямованість. Сюди насамперед належали алгоритмічні системи і алгоритмічні мови (основа теорії програмування) універсальних ЕОМ, цифрові автомати. Саме поняття алгоритму тісно пов'язане з лінгвістикою, економікою, фізіологією мозку і психологією, філософією і природознавством тощо. Прикладом може послужити розумова чи практична діяльність людини у будь- якій сфері. Підвищення ефективності технологій виробництва, транспорту, зв'язку, енергетики, медицини тощо, а також відбору, зберігання, поширення, створення відповідних знань потребували удосконалення та розвитку інформаційних (вимірювальних) та управляючих (керуючих) алгоритмів. Це успішно здійснюється на базі математичних моделей величин, сигналів, фізичних полів. Виникла теорія таких алгоритмів. Отже, для математика ТА -- означення поняття алгоритму, алгоритмічні системи (рекурсивні функції, машини Тюрінга, нормальні алгоритми Маркова та ін.), формальні перетворення і оцінки алгоритмів, теорія автоматів і універсальні ЕОМ, формальна побудова і аналіз мов програмування тощо.

1. Основні теоретичні відомості

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

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

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

Виник важливий напрямок в теорії алгоритмів - складність алгоритмів і обчислень. Почала складатися так звана метрична теорія алгоритмів, основним змістом якої є класифікація задач за класами складності. Самі алгоритми стали об'єктом точного дослідження як і ті об'єкти, для роботи з якими вони призначені.

Якщо показується, що складність (час або пам'ять) обчислення для цього алгоритму не перевищує значення підходящої функції при всіх значеннях аргументу, то ця функція оголошується верхньою оцінкою складності рішення розглянутої задачі. В області знаходження верхніх оцінок отримано 7 багато яскравих результатів для конкретних задач. Серед них розроблені швидкі алгоритми множення цілих чисел, багаточленів, матриць, рішення лінійних систем рівнянь, які вимагають значно менше ресурсів, ніж традиційні алгоритми.

У зв'язку з цим отримала розвиток проблематика отримання «відносних» нижніх оцінок, так звана теорія NP-повноти, яка пов'язана з труднощами розв'язку задач перебору.

Розглянемо неформально, що саме в інтуїтивному понятті алгоритму потребує уточнення.

Основні вимоги до алгоритмів:

1. Кожен алгоритм має справу з даними - вхідними, проміжними, вихідними. Для того, щоб уточнити поняття даних, фіксується кінцевий алфавіт вихідних символів (цифри, букви і т.п.) і вказуються правила побудови алгоритмічних об'єктів. Типовим використовуваним засобом є індуктивна побудова. Наприклад, визначення ідентифікатора в Алгол: ідентифікатор - це або буква, або ідентифікатор, до якого приписана праворуч або буква, або цифра. Слова кінцевої довжини в кінцевих алфавітах - найбільш звичайний тип алгоритмічних даних, а число символів в слові - природна міра об'єму даних. Інший випадок алгоритмічних об'єктів - формули. Прикладом можуть служити формули алгебри предикатів і алгебри висловлювань. У цьому випадку не кожне слово в алфавіті буде формулою.

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

3. Алгоритм складається з окремих елементарних кроків, причому множина різних кроків, з яких складений алгоритм, кінцеві. Типовий приклад множини елементарних кроків - система команд процесора.

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

5. Алгоритм повинен бути результативним, тобто зупинятися після кінцевого числа кроків (залежного від вхідних даних) з видачею результату. Дана властивість іноді називають збіжністю алгоритму.

6. Алгоритм передбачає наявність механізму реалізації, який за описом алгоритму породжує процес обчислення на основі вхідних даних. Передбачається, що опис алгоритму та механізм його реалізації кінцеві. Можна помітити аналогію з обчислювальними машинами. Вимога 1 відповідає цифровій природі ПК, вимога 2 - пам'ять ПК, вимога 3 - програмі машини, вимога 4 - її логічній природі, вимоги 5, 6 - обчислювальному пристрою і його можливостям.

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

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

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

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

Іншою теоретичною моделлю даного типу є машина довільного доступу (МДД) - введена досить недавно (у 70-х роках) з метою моделювання реальних обчислювальних машин та отримання оцінок складності обчислень.

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

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

Теорія алгоритмів має істотний вплив на розвиток ЕОМ і практику програмування. В теорії алгоритмів передбачені основні концепції, які закладені в апаратуру і мови програмування ЕОМ. Згадувані вище основні алгоритмічні моделі математично еквівалентні. Але на практиці вони істотно розрізняються ефектами складності, що виникають при реалізації алгоритмів, і породили різні напрямки в програмуванні. Так, мікропрограмування будується на ідеях машин Тьюринга, структурне програмування запозичило свої конструкції з теорії рекурсивних функцій, мови символьної обробки інформації (РЕФАЛ, ПРОЛОГ) беруть початок від нормальних алгоритмів Маркова та систем Посту.

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

Початковою точкою відліку сучасної теорії алгоритмів вважають роботу німецького математика Курта Геделя (1931 рік - теорема про неповноту символічних логік.

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

2. Машина Поста

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

Наприклад, рішення рівняння 3*х +9 = 0 - це одна з конкретних проблем, а рішення рівняння a * x + b = 0 - це загальна проблема.

Алгоритм (сам термін «алгоритм» не використовується Постом) повинен бути універсальним, тобто повинен бути співвіднесений із загальною проблемою. .

Таблиця 1. Постівський простір символів.

	V			V	V	V		V

Постівський простір символів - це нескінченна стрічка комірок (ящиків). Кожен ящик або комірка можуть мати або не мати позначки див. таб. 1.

Конкретна проблема задається «зовнішньою силою» (термін Посту) - позначкою кінцевого кількості комірок, при цьому, очевидно, що будь-яка конфігурація починається і закінчується поміченою коміркою.

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

Пост запропонував набір інструкцій (елементарних операцій), які виконує «працівник». Відзначимо, що в 1936 році не було ще жодної електронної обчислювальної машини. Огляд мінімальних команд, представлений нижче або в таблиці 2.

1) Помітити ящик, якщо він порожній.

2) Стерти мітку, якщо вона є.

3) Переміститися вліво на 1 ящик.

4) Переміститися вправо на 1 ящик.

5) Визначити чи має ящик позначку або ні, і за результатом перейти на одну з двох зазначених інструкцій.

6) Зупинитися.

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

Ще систему команд можна зобразити таким чином:

Таблиця 2. Система команд в машині Поста

№ п/п	Команда		Опис дій машини
1	Крок вправо		Переміщення на одну секцію вправо
2	Крок вліво		Переміщення на одну секцію вліво
3	Установка мітки		В утворену секцію установлюється мітка
4	Стирання мітки		З утвореної секції видаляється мітка
5	Передача керування		При відсутності мітки в утворенії секції управління передається команді , при наявності команди
6	Зупинка	x стоп	Завершення роботи машини

3. Машина Тьюрінга

Алан Тьюрінг (Turing) в 1936 році опублікував у працях Лондонського математичного товариства статтю, яка нарівні з роботами Посту і Черча, лежить в основі сучасної теорії алгоритмів.

Модель обчислень, в якій кожен алгоритм розбивався на послідовність простих, елементарних кроків і була логічною конструкцією, названої згодом машиною «Тьюрінга».

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

У кожній машині Тьюрінга є дві частини:

1) необмежена в обидві сторони стрічка, розділена на клітинки;

2) автомат (каретка для зчитування / запису, керована програмою).

З кожною машиною Тьюрінга пов'язані два кінцевих алфавіту:

- алфавіт вхідних символів A = {a0, a1, ..., am}

- алфавіт станів Q = {q0, q1, ..., qp}.

(З різними машинами Тьюрінга можуть бути пов'язані різні алфавіти A і Q.)

Стан q0 називається пасивним. Вважається, що якщо машина потрапила в цей стан, то вона закінчила свою роботу.

Стан q1 називається початковим. Перебуваючи в цьому стані, машина починає свою роботу

Вхідне слово розміщується на стрічці по одній літери в розташованих підряд клітинках. Ліворуч і праворуч від вхідного слова знаходяться тільки порожні клітинки (в алфавіт А завжди входить порожня буква а0 - ознака того, що клітинка порожня).

Автомат може рухатися вздовж стрічки вліво або вправо, читати вміст комірок і записувати в клітинку літери. Автомат кожного разу "бачить" тільки одну клітинку. Залежно від того, яку літеру він бачить, а також залежно від свого стану qj автомат може виконувати наступні дії: :

- записати нову букву в клітинку, що оглядається;

- виконати зрушення по стрічці на одну клітинку вправо / вліво або залишитися нерухомим;

- перейти в новий стан.

Тобто у машини Тьюрінга є три види операцій. Щоразу для чергової пари (qj, ai) машина Тьюрінга виконує команду, що складається з трьох операцій з певними параметрами.

Програми для машин Тьюрінга записуються у вигляді таблиці, де перші стовпець і рядок містять літери зовнішнього алфавіту та можливі внутрішні стани автомата (внутрішній алфавіт). Вміст таблиці являє собою команди для машини Тьюрінга. Літера, яку зчитує каретка в клітинці (над якою вона знаходиться в даний момент), і внутрішній стан каретки визначають, яку команду потрібно виконати. Команда визначається перетином символів зовнішнього і внутрішнього алфавітів в таблиці.

Щоб задати конкретну машину Тьюрінга, потрібно описати для неї наступні складові:

- Зовнішній алфавіт. Кінцева безліч (наприклад, А), елементи якої називаються літерами (символами). Одна з літер цього алфавіту (наприклад, а0) повинна являти собою порожній символ.

- Внутрішній алфавіт. Кінцева безліч станів каретки (автомата). Один зі станів (наприклад, q1) повинний бути початковим (що запускає програму). Ще один зі станів (q0) повинний бути кінцевим (завершальним програму) - стан зупинки.

- Таблиця переходів. Опис поведінки автомата (голівки) в залежності від стану і символу, що зчитується. 26 Одна команда для машини Тьюрінга якраз і являє собою конкретну комбінацію цих трьох складових: вказівок, який символ записати в комірку (над якою стоїть автомат), куди пересунутися і в який стан перейти. Хоча команда може містити і не всі складові (наприклад, не змінювати символ, не пересуватися або не змінювати внутрішній стан).

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

На прикладі машини Тьюрінга добре простежуються властивості алгоритмів. - Дискретність. Машина Тьюрінга може перейти до (к + 1)-го кроку тільки після виконання к-го кроку, оскільки саме к-й крок визначає, яким буде (до + 1) -й крок.

- Зрозумілість. На кожному кроці в комірку пишеться символ з алфавіту, автомат робить один рух (Л, П, Н) і машина Тьюрінга переходить в один з описаних станів.

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

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

- Масовість. Кожна машина Тьюрінга визначена над усіма допустимими словами з алфавіту, в цьому і полягає властивість масовості. Кожна машина Тьюрінга призначена для вирішення одного класу задач, тобто для кожного.

Рисунок 1.Приклад роботи машини Тьюрінга

Отже, Машина Тьюрінга складається з необмеженої в обидва боки стрічки, розділеної на гнізда, послідовно пронумеровані цілими числами, як позитивними, так і негативними. У кожнім гнізді стрічки може стояти будь-який символ із заданого алфавіту, у якім виділений «порожній» символ -- ознака того, що гніздо порожнє.

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

Програма -- це таблиця, у якій у кожній клітці записана команда. Кожна клітка визначається двома параметрами -- символом алфавіту й станом машини. Команда -- ця вказівка, куди пересунути головку читання/запису з поточного стану, який символ записати в поточне гніздо й у який стан перейде машина.

Машина Тьюрінга -- це модель комп'ютера. Машина одержала ім'я математика А. Тьюрінга (Англія) і вирішує наступну проблему: якщо для рішення завдання можна побудувати машину Тьюрінга, вона алгоритмічно розв'язна.

І машина Тьюрінга, і машина Поста еквівалентні по своїх можливостях.

Розроблені практично в те саме час (в 1936 р.) незалежно друг від друга.

чи Можна будь-який алгоритм представити у формі машини Тьюрінга? Відповідь на це питання дається у вигляді так званого тези Тьюрінга: усякий алгоритм представимо у формі машини Тьюрінга.

Клас нормальних алгоритмів Маркова й клас алгоритмів, представлених у формі машин Тьюрінга, збігаються.

4. Алгоритми Маркова

Нормальний алгоритм Маркова -- система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті. У 1956 році вітчизняним математиком А.А. Марковим було запропоновано нове уточнення поняття алгоритму, яке пізніше було названо його ім'ям. У цьому уточненні виділені нами 7 параметрів були визначені таким чином:

· Сукупність початкових даних - слова в алфавіті S;

· Сукупність можливих результатів - слова в алфавіті W;

· Сукупність можливих проміжних результатів - слова в алфавіті

· Р = SWV, де V - алфавіт службових допоміжних символів.

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

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

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

Алгоритми, побудовані у межах нормальних алгоритмів Маркова, зручніше за все представляти за допомогою граф-схем. Точки, що на граф-схемі відповідають підстановкам, мають одну вихідну стрілку, точки, що відповідають розпізнавачу, мають дві вихідні стрілки.

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

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

У нормальних алгоритмах використовується один тип елементарних операторів -- оператори підстановок, та один тип елементарних розпізнавачів -- розпізнавачі входження. Залежно від того, як з'єднуються вузли, алгоритми розрізняються між собою: якщо в нормальних алгоритмах у будь-який оператор підстановки можна потрапити тільки за стрілкою з відповідного до нього розпізнавача, то такий алгоритм називається узагальненим нормальним алгоритмом Рис. 2.



Рисунок 2. Узагальнений нормальний алгоритм Маркова

А власне нормальні алгоритми відрізняються від узагальнених нормальних алгоритмів тим, що відповідають таким умовам:

1) всі вузли впорядковуються та нумеруються натуральними числами 1, ..., n;

2) стрілки, що виходять з точки оператора підстановки, прямують або до першого розпізнавача, або до вузла «вихід». В останньому випадку підстановка називається заключною, вона може бути не одна в алгоритмі;

3) вхідний вузол з'єднується з першим розпізнавачем.

Такий зв'язок між вузлами реалізує певний порядок обробки вхідного слова: процес перетворення закінчується, коли жодна з підстановок не може бути застосована Рис. 3. або коли виконується одна з заключних підстановок.

Рисунок 3. Нормальний алгоритм Маркова

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

Існують різні способи композиції нормальних алгоритмів, які дозволяють отримувати нові алгоритми у класі нормальних алгоритмів:

1. Суперпозиція двох алгоритмів А та В є алгоритм С -- такий, що вихідне слово алгоритму А є вхідним словом до алгоритму В, тобто: С(р) = В(А(р)). Суперпозиція може виконуватись для будь-якої кількості алгоритмів.

2. Об'єднання двох алгоритмів А та В є алгоритм С, який перетворює слово р, що належить перетину областей визначення алгоритмів А та В, у слово С(р) = А(р) В(р).

3. Розгалуження алгоритмів -- це така композиція з трьох алгоритмів А, В, С, тобто такий алгоритм D, область визначення якого є перетином областей визначення алгоритмів А, В, С, а діє він на слово з області визначення таким чином:

4. Повторення (ітерація) двох алгоритмів А та В -- це така їх композиція С, що до будь-якого слова p багаторазово застосовується алгоритм А, доки не отримаємо слово, яке потім перетворюється алгоритмом В у деяке фіксоване слово.

Отже, Нормальний алгоритм в алфавiтi T (скорочено НА в алфавiтi T ) - це упорядкована послідовність підстановок (продукцій, правил) вигляду або , де * , T та , T . Підстановки вигляду називають фінальними, а - простими. Довільну скінченну послідовність підстановок називають схемою нормального алгоритму. Кожен НА в алфавіті T задає певне словарне відображення * * T T . Слово, яке є результатом обробки слова x нормальним алгоритмом A , позначимо A x. Слово входить в слово , якщо існують слова 1 та 2 (можливо порожні) такі, що 1 2 . Обробку слова x нормальним алгоритмом A проводять поетапно. Нульовий етап. Покладемо 0 x x i скажемо, що 0 x отримане з x після 0 етапів. n 1-й етап. Нехай слово n x отримане зі слова x після n етапів. Шукаємо першу за порядком продукцію або таку, що пiдслово n x . Застосуємо цю продукцію до n x , тобто замінимо в n x найлiвiше входження на . Отримане слово 39 позначимо n 1 x . Якщо застосована на n 1-му етапі продукція не фінальна, тобто , то переходимо до n 2-го етапу. Якщо ця продукція фінальна, тобто , то після її застосування нормальний алгоритм A зупиняється i n 1 x x A . Якщо ж на n 1-му етапі жодна продукція нормального алгоритму A незастосовна до n x , тобто в A немає продукцiй, ліва частина яких - пiд слово слова n x , то A зупиняється i n A x x .

Якщо в процесі обробки слова x НА A не зупиняється ні на якому етапі, то вважаємо, що результат обробки слова x нормальним алгоритмом A невизначений. Нормальний алгоритм називають нормальним алгоритмом над алфавітом T , якщо він - нормальний алгоритм у деякому розширенні T T. НА над Т задає словарне відображення * * T T , використовуючи в процесі обробки слів допоміжні символи поза алфавітом T. Зупинка НА над T у роботі над словом * x T є результативна, коли алгоритм зупинився з результатом * y T, інакше результат роботи нормального алгоритму над словом x невизначений. Зауважимо, що порожній символ у необмеженій кількості зустрічається перед/між/після будь-яких символів скінченного алфавіту T .

Нормальні алгоритми A i B еквівалентні відносно алфавіту T, якщо для всіх * x T значення A x та B x одночасно визначені або невизначені, та у випадку визначеності A B x x . Відомо, що для кожного НА над алфавітом T існує еквівалентний йому відносно T НА в алфавіті T s з єдиним допоміжним символом s T. Словарне відображення, яке кожне слово * x T переводить у слово xx , не може бути заданим жодним НА в алфавіті T, але це можна зробити в алфавіті Т.?

Розглянемо деякі поняття асоціативного обчислення. Нехай є алфавіт (кінцевий набір різних символів). Складові його символи будемо називати буквами. Будь-яка кінцева послідовність літер алфавіту (лінійний їх ряд) називається словом в цьому алфавіті.

Розглянемо два слова N и М в деякому алфавіті А. якщо N є частиною М, то кажуть, що N входить в М.

Задамо в деякому алфавіті кінцеву систему підстановок N - М, S - Т, ..., де N, М, S, Т, ... - слова в цьому алфавіті. будь-яку підстановку N-M можна застосувати до деякого слову К в такий спосіб: якщо в К є одне або кілька входжень слова N, то будь-яка з них може бути замінено словом М, і, навпаки, якщо є входження М, то його можна замінити словом N.

Наприклад, в алфавіті А = {а, b, с} є слова N = ab, М = bcb, К = abcbcbab, Замінивши в слові К слово N на М, отримаємо bcbcbcbab або abcbcbbcb, і, навпаки, замінивши М на N, отримаємо aabcbab або аbсаbаb. Підстановка ab - bcb недопустима до слова bacb, так як ні ab, ні bcb не входить до цього слово. До отриманих за допомогою допустимих підстановок словами можна знову застосувати допустимі підстановки і т. Д. Сукупність усіх слів в даному алфавіті обчисленням. Щоб задати асоціативне обчислення, досить задати алфавіт і систему підстановок.

5. Лямбда-числення

Лямбда-числення, або л-числення -- формальна система, що використовується в теоретичній кібернетиці для дослідження визначення функції, застосування функції, та рекурсії. Це числення було запропоноване Алонсо Черчем та Стівеном Кліні в 1930-ті роки, як частина більшої спроби розробити базис математики на основі функцій, а не множин (задля уникнення таких перешкод, як Парадокс Рассела). Однак Парадокс Кліні-Россера демонструє, що лямбда-числення не здатне уникнути теоретико-множинних парадоксів. Незважаючи на це, лямбда-числення виявилось зручним інструментом в дослідженні обчислюваності функцій, та лягло в основу парадигми функціонального програмування^.

Лямбда-числення можна розглядати як ідеалізовану, мінімалістичну мову програмування, в цьому сенсі лямбда-числення подібне до машини Тюрінга, іншої мінімалістичної абстракції, здатної визначати будь-який алгоритм. Відмінність між ними полягає в тому, що лямбда-числення відповідає функціональній парадигмівизначення алгоритмів, а машина Тюрінга, натомість -- імперативній. Тобто, машина Тюрінга має певний «стан» -- перелік символів, що можуть змінюватись із кожною наступною інструкцією. На відміну від цього, лямбда-числення уникає станів, воно має справу з функціями, котрі отримують значення параметрів та повертають результати обчислень (можливо, інші функції), але не спричиняють до зміни вхідних даних (сталість).

Ядро л-числення ґрунтується трохи більше ніж на визначені змінних, області видимості змінних та впорядкованому заміщенні змінних виразами. л-числення є замкненою мовою, тобто, семантика мови може бути визначена на основі еквівалентності виразів (або термів) самої мови.

Типізоване лямбда-числення -- це система лямбда-числення, у якій кожний вислів має тип. У цьому контексті тип -- це формула певної системи числення, як-от (інтуїціоністської) пропозиційної логіки або логіки першого порядку.

6. Рекурсивні функції

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

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

Поняття рекурсивних функцій:

Базовими примітивними функціями, за визначенням, є:

1. нульова функція

2. функція слідування

3. функція проектування

Операція суперпозиції.

Функція виникає із функцій , ,…, суперпозицією, якщо

Операція примітивної рекурсії

Функція виникає функцій при-мітивною рекурсією якщо для всіх натуральних значень маємо

Операція мінімізації.

Позначимо через найменше значення , для якого . Будемо вважати, що не визначено, якщо:

1. значення визначено для всіх y < б, але відмінні від xn, а значення невизначено (б=0, 1, 2, …).

2. значення визначені для всіх б = 0, 1, 2, … та відмінні від xn. Таким чином, значення є функцією від змінних Кажуть, що ця функція отримана від функції із допомогою мінімізації.

Примітивно рекурсивна функція.

Функція називається примітивно рекурсивною, якщо її можна отримати із функцій та скінченною кількістю операцій суперпозиції та примітивної рекурсії.

Частково рекурсивна функція

Функція називається частково рекурсивною, якщо отримана із вказаних функцій застосуванням скінченної кількості операцій суперпозиції, примітивної рекурсії та мінімізації. Всюди визначена частково рекурсивна функція називається загально рекурсивною.

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

У теорії рекурсивних функцій доведені наступні теореми:

Теорема 1. Для всіх {\displaystyle n=1,2,\dots }n=1,2,… системи всіх {\displaystyle n}n-місних примітивно-рекурсивних функцій не містить примітивно-рекурсивної універсальної функції.

Теорема 2. Система всіх {\displaystyle n}n-місних загально-рекурсивних функцій не містить загально-рекурсивної універсальної функції {\displaystyle (n=1,2,\dots )}(n=1,2,…)

Теорема 3. Для кожного n=1,2,…{\displaystyle n=1,2,\dots } клас всіх {\displaystyle n}n-місних примітивно-рекурсивних функцій містить {\displaystyle (n+1)}(n+1)-місну загально-рекурсивну універсальну функцію.

Теорема4. Для кожного n=1,2,… {\displaystyle n=1,2,\dots }існує частково-рекурсивна функція{\displaystyle \varphi _{n}^{n+1}(x_{0},x_{1},\dots ,x_{n})} універсальна для класу всіх {\displaystyle n}n-місних частково- рекурсивних функцій.

Висновки

Теорія алгоритмів -- окремий розділ математики, що вивчає загальні властивості алгоритмів. Виникла в 30-х роках 20 століття. Поняття алгоритму належить не лише до фундаментальних наукових понять, а й до людських надбань. Будь-яку людську діяльність можна подати у вигляді алгоритмічного процесу. Автори огляду основних досягнень теорії алгоритмів стверджують: "Алгоритмічні концепції відіграють у процесі навчання і виховання сучасної людини фундаментальну роль, порівнянну лише з роллю писемності".

Теорія алгоритмів подібна до математичної логіки. Із семантичними об'єктами, що несуть у собі зміст, математики, ще не звикли поводитися. Сенс терму або формули в математичній логіці “вказівний“: терм вказує на річ (тобто позначає), а формула - на факт. Сенс алгоритму “наказовий“: алгоритм повинен бути виконаний. Таким чином, теорія, що вивчає алгоритми, може трактуватися як свого роду лінгвістика наказових пропозицій. І, по-третє, теорія алгоритмів виникла на стику математики та інформатики. Тому вчені з обох боків “тягнули до себе ковдру“ при побудові теорії алгоритмів. Цю специфіку можна помітити, вивчаючи монографії та підручники з теорії алгоритмів. Залежно від того, ким вони написані - математиками чи знавцями інформатики, ми відчуваємо особливість змісту матеріалу, відображеного в них.

Алгоритми, проте, простежуються в математиці протягом всього часу її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв'язку багатьох масових проблем, в першу чергу пов'язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул та формул першопорядкового числення предикатів, 10-та проблема Гільберта про розв'язність діофантових рівнянь та ін.). Для доведення неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерговою стала проблема знаходження адекватних

Список використаної літератури

алгоритм програмування машина тьюрінга

1. Л. М. Клакович, С. М. Левицька. Теорія алгоритмів: Навчальний посібник. -- Друге видання, доповнене. -- Львів : Видавничий центр ЛНУ ім. Івана Франка, 2015. -- 161 с.

2. «Енциклопедія кібернетики», відповідальний ред. В. Глушков, 2 тт., 1973.

3. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика / А.В. Могилев, Н.И. Пак, Е.К. Хеннер - М.: Академия, 2004. - 848 с.

4. Фаронов В.В. Турбо Паскаль 7.0 / В.В. Фаронов - М.: «ОМД Групп», 2003. - 616 с.

5. Математическая энциклопедия. - М.: Советская энциклопедия И. М. Виноградов 1977-1985

6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -- М. : Мир, 1982. -- 416 с. Пенроуз Р. Новый ум короля. -- М. : URSS, 2011. -- 400 с.

7. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. -- М. : Вильямс, 2007. -- 528 с.

8. Эббинхауз Г.-Д., Якобс К., Ман Ф.-К., Хермес Г. Машины Тьюринга и рекурсивные функции. -- М. : Мир, 1972. -- 264 с.

9. Джон Хопкрофт, Раджів Мотані, Джеффрі Ульман РОЗДІЛ 8. Введення в теорію машин Тюрінга // Введення в теорію автоматів, мов і обчислень. - М., 2002. - С528.

10. Енциклопедія кібернетики, т. 2, с. 290-292

Размещено на Allbest.ru

...