Лабораторна робота № 3
"Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ)".
Мета роботи : Ознайомлення зі способом зменшення часової складності.
Зміст роботи:
I. Теоретична частина.
Математичні ФАС
Структура МТ.
Способи зменшення часової складності МТ
Обмеженність використання МТ.
Послідовність розв’язання задач на МТ.
II. Практична частина
Практичне заняття
Побудувати алгоритм МТ (“слід” МТ, програма) у відповідності до варіанту завдання.
Підрахувати часову, програмну та емкістну складність.
____________________________________________________________________________
Лабораторна робота
1. Скласти програму для МТ, користуючись програмою HYPERLINK "Mawuna%20Tur/ALGO2000.EXE"ALGO2000.EXE
2. Визначити часову, програмну та эмкыстну складнысть алгоритму
III. Висновки.
=============================================================================
Теза Тьюрінга: Будь-яка обчислювальна функція може бути реалізована на деякій машині Тьюрінга.
Математичні ФАС
Основним призначенням математичних ФАС є дослідження проблем розв’язності. Для цієї проблеми вимога елементарності кроку є необхідною. Оскільки ця вимога не може бути математично точно сформульована, вона інтерпретується як умова загальної зрозумілості. Математичні моделі ФАС ( вийнятки становлять рекурсивні функції) використовують елементарні операції типу розпізнавання символу, трасування, заміна або зміщення. Всі ці операції нагадують дитячу гру з кубиками, тому можуть вважатись загальнозрозумілими або елементарними.
Прикладом ФАС є машина Тьюрінга.
Структура МТ.
Існує низка варіантів детермінованих машин Тьюрінга: однострічкова, багатострічкова, універсальна та ін.Відмінність цих варіантів не принципова, вони зумовлені пошуком способів зменшення часової складності.
Модель однострічкової детермінованої МТ задається шісткою:
М = < 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}. Звідси, стан це мить, коли читаний із стрічки символ EMBED Equation.3 та новий символ EMBED Equation.3 готові до виконання нової команди.
Способи зменшення часової складності МТ
Часова складність МТ задається послідовністю миттєвих станів машини. Місткісна складність вимірюється кількістю комірок стрічки, яка необхідна для реалізації алгоритму. Складність програми визначається кількістю команд.
Мінімізація часової складності МТ пов’язана з використанням наступних способів:
? зміна розташування початкових даних на стрічці;
? вибір місця розташування проміжних результатів;
? вибір стратегії руху головки;
? вибір початкового положення головки;
? збільшення символів зовнішнього алфавіту;
? застосування паралелізму ( багатострічкова МТ ).

Обмеженність використання МТ.
Наведені способи мінімізації часової складності, крім останньго, не мають практичного значення для комп’ютерної реалізації. МТ є ідеалізованою моделлю алгоритму. Основним пунктом її ідеалізації, як і всіх інших математичних ФАС, є неврахування апаратних витрат, необхідних для реалізації алгоритму. Ця особливість математичних ФАС не дозволяє у повній мірі використовувати досягнення теорії ФАС у проектуванні апаратно-програмних засобів. А у деяких випадках цей недолік приводить до практично неприйнятних висновків. Прикладом тому є теорема про лінійне прискорення.
Послідовність розв’язання задач на МТ.
Розміщуються дані на стрічці
Визначається необхідність використання додаткових символів і місця їх розташування
Розробляється стратегія розв’язання задачі (слід машина Тюрінга )
Будується таблиця програми.
У відповідності до сліду машина Тюрінга розробляється набір команд, які розміщуються в клітинах таблиці.
Мінімізується кількість станів (команд) не змінюючи стратегії розв’язання задачі
Основна гіпотеза теорії алгоритмів: уточнення змісту алгоритму за допомогою рекурсивних функцій, моделей алгоритму: машини Тюрінга, нормальних алгоритмів Маркова – еквівалентні один одному. Основу гіпотези складають наступні тези:
Теза Чьорча: клас рекурсивно – примітивних функцій співпадає з класом обчислювальних функцій.
Теза Тюрінга: будь-яка обчислювальна функція може бути реалізована на відповідній машині Тюрінга.
Теза Маркова: будь-який довільний потенційно-здійснюваний процес перероблення слів в деякому алфавіті може бути представлений у вигляді певного нормальних алгоритму.


