Контрольные вопросы и задания

1. С чем связана необходимость четкого определения понятия «алгоритм»?

2. Почему приведенное в п.7.1. определение метода названо «нестрогим»?

3. Можно ли считать методом: (а) правила правописания; (b) законы физики; (с) математические формулы; (d) статьи уголовного кодекса. Ответы докажите.

4. На какие характеристики метода окажет воздействие выбор того либо другого исполнителя для решения одной и той же задачки?

5. Можно ли считать исполнителем метода: (а) человека, ведущего запись текста под диктовку, (b) компьютер; (с) компьютерную программку, (d) дрессированное животное. Ответы докажите.

6. Обосновать, что примитивно-рекурсивными являются функции: (а) х-у; (b) x^y; (с) п!

7. Каким образом связаны характеристики метода и особенности устройства алгоритмической машины?

8. Какие деяния алгоритмической машины следует считать простыми?

9. Решите последующие задачки, используя алгоритмическую машину Поста; во всех задачках в начальном состоянии обозревается последняя левая ячейка:

• a) на ленте находятся два числа N и Q, разбитые одной пустой ячейкой. Напишите программку нахождения суммы N+Q.
• b) решите предшествующую задачку при условии, что начальные числа разбиты произвольным числом пустых ячеек.
• c) на ленте находятся два числа N и Q (N > Q), разбитые одной пустой ячейкой. Напишите программку нахождения разности N — Q.
• d) на ленте N меток. Выстроить такое же количество меток справа от имеющихся через одну пустую.
• e) на ленте находятся два числа N и Q, разбитые одной пустой ячейкой. Напишите программку нахождения произведения N — Q.

10. На каком-либо языке программирования высочайшего уровня разработайте программку эмуляции работы машины Поста.

11. Решите последующие задачки, используя алгоритмическую машину Тьюринга; во всех задачках в начальном состоянии обозревается последняя левая ячейка:

• a) Сложение 2-ух чисел в унарной системе счисления (к примеру, 1111+111).
• b) Дано слово из символов а и b случайной длины (к примеру, abb-bab), при этом, заблаговременно не понятно, какой символ 1-ый (а либо b). Нужно 1-ый символ переместить в конец слова.
• c) Добавление 1 к числу в случайной данной системе счисления.
• d) Перевод целого числа из одной системы счисления в другую.

12. На каком-либо языке программирования высочайшего уровня разработайте программку эмуляции работы машины Тьюринга.

13. Отыскать значение функции S²(S¹,S¹) (т.е. итог подстановки функции конкретного следования самой в себя).

14. Обычный метод имеет алфавит А = {а, b, с} и систему подстановок: ас→аа, aab→bc, bc→cab. Отыскать итог внедрения метода к начальным словам: (1) cbcbba; (2) abccba; (3) accca.

15. На каком-либо языке программирования высочайшего уровня разработайте программку, обеспечивающую задание и выполнение обычных алгоритмов Маркова.

16. Разработайте обычные методы, обеспечивающие:

• a) выполнение операции вычитания единицы из числа в троичной системе счисления;
• b) выполнение операции прибавления единицы к числу в двоичной системе счисления;
• c) инверсию числа в двоичном алфавите;
• d) преобразование док→тоска. Применить его к словам ток, дот.