МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Лабораторна робото №1 На тему: " Програмування машин Тьюрінга" «Алгоритми та методи обчислень» № варіанту = 21 1.Мета роботи Вивчити принципи роботи машин Тюринга, набути практичних навичок програмування машин Тьюрінга. 2.Загальні теоретичні відомості Алгоритм - це точний набір інструкцій, що описують послідовність дій деякого виконавця для досягнення результату, Розв'язок деякого завдання за кінцевий час. У зв'язку з розвитком паралельності в роботі комп'ютерів слово «послідовність» стали заміняти більше загальним словом «порядок». Це пов'язане з тим, що якісь дії алгоритму повинні бути виконані тільки один за одним, але якісь можуть бути й незалежними. 3.Індивідуальне Завдання 21. A={a,b}. Для непорожнього слова P визначити, чи входить в нього ще раз його перший символ. Відповідь: a (так) або порожнє слово (ні). 4.Опис алгоритму В залежності від символа ‘a’ чи ‘b’ ,переходимо в стан в якому шукаємо чи повториться наш вхідний символ ,якщо найшли потрібний нам символ, йдемо в кінець рядка стираємо наше слово і друкуємо ‘a’,в іншому випадку (якщо символ не повторяється) йдемо в кінець рядка стираємо наше слово і залишаємо стрічку пустою. 5. Алгоритм у вигляді програми для МТ 6.Ефективність алгоритму Часова складність визначається послідовністю миттєвих станів машини і дорівнює кількості тактів, які треба виконати МТ для переробки заданого слова. Часова: Т=9, для слова baaba Місткісна складність визначається кількістю комірок стрічки, які використовуються в процесі виконання програми по переробці заданого слова. Місткістна: М=19 Програмна складність визначається загальною кількістю тактів, записаних в таблиці МТ. Програмна: Р=12 7.Результат виконання програми 8.Висновки На даній лабораторній роботі,я вивчив принципи роботи абстрактних машин, набув практичних навичок програмування машин Тьюрінга.