Міністерство освіти та науки України Національний університет «Львівська політехніка» Кафедра ЕОМ / ЗВІТ З лабораторної роботи №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 Висновок. Я ознайомилась зі способами зменшення часової складності.