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

Перехід до торгівельного партнера Binance

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

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

ВУЗ:

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

Інститут:

ІКТА

Факультет:

КН

Кафедра:

Кафедра ЕПМС

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

Рік:

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:05-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись