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

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

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

РТ

Кафедра:

Не вказано

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

Рік:

2012

Тип роботи:

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

Предмет:

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

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Лабораторна робота №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:12-

Коментарі

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

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

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

поділитись