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

Перехід до торгівельного партнера Binance

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

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

ВУЗ:

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

Інститут:

ІКТА

Факультет:

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

Кафедра:

Кафедра ЕПМС

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

Рік:

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:05-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись