Вс. Апр 14th, 2024

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

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

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

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

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

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

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. Отыскать значение функции S2(S1,S1) (т.е. итог подстановки функции конкретного следования самой в себя).

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

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

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

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

От content

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *