Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ)
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
Лабораторна робота №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»
Висновок: на дані лабораторні роботі я засвоїв роботу машини Тюрінга. Визначив основні властивості алгоритмів.
28.01.2013 14:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора