Програмування машини Тюринга. Лабораторна робота з АМО. Робота № 524322

Програмування машини Тюринга

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

ВУЗ:

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

Інститут:

ІКТА

Факультет:

КН

Кафедра:

ЕОМ

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

Рік:

2013

Тип роботи:

Лабораторна робота

Предмет:

АМО

Варіант:

Завантажити

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

Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 1 на тему: " Програмування машин Тьюрінга " з дисципліни: " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ " Вибір індивідуального завдання: DN = 17 Pr1 = №(S) = 83 № V=(17+83)%30+1=11 Мета роботи Вивчити принципи роботи машин Тюринга, набути практичних навичок програмування машин Тьюрінга. Постановка задачі Загальна частина Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Використання додаткових символів, що не входять в алфавит А, має бути обгрунтоване. Скласти програму для мишини Тьюрінга. В початковому стані каретка МТ має розпізнавати перший зліва символ вхідного слова Р. В кінцевому стані каретка МТ має зупинитись під одним із символів вихідного слова (під яким саме - не має значення). Відлагодження і тестування програми провести в середовищі емулятора мишини Тьюрінга. Записати в середовищі емулятора в поле Условие задачи варіант і умову індивідуального завдання. В поле Комментарий записати коротке пояснення дій, які реалізуються у відповідних станах каретки. Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МТ. Індивідуальне завдання A={0,1}. Вважаючи непорожнє слово P записом двійкового числа, видалити з нього незначущі нулі, якщо такі є. Словесний опис алгоритму Для розв'язання цієї задачі потрібно перемістити каретку під крайній лівий елемент послідовності і переміщати каретку вправо замінюючи «0» на «порожнє» доки не зустрінеться «1» або «порожнє» Алгоритм у вигляді програми для МТ Вхідне слово: 0001101 4.1 Повна таблиця Q A a0 0 1 q1 q00 q1a0R q01 4.2 Скорочена таблиця Q A a0 a b q1 q00 a0R q0 4.3 Протокол роботи МТ K0 0 0 0 1 1 0 1 q1 0q1001101 K1 0 1 1 1 0 1 q1 0q101101 K2 0 1 1 1 0 1 q1 0q11101 K3 1 1 0 1 q1 1q1101 K4 1 1 0 1 q0 1q0101 0q1001101=>0q101101=>0q11101=>1q1101=>1q0101 Ефективність алгоритму 5.1 Часова складність Кількість виконаних тактів по переробці слова0001101 дорівнює 5, тобто часова складність T=5. 5.2 Місткісна складність В процесі роботи використовуються комірки стрічки з номерами від -3 до 6, тобто місткісна складність М=10. 5.3 Програмна складність Табличне представлення МТ містить 5 заповнені комірки, отже програмна складність цієї МТ дорівнює Р=3. Результати виконання програми / / Висновок У цій лабораторній роботі я вивчив принципи роботи машин Тюринга та набув практичних навичок програмування машин Тьюрінга.

Лабораторна робота АМО

Skiff

26.05.2013 18:47

Коментарі

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

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

поділитись