Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт Лабораторна робота №3 "Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ)". Прийняв: Львів 2008 Мета роботи : Ознайомлення зі способом зменшення часової складності. Теоретична частина. Математичні ФАС Основним призначенням математичних ФАС є дослідження проблем розв’язності. Для цієї проблеми вимога елементарності кроку є необхідною. Оскільки ця вимога не може бути математично точно сформульована, вона інтерпретується як умова загальної зрозумілості. Математичні моделі ФАС ( вийнятки становлять рекурсивні функції) використовують елементарні операції типу розпізнавання символу, трасування, заміна або зміщення. Всі ці операції нагадують дитячу гру з кубиками, тому можуть вважатись загальнозрозумілими або елементарними. Прикладом ФАС є машина Тьюрінга. . Структура МТ. Існує низка варіантів детермінованих машин Тьюрінга: однострічкова, багатострічкова, універсальна та ін.Відмінність цих варіантів не принципова, вони зумовлені пошуком способів зменшення часової складності. Модель однострічкової детермінованої МТ задається шісткою: М = < A, Q, q0, qf, a0, p >, де A – кінцева множина символів зовнішнього алфавіту, Q – кінцева множина символів внутрішнього алфавіту, q0 – початковий стан, qf – кінцевий стан, q0, qf Є Q a0 – позначення порожньої комірки стрічки, p – така програма, яка не може мати двох команд, у яких би збігалися два перші символи: {A}x{Q} {A}{L,R,S}{Q}, де L – зсувати головку вліво, R - зсувати головку вправо, S – головка залишається на місці. 3.Способи зменшення часової складності МТ Часова складність МТ задається послідовністю миттєвих станів машини. Місткісна складність вимірюється кількістю комірок стрічки, яка необхідна для реалізації алгоритму. Складність програми визначається кількістю команд. Мінімізація часової складності МТ пов’язана з використанням наступних способів:  зміна розташування початкових даних на стрічці;  вибір місця розташування проміжних результатів;  вибір стратегії руху головки;  вибір початкового положення головки;  збільшення символів зовнішнього алфавіту;  застосування паралелізму ( багатострічкова МТ ). 4.Обмеженність використання МТ. Наведені способи мінімізації часової складності, крім останньго, не мають практичного значення для комп’ютерної реалізації. МТ є ідеалізованою моделлю алгоритму. Основним пунктом її ідеалізації, як і всіх інших математичних ФАС, є неврахування апаратних витрат, необхідних для реалізації алгоритму. Ця особливість математичних ФАС не дозволяє у повній мірі використовувати досягнення теорії ФАС у проектуванні апаратно-програмних засобів. А у деяких випадках цей недолік приводить до практично неприйнятних висновків. Прикладом тому є теорема про лінійне прискорення. 5.Послідовність розв’язання задач на МТ. Розміщуються дані на стрічці Визначається необхідність використання додаткових символів і місця їх розташування Розробляється стратегія розв’язання задачі (слід машина Тюрінга ) Будується таблиця програми. У відповідності до сліду машина Тюрінга розробляється набір команд, які розміщуються в клітинах таблиці. Мінімізується кількість станів (команд) не змінюючи стратегії розв’язання задачі Завдання: Виконати операцію операцію переводу формата числа із десяткового в двійковий X(10)  Y(2),  EMBED Visio.Drawing.5 
  EMBED Visio.Drawing.5 
 Програма до виконання:
Програма після виконання:
Часову (L) складність =170 Програмна (P) складність =15 Місткісна (M) складність=9 Максимальна часову (L) складність =232 «1111+1111» Мінімальна часову (L) складність =34 «0000+0001» Висновок: на дані лабораторні роботі я засвоїв роботу машини Тюрінга. Визначив основні властивості алгоритмів.