Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 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. Результати виконання програми / / Висновок У цій лабораторній роботі я вивчив принципи роботи машин Тюринга та набув практичних навичок програмування машин Тьюрінга.