Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Програмування машин Тьюрінга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Компютерних технологій автоматики та метрології
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Група:
КІ
Варіант:
2
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Звіт
До лабораторної роботи №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
Висновки
Навчився принципам роботи машин Тьюрінга, набувпрактичнихнавичок програмування машин Тьюрінга.
27.11.2012 18:15
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора