Перевіримо цей алгоритм на томуж вхідному слові bbаbа :

Приклад 8 (використання декількох спецзнаків)

А={а, b}. Подвоїти слово Р, тобто приписати до P (ліворуч або справа) його копію. Наприклад: abb → abbabb

Рішення.

НАМ:

Тут формули (1) -(3) "переганяють" зірочку в кінець вхідного слова і замінюють її на символ =. Формул (4) -(7) переганяють символ A в кінець слова, після чого замінюють на а. Формули (8) -(11) роблять те ж саме з B і b. Формули (12 і (13) "вводять в гру" символи A і B, відповідні тому символу вхідного слова, який має бути скопійований наступним. Формула (14) застосовується тільки тоді, коли праворуч від # немає ні а, ні b, тобто коли повністю проглянуто усе вхідне слово. І, нарешті, формула (15) вводить відразу два спецзнаки # і *.

Перевіримо цей алгоритм на двох вхідних словах - на порожньому і на аbb:

Інше рішення

Приведемо ще одне рішення задачі подвоєння слова, в якому пропонується виконати наступні дії. (Перевірити роботу на 2-х словах)

Індивідуальні завдання.

Приклад оформлення титульної сторінки (додаток 1).

Зміст звіту.

Прочитати теоретичні відомості, виконати де вказано перевірку роботи НАМ (переписати умову задачі, НАМ, навести перевірку роботи на 2-х словах).

Виберіть індивідуальне завдання відповідно списку журнала академічної групи.

1) Теоретичне питання, відповідь 1 - 3 ст. А1

Зауваження до 2) завдання.

1. У завданнях розглядаються тільки цілі не негативні числа, якщо не сказано інше.

2. Під "одиничною" системою числення розуміється запис не негативного цілого числа за допомогою паличок - має бути виписано стільки паличок, яка величина числа; наприклад: 2 → | | , 5 → | | | | | , 0 → <порожнє слово>.

1. 1) Проблема алгоритмічної розв’язності в математиці.

2) A={ | }. Вважаючи слово P записом числа в одиничній системі числення, отримати залишок від ділення цього числа на 2, тобто отримати слово з однієї палички, якщо число непарне, або порожнє слово, якщо число парне.

2. 1) Засновники теорії алгоритмів - Кліні, Черч.

2)A={a, b, c}. Визначити, чи входить символ a в слово P. Відповідь (вихідне слово): слово a, якщо входить, або порожнє слово, якщо не входить.

3. 1) Основні визначення і теореми теорії рекурсивних функцій

2)A={a, b}. Якщо в слово P входить більше символів a, ніж символів b, то як відповідь видати слово з одного символу a, якщо в P рівна кількість a і b, то як відповідь видати порожнє слово, а інакше видати відповідь b.

4. 1) Проблеми обчислюваності в математичній логіці. Машина Поста. Машина Тюринга.

2)A={0, 1, 2, 3}. Перетворити слово P так, щоб спочатку йшли усі парні цифри (0 і 2), а потім - усі непарні.

5. 1) Нормальні алгоритми Маркова і асоціативні числення в дослідженнях по штучному інтелекту.

2)A={a, b, c}. Перетворити слово P так, щоб спочатку йшли усі символи a, потім - усі символи b і у кінці - усі символи c.

6. 1) Неформальні аксіоматичні теорії.

2)A={a, b, c}. Визначити, із скількох різних символів складено слово P; відповідь отримати в одиничній системі числення (наприклад: acaac → | | ).

7. 1) Застосування логіки предикатів до логіко-математичної практики та до формалізованого числення предикатів

2)А={а, b}. Приписати справа до слова Р стільки паличок, скільки усього символів входить в Р (наприклад: bаbb → bаbb | | | | ).

8. 1) Формальні аксіоматичні теорії

2)А={а, b, c}. Видалити із слова Р третє входження символу а, якщо такий є.

9. 1) Нерозв'язні алгоритмічні проблеми

2)А={а, b, c}. Залишити в слові Р тільки перше входження символу а, якщо такий є.

10. 1) Властивості аксіоматичних теорій

2)А={а, b, c}. У непорожньому слові Р залишити тільки останній символ.

11. 1) Засновники теорії алгоритмів - Кліні, Черч.

А={0,1}. Вважаючи непорожнє слово Р записом двійкового числа, визначити, чи являється це число ступенем 2 (1, 2, 4, ..). Відповідь: слово 1, якщо являється, або слово 0 інакше.

12. 1) Криптографічні алгоритми шифрування.

2)А={0,1,2,3}. Вважаючи непорожнє слово Р записом числа в четвірковій системі, отримати залишок від ділення цього числа на 4.

13. 1) Навести опис Алгоритма Меркле–Хелмана.

2)А={0,1}. Вважаючи непорожнє слово Р записом двійкового числа, отримати це ж число, але в четверичній системі. (Зауваження: врахувати, що в двійковому числі може бути непарна кількість цифр).

14. 1) Нерозв'язні алгоритмічні проблеми

2)А={0,1,2}. Вважаючи непорожнє слово Р записом трійкового числа, збільшити це число на 1.

15. 1) Навести опис алгоритма RSA

2)А={0,1,2}. Вважаючи непорожнє слово Р записом позитивного трійкового числа, зменшити це число на 1.

16. 1) Властивості аксіоматичних теорій

2)А={ | }. Вважаючи слово Р записом числа в одиничній системі числення, отримати запис цього числа в трійковій системі. (Рекомендація: слід в циклі видаляти з "одиничного" числа по паличці і кожного разу додавати 1 до трійкового числа, яке спочатку покласти рівним 0).

17. 1) Основні визначення і теореми теорії рекурсивних функцій

2)А={0, 1, 2}. Вважаючи непорожнє слово Р записом числа в трійковій системі, отримати запис цього числа в одиничній системі.

18. 1) Криптографічні алгоритми шифруванн.

2)А={а, b, c}. Визначити, чи входить перший символ непорожнього слова Р ще раз в це слово. Відповідь: слово а, якщо входить, або порожнє слово інакше.

19. 1) Навести опис алгоритма Меркле–Хеллмана.

2)А={а, b}. У непорожньому слові Р переставити перший і останній символи.

20. 1) Навести опис алгоритма RSA

2)А={а, b}. Якщо в непорожньому слові Р співпадають перший і останній символи, то видалити обидва ці символи, а інакше слово не міняти.

21. 1) Застосування логіки предикатів до логіко-математичної практики і формалізованого числення предикатів

2)А={а, b}. Визначити, чи являється слово Р паліндромом (перевертнем, симетричним словом). Відповідь: слово а, якщо являється, або порожнє слово інакше.

22. 1) Нормальні алгоритми Маркова і асоціативні числення в дослідженнях по штучному інтелекту.

2)А={ | }. Вважаючи слово Р записом числа в одиничній системі, визначити, чи являється це число ступенем 3 (1, 3, 9, 27, ..). Відповідь: порожнє слово, якщо являється, або слово з однієї палички інакше.

23. 1) Проблеми обчислюваності в математичній логіці. Машина Поста.

2)А={а, b, c}. Видалити із слова Р друге входження символу а, якщо такий є.

24. 1) Нерозв'язні алгоритмічні проблеми

2)А={а, b}. Перевернути слово Р (наприклад: аbb → bbа).

(25 - 28) Нехай слово Р має наступний вигляд:

де - один із знаків +, -, х, /, зліва від якого вказано n паличок, а справа - m паличок. Реалізувати відповідну операцію в одиничній системі числення (як відповідь видати слово, вказане праворуч від стрілки):

Варіант 25. 1) Основні визначення і теореми теорії рекурсивних функцій

2) додавання:

Варіант 26. 1) Засновники теорії алгоритмів - Кліні, Черч.

2) віднімання:

Варіант 27. 1) Формальні аксіоматичні теорії

2) множення:

Варіант 28. 1) Машини Тюринга і сучасні ЕОМ.

2) ділення: