Лабораторна робота №1. Лабораторна робота з Алгоритми та методи обчислень. Робота № 525316

Лабораторна робота №1

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

РТ

Кафедра:

Не вказано

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

Рік:

2013

Тип роботи:

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

Предмет:

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

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Лабораторна робота №1 Програмування машин Тьюрінга № варіанту = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 30 + 1= =(14+84)%30+1=98%30+1=8+1=9 Львів – 2012 1. Мета роботи Вивчити принципи роботи машин Тюринга, набути практичних навичок програмування машин Тьюрінга. 2. Постановка задачі Загальна частина: Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Використання додаткових символів, що не входять в алфавит А, має бути обгрунтоване. Скласти програму для мaшини Тьюрінга. В початковому стані каретка МТ має розпізнавати перший зліва символ вхідного слова Р. В кінцевому стані каретка МТ має зупинитись під одним із символів вихідного слова (під яким саме - не має значення). Відлагодження і тестування програми провести в середовищі емулятора машини Тьюрінга. Записати в середовищі емулятора в поле Условие задачи варіант і умову індивідуального завдання. В поле Комментарий записати коротке пояснення дій, які реалізуються у відповідних станах каретки. Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МТ. 9. A={a,b,c}. Замінити в непорожньому слові P кожне входження символів bc на символ a. 3.Словесний опис алгоритму Переглядаємо вхідне слово зліва направо до порожньої комірки або до першого символу b. В першому випадку символ bc не входить в слово P, тому нічого не робимо. В іншому випадку треба на місце символу с записати символ а , а потiм переміщаємо початок слова P (від знайденого символу bc до першого символу) на одну позицію вправо. Якщо через позначити стан, у якому в комірку треба записати символ x, який перебував раніше в комірці зліва.Для цього потрібно виконати такт , у якому об'єднані наступні три дії: - по-перше, в комірку записується символ x, взятий із комірки зліва; - по-друге, каретка переміщується вправо (під комірку, в яку потім треба буде записати тільки що замінений символ y); - по-третє, каретка переходить в стан , у якому вона і буде виконувати цей запис. Повторення таких тактів у циклі і приведе до переміщення вправо на одну позицію початкових символів вхідного слова. Цей цикл повинен закінчитись, коли в черговій комірці виявиться символ a або (y=a або y=), а на початку циклу можна вважати, що на місце першого символу зліва переноситься символ «порожньо» (x=). 4. Алгоритм у вигляді програми для МТ 4.1. Повна таблиця Q A a0 a b c Пояснення q1 q0 a0 q1 a R q2 b R q1 c R аналіз вхiдного слова до першого b , розгалуження q2 q0 a0 q1 a R q1 b R q3 a L якщо наступний символ с то спочатку q3 а потiм q4 q3 q4 a L q4 b L q4 c L переміститись наліво q4 q8a0L q5 a L q6 b L q7 c L розгалуження q5 q3 a L q3 a L q3 a L запис a справа q6 q3 b L q3 b L q3 b L запис b справа q7 q3 c L q3 c L q3 c L запис c справа q8 q1 a0 L q1 a0 L q1 a0 L a0 замiсть першого символа 4.2. Скорочена таблиця Q A a0 a b c Пояснення q1 q0 R q2 R R аналіз вхiдного слова до першого b , розгалуження q2 q0 R q1 R q3 a L якщо наступний символ с то спочатку q3 а потiм q4 q3 q4 L q4 L q4 L переміститись наліво q4 q8a0L q5 L q6 L q7 L розгалуження q5 q3 L q3 a L q3 a L запис a справа q6 q3 b L q3 L q3 b L запис b справа q7 q3 c L q3 c L q3 L запис c справа q8 q1 a0 L q1 a0 L q1 a0 L a0 замiсть першого символа 5.Ефективність алгоритму 5.1. Часова складність Запустивши покроково (F8) програму на виконання можна порахувати, що кількість виконаних тактів по переробці слова acbccb дорівнює 20, тобто часова складність T=20. 5.1. Місткісна складність Можна зауважити, що в процесі роботи використовуються комірки стрічки з номерами від 2 до 7 , тобто місткісна складність М=6. 5.1. Програмна складність Табличне представлення МТ містить 32 заповнені комірки, отже програмна складність цієї МТ дорівнює Р=32. 6. Результати виконання програми

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

ggggg

19.12.2013 23:45

Коментарі

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

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

поділитись