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