Приклади.
1. Виконати операцію (Х mod 3), де Х= 100111.
Визначити часову (L), програмну (P) та місткісну (M) складність алгоритму.
EMBED Visio.Drawing.5










P = 44
В алгоритмі використано наступну властивість :
Якщо С = А + В , то С mod3 =(A mod3 + B mod3) mod3

2. Виконати операцію кон’юнкції: (Х ? Y), де Х= 0101, Y = 0110.
Визначити часову (L), програмну (P) та місткісну (M) складність алгоритму.
EMBED Visio.Drawing.5








P = 29






3. Виконати операцію переводу формата числа із десяткового в унарний : Х(10) ? Y(1), де Х= 10.
Визначити часову (L), програмну (P) та місткісну (M) складність алгоритму.

EMBED Visio.Drawing.5











Варіанти завдань.
Номер варіанту відповідає номеру студента в журналі.
Виконати операцію Y = (X mod 3 ), де X, Y – двійкові числа. L=20
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операціюY = (X mod 3), де X, Y – двійкові числа з мінімальною часовою складністю L=10
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію Y = (X mod 3), де X, Y – десяткові числа
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5

Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Без збереження вхідних даних.
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Без збереження вхідних даних.
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Зі збереженням вхідних даних.
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Зі збереженням вхідних даних.
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Результат розташувати на місці вхідних даних

Виконати операцію додавання двох двійкових чисел:Z= ( X+Y) з мінімальною часовою складністю
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Розташування даних довільне.
Виконати операцію додавання двох десяткових чисел, Z=( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Без збереження вхідних даних.
Виконати операцію додавання двох десяткових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Без збереження вхідних даних.
Виконати операцію додавання двох десяткових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Зі збереженням вхідних даних.
Виконати операцію додавання двох десяткових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Зі збереженням вхідних даних.
Виконати операцію додавання двох десяткових чисел: Z= ( X+Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Результат розташувати на місці вхідних даних
Виконати операцію віднімання двох двійкових чисел, Z=( X-Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Без збереження вхідних даних. Числа представлені в прямому коді.
Виконати операцію віднімання двох двійкових чисел: Z= ( X-Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Без збереження вхідних даних. Числа представлені в прямому коді.

Виконати операцію віднімання двох двійкових чисел: Z= ( X-Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Зі збереженням вхідних даних. Числа представлені в прямому коді.
Виконати операцію віднімання двох двійкових чисел: Z= ( X-Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Зі збереженням вхідних даних. Числа представлені в прямому коді.
Виконати операцію віднімання двох десяткових чисел, Z=( X-Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
X>=Y
Виконати операцію віднімання двох десяткових чисел, Z=( X-Y)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
X<Y
Виконати операцію операцію переводу формата числа із десяткового в унарний X(10) ? Y(1),
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію операцію переводу формата числа із десяткового в двійковий X(10) ? Y(2),
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію операцію переводу формата числа із двійкової в десяткову X(2) ? Y(10),
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію кон'юнкції (AND ) двох двійкових чисел: Z= (X v Y),
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5

Виконати операцію дезюнкції ( OR ) двох двійкових чисел:Z= ( X^ Y) з мінімальною часовою складністю
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Розташування даних довільне.
Представити число Х (Xn Xn-1…. X1 X0) в двійково-інверсному коді (X0 X1…. Xn-1 Xn)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Розташування даних довільне.
Представити число Х (Xn Xn-1…. X1 X0) в двійково-інверсному коді (X0 X1…. Xn-1 Xn)
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію зсувудвійкового числа Х вліво на 4 розряди
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію зсувудвійкового числа Х вліво на Y розрядів
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію циклічного зсуву двійкового числа Х вліво на Y розрядів
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію циклічного зсуву двійкового числа Х вправо на Y розрядів
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
Виконати операцію множення двох десяткових чисел X*Y
EMBED Visio.Drawing.5
EMBED Visio.Drawing.5
X<10, Y<10 Розташування результату довільне.
EMBED Visio.Drawing.5 - початкове положення рухомої головки задано
EMBED Visio.Drawing.5 - виберіть початкове положення рухомої головки таким чином, щоб часова складність була найменшою