МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ Звіт До лабораторної роботи №1 “Програмування машин Тьюрінга” з дисципліни " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" Львів – 2012 1. Мета роботи Вивчити принципи роботи машин Тюрiнга, набути практичних навичок програмування машин Тьюрінга. 2. Постановка задачі 2.1. Загальна частина Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Використання додаткових символів, що не входять в алфавит А, має бути обгрунтоване. Скласти програму для мишини Тьюрінга. В початковому стані каретка МТ має розпізнавати перший зліва символ вхідного слова Р. В кінцевому стані каретка МТ має зупинитись під одним із символів вихідного слова (під яким саме - не має значення). Відлагодження і тестування програми провести в середовищі емулятора мишиниТьюрінга. Записати в середовищі емулятора в поле Условие задачи варіант і умову індивідуального завдання. В поле Комментарий записати коротке пояснення дій, які реалізуються у відповідних станах каретки. Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МТ. 2.2. Індивідуальне завдання A={a,b,c}. Якщо P - слово парної довжини (0, 2, 4, ...), то видати як відповідь символ a, інакше - порожнє слово. 3. Словесний опис алгоритму Для розв’язання поставленої задачі необхідно посимвольно пройти кареткою тим самим змінюючи стани, тобто використовувати Q1– для непарного номеру символа в слові, аQ2 – для парного. Проходячи по слову видаляєм символи, змінюючи стани Q1 і Q2. При знаходженні “_” відповідно для парних і непарних змінюєм на стан Q3 іQ4. Де Q3 – завершує виконання програми(зміною стану на Q0) і як результат ми отримаємо “порожнє слово”, а Q4 –для заміни «_» на символ а і переключає стан на Q0. 4. Алгоритм у вигляді програми для МТ 4.1. Повна таблиця QA a b c _  q1 q2 a R q2 b R q2 c R q4 _ L  q2 q1 a R q1 b R q1 c R q3 _ L  q3 q3 _ L q3 _ L q3 _ L q0 _ R  q4 q4 _ L q4 _L q4 _ L q0 a   4.2. Скорочена таблиця QA a b c _  q1 q2 R q2 R q2 R q4L  q2 q1 R q1 R q1 R q3 L  q3 _ L  _ L _ L q0 R  q4 _ L _ L  _ L q0 a   4.3. Протокол роботи МТ Для демонстрації програми та визначення протоколу, приймем: Слово P = abc Слово P = abac *Примітка: “_” - позначення пробілу, пустої клітинки. 1.abc Конфігурації ↓q1 _ a b c _  ↓q2 _ a b c _  ↓q1 _ a b c _  ↓q2 _ a b c _  ↓q3 _ a b _ _   ↓q3 _ a _ _ _  ↓q3 _ _ _ _ _  ↓q3 _ _ _ _ _  ↓q0 _ _ _ _ _   Результат: пусте слово. Протокол: q1abc→aq2 bc→abq1 c→abcq2 _ →abq3 _ _ →aq3 _ _ _ →q3 _ _ _ _ → q3 _ _ _ _ _ → _ q0 _ _ _ 2. abac Конфігурації ↓q1 _ a b a c _  ↓q2 _ a b a c _  ↓q1 _ a b a c _  ↓q2 _ a b a c _  ↓q1 _ a b a c _  ↓q4 _ a b a _ _  ↓q4 _ a b _ _ _  ↓q4 _ a _ _ _ _  ↓q4 _ _ _ _ _ _  ↓q4 _ _ _ _ _ _  ↓q0 _ a _ _ _ _   Результат: а. Протокол: q1 a b a c→ a q2 b a c→ a b q1 a c→ a b a q2 c→ a b a c q1 _ → a b a q4 _ _ → →a b q4 _ _ _ → a q4 _ _ _ _ → q4 _ _ _ _ _ →q4 _ _ _ _ _ _ → _ q0 a _ _ _ _ 5. Ефективність алгоритму 5.1. Часова складність Часова складність визначається послідовністю миттєвих станів машини і дорівнює кількості тактів, які треба виконати МТ для переробки заданого слова. T= 9 (для слова abc) T= 11 (для слова abac) 5.1. Місткісна складність Місткісна складність визначається кількістю комірок стрічки, які використовуються в процесі виконання програми по переробці заданого слова. M= 5 (для слова abc) M= 6 (для слова abac) 5.1. Програмна складність Програмна складність визначається загальною кількістю тактів, записаних в таблиці МТ. P = 16 6. Результати виконання програми / Мал.1 Результат для слова abc / Мал.2Результат для слова abac Висновки Навчився принципам роботи машин Тьюрінга, набувпрактичнихнавичок програмування машин Тьюрінга.