машина Тюрінга. Звіт до лабораторної роботи з АМО. Робота № 524320

машина Тюрінга

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКТА

Факультет:

Комп'ютерна інженерія

Кафедра:

Кафедра ЕПМС

Інформація про роботу

Рік:

2013

Тип роботи:

Звіт до лабораторної роботи

Предмет:

АМО

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 1 на тему: " Програмування машин Тьюрінга " з дисципліни: " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ " № варіанта = [21+ 77] % 30 + 1=9 1. МЕТА РОБОТИ Вивчити принципи роботи машин Тюринга, набути практичних навичок програмування машин Тьюрінга. ПОСТАНОВКА ЗАДАЧІ 2.1. Загальна частина Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Використання додаткових символів, що не входять в алфавит А, має бути обгрунтоване. Скласти програму для мишини Тьюрінга. В початковому стані каретка МТ має розпізнавати перший зліва символ вхідного слова Р. В кінцевому стані каретка МТ має зупинитись під одним із символів вихідного слова (під яким саме - не має значення). Відлагодження і тестування програми провести в середовищі емулятора мишини Тьюрінга. Записати в середовищі емулятора в поле Условие задачи варіант і умову індивідуального завдання. В поле Комментарий записати коротке пояснення дій, які реалізуються у відповідних станах каретки. Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МТ. 2.2. Індивідуальне завдання 9. A={a,b,c}. Замінити в непорожньому слові P кожне входження символів bc на символ a. СЛОВЕСНИЙ ОПИС АЛГОРИТМУ Для розв'язання цієї задачі потрібно виконати наступні дії: Вихідне слово будемо будувати справа від вхідного. Щоб розмежувати ці слова, відокремимо їх деяким допоміжним символом, відмінним від всіх символів алфавіту A, наприклад знаком = (крок 1). Після цього повертаємось до початку вхідного слова (крок 2). Далі в циклі копіюємо і переносимо всі символи вхідного слова, крім символа c, вправо за знак =, тобто формуємо вихідне слово. Для цього аналізуємо кожний символ вхідного слова і заміняємо його на двійника. Якщо це символ c, то повертаємося до попереднього символа (крок 4). Якщо попередній символ b, то біжимо вправо до першої вільної комірки (крок 5). Повертаємося на 1 символ вліво (останній символ вихідного слова) і заміняємо його на символ a (крок 6). Якщо ж цей символ відмінний від b, то записуємо символ c вкінці вихідного слова. Коли буде скопійовано останній символ вхідного слова і повернуто до його двійника, то потім після переміщення на одну позицію вправо потрапимо на знак = (крок 6). Це сигнал про те, що вхідне слово повністю скопійовано, тому роботу МТ треба завершувати, а кретку перемістити на 1 символ вліво. 3.1. Обгрунтування вибору додаткових символів, що не входять в алфавит А Щоб розмежувати вхідне і вихідне слово, я відокремив їх деяким допоміжним символом, відмінним від всіх символів алфавіту A, знаком =. Оскільки я копіюю вхідне слово, то записавши справа копію чергового символу, потрібно повернутися до вхідного слова в позицію цього символа, і потім переміститися вправо до наступного символа, щоб скопіювати вже його. Щоб довідатися в яку позицію вхідного слова треба повернутися, вводимо додаткові символи. Коли ми опиняємось в цій позиції в перший раз, то заміняємо символ, що в ній знаходиться, на його двійника - на новий допоміжний символ, причому різні символи заміняємо на різні двійники : a на A , b на B , с на С. Після цього виконуються якісь дії в інших місцях стрічки. Щоб потім повернутись до потрібної позиції, треба просто відшукати на стрічці ту комірку, де перебуває символ A або B. Саме для відновлення колишнього символу і треба було ввести додаткові символи. АЛГОРИТМ У ВИГЛЯДІ ПРОГРАМИ ДЛЯ МТ Повна таблиця a0 a b c = A B C Пояснення q1 q2=L q1aR q1bR q1cR ставимо знак = після слова q2 q3a0R q2aL q2bL q2cL йдемо вліво на 1-й символ q3 q4AR q8BL q6CR q0=L аналіз і заміна чергового символа q4 q7a q4aR q4bR q4cR q4=R запис а зправа q5 q7b q5aR q5bR q5cR q5=R запис b зправа q6 q7c q6aR q6bR q6cR q6=R запис c зправа q7 q7aL q7bL q7cL q7=L q3aR q3bR q3cR повернення, відновлення, перехід до наступного q8 q9a0R q9a q9bR q9cR q9=R аналіз попереднього символа q9 q10a0L q9aR q9bR q9cR q9=R q9BR перехід до останнього елемента q10 q7c q5b q5c q5= аналіз і заміна потрібного символа Скорочена таблиця a0 a b c = A B C Пояснення q1 q2=L R R R ставимо знак = після слова q2 q3R L L L йдемо вліво на 1-й символ q3 q4AR q8BL q6CR q0L аналіз і заміна чергового символа q4 q7a R R R R запис а зправа q5 q7b R R R R запис b зправа q6 q7c R R R R запис c зправа q7 L L L L q3aR q3bR q3cR повернення, відновлення, перехід до наступного q8 q9R q9 q9R q9R q9R аналіз попереднього символа q9 q10L R R R R R перехід до останнього елемента q10 q7c q5 q5 q5 аналіз і заміна потрібного символа Протокол роботи МТ Для демонстрації програми та визначення протоколу, приймем: Слово P = cabc *Примітка: “_” - позначення пробілу, пустої клітинки. / Результат:cabc=ccc Протокол: q1cabc → cq1abc → caq1bc → cabq1c → cabcq1 → cabq1c=→ caq2bc= → cq2abc= → q2cabc= → q2_cabc= → q3cabc= → Cq6abc= → Caq6bc= → Cabq6c= → Cabcq6= → Cabc=q6 → Cabc=q7c → Cabcq7=c → Cabq7c=c → Caq7bc=c → Cq7abc=c → q7Cabc=c→ Cq3abc=c → cAq4bc=c → cAbq4c=c → cAbcq4=c → cAbc=q4c → cAbc=cq4 → cAbc=cq7a → cAbc=q7ca → cAbcq7=ca → cAbq7c=ca → cAq7bc=ca → cq7Abc=ca → caq7bc=ca → cq8aBc=ca → cq9aBc=ca → caq9Bc=ca → caBq9c=ca → caBcq9=ca → caBc=q9ca → caBc=cq9a → caBc=caq9 → caBc=cq10a → caBc=cq7c → caBc=q7cc → caBcq7=cc → caBq7c=cc → caq7Bc=cc → cabq3c=cc → cabCq6=cc → cabC=q6cc → cabC=cq6c → cabC=ccq6 → cabC=ccq7c → cabC=cq7cc → cabC=q7ccc → cabCq7=ccc → cabq7C=ccc →cabcq3=ccc → cabq0c=ccc ЕФЕКТИВНІСТЬ АЛГОРИТМУ 5.1. Часова складність Часова складність визначається послідовністю миттєвих станів машини і дорівнює кількості тактів, які треба виконати МТ для переробки заданого слова. T= 60 (для слова cabc) 5.1. Місткісна складність Місткісна складність визначається кількістю комірок стрічки, які використовуються в процесі виконання програми по переробці заданого слова. M= 9 (для слова cabc) 5.1. Програмна складність Програмна складність визначається загальною кількістю тактів, записаних в таблиці МТ. P = 49 РЕЗУЛЬТАТ ВИКОНАННЯ ПРОГРАМИ / Висновки Навчився принципам роботи машин Тьюрінга, набув практичних навичок програмування машин Тьюрінга.

Звіт до лабораторної роботи АМО

Makogin

25.05.2013 17:00

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись