Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт Лабораторна робота №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 – головка залишається на місці. Завдання: Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)  EMBED Visio.Drawing.5 
  EMBED Visio.Drawing.5 
 Результат розташувати на місті вхідних даних Програма до виконання;
Після:
Алгоритм завдання: пересувати рухому головку вправо поки головка не стане на пусту клітинку, після цього пересунути головку вліво, якщо в цій клітинці знаходиться «0» то поміняти «1» і таке пересування повторювати доти поки в клітинці не буде «1» (якщо буде «+» то прогу закінчити), після цього пересувати головку вліво поки головка не буде вказувати на клітинку з «+» після цього пересунути головку вліво, якщо в цій клітинці знаходиться «1» то поміняти «0» і таке пересування повторювати доти поки в клітинці не буде «0» або «_», після цього повторювати всі вище зазначені дії поки не попаде на вище зазначену умову кінця. Часову (L) складність =170 Програмна (P) складність =15 Місткісна (M) складність=9 Максимальна часову (L) складність =232 «1111+1111» Мінімальна часову (L) складність =34 «0000+0001» Висновок: на дані лабораторні роботі я засвоїв роботу машини Тюрінга. Визначив основні властивості алгоритмів.