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

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

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

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

ВУЗ:

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

Інститут:

ІКТА

Факультет:

КН

Кафедра:

ЕОМ

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

Рік:

2012

Тип роботи:

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

Предмет:

АМО

Варіант:

Завантажити

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

Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 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:05-

Коментарі

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

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

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

поділитись