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

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Електронні обчислювальні машини

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

Рік:

2015

Тип роботи:

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

Предмет:

Алгоритми та методи оптимізації

Група:

КI

Завантажити

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

Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт Лабораторна робота №3 "Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ)". Виконав: ст.гр. КІ-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» Висновок: на дані лабораторні роботі я засвоїв роботу машини Тюрінга. Визначив основні властивості алгоритмів.

Лабораторна робота Алгоритми та методи оптимізації

2015

Коментарі

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

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

поділитись