Теория алгоритмов. Тест 2 МЭСИ без ответов

1. В алгоритмах Маркова дана система подстановок в алфавите A={a, b, c}: cb - abc; bac - ac; cab - b. Преобразуйте с помощью этой системы слово bcabacab:

 

2. В алгоритмах Маркова дана система подстановок в алфавите А = {а, b, с}: cb — abс; bac — ac; саb — b. Преобразуйте с помощью этой системы слово bcabacab:

 

3. В алгоритмах Маркова дана система подстановок в алфавите А = {а, Ь, с}: cb — abc, Ьас — ас, cab — Ь. Преобразуйте с помощью этой системы слово bcabacab:

 

4. В алгоритмах Маркова дана система подстановок в алфавите Л = {а, Ь, с}: abc — с, ba — cb, ca — ab. Преобразуйте с помощью этой системы слово bacaabc:

 

5. В алгоритмах Маркова дана система подстановок в алфавите Л={a,b,c}: abc - c; ba - cb; ca - ab. Преобразуйте с помощью этой системы слово bacaabc:

 

6. В алгоритме Маркова ассоциативным исчислением называется:

 

7. В алгоритме Маркова ассоциативным исчислением называется:

 

8. В алгоритме Маркова дана цепочка Р Р, Р2 ... Рк. Если слова Р,, Р2, ..., Рк_, смежные и цепочка существует и в обратную сторону, то слова Р\лРк называют:

 

9. В алгоритме Маркова дана цепочка Р Р, Р2 ... Р„. Если слова P1f Р2 Рк_! смежные, то цепочка называется:

 

10. В алгоритме Маркова дана цепочка Р Р1, Р2,..., Рn. Если слова Р1, Р2,..., Рn смежные, то цепочка называется:

 

11. В алгоритме Меркова дана цепочка Р Р1, Р2,...Рк. Если слова Р1, Р2,...,Рк смежные и цепочка существует и в обратную сторону, то слова Р1 и Рк называют:

 

12. В ассоциативном счислении два слова называются смежными:

 

13. В машине Поста некорректным алгоритм будет в следующем случае:

 

14. В машине Поста некорректным алгоритм будет в следующем случае:

 

15. В машине Поста останов будет результативным:

 

16. В машине Поста останов будет результативным:

 

17. В машине Тьюринга предписание L для лентопротяжного механизма означает:

 

18. В машине Тьюринга предписание L для лентопротяжного механизма означает:

 

19. В машине Тьюринга предписание R для лентопротяжного механизма означает:

 

20. В машине Тьюринга предписание R для лентопротяжного механизма означает:

 

21. В машине Тьюринга предписание S (H) для лентопротяжного механизма означает:

 

22. В машине Тьюринга предписание S для лентопротяжного механизма означает:

 

23. В машине Тьюринга рабочий алфавит:

 

24. В машине Тьюринга состояниями являются:

 

25. Команда машины Поста имеет структуру nKm, где:

 

26. Команда машины Поста имеет структуру п Km, где:

 

27. Рекурсия в алгоритме будет косвенной, когда:

 

28. Рекурсия в алгоритме будет прямой, когда:

 

29. Свойство алгоритма записываться в виде только тех команд, которые находятся в Системе Команд Исполнителя, называется:

 

30. Свойство алгоритма записываться в виде упорядоченной совокупности отделенных друг от друга предписаний (директив):