Кафедра: Автоматика та інформаційні технології
ТЕОРІЯ АЛГОРИТМІВ
Єкатеринбург
2006
Наводиться формалізація поняття «алгоритм». Обговорюються два способи формального опису алгоритму-за допомогою нормальних алгоритмів Маркова і через машини Тьюрінга. Наводяться міри складності алгоритмів, визначаються легко і важковирішувані завдання, класи завдань P і NP, алгоритмічно нерозв'язні проблеми.
Зміст
ФОPМАЛІЗАЦІЯ ПОНЯТТЯ Алгоpитм
Визначення
Нормальний алгоритм Маркова
Теза Маркова
Машина Тьюрінга
Основна гіпотеза теорії алгоритмів (теза Черча)
Універсальна машина Тьюрінга
Застережні СКЛАДНОСТІ Алгоpитм
Оцінка алгоритму
Практичні та NP-повні алгоритми
Алгоритмічно нерозв'язні проблеми
«Формалізація поняття алгоритму; Машина Тьюрінга. Теза Черча; Алгоритмічні нерозв'язні проблеми. Заходи складності алгоритмів. Легко і важковирішувані завдання. Класи задач P і NP. NP - повні задачі. Поняття складності обчислень; ефективні алгоритми. »(Зі стандарту спеціальності ВМКСС, дисципліна« Математична логіка і теорія алгоритмів)
Індивідуальна завдання виходить з масовою, якщо всім параметрам масової завдання присвоїти конкретні (допустимі) значення.
Під алгоритмом прийнято розуміти кінцеву послідовність операцій, називаються елементарними, виконання якої призводить до вирішення будь-якої задачі з заданої множини завдань. У це визначення входять такі властивості алгоритму, як дискретність, кінцівку (кінцеве число виконуваних операцій), масовість (вирішується не єдине завдання, а їхній клас), результативність (в результаті отримуємо рішення задачі). Крім того, має виконуватися ще одна необхідна властивість алгоритму - детермінізм, яке визначається як однозначне розуміння кожної операції, або, що те ж саме, незалежність результату виконання кожної елементарної операції від того, хто її виконує.
Під це визначення підходить широке коло алгоритмів. Це може бути алгоритм обчислення математичної функції, алгоритм технологічного процесу, алгоритм проектування ЕОМ або цеху заводу і т.д. Елементарні операції можуть бути досить складними: при обчисленні функції це може бути, наприклад, знаходження коренів рівняння, в проектних або технологічних алгоритмах - прийняття складних проектних або технологічних рішень.
Дане вище визначення алгоритму не є формалізованим і суворим з двох причин. По-перше, в ньому не формалізоване поняття елементарної операції, і, по-друге, не формалізоване подання послідовності операцій. Важливість розробки спільного для всіх алгоритмів формального опису полягає в тому, що воно дає можливість мати спільні інструментарії для порівняння, оцінки, перетворення та інших дій над алгоритмами.
Формалізація операцій алгоритмів пов'язано з наступним. Будь-який алгоритм визначений для деякого об'єкта дії, кожен об'єкт представляється у вигляді опису, причому описом може бути не тільки тексти мовою, але й малюнки, креслення і т.п. Значить, можна припустити, що об'єкт описаний у вигляді слова в заданому алфавіті.
Об'єкт може знаходитися в різних станах, чому відповідають різні слова. Так, об'єктом для математичних алгоритмів є математичний опис завдання у формі матриць коефіцієнтів, графа суміжності і т.п.т., для проектних алгоритмів - проектований об'єкт у вигляді технічного завдання на проектування або перелік вимог та умов до результату.
Операція визначається над описом об'єкта і її результатом є нове (змінене) опис (нове слово). Наприклад, якщо вирішується графова завдання, то результатом операції може бути опис графа з проміжним зважуванням ребер і / або вершин. Результатом проектної операції буде більш повне, уточнене опис об'єкта.
Результатом роботи всього алгоритму в графових завданню може бути виділений шлях або ланцюг, частковий підграф або ваги вершин чи ребер. Результатом роботи алгоритму проектування є опис об'єкта проектування, достатній для його виготовлення в заданій технологічній базі.
Розглянемо кілька способів формального опису алгоритмів.
Алгоритм задають у вигляді системи підстановок, що реалізують відображення слів pi в слова qi.
pi ® qi = 1, ..., k.
Порядок підстановок зафіксований. Об'єктом i-й елементарної операції алгоритму є слово в алфавіті A, операція полягає в знаходженні в цьому слові першому зліва входження слова pi і заміну його на qi. Результатом операції буде змінене слова, якщо входження знайдено, або вхідне слово, якщо не найдено.Факт заміни фіксується і використовується в організації проходження операцій.
Початкове завдання представляється деяким словом в алфавіті A. Це слово є вхідним для першої операції, якщо заміна відбулася, то знову виконується перша операція, якщо немає, то виконується наступна операція. Після кожної операції виконується наступна операція, якщо заміна відбулася, інакше переходять до виконання першої операції.
Алгоритм зручно представити у вигляді орієнтованого графа, вершинами якого є елементарні оператори і розпізнавачі.
Розпізнавач перевіряє умову - чи має місце входження рi у вхідний слово p. Якщо ТАК, то за ним слід оператор, який замінює перший зліва входження слова рi на слово qi. Якщо НІ, то управління передається на вхід наступного розпізнавача.
Дуги, що виходять з операторних вершин, приєднуються або до першої вершини - розпізнавача, або до вихідний вершині. У першому випадку підстановка називається звичайної, у другому - заключної.
Крім того, є вхідна і вихідна вершини. Вхідна вершина пов'язані дугою з першим розпізнавачем.
На вхід графа подається деякий вхідне слово p.
Приклад. Граф для трьох підстановок (к = 3) (рис.1) має три розпізнавача (РВ1, РВ2, РВ3) і три операторні вершини (ОП1, ОП2, ОП3).
Якщо підстановки задані як ba ® ab, bc ® ba, bb ® ac, а вхідний слово
р = bcbaab, то робота алгоритму буде мати наступний вигляд.
SHAPE \ * MERGEFORMAT
Пpимеp. Задано алфавіт А = {+, 1} і система підстановок:
"1 + 1 ' ® '11 ', '1' ® `1`.
Звичайна Заключна
підстановка підстановка
Нехай дано вхідне слово р = '11 +11 + 1 ' . Воно переробляється алгоритмом в рядок:
'11 +11 +1' ® '1111 +1' ® '11111 '® `11111`!
Алгоритм реалізує складання одиниць.
Усі відомі досі алгоритми нормалізуеми.
Машина Тьюрінга складається з наступних частин:
1. Інформаційної стрічки, що представляє нескінченну пам'ять машини. Це нескінченна стрічка, розділена на осередки. У кожній клітинці можна помістити лише один символ з можливого їх безлічі S = {S 1, S 2, ...., S m}, яка складає зовнішній алфавіт МТ. У цьому алфавіті один з символів (нехай це буде S 1) відповідає порожньому символу.
2. Голівки, що зчитує - чутливого спеціального елемента, здатного оглядати вміст комірок. Стрічка може переміщатися уздовж головки так, що в кожний момент часу головка оглядає одну клітинку.
3. Керуючого пристрою (УУ), яке в кожний момент часу знаходиться в деякому стані. Число станів звичайно. Позначимо множину станів як {q 1, q 2, ..., q n}. Серед станів одне відповідає заключного, при якому МТ зупиняється. УУ пов'язано зі зчитування голівкою.
Крім того, УУ виробляє три команди на переміщення стрічки: П, Л, Н, де
П - переміститися на сусідню праворуч осередок;
Л - переміститися сусідню зліва осередок;
Н - продовжувати оглядати ту ж комірку.
Сукупність символів {q 1, q 2, ..., q n} і {П, Л, Н} утворюють внутрішній алфавіт МТ.
Робота машини відбувається в дискретному часі. У початковий момент часу в обмежений ділянка стрічки записано слово в алфавіті S, що представляє вихідна умова завдання. В інших осередках передбачається записаним порожній символ. Керуючий пристрій знаходиться в початковому стані q 1. На кожному кроці роботи МТ оглядає на стрічці символ S k і залежно від нього і від стану q i, переходить в стан q j, замінює S k на символ S l і пересуває стрічку (або ні) на одну клітинку.
Кожна елементарна операція має вигляд
q i S k ® q j S l П (Л, Н).
Безліч елементарних операцій впорядковано і утворить абстрактну програму, яка представляє алгоритм.
Зчитує головка і керуючий пристрій утворюють логічний блок, який представляє собою (2,3)-полюснік.
SHAPE \ * MERGEFORMAT
Структура МТ має наступний вигляд:
Q - осередок зберігає символ стану, а Р - осередок - символ зсуву. У них відбувається затримка даних символів до початку наступного такту.
В якості початкової інформації на стрічку можна записати будь-яку кінцеву послідовність символів (вхідний слово) U зовнішнього алфавіту. На початку роботи алгоритму пристрій управління знаходиться в початковому стані, головка оглядає перший зліва непорожній символ вхідного слова U. Якщо після кінцевого числа тактів МТ зупиняється, переходячи в заключне стан, а на стрічці виявляється інформація B, то кажуть, що машина застосовна до послідовності U і переробляє її в послідовність B.
Якщо зупинка і сигнал про зупинку ніколи не надходять, то говорять, що МТ не може бути застосована до послідовності U.
Розглянемо функціонування МТ на прикладі складання двох чисел, які будемо зображати у вигляді набору одиниць.
Зовнішній алфавіт буде складатися з символів: {1, +, Ù}, де Ù - порожній символ.
Внутрішній алфавіт буде складатися з чотирьох символів {q 1, q 2, q 3,!}, Де символ q 1 означає початковий стан, а! - Заключне стан.
Нехай на стрічці записана початкова інформація:
МТ має її переробити в результуючу інформацію:
Абстрактна програма, що реалізує операцію складання, буде мати вигляд:
Початковий стан УУ = q1, стан стрічки має вигляд:
Після першого кроку стан YY = q3, стан стрічки як на рис.
Після п'ятого кроку YY перейде в стан q2. Стан стрічки показано на рис.
Після десятого кроку YY в стані q1 (мал.)
Послідовність команд, що реалізують операцію складання, зручно задати таблицею, яку називають функціональною схемою алгоритму.
Обгрунтування гіпотези.
Мова не йде про доведення гіпотези, так як вона містить не формалізовані математичні поняття.
Впевненість у справедливості гіпотези заснована, головним чином, на досвіді. Усі відомі до цього часу алгоритми можуть бути задані за допомогою тьюрінгових функціональних схем. Крім того, всередині самої теорії алгоритмів основна гіпотеза не застосовується, тобто при доказі теорем цієї теорії посилань на основну гіпотезу не робиться.
ТЕОРІЯ АЛГОРИТМІВ
Єкатеринбург
2006
Наводиться формалізація поняття «алгоритм». Обговорюються два способи формального опису алгоритму-за допомогою нормальних алгоритмів Маркова і через машини Тьюрінга. Наводяться міри складності алгоритмів, визначаються легко і важковирішувані завдання, класи завдань P і NP, алгоритмічно нерозв'язні проблеми.
Зміст
ФОPМАЛІЗАЦІЯ ПОНЯТТЯ Алгоpитм
Визначення
Нормальний алгоритм Маркова
Теза Маркова
Машина Тьюрінга
Основна гіпотеза теорії алгоритмів (теза Черча)
Універсальна машина Тьюрінга
Застережні СКЛАДНОСТІ Алгоpитм
Оцінка алгоритму
Практичні та NP-повні алгоритми
Алгоритмічно нерозв'язні проблеми
«Формалізація поняття алгоритму; Машина Тьюрінга. Теза Черча; Алгоритмічні нерозв'язні проблеми. Заходи складності алгоритмів. Легко і важковирішувані завдання. Класи задач P і NP. NP - повні задачі. Поняття складності обчислень; ефективні алгоритми. »(Зі стандарту спеціальності ВМКСС, дисципліна« Математична логіка і теорія алгоритмів)
ФОPМАЛІЗАЦІЯ ПОНЯТТЯ Алгоpитм
Визначення
Завдання (масова завдання) - деякий загальний питання, на який слід дати відповідь. Зазвичай завдання містить декілька параметрів, або вільних змінних, конкретні значення яких не визначено. Завдання визначається 1) загальним списком параметрів, 2) формулюванням тих властивостей, яким повинен задовольняти відповідь (рішення задачі).Індивідуальна завдання виходить з масовою, якщо всім параметрам масової завдання присвоїти конкретні (допустимі) значення.
Під алгоритмом прийнято розуміти кінцеву послідовність операцій, називаються елементарними, виконання якої призводить до вирішення будь-якої задачі з заданої множини завдань. У це визначення входять такі властивості алгоритму, як дискретність, кінцівку (кінцеве число виконуваних операцій), масовість (вирішується не єдине завдання, а їхній клас), результативність (в результаті отримуємо рішення задачі). Крім того, має виконуватися ще одна необхідна властивість алгоритму - детермінізм, яке визначається як однозначне розуміння кожної операції, або, що те ж саме, незалежність результату виконання кожної елементарної операції від того, хто її виконує.
Під це визначення підходить широке коло алгоритмів. Це може бути алгоритм обчислення математичної функції, алгоритм технологічного процесу, алгоритм проектування ЕОМ або цеху заводу і т.д. Елементарні операції можуть бути досить складними: при обчисленні функції це може бути, наприклад, знаходження коренів рівняння, в проектних або технологічних алгоритмах - прийняття складних проектних або технологічних рішень.
Дане вище визначення алгоритму не є формалізованим і суворим з двох причин. По-перше, в ньому не формалізоване поняття елементарної операції, і, по-друге, не формалізоване подання послідовності операцій. Важливість розробки спільного для всіх алгоритмів формального опису полягає в тому, що воно дає можливість мати спільні інструментарії для порівняння, оцінки, перетворення та інших дій над алгоритмами.
Формалізація операцій алгоритмів пов'язано з наступним. Будь-який алгоритм визначений для деякого об'єкта дії, кожен об'єкт представляється у вигляді опису, причому описом може бути не тільки тексти мовою, але й малюнки, креслення і т.п. Значить, можна припустити, що об'єкт описаний у вигляді слова в заданому алфавіті.
Об'єкт може знаходитися в різних станах, чому відповідають різні слова. Так, об'єктом для математичних алгоритмів є математичний опис завдання у формі матриць коефіцієнтів, графа суміжності і т.п.т., для проектних алгоритмів - проектований об'єкт у вигляді технічного завдання на проектування або перелік вимог та умов до результату.
Операція визначається над описом об'єкта і її результатом є нове (змінене) опис (нове слово). Наприклад, якщо вирішується графова завдання, то результатом операції може бути опис графа з проміжним зважуванням ребер і / або вершин. Результатом проектної операції буде більш повне, уточнене опис об'єкта.
Результатом роботи всього алгоритму в графових завданню може бути виділений шлях або ланцюг, частковий підграф або ваги вершин чи ребер. Результатом роботи алгоритму проектування є опис об'єкта проектування, достатній для його виготовлення в заданій технологічній базі.
Розглянемо кілька способів формального опису алгоритмів.
Нормальний алгоритм Маркова
Алгоритмічна система, створена А. А. Марковим, заснована на відповідності між словами в абстрактному алфавіті A.Алгоритм задають у вигляді системи підстановок, що реалізують відображення слів pi в слова qi.
pi ® qi = 1, ..., k.
Порядок підстановок зафіксований. Об'єктом i-й елементарної операції алгоритму є слово в алфавіті A, операція полягає в знаходженні в цьому слові першому зліва входження слова pi і заміну його на qi. Результатом операції буде змінене слова, якщо входження знайдено, або вхідне слово, якщо не найдено.Факт заміни фіксується і використовується в організації проходження операцій.
Початкове завдання представляється деяким словом в алфавіті A. Це слово є вхідним для першої операції, якщо заміна відбулася, то знову виконується перша операція, якщо немає, то виконується наступна операція. Після кожної операції виконується наступна операція, якщо заміна відбулася, інакше переходять до виконання першої операції.
Алгоритм зручно представити у вигляді орієнтованого графа, вершинами якого є елементарні оператори і розпізнавачі.
Розпізнавач перевіряє умову - чи має місце входження рi у вхідний слово p. Якщо ТАК, то за ним слід оператор, який замінює перший зліва входження слова рi на слово qi. Якщо НІ, то управління передається на вхід наступного розпізнавача.
Дуги, що виходять з операторних вершин, приєднуються або до першої вершини - розпізнавача, або до вихідний вершині. У першому випадку підстановка називається звичайної, у другому - заключної.
Крім того, є вхідна і вихідна вершини. Вхідна вершина пов'язані дугою з першим розпізнавачем.
На вхід графа подається деякий вхідне слово p.
Приклад. Граф для трьох підстановок (к = 3) (рис.1) має три розпізнавача (РВ1, РВ2, РВ3) і три операторні вершини (ОП1, ОП2, ОП3).
Якщо підстановки задані як ba ® ab, bc ® ba, bb ® ac, а вхідний слово
р = bcbaab, то робота алгоритму буде мати наступний вигляд.
SHAPE \ * MERGEFORMAT
р = bcb aa b ® bc a b a b ® bc aa bb ® b aaa bb ® a b aa bb ® aa b a bb ® aaa bbb ® aaaa cb. |
+ |
+ |
РВ 1 |
РВ 2 |
РВ 3 |
ВП 3 |
+ |
ВП 2 |
q |
- |
- |
р |
ВП 1 |
Пpимеp. Задано алфавіт А = {+, 1} і система підстановок:
"1 +
Звичайна Заключна
підстановка підстановка
Нехай дано вхідне слово р = '11 +11 +
'11 +11 +1' ® '1111 +1' ® '11111 '® `11111`!
Алгоритм реалізує складання одиниць.
Теза Маркова
Для будь-якого алгоритму в довільному кінцевому алфавіті А можна побудувати еквівалентний йому нормальний алгоритм.Усі відомі досі алгоритми нормалізуеми.
Машина Тьюрінга
Одне з уточнень понять алгоритму було дано Е. Постом і А. Тьюрінгом незалежно один від одного в 1936-1937гг. Основна думка їх полягала в тому, що алгоритмічні процеси - це процеси, які може здійснити відповідним чином влаштована "машина". Ними були описані гіпотетичні (умовні) пристрої, які отримали назву «Машина Поста» і «Машина Тьюрінга» (МТ). Так як в них багато спільного, то розглянемо тільки машину Тьюрінга.Машина Тьюрінга складається з наступних частин:
1. Інформаційної стрічки, що представляє нескінченну пам'ять машини. Це нескінченна стрічка, розділена на осередки. У кожній клітинці можна помістити лише один символ з можливого їх безлічі S = {S 1, S 2, ...., S m}, яка складає зовнішній алфавіт МТ. У цьому алфавіті один з символів (нехай це буде S 1) відповідає порожньому символу.
2. Голівки, що зчитує - чутливого спеціального елемента, здатного оглядати вміст комірок. Стрічка може переміщатися уздовж головки так, що в кожний момент часу головка оглядає одну клітинку.
3. Керуючого пристрою (УУ), яке в кожний момент часу знаходиться в деякому стані. Число станів звичайно. Позначимо множину станів як {q 1, q 2, ..., q n}. Серед станів одне відповідає заключного, при якому МТ зупиняється. УУ пов'язано зі зчитування голівкою.
Крім того, УУ виробляє три команди на переміщення стрічки: П, Л, Н, де
П - переміститися на сусідню праворуч осередок;
Л - переміститися сусідню зліва осередок;
Н - продовжувати оглядати ту ж комірку.
Сукупність символів {q 1, q 2, ..., q n} і {П, Л, Н} утворюють внутрішній алфавіт МТ.
Робота машини відбувається в дискретному часі. У початковий момент часу в обмежений ділянка стрічки записано слово в алфавіті S, що представляє вихідна умова завдання. В інших осередках передбачається записаним порожній символ. Керуючий пристрій знаходиться в початковому стані q 1. На кожному кроці роботи МТ оглядає на стрічці символ S k і залежно від нього і від стану q i, переходить в стан q j, замінює S k на символ S l і пересуває стрічку (або ні) на одну клітинку.
Кожна елементарна операція має вигляд
q i S k ® q j S l П (Л, Н).
Безліч елементарних операцій впорядковано і утворить абстрактну програму, яка представляє алгоритм.
Зчитує головка і керуючий пристрій утворюють логічний блок, який представляє собою (2,3)-полюснік.
SHAPE \ * MERGEFORMAT
S k |
S 1 |
ЛБ |
q i |
q j |
{П, Л, Н} |
Рис. 2 |
Структура МТ має наступний вигляд:
| S 1 | S 2 | ... | S k | ... | S m |
ЛБ |
Q |
P |
S l |
S k |
q i |
q j |
П (Л, Н) |
Q - осередок зберігає символ стану, а Р - осередок - символ зсуву. У них відбувається затримка даних символів до початку наступного такту.
В якості початкової інформації на стрічку можна записати будь-яку кінцеву послідовність символів (вхідний слово) U зовнішнього алфавіту. На початку роботи алгоритму пристрій управління знаходиться в початковому стані, головка оглядає перший зліва непорожній символ вхідного слова U. Якщо після кінцевого числа тактів МТ зупиняється, переходячи в заключне стан, а на стрічці виявляється інформація B, то кажуть, що машина застосовна до послідовності U і переробляє її в послідовність B.
Якщо зупинка і сигнал про зупинку ніколи не надходять, то говорять, що МТ не може бути застосована до послідовності U.
Розглянемо функціонування МТ на прикладі складання двох чисел, які будемо зображати у вигляді набору одиниць.
Зовнішній алфавіт буде складатися з символів: {1, +, Ù}, де Ù - порожній символ.
Внутрішній алфавіт буде складатися з чотирьох символів {q 1, q 2, q 3,!}, Де символ q 1 означає початковий стан, а! - Заключне стан.
Нехай на стрічці записана початкова інформація:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||||
| 1 | 1 | + | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||||
| 1 | 1 | 1 |
| 1q 1 1q 3 → 1q 3 П + Q 3 → + q 3 П | Ùq 3 → 1q 2 H + q 2 → + q 2 Л 1q 2 → 1q 2 Л Ùq 2 → Ùq 1 П + Q 1 → Ù! Н |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||
| 1 | 1 | + | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||
| 1 | + | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||
| 1 | + | 1 | 1 |
Після десятого кроку YY в стані q1 (мал.)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||
| + | 1 | 1 |
| q 1 | q 2 | q 3 | |
| 1 | Ùq 3 П | 1q 2 Л | 1q 3 П |
| Ù | Ùq 1 П | Ùq 1 П | 1q 2 H |
| + | Ù! Н | + Q 2 Л | + Q 3 П |
Основна гіпотеза теорії алгоритмів (теза Черча)
Всякий алгоритм може бути заданий за допомогою тьюрінговой функціональної схеми і реалізований у відповідній машині Тьюринга.Обгрунтування гіпотези.
Мова не йде про доведення гіпотези, так як вона містить не формалізовані математичні поняття.
Впевненість у справедливості гіпотези заснована, головним чином, на досвіді. Усі відомі до цього часу алгоритми можуть бути задані за допомогою тьюрінгових функціональних схем. Крім того, всередині самої теорії алгоритмів основна гіпотеза не застосовується, тобто при доказі теорем цієї теорії посилань на основну гіпотезу не робиться.
Машина Тьюрінга вкрай примітивна. Але примітивність її не в тому, що вона використовує стрічку і механічний рух голівки, а те, що її набір операцій з пам'яттю дуже простий (запис і читання символів), а доступ до пам'яті в ній відбувається не за адресою, а шляхом послідовного переміщення уздовж стрічки. Тому виконання на ній навіть таких простих функцій як складання і множення вимагає багато кроків. Машина Тьюрінга була придумана не для того, щоб виробляти на ній реальні обчислення, а щоб показати, що як завгодно складний алгоритм можна побудувати з дуже простих операцій, причому самі операції і перехід від однієї операції до іншої виконуються автоматично.
Вимоги до кодування:
1. різним буквах повинні зіставлятися різні кодові групи, і одна і та ж буква скрізь замінюється однієї і тієї ж кодової групою;
2. Рядок тексту повинна однозначним чином розбиватися на кодові групи.
Складність універсальної машини Тьюринга визначається твором числа символів її зовнішнього алфавіту на число станів усторйством управління.
Теорема Триттером визначає, що мінімальна універсальна машина Тьюрінга має 4 символу в зовнішньому алфавіті та її УУ має 6 станів.
Під просторової ефективністю розуміють обсяг пам'яті, необхідної для виконання програми.
Тимчасова ефективність програми визначається часом, необхідним для її виконання. При цьому необхідно враховувати наступні моменти.
По-перше, час роботи програми може обмежуватися її призначенням. Якщо ця програма реального часу, наприклад, бронювання авіаквитків, то час обробки завдання не повинно перевищувати декількох хвилин. Якщо ця програма автоматичного управління будь-яким пристроєм (наприклад, управлінням літака), то вона повинна «встигати» відпрацьовувати надходить, і своєчасно видавати керуючі впливу.
По-друге, буває важливо знати, як змінюється час роботи програми при збільшенні розмірності задачі. Це дозволить оцінити обсяг вихідних даних, які можуть бути оброблені на комп'ютері за прийнятний час.
Реальний час роботи програми на комп'ютері залежить не тільки від вибраного алгоритму. Значною мірою воно визначається типом ЕОМ, структурою подання даних, програмною реалізацією.
Найпростішим способом оцінити алгоритм - зіставити йому число елементарних операцій в описі. При реалізації це може бути кількість команд у програмі або обсяг пам'яті, яку займає програма. У цьому випадку оцінка d алгоритму A є деяке число k: d (A) = k.
Більш цікавою може бути оцінка пари: алгоритму A і конкретного завдання a, яка їм вирішується. Наприклад, оцінкою може бути обсяг пам'яті під програму, вихідні та проміжні дані, необхідні для вирішення даної задачі a, або час для вирішення цього завдання з допомогою алгоритму A. У будь-якому випадку це буде число d (A (a)) = k (a).
Властивість масовості алгоритму припускає, що алгоритм буде використовуватися для вирішення класу A подібних завдань, з різними вихідними даними. Тому більш складною оцінкою буде оцінка як функція властивості завдання. Cопоставім кожній задачі з класу задач, що розв'язуються алгоритмом, деякий вектор числових параметрів задачі N = (n1, n2, ..., nt). У цьому випадку оцінка d (A (A)) = k (N), і це вже буде функція від параметрів задачі.
Приклад. Необхідно цінувати алгоритм Прима - алгоритм виділення мінімального кістяка. У першому випадку ми розглядаємо число операторів в описі програми, що реалізує алгоритм - число порівнянь, умовних переходів і т.д. У другому випадку аналізується робота алгоритму (програми) виділення кістяка деякого заданого графа і визначається необхідний обсяг пам'яті. В останньому випадку графу припишемо параметри - число вершин у графі і число його ребер, і можна порівняти вирішення завдання функцію від цих параметрів.
У багатьох завданнях можливо звести вектор завдання до одного параметру. Так, для графа можливо характеризувати його числом вершин, враховуючи, що число ребер у ньому корельовано з кількістю вершин. Для завдань, пов'язаних з булевими функціями, параметром може бути число аргументів функції.
Будемо розглядати тільки такі завдання. У цьому випадку оцінкою алгоритму буде функція від одного параметра. Тимчасова складність алгоритму відображає потрібні для його роботи витрати часу Ця функція вставить кожної вхідний довжині n у відповідність максимальна (за всіма індивідуальним завданням довжини n) час, що витрачається алгоритмом на вирішення індивідуальних завдань цієї довжини.
Приклад. Нехай функція оцінки має вигляд як на мал.1. Необхідно вирішувати задачі з параметром n, що лежить в межах від 5 до 15. У цьому випадку необхідно вибрати для реалізації алгоритм A1. Якщо параметр змінюється від 20 до 30, краще використовувати алгоритм A2. Якщо параметр змінюється в межах від 10 до 35, то можливо або вибрати будь-який з даних алгоритмів, або побудувати новий алгоритм, який, наприклад, перевіряє кожен раз значення параметра і вибирає відповідний алгоритм.
SHAPE \ * MERGEFORMAT
Припустимо, що можна розглянути всі можливі алгоритми A i рішення задачі a і для кожного параметра n оцінити завдання двома оцінками d 1 (a) = min (d (A i (a))) і d 2 (a) = max (d (A i (a))), де min і max береться за всіма алгоритмами. У цьому випадку отримаємо два кордони рішення даного завдання - нижню і верхню (рис.2). Цей малюнок визначає той розкид складності рішень задачі і допомагає відповісти на питання: чи потрібно витрачати сили на пошук хорошого алгоритму або достатньо взяти перший-ліпший.
Дуже часто можливо оцінити, виходячи з аналізу самого завдання вид функції оцінки з точністю до деякого множника - константи. У цьому випадку ця оцінка буде не тільки оцінка алгоритму, але й оцінка завдання.
Функція f (n) є O (g (n)), якщо існує константа с, така, що f (n) <O (g (n)) для всіх значень n> 0.
SHAPE \ * MERGEFORMAT
По виду цієї функції алгоритми поділяються на такі групи:
з лінійною оцінкою складності, якщо функція d = C · n;
з квадратичною складністю, якщо d = C · n 2;
з поліноміальної складністю, якщо d = C0 + C1 · n + ... + Ck · n k;
з факторіальною складністю, якщо d = C · n!;
з експоненційної складністю, якщо d = C · a n;
з гіперекспоненціальной складністю, якщо d = C · a t, де t = a n.
Тут C, a і k = деякі константи, при цьому число C може бути дуже великим.
У табл. 1 наведена залежність часу роботи алгоритмів різної складності для задач різної розмірності, за умови, що час виконання однієї операції у всіх алгоритмах однакові. З таблиці видно, що для полінома, ступеня 5 завдання розмірності 6о вирішити можна за прийнятний час, в той же час для експоненційних алгоритмів вже для розмірності, більше 30 завдання не вирішується.
Зростання швидкості обчислень не зменшить значення ефективних алгоритмів, що ілюструє табл. 2 ..
Якщо доведено, що задача є NP - повної, то це означає, що її рішення для параметрів, що мають практичне значення, пов'язане з величезними витратами часу або пам'яті, які не дозволять отримати рішення. У цьому випадку необхідно переформулювати завдання. Наприклад, завдання пошуку мінімальної формули для булевої функції є завданням NP - повної, тому при проектуванні схем, де це завдання зустрічається, вирішують завдання, яку формулюють як пошук функцій, близькою до мінімальної, для чого користуються евристичними, заснованими на припущеннях здорового глузду. Так, якщо вирішується завдання розміщення об'єктів в деякому блоці, то розумно починати розміщення з самого великого об'єкту. У цих алгоритмах не завжди гарантується отримання мінімального рішення, але якщо для більшості завдань оцінка відрізняється не більше, ніж на 10-15% від мінімального, то це часто влаштовує користувачів.
Пpимеp. Оцінимо складність алгоритму Прима пошуку мінімального кістяка в графі. Нехай граф описаний матрицею суміжності.
Алгоритм. Виберемо будь-яку вершину і включимо її в остов. Розглянемо пов'язані з нею ребра. Знайдемо вершину, пов'язану з включеною в остов ребром мінімальної ваги і включимо її в остов. Для вершин, включених до остов, розглянемо пов'язані з ними ребра до вершин, не включеним в остов. Виберемо вершину, пов'язану ребром мінімальної ваги і включимо її в остов. Цю процедуру продовжимо до тих пір, поки всі вершини не будуть включені в остов.
Для матричного представлення алгоритм прийме, такий вигляд. Виберемо будь-яку вершину і у відповідній їй рядку матриці знайдемо клітинку з мінімальною вагою. Ця процедура зажадає n порівнянь, де n-порядок матриці (число вершин у графі). Ім'я стовпця цього осередку визначає вершину, яку потрібно включити до остов. Об'єднаємо ці вершини в одну, відповідну вершин, включеним в остов. Для цього розглянемо рядки і стовпці цих вершин. Якщо в i-й осередку однієї з рядків не нульове число, воно запишеться в результуючу рядок, якщо ненульове значення в обох рядках, в результуючу запишемо мінімальне. Таким чином, для «обробки» однієї вершини потрібно число операцій, кратних 2 n. Число вершин у розглянутому графі скоротиться на одиницю. Повторимо те ж саме для результуючої рядка, поки число вершин не стане рівною одиниці. Значить, загальне число операцій оцінюється числом, пропорційним n 2, тобто оцінка має квадратичну складність d = C · n 2.
Існує велика кількість завдань, які є алгоритмічно нерозв'язними. Тобто мова йде про відсутність єдиного алгоритму, вирішального це завдання. При цьому зовсім не виключається можливість вирішення завдання в окремих випадках, але різними способами для кожного випадку.
Розглянемо кілька прикладів алгоритмічно нерозв'язних завдань.
1 Завдання еквівалентності алгоритмів
По двох довільно заданими алгоритмами визначити чи будуть вони видавати однакові вихідні результати на будь-яких вихідних даних.
2 Завдання зупинки машини Тьюрінга
Не існує алгоритму, що дозволяє за описом довільного алгоритму і його вихідних даних визначити, чи зупиняється алгоритм на цих даних або працює нескінченно.
3 Задача еквівалентності двох слів в асоціативному обчисленні
Асоціативним обчисленням називають сукупність усіх слів у деякому алфавіті разом з якою-небудь кінцевої системою допустимих підстановок.
Підстановка P ® Q називається орієнтованою. Вона полягає в заміні фрагмента P у слові R фрагментом Q.
Підстановка P - Q називається неориентированной. Вона полягає як в заміні фрагмента P у слові R фрагментом Q, так і в заміні в слові R фрагмента Q фрагментом P.
Приклад. R = 'aabcb' P = 'ab' Q = 'bcb'
При P ® Q отримаємо: R '=' abcbcb '.
При P - Q отримаємо як R '=' abcbcb ', так і R''=' aaab '.
Два слова R1 і R2 називаються еквівалентними для заданої системи орієнтованих підстановок, якщо від слова R1 можна, застосовуючи кінцеве число разів підстановки, перейти до слова R2.
Якщо ж підстановки неорієнтованих, то можливість переходу потрібно як від R1 до R2, так і від R2 до R1.
Завдання еквівалентності слів в асоціативному обчисленні полягає в наступному: для будь-яких двох слів у даному обчисленні потрібно дізнатися, еквівалентні вони чи ні.
Завдання слів не є надуманою, тому що до неї може бути зведена будь-яка відома завдання.
Наприклад, розглянемо завдання пошуку шляху в лабіринті. Зобразимо лабіринт у вигляді графа, в якому вершин відповідають майданчики, а ребрам - з'єднують їх коридори. Кожній майданчику або вершині графа зіставимо деяке слово. Кожному коридором чи ребру xixj зіставимо неорієнтовану підстановку, що переводять слово, відповідне xi, в слово, відповідне xj.
Наприклад, якщо вершині x1 відповідає слово 'xypt', а суміжній вершині x2 - слово 'xyqt', то неорієнтована підстановка буде мати вигляд:
'P' - 'q'.
Завдання слів вирішена для деяких окремих випадків. Наприклад, нехай дано алфавіт {x, y, z, p, q} і система неорієнтованих підстановок:
xz - zx, xp - px, yz - zy, yp - py, xyxz - xyxzq, qzx - xq, qpy - yq.
Питається, еквівалентні чи в даному асоціативному обчисленні слова: xyxxzp і xzypxp?
Відповідь: ні, не еквівалентні, тому що в першому слові непарне число букв x, а в другому - парне; система ж підстановок зберігає парність або непарність букв x у словах.
У загальному ж випадку завдання слів алгоритмічно нерозв'язна.
4 Завдання розпізнавання виводимості
Із завданням еквівалентності двох слів в асоціативному обчисленні тісно пов'язана задача розпізнавання виводимості, яка є однією з найважливіших задач математичної логіки.
Завдання розпізнавання виводимості полягає в наступному:
для будь-яких двох слів (формул) S і T в логічному обчисленні визначити виведена чи формула T з формули S.
Це завдання також алгоритмічно нерозв'язна.
Теорія алгоритмів Методичний посібник з дисципліни "Математична логіка і теорія алгоритмів» / В.П. Бітюцький, Н.В. Папуловская. Єкатеринбург: ГОУ ВПО УГТУ-УПІ, 2006, с.
Універсальна машина Тьюрінга
Універсальна машина дозволяє вирішити будь-яке завдання, якщо поряд з вихідними даними в неї записати алгоритм. Як і будь-яка машина Тьюрінга, універсальна машина повинна мати кінцеві зовнішній і внутрішній алфавіти, в той же час вона повинна мати можливість приймати у якості зовнішнього алфавіту будь-які алфавіти. Це досягається за рахунок кодування зовнішнього алфавіту в алфавіті універсальної машини Тьюрінга.Вимоги до кодування:
1. різним буквах повинні зіставлятися різні кодові групи, і одна і та ж буква скрізь замінюється однієї і тієї ж кодової групою;
2. Рядок тексту повинна однозначним чином розбиватися на кодові групи.
Складність універсальної машини Тьюринга визначається твором числа символів її зовнішнього алфавіту на число станів усторйством управління.
Теорема Триттером визначає, що мінімальна універсальна машина Тьюрінга має 4 символу в зовнішньому алфавіті та її УУ має 6 станів.
Застережні СКЛАДНОСТІ Алгоpитм
Оцінка алгоритму
Оцінка алгоритму буває потрібною в тому випадку, коли при вирішенні деякої задачі є кілька різних алгоритмів, і стоїть завдання вибору одного з них для реалізації. Навіть якщо завдання вирішується єдиним алгоритмом, буває потрібно оцінити складність його реалізації і його роботи (обсяг пам'яті, час рішення).Під просторової ефективністю розуміють обсяг пам'яті, необхідної для виконання програми.
Тимчасова ефективність програми визначається часом, необхідним для її виконання. При цьому необхідно враховувати наступні моменти.
По-перше, час роботи програми може обмежуватися її призначенням. Якщо ця програма реального часу, наприклад, бронювання авіаквитків, то час обробки завдання не повинно перевищувати декількох хвилин. Якщо ця програма автоматичного управління будь-яким пристроєм (наприклад, управлінням літака), то вона повинна «встигати» відпрацьовувати надходить, і своєчасно видавати керуючі впливу.
По-друге, буває важливо знати, як змінюється час роботи програми при збільшенні розмірності задачі. Це дозволить оцінити обсяг вихідних даних, які можуть бути оброблені на комп'ютері за прийнятний час.
Реальний час роботи програми на комп'ютері залежить не тільки від вибраного алгоритму. Значною мірою воно визначається типом ЕОМ, структурою подання даних, програмною реалізацією.
Найпростішим способом оцінити алгоритм - зіставити йому число елементарних операцій в описі. При реалізації це може бути кількість команд у програмі або обсяг пам'яті, яку займає програма. У цьому випадку оцінка d алгоритму A є деяке число k: d (A) = k.
Більш цікавою може бути оцінка пари: алгоритму A і конкретного завдання a, яка їм вирішується. Наприклад, оцінкою може бути обсяг пам'яті під програму, вихідні та проміжні дані, необхідні для вирішення даної задачі a, або час для вирішення цього завдання з допомогою алгоритму A. У будь-якому випадку це буде число d (A (a)) = k (a).
Властивість масовості алгоритму припускає, що алгоритм буде використовуватися для вирішення класу A подібних завдань, з різними вихідними даними. Тому більш складною оцінкою буде оцінка як функція властивості завдання. Cопоставім кожній задачі з класу задач, що розв'язуються алгоритмом, деякий вектор числових параметрів задачі N = (n1, n2, ..., nt). У цьому випадку оцінка d (A (A)) = k (N), і це вже буде функція від параметрів задачі.
Приклад. Необхідно цінувати алгоритм Прима - алгоритм виділення мінімального кістяка. У першому випадку ми розглядаємо число операторів в описі програми, що реалізує алгоритм - число порівнянь, умовних переходів і т.д. У другому випадку аналізується робота алгоритму (програми) виділення кістяка деякого заданого графа і визначається необхідний обсяг пам'яті. В останньому випадку графу припишемо параметри - число вершин у графі і число його ребер, і можна порівняти вирішення завдання функцію від цих параметрів.
У багатьох завданнях можливо звести вектор завдання до одного параметру. Так, для графа можливо характеризувати його числом вершин, враховуючи, що число ребер у ньому корельовано з кількістю вершин. Для завдань, пов'язаних з булевими функціями, параметром може бути число аргументів функції.
Будемо розглядати тільки такі завдання. У цьому випадку оцінкою алгоритму буде функція від одного параметра. Тимчасова складність алгоритму відображає потрібні для його роботи витрати часу Ця функція вставить кожної вхідний довжині n у відповідність максимальна (за всіма індивідуальним завданням довжини n) час, що витрачається алгоритмом на вирішення індивідуальних завдань цієї довжини.
Приклад. Нехай функція оцінки має вигляд як на мал.1. Необхідно вирішувати задачі з параметром n, що лежить в межах від 5 до 15. У цьому випадку необхідно вибрати для реалізації алгоритм A1. Якщо параметр змінюється від 20 до 30, краще використовувати алгоритм A2. Якщо параметр змінюється в межах від 10 до 35, то можливо або вибрати будь-який з даних алгоритмів, або побудувати новий алгоритм, який, наприклад, перевіряє кожен раз значення параметра і вибирає відповідний алгоритм.
SHAPE \ * MERGEFORMAT
A 1 |
A 2 |
5 10 15 20 25 30 35 |
Жовтень 1912 10 серпня 10 Квітня 10 лютого 10 лютого 10 лютого 10 лютого |
Рис. 1 |
n |
Припустимо, що можна розглянути всі можливі алгоритми A i рішення задачі a і для кожного параметра n оцінити завдання двома оцінками d 1 (a) = min (d (A i (a))) і d 2 (a) = max (d (A i (a))), де min і max береться за всіма алгоритмами. У цьому випадку отримаємо два кордони рішення даного завдання - нижню і верхню (рис.2). Цей малюнок визначає той розкид складності рішень задачі і допомагає відповісти на питання: чи потрібно витрачати сили на пошук хорошого алгоритму або достатньо взяти перший-ліпший.
Дуже часто можливо оцінити, виходячи з аналізу самого завдання вид функції оцінки з точністю до деякого множника - константи. У цьому випадку ця оцінка буде не тільки оцінка алгоритму, але й оцінка завдання.
Функція f (n) є O (g (n)), якщо існує константа с, така, що f (n) <O (g (n)) для всіх значень n> 0.
SHAPE \ * MERGEFORMAT
Рис. 2 |
n |
d2 (a) |
5 10 15 20 25 30 35 |
Жовтень 1912 10 серпня 10 Квітня 10 лютого 10 лютого 10 лютого 10 лютого |
d1 (a) |
По виду цієї функції алгоритми поділяються на такі групи:
з лінійною оцінкою складності, якщо функція d = C · n;
з квадратичною складністю, якщо d = C · n 2;
з поліноміальної складністю, якщо d = C0 + C1 · n + ... + Ck · n k;
з факторіальною складністю, якщо d = C · n!;
з експоненційної складністю, якщо d = C · a n;
з гіперекспоненціальной складністю, якщо d = C · a t, де t = a n.
Тут C, a і k = деякі константи, при цьому число C може бути дуже великим.
Практичні та NP-повні алгоритми
По виду функцій алгоритми (і відповідні завдання) поділяються на два класи. До першого належать алгоритми груп 1-3, коли для поліноміальних алгоритмів k ≤ 7. Ці алгоритми називаються практичними. Всі інші алгоритми складають другий клас і називаються NP - повними.У табл. 1 наведена залежність часу роботи алгоритмів різної складності для задач різної розмірності, за умови, що час виконання однієї операції у всіх алгоритмах однакові. З таблиці видно, що для полінома, ступеня 5 завдання розмірності 6о вирішити можна за прийнятний час, в той же час для експоненційних алгоритмів вже для розмірності, більше 30 завдання не вирішується.
| Таблиця 1. | ||||||
| Складність завдання | ||||||
| Складність алгоритму | 10 | 20 | 30 | 40 | 50 | 60 |
| N | 0.00001с | 0,00002 з | 0,00003 з | 0,0004 з | 0,0005 з | 0,00006 з |
| N ^ 2 | 0,0001 с | 0,0004 з | 0,0009 з | 0,0016 з | 0,025 з | 0,0036 з |
| N ^ 3 | 0,001 з | 0,008 з | 0,027 з | 0,064 з | 0,125 з | 0,216 з |
| N ^ 5 | 0,1 c | 3,2 c | 24,3 c | 1,7 хв | 5,2 хв | 13,0 хв |
| 2 ^ n | 0,001 c | 1 c | 17,9 хв | 12,7 днів | 35,7 років | 366 століть |
| 3 ^ n | 0,059 c | 58 хв | 6,5 років | 3855 сторіч | 2 * 10 ^ 8стол | 1,3 * 10 ^ 13 стола |
| Таблиця 2 | |||
| Складність алгоритму | Максимальний розмір задачі, яка вирішується за одиницю часу | ||
| На сучасних ЕОМ | Якщо виробниц * 10 | Якщо виробниц * 1000 | |
| N | k | 10k | 1000k |
| Nlog n | k | Майже 10k при великих до | Майже 10k при великих до |
| N ^ 2 | k | 3,16 k | 31,6 k |
| N ^ 3 | k | 2,15 k | 10k |
| 2 ^ n | k | K +3,3 | K +9,97 |
Пpимеp. Оцінимо складність алгоритму Прима пошуку мінімального кістяка в графі. Нехай граф описаний матрицею суміжності.
Алгоритм. Виберемо будь-яку вершину і включимо її в остов. Розглянемо пов'язані з нею ребра. Знайдемо вершину, пов'язану з включеною в остов ребром мінімальної ваги і включимо її в остов. Для вершин, включених до остов, розглянемо пов'язані з ними ребра до вершин, не включеним в остов. Виберемо вершину, пов'язану ребром мінімальної ваги і включимо її в остов. Цю процедуру продовжимо до тих пір, поки всі вершини не будуть включені в остов.
Для матричного представлення алгоритм прийме, такий вигляд. Виберемо будь-яку вершину і у відповідній їй рядку матриці знайдемо клітинку з мінімальною вагою. Ця процедура зажадає n порівнянь, де n-порядок матриці (число вершин у графі). Ім'я стовпця цього осередку визначає вершину, яку потрібно включити до остов. Об'єднаємо ці вершини в одну, відповідну вершин, включеним в остов. Для цього розглянемо рядки і стовпці цих вершин. Якщо в i-й осередку однієї з рядків не нульове число, воно запишеться в результуючу рядок, якщо ненульове значення в обох рядках, в результуючу запишемо мінімальне. Таким чином, для «обробки» однієї вершини потрібно число операцій, кратних 2 n. Число вершин у розглянутому графі скоротиться на одиницю. Повторимо те ж саме для результуючої рядка, поки число вершин не стане рівною одиниці. Значить, загальне число операцій оцінюється числом, пропорційним n 2, тобто оцінка має квадратичну складність d = C · n 2.
Алгоритмічно нерозв'язні проблеми
Завдання, для яких доведено, що вирішального їх алгоритму не існує, називаються алгоритмічно нерозв'язними.Існує велика кількість завдань, які є алгоритмічно нерозв'язними. Тобто мова йде про відсутність єдиного алгоритму, вирішального це завдання. При цьому зовсім не виключається можливість вирішення завдання в окремих випадках, але різними способами для кожного випадку.
Розглянемо кілька прикладів алгоритмічно нерозв'язних завдань.
1 Завдання еквівалентності алгоритмів
По двох довільно заданими алгоритмами визначити чи будуть вони видавати однакові вихідні результати на будь-яких вихідних даних.
2 Завдання зупинки машини Тьюрінга
Не існує алгоритму, що дозволяє за описом довільного алгоритму і його вихідних даних визначити, чи зупиняється алгоритм на цих даних або працює нескінченно.
3 Задача еквівалентності двох слів в асоціативному обчисленні
Асоціативним обчисленням називають сукупність усіх слів у деякому алфавіті разом з якою-небудь кінцевої системою допустимих підстановок.
Підстановка P ® Q називається орієнтованою. Вона полягає в заміні фрагмента P у слові R фрагментом Q.
Підстановка P - Q називається неориентированной. Вона полягає як в заміні фрагмента P у слові R фрагментом Q, так і в заміні в слові R фрагмента Q фрагментом P.
Приклад. R = 'aabcb' P = 'ab' Q = 'bcb'
При P ® Q отримаємо: R '=' abcbcb '.
При P - Q отримаємо як R '=' abcbcb ', так і R''=' aaab '.
Два слова R1 і R2 називаються еквівалентними для заданої системи орієнтованих підстановок, якщо від слова R1 можна, застосовуючи кінцеве число разів підстановки, перейти до слова R2.
Якщо ж підстановки неорієнтованих, то можливість переходу потрібно як від R1 до R2, так і від R2 до R1.
Завдання еквівалентності слів в асоціативному обчисленні полягає в наступному: для будь-яких двох слів у даному обчисленні потрібно дізнатися, еквівалентні вони чи ні.
Завдання слів не є надуманою, тому що до неї може бути зведена будь-яка відома завдання.
Наприклад, розглянемо завдання пошуку шляху в лабіринті. Зобразимо лабіринт у вигляді графа, в якому вершин відповідають майданчики, а ребрам - з'єднують їх коридори. Кожній майданчику або вершині графа зіставимо деяке слово. Кожному коридором чи ребру xixj зіставимо неорієнтовану підстановку, що переводять слово, відповідне xi, в слово, відповідне xj.
Наприклад, якщо вершині x1 відповідає слово 'xypt', а суміжній вершині x2 - слово 'xyqt', то неорієнтована підстановка буде мати вигляд:
'P' - 'q'.
Завдання слів вирішена для деяких окремих випадків. Наприклад, нехай дано алфавіт {x, y, z, p, q} і система неорієнтованих підстановок:
xz - zx, xp - px, yz - zy, yp - py, xyxz - xyxzq, qzx - xq, qpy - yq.
Питається, еквівалентні чи в даному асоціативному обчисленні слова: xyxxzp і xzypxp?
Відповідь: ні, не еквівалентні, тому що в першому слові непарне число букв x, а в другому - парне; система ж підстановок зберігає парність або непарність букв x у словах.
У загальному ж випадку завдання слів алгоритмічно нерозв'язна.
4 Завдання розпізнавання виводимості
Із завданням еквівалентності двох слів в асоціативному обчисленні тісно пов'язана задача розпізнавання виводимості, яка є однією з найважливіших задач математичної логіки.
Завдання розпізнавання виводимості полягає в наступному:
для будь-яких двох слів (формул) S і T в логічному обчисленні визначити виведена чи формула T з формули S.
Це завдання також алгоритмічно нерозв'язна.
Теорія алгоритмів Методичний посібник з дисципліни "Математична логіка і теорія алгоритмів» / В.П. Бітюцький, Н.В. Папуловская. Єкатеринбург: ГОУ ВПО УГТУ-УПІ, 2006, с.