Дослідження ефективності машин Тьюрінга

Будемо оцінювати ефективність роботи МТ з точки зору часової (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 (так) або порожнє слово (ні).