Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ). Лабораторна робота з Інші. Робота № 518999

Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ)

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2013

Тип роботи:

Лабораторна робота

Предмет:

Інші

Завантажити

Частина тексту файла (без зображень, графіків і формул):

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

Лабораторна робота Інші

infoman

28.01.2013 14:26

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись