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

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

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

ВУЗ:

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

Інститут:

ІКТА

Факультет:

КН

Кафедра:

Кафедра ЕПМС

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

Рік:

2014

Тип роботи:

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

Предмет:

Алгоритми та методи обчислень

Варіант:

Завантажити

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

Міністерство освіти та науки України Національний університет «Львівська політехніка» Кафедра ЕОМ / ЗВІТ З лабораторної роботи №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 – головка залишається на місці. Машини Тьюрінга мають одну і ту ж конфігурацію засобів реалізації алгоритму. У конфігурацію входять такі елементи: нескінчена нерухома стрічка, що поділена на окремі комірки, в які можна помістити тільки один символ зовнішнього алфавіту ; рухома головка, яка може стирати, записувати і зчитувати символи зовнішнього алфавиту в комірках стрічки, програма з кінцевою кількістю станів. Ці елементи і лінії передавання повідомлень, що їх пов’язують, утворюють структуру машини Тьюрінга, яка не залежить від структури алгоритму, що моделюється. [] Ця важлива особливість мМТ дозволяє кількісно порівнювати різні алгоритми з часової, місткісної складності і складності програм. Машина Тьюрінга як модель алгоритму відповідає визначенню алгоритму. В явному вигляді тут означені всі сім параметрів. Слід машини наочно відображає структуру алгоритму, кількість циклів програми. Особливості роботи МТ не суперечать властивостям алгоритму. Кроки МТ дискретні і детерміновані, мають властивість масовості. Єдина властивість, яка приймається умовно – це елементарність кроку. У машині Тьюрінга крок алгоритму супроводжується декількома операціями: читання символу в комірці стрічки, пошук необхідної команди, виконання команди – операція зі змістом комірки ( залишити попередній символ, стерти його, записати новий ), операція переміщення головки ( залишити на місці, зсунути ліворуч чи праворуч). Всі ці операці, що складають крок алгоритму, є загальнозрозумілими. Крок машини Тюрінга описується виразом {A}x{Q}x{→}x{A}x{R,L,S}x{Q}. Звідси, стан це мить, коли читаний із стрічки символ та новий символ готові до виконання нової команди. Способи зменшення часової складності МТ . Часова складність МТ задається послідовністю миттєвих станів машини. Місткісна складність вимірюється кількістю комірок стрічки, яка необхідна для реалізації алгоритму. Складність програми визначається кількістю команд. Мінімізація часової складності МТ пов’язана з використанням наступних способів: ( зміна розташування початкових даних на стрічці; ( вибір місця розташування проміжних результатів; ( вибір стратегії руху головки; ( вибір початкового положення головки; ( збільшення символів зовнішнього алфавіту; ( застосування паралелізму ( багатострічкова МТ ). Обмеженність використання МТ. Наведені способи мінімізації часової складності, крім останньго, не мають практичного значення для комп’ютерної реалізації. МТ є ідеалізованою моделлю алгоритму. Основним пунктом її ідеалізації, як і всіх інших математичних ФАС, є неврахування апаратних витрат, необхідних для реалізації алгоритму. Ця особливість математичних ФАС не дозволяє у повній мірі використовувати досягнення теорії ФАС у проектуванні апаратно-програмних засобів. А у деяких випадках цей недолік приводить до практично неприйнятних висновків. Прикладом тому є теорема про лінійне прискорення. Послідовність розв’язання задач на МТ. Розміщуються дані на стрічці Визначається необхідність використання додаткових символів і місця їх розташування Розробляється стратегія розв’язання задачі (слід машина Тюрінга ) Будується таблиця програми. У відповідності до сліду машина Тюрінга розробляється набір команд, які розміщуються в клітинах таблиці. Мінімізується кількість станів (команд) не змінюючи стратегії розв’язання задачі Основна гіпотеза теорії алгоритмів: уточнення змісту алгоритму за допомогою рекурсивних функцій, моделей алгоритму: машини Тюрінга, нормальних алгоритмів Маркова – еквівалентні один одному. Основу гіпотези складають наступні тези: Теза Чьорча: клас рекурсивно – примітивних функцій співпадає з класом обчислювальних функцій. Теза Тюрінга: будь-яка обчислювальна функція може бути реалізована на відповідній машині Тюрінга. Теза Маркова: будь-який довільний потенційно-здійснюваний процес перероблення слів в деякому алфавіті може бути представлений у вигляді певного нормальних алгоритму. ПОРЯДОК ВИКОНАННЯ РОБОТИ Виконати операцію додавання двох двійкових чисел: Z= ( X+Y) Без збереження вхідних даних. Q A q0 q1 q2 q3 q4 q5 1 yLq0 Rq1 a0Lq3 Lq3 Rq4 a0Rq5 0 xLq0 Rq1 Lq3 Rq4 Rq5 + Lq0 Rq1 Lq3 1Rq5 = Rq1 a0Rq4 x Rq1 1Lq4 y Rq1 0Lq3 a0Lq4 a0 Lq2 Rq4 qf P = 25 Висновок. Я ознайомилась зі способами зменшення часової складності.

Лабораторна робота Алгоритми та методи обчислень

esxcfxfcvh4e7yfcv6yugvb

27.05.2014 22:44

Коментарі

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

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

поділитись