Дослідження ефективності машин Тьюрінга
Будемо оцінювати ефективність роботи МТ з точки зору часової (T), місткісної (М) та програмної (Р) складностей алгоритму.
Часова складність визначається послідовністю миттєвих станів машини і дорівнює кількості тактів, які треба виконати МТ для переробки заданого слова.
Місткісна складність визначається кількістю комірок стрічки, які використовуються в процесі виконання програми по переробці заданого слова.
Програмна складність визначається загальною кількістю тактів, записаних в таблиці МТ.
Наприклад, якщо запустити програму EXAMPLES\ double_word.tur , то середовище емулятора МТ набуде такого вигляду:
Запустивши покроково (F8) програму на виконання можна порахувати, що кількість виконаних тактів по переробці слова abbab дорівнює 84, тобто часова складність T=84.
Можна зауважити, що в процесі роботи використовуються комірки стрічки з номерами від -1 до 10, тобто місткісна складність М=12.
Табличне представлення МТ містить 22 заповнені комірки, отже програмна складність цієї МТ дорівнює Р=22.
ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики.
2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.
3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.
|
|
|
4. Протестувати програму згідно зі складеною системою тестів і, при потребі, відкоректувати текст програми. Проаналізувати отримані результати.
5. Написати контрольне опитування по темі.
6. Оформити звіт по роботі.
Без підготовкі до лабораторної роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.
ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
Вибір варіанту індивідуального завдання
№ варіанту = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 30 + 1
Варіанти завдань
Загальна частина:
Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Використання додаткових символів, що не входять в алфавит А, має бути обгрунтоване.
Скласти програму для мишини Тьюрінга. В початковому стані каретка МТ має розпізнавати перший зліва символ вхідного слова Р. В кінцевому стані каретка МТ має зупинитись під одним із символів вихідного слова (під яким саме - не має значення).
Відлагодження і тестування програми провести в середовищі емулятора мишини Тьюрінга. Записати в середовищі емулятора в поле Условие задачи варіант і умову індивідуального завдання. В поле Комментарий записати коротке пояснення дій, які реалізуються у відповідних станах каретки.
|
|
|
Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МТ.
Індивідуальні завдання:
1. A={a,b,c}. Дописати зліва до слова P символ b (P → bР).
2. A={a,b,c}. Дописати справа до слова P символи bc (P → Pbc).
3. A={a,b,c}. Замінити на символ a кожний другий символ у слові P.
4. A={a,b}. Замінити в непорожньому слові P кожне входження символа a на символи bb.
5. A={a,b,c}. Залишити в слові P тільки останній символ (порожнє слово не міняти).
6. A={a,b,c}. Визначити, чи є P словом ab. Відповідь (вихідне слово): слово ab, якщо є, або порожнє слово, якщо не є.
7. A={a,b,c}. Визначити, чи входить в слово P символ a. Відповідь: слово з одного символу a (так, входить) або порожнє слово (ні, не входить).
8. A={a,b,c}. Якщо в слово P не входить символ a, то замінити в P всі символи b на символи с, інакше як відповідь видати слово з одного символу a.
9. A={a,b,c}. Замінити в непорожньому слові P кожне входження символів bc на символ a.
10. A={a,b,0,1}. Визначити, чи є слово P записом числа у двійковій системі числення ( тобто непорожнім словом, що складається тільки з цифр 0 і 1). Відповідь: слово 1 (так) або слово 0 (ні).
|
|
|
11. A={0,1}. Вважаючи непорожнє слово P записом двійкового числа, видалити з нього незначущі нулі, якщо такі є.
12. A={0,1}. Для непорожнього слова P визначити, чи є воно записом ступеня двійки (1, 2, 4, 8, 16, 32 ...) в двійковій системі числення. Відповідь: слово 1 (є) або слово 0 (ні).
13. A={a,b,c}. Замінити в непорожньому слові P кожне входження символа a на символи abc.
14. A={0,1}. Вважаючи непорожнє слово P записом числа у двійковій системі числення, отримати двійкове число, що дорівнює учетверенному числу P (наприклад: 101 → 10100).
15. A={a,b,c}. Замінити в непорожньому слові P кожне входження символа b на символи aс.
16. A={a,b,c}. Якщо P - слово парної довжини (0, 2, 4, ...), то видати як відповідь символ a, інакше - порожнє слово.
17. A={0,1,2}. Вважаючи непорожнє слово P записом числа в трійковій системі числення, визначити, чи є воно парним числом, чи ні. Відповідь: 1 (так) або 0 (ні). (Зауваження: в парному трійковому числі має бути парна кількість цифр 1.)
18. A={a,b,c}. Нехай P має непарну довжину. Залишити в P тільки середній символ.
19. A={a,b,c}. Замінити в непорожньому слові P кожне входження символа c на символи ab.
|
|
|
20. A={a,b,c}. Дописати зліва до непорожнього слова P його перший символ.
21. A={a,b}. Для непорожнього слова P визначити, чи входити в нього ще раз його перший символ. Відповідь: a (так) або порожнє слово (ні).
22. A={a,b}. В непорожньому слові P поміняти місцями його перший і останній символи.
23. A={a,b}. Якщо в непорожньому слові P символів a більше, ніж символів b, то видати відповідь a, якщо символів a менше символів b, то видати відповідь b, а інакше в якості відповіді видати порожнє слово.
24. A={a,b,c}. Залишити в слові P тільки перший символ (порожнє слово не міняти).
25. A={a,b,c}. Замінити в непорожньому слові P кожне входження символів ab на символ c.
26. A={a,b}. Подвоїти слово P (наприклад: abb → abbabb).
27. A={a,b}. Подвоїти кожний символ непорожнього слова P (наприклад: bab → bbaabb).
28. A={a,b}. Перевернути непорожнє слово P (наприклад: abb → bba).
29. A={a,b,c}. Замінити в непорожньому слові P кожне входження символів cc на символи ab.
30. A={a,b,0,1}. Визначити, чи є слово P ідентифікатором ( тобто непорожнім словом, що починається з букви). Відповідь: слово a (так) або порожнє слово (ні).
ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ
I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.
II. В звіті мають бути відображені наступні пункти:
1. Мета роботи
2. Постановка задачі
2.1. Загальна частина
2.2. Індивідуальне завдання
3. Словесний опис алгоритму
3.1. Обгрунтування вибору додаткових символів, що не входять в алфавит А (за потребою)
4. Алгоритм у вигляді програми для МТ
4.1. Повна таблиця
4.2. Скорочена таблиця
4.3. Протокол роботи МТ
5. Ефективність алгоритму
5.1. Часова складність
5.1. Місткісна складність
5.1. Програмна складність
6. Результати виконання програми
Висновки
КОНТРОЛЬНІ ЗАВДАННЯ
Задана машина Тьюрінга з наступною функціональною схемою:
| 
| |
| 
| 
|
| 0 | 
|
|
| 1 | 
| 
|
1. Записати зовнішній алфавіт та алфавіт внутрішніх станів цієї МТ.
2. Записати програму в скороченому табличному представленію.
3. Записати протокол роботи програми по переробці вхідного слова 
, якщо машина в початковому стані розпізнає третій починаючи зліва символ вхідного слова 
.
4. Визначити в яке слово переробляє МТ слово 
, якщо в початковому стані каретка вказує на перший зліва символ слова, що переробляється.
5. Визначити часову, місткісну та програмну складності МТ для попереднього завдання 4.
СПИСОК ЛІТЕРАТУРИ
1. Ершов, С.С. Элементы теории алгоритмов. – Челябинск: Издательский центр ЮУрГУ, 2009. – 64 с.
2. Корухова Л.С., Шура-Бура М.Р. Введение в алгоритмы (учебное пособие для студентов 1 курса) – М., Издательский отдел факультета ВМК МГУ, 1997.
3. Марков А.А., Нагорный Н.М. Теория алгорифмов. – М., ФАЗИС, 1996.
4, Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач. – М.: МГУ, 2006. – 47 с.
ЗМІСТ
1. Мета роботи……………………………………..………………………………………...…3
2. Теоретичні відомості..........….………………………………………………………….…. .3
2.1. Поняття алгоритму….………………………………………………………...….…. .3
2.2. Машина Тьюрінга….……………………………………………………….....….…. .3
2.3. Структура машини Тьюрінга…………………………………………………....…. .4
2.4. Такт роботи машини Тьюрін………………………………………………….....…. .5
2.5. Програма для машини Тьюрінга ……………………………………………......…. .5
2.6. Правила виконання програми ………………………………………………......…. .6
2.7. Приклади створення програм для МТ …………………………………….........…. .7
2.8. Емулятор машини Тьюрінга ………………………………………………..….…. .15
2.9. Дослідження ефективності машин Тьюрінга ………………………………....…. .17
3. Порядок виконання роботи..............………………………………………..……..…….....17
4. Завдання на лабораторну роботу ....………………………………………..……………...18
4.1. Вибір варіанта індивідуального завдання ……………………………..….....…...18
4.2. Варіанти завдань …………………………..……..……….….………..…………......18
5. Вимоги до оформлення звіту.......................……...……..………………………..………. 19
6. Контрольні завдання................………..……………………………………………...……. 19
Список літератури ………...……….....................…………………………………………..20
Навчальне видання
Методичні вказівки
до лабораторної роботи
" Програмування машин Тьюрінга"
з дисципліни
“ Алгоритми та методи обчислень "
для підготовки студентів напряму
6.050102 “Комп’ютерна інженерія”
Укладач Т.А.Матвейчук, ст. викладач каф.ЕОМ
Редактор
Комп’ютерне складання
Підписано до друку 2010 р.
Формат 70 х 100 1/16. Папір офсетний.
Друк на різографі. Умовн. друк. арк. ...... Обл.-вид. арк. ......
Наклад ..... прим. Зам.
Поліграфічний центр
Видавництва Національного університету “Львівська політехніка”
вул. Колесси, 2, 79000, Львів
Дата добавления: 2018-05-13; просмотров: 1212; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!