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

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) Сложение двух чисел в унарной системе счисления (например, 1111+111).

b) Дано слово из знаков а и b произвольной длины (например, abb-bab), причем, заранее не известно, какой знак первый (а или b). Необходимо первый знак переместить в конец слова.

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) преобразование док→тоска. Применить его к словам ток, дот.

Читайте также:

Пример 7.5

Исполнитель алгоритма

Глава 4. Представление и обработка чисел в компьютере

Глава 3. Кодирование символьной информации

Пример 9.5