Теория алгоритмов.doc

1. Как называется графическое представление алгоритма: 1) последовательность формул; 2) блок-схема; 3) таблица; 4) словесное описание?

2. На рисунке представлена часть блок-схемы. Как называется такая вершина:

1) предикатная; 2) объединяющая; 3) функциональная; 4) сквозная?

3. На рисунке представлена часть блок-схемы. Как называется такая вершина:

1)          предикатная;

2)        объединяющая;

3)         функциональная;

4)         сквозная?

4.  На рисунке представлена часть блок-схемы. Как она называется:

1)         альтернатива;

2)       итерация;

3)       вывод данных;

4)       следование?

5.  На рисунке представлена часть блок-схем Как она называется:

1)          альтернатива;

2)         композиция;

3)         цикл с предусловием;

4)        итерация?

6.  На рисунке представлена часть блок-схемы.
Как она называется:

1) альтернатива;

2)         композиция;

3)         цикл с предусловием;

4)         цикл с постусловием?

7.  На рисунке представлена часть блок-схемы.Как она называется:

1)          альтернатива;

2)        композиция;

3)        цикл с постусловием;

4)         цикл с предусловием?

8.  Как называется конструкция блок-схемы, изображенная на рисунке:

1) выполнение операций;

2)       начало-конец алгоритма;

3)       вызов вспомогательного алгоритма;

4)       ввод/вывод данных?

9.  Как называется конструкция блок-схемы, изображенная на рисунке:

1) выполнение операций;

2)      начало-конец алгоритма;

3)       вызов вспомогательного алгоритма;

4)       ввод/вывод данных?

10.  Как называется конструкция блок-схемы, изоб­
раженная на рисунке:

1) выполнение операций;

2)       начало-конец алгоритма;

3)       вызов вспомогательного алгоритма;

4)       ввод/вывод данных?

11.  Как называется конструкция блок-схемы, изображенная на рисунке:

1) выполнение операций;

2)       начало-конец алгоритма;

3)       вызов вспомогательного алгоритма;

4)       ввод/вывод данных?

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

1) понятность; 2) определенность; 3) дискретность; 4) массовость.

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

1) понятность; 2) определенность; 3) дискретность; 4) результативность.

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

1) дискретность; 2) понятность3) определенность; 4) результативность

15.               Свойство алгоритма, что при точном исполнении всех предписаний процессдолжен прекратиться за конечное число шагов с определенным ответом на поставленную задачу:

1) понятность; 2) детерминированность; 3) дискретность; 4) результативность.

16.   Свойство алгоритма обеспечения решения не одной задачи, а целого класса
задач этого типа:

1) понятность; 2) определенность; 3) дискретность; 4) массовость.

17.   Что называют служебными словами в алгоритмическом языке:

1) слова, употребляемые для записи команд, входящих в СКИ;

2)       слова, смысл и способ употребления которых задан раз и навсегда;

3)        вспомогательные алгоритмы, которые используются в составе других алгоритмов;

4)       константы с постоянным значением?

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

1)      рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение;

2)      порядок следования команд определяется в зависимости от результатов проверки некоторых условий;

3)      команда обращения алгоритма к самому себе находится в самом алгоритме;

4)     один вызов алгоритма прямо следует за другим.

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

1)     порядок следования команд определяется в зависимости от результатов проверки некоторых условий;

2)      команда обращения алгоритма к самому себе находится в самом алгоритме;

3)     один вызов алгоритма прямо следует за другим.

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

1) п — действие, выполняемое головкой; К— номер следующей команды, подлежащей выполнению; т — порядковый номер команды;

2)      п — порядковый номер команды; К — действие, выполняемое головкой; т — номер следующей команды, подлежащей выполнению;

3)      п — порядковый номер команды; К— номер следующей команды, подлежащей выполнению; т — действие, выполняемое головкой;

4)      п — порядковый номер команды; К — действие, выполняемое головкой; т — номер клетки, с которой данную команду надо произвести.

21.   Сколько существует команд у машины Поста:

1) 2; 2) 4; 3) 6; 4) 8?

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

1)        при выполнении недопустимой команды;

2)       если машина не останавливается никогда;

3)      если результат выполнения программы такой, какой и ожидался;

4)      по команде «Стоп».

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

1)        при выполнении недопустимой команды;

2)       результат выполнения программы такой, какой и ожидался;

3)        машина не останавливается никогда;

4)    по команде «Стоп».

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

1)        А = {а₄₀ О, Ь_А0 1, с₄₀ 2, ..., w₄₀ ?};

2)   Л = {а₄₀ 0, а₄₀ 1, а₄₀ 2, ..., а₄₀ ?};

3)       Л = {а₄₀ 0, а₄₁ 0, о₄₂ 0, ..., а₄₁ 0};

4)    Л = {а,₀ 0, а₂₀ 0, о₃о 0, ■•■, «ад 0}.

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

                1){a₄₀ 0, a₄₀ 1,a₄₀2, …,a₄₀ t};

                2) {q₄₁, q₄₂, q₄₃, …, q_4s};

          3){q₄₁, q₄₂, q₄₃, …, q_4s, a₄₀ 0, a₄₀ 1, a₄₀ 2,…,a₄₀ t};   

           4){q₄₀, q₄₁, q₄₂, …, q_4s}.

26. В машине Тьюринга предписание L для лентопротяжного механизма означает:1) переместить ленту вправо; 2) переместить ленту влево;

3)  остановить машину; 4) занести в ячейку символ.

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

1) переместить ленту вправо; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку символ.

28. В машине Тьюринга предписание S для лентопротяжного механизма означает:1) переместить ленту вправо; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку символ.

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

1)       совокупность всех слов в данном алфавите;

2)      совокупность всех допустимых систем подстановок;

3)      совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;

4)      когда все слова в алфавите являются смежными.

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

1) если одно из них может быть преобразовано в другое применением подстановок;

2)     если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;

3)     когда существует цепочка от одного слова к другому и обратно;

4)    когда они дедуктивны.

31.   В алгоритме Маркова дана цепочка Р Р, Р₂ ... Р„. Если слова P_1f Р_{2.....................................} Р_к_!

смежные, то цепочка называется:

1) ассоциативной;

2)        эквивалентной;

3)        индуктивной;

4)        дедуктивной.

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

1) ассоциативными;

2)       эквивалентными;

3)       индуктивными;

4)       дедуктивными.

33. В алгоритмах Маркова дана система подстановок в алфавите Л = {а, Ь, с}:
abc — с

ba — cb

ca — ab

Преобразуйте с помощью этой системы слово bacaabc: 1) cbc; 2) ccbcbbc; 3) cbacba; 4) cbabc.

34.     В алгоритмах Маркова дана система подстановок в алфавите А = {а, Ь, с}:
cb — abc

Ьас — ас cab — Ь

Преобразуйте с помощью этой системы слово bcabacab: 1) ccb; 2) cab; 3) cbc; 4) bcaab.

35.  Способ композиции нормальных алгоритмов будет суперпозицией, если:

1) выходное слово первого алгоритма является входным для второго;

2)      существует алгоритм С, преобразующий любое слово р, содержащееся i
пересечении областей определения алгоритмов А и В;

3)      алгоритм D будет суперпозицией трех алгоритмов ABC, причем область
определения D является пересечением областей определения алгоритмов
А В и С, а для любого слова р из этого пересечения D(p) = А(р), если
С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;

4)      существует алгоритм С, являющийся суперпозицией алгоритмов А и Д
такой, что для любого входного слова р С{р) получается в результате
последовательного многократного применения алгоритма А до тех пор,
пока не получится слово, преобразуемое алгоритмом В.

36.  Способ композиции нормальных алгоритмов будет объединением, если:

1)       выходное слово первого алгоритма является входным для второго;

2)      существует алгоритм С, преобразующий любое слово р, содержащееся в
пересечении областей определения алгоритмов А и В;

3)       алгоритм В будет суперпозицией трех алгоритмов ABC, причем область
определения D является пересечением областей определения алгоритмов
А В и С, а для любого слова р из этого пересечения D(p) — A(p), если
С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;

4)      существует алгоритм С, являющийся суперпозицией алгоритмов А и Д
такой, что для любого входного слова р С(р) получается в результате
последовательного многократного применения алгоритма А до тех пор,
пока не получится слово, преобразуемое алгоритмом В.

37.  Способ композиции нормальных алгоритмов будет разветвлением, если:

1)         выходное слово первого алгоритма является входным для второго;

2)       существует алгоритм С, преобразующий любое слово р, содержащееся в
пересечении областей определения алгоритмов А и В;

3)       алгоритм D будет суперпозицией трех алгоритмов ABC, причем область
определения D является пересечением областей определения алгоритмов
А В и С, а для любого слова р из этого пересечения D(p) = А(р), если
С(р) = е, D{p) - В{р), если С(р) = е, где е — пустая строка;

4)       существует алгоритм С, являющийся суперпозицией алгоритмов А и В,
такой, что для любого входного слова р С{р) получается в результате
последовательного многократного применения алгоритма А до тех пор,
пока не получится слово, преобразуемое алгоритмом В.

38.  Способ композиции нормальных алгоритмов будет итерацией, если:

1)        выходное слово первого алгоритма является входным для второго;

2)       существует алгоритм С, преобразующий любое слово р, содержащееся в
пересечении областей определения алгоритмов А и В;

3)   алгоритм D будет суперпозицией трех алгоритмов ABC, причем область
определения D является пересечением областей определения алгоритмов
А В к С, а для любого слова р из этого пересечения D{p)= A(p), если
С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка;4) существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

66. Задание

Выбери правильный ответ

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

£  n - действие, выполняемое головкой; K - номер следующей команды, подлежащей выполнению; m - порядковый номер команды

R  n - порядковый номер команды; K - действие, выполняемое головкой;m - номер следующей команды, подлежащей выполнению

£  n - порядковый номер команды; K - номер следующей команды, подлежащей выполнению; m - действие, выполняемое головкой

£  n - порядковый номер команды; K - действие, выполняемое головкой; m - номер клетки, с которой данную команду надо произвести

67. Задание

Выбери правильный ответ

Сколько существует команд у машины Поста?

£  2

£  4

R  6

£  8

68. Задание

Выбери правильный ответ

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

£  При выполнении недопустимой команды

£  Если машина не останавливается никогда

£  Если результат выполнения программы такой, какой и ожидался

R  По команде "Стоп"

69. Задание

Выбери правильный ответ

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

£  При выполнении недопустимой команды

£  Результат выполнения программы такой, какой и ожидался

R  Машина не останавливается никогда

£  По команде "Стоп"

70. Задание

Выбери правильный ответ

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

£  Переместить ленту вправо

R  Переместить ленту влево

£  Остановить машину

£  Занести в ячейку символ

71. Задание

Выбери правильный ответ

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

R  Переместить ленту вправо

£  Переместить ленту влево

£  Остановить машину

£  Занести в ячейку символ

72. Задание

Выбери правильный ответ

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

£  Переместить ленту вправо

£  Переместить ленту влево

R  Остановить машину

£  Занести в ячейку символ

73. Задание

Выбери правильный ответ

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

£  Совокупность всех слов в данном алфавите

£  Совокупность всех допустимых подстановок

R  Совокупность всех слов в данном алфавите вместе с допустимой системой подстановок

£  Когда все слова в алфавите являются смежными

74. Задание

Выбери правильный ответ

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

£  Если одно из них может быть преобразовано в другое применением подстановок

£  Когда существует цепочка от одного слова к другому и обратно

£  Когда они дедуктивны

R  Если одно из них может быть преобразовано в другое однократным применением допустимой подстановки

75. Задание

Выбери правильный ответ

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

£  Ассоциативной

£  Эквивалентной

£  Индуктивной

R  Дедуктивной

76. Задание

Выбери правильный ответ

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

£  Ассоциативными

R  Эквивалентными

£  Индуктивными

£  Дедуктивными

77. Задание

Выбери правильный ответ

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

£  cbc

R  ccbcbbc

£  cbacba

£  cbabc

78. Задание

Выбери правильный ответ

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

£  ccb

£  cab

£  cbc

R  bcaab

79. Задание

Вобери правильный ответ

Способ композиции нормальных алгоритмов будет суперпозицией, если:

£  Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В

R  Выходное слово первого алгоритма является входным для второго

£  Алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов A B и C, а для любого слова р из этого пересечения D(p)= A(p), C(p)=e, D(p)=B(p), если C(p)=е, где е - пустая строка

£  Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

80. Задание

Выбери правильный ответ

Способ композиции нормальных алгоритмов будет объединением, если:

£  Входное слово первого алгоритма является входным для второго

R  Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В

£  Алгоритм В будет суперпозицией трех алгоритмов АВС, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(р)=А(р), C(p)=e, D(p)=B(p), если С(р)=е, где е - пустая строка

£  Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

81. Задание

Выбери правильный ответ

Способ композиции нормальных алгоритмов будет разветвлением, если:

£  Выходное слово первого алгоритма является входным для второго

£  Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В

R  Алгоритм Д будет суперпозицией трех алгоритмов АВС, причем область определения Д является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения Д(р)=А(р), если С(р)=е, Д(р)=В(р), если С(р)=е, где е - пустая строка

£  Существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

82. Задание

Выбери правильный ответ

Способ композиции нормальных алгоритмов будет итерацией, если:

£  Выходное слово первого алгоритма является входным для второго

£  Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В

£  Алгоритм Д будет суперпозицией трех алгоритмов АВС, причем область определения Д является пересечением областей определения алгоритмов А В С, а для любого слова р из этого пересечения Д(р)=А(р), если С(р)=е, Д(р)=В(р), если С(р)=е, где е - пустая строка

R  Существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

83. В машине Тьюринга предписание L для лентопротяжного механизма означает:
1) переместить ленту вправо; 2) переместить ленту влево;

3)  остановить машину; 4) занести в ячейку символ.

84. В машине Тьюринга предписание R для лентопротяжного механизма означает:
1) переместить ленту вправо; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку символ.

85. В машине Тьюринга предписание S для лентопротяжного механизма означает:
1) переместить ленту вправо; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку символ.

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

1.                совокупность всех слов в данном алфавите;

2.               совокупность всех допустимых систем подстановок;

3.               совокупность всех слов в данном алфавите вместе с допустимой системой
подстановок;

4.               когда все слова в алфавите являются смежными.

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

1.  если одно из них может быть преобразовано в другое применением подстановок;

2.               если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;

3.               когда существует цепочка от одного слова к другому и обратно;

4.              когда они дедуктивны.

88.   В алгоритме Маркова дана цепочка Р Р, Р₂ ... Р„. Если слова P_1f Р_{2.....................................} Р_к_!

смежные, то цепочка называется:

1.  ассоциативной;

2.               эквивалентной;

3.               индуктивной;

4.               дедуктивной.

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

1.  ассоциативными;

2.               эквивалентными;

3.               индуктивными;

4.               дедуктивными.

90. В алгоритмах Маркова дана система подстановок в алфавите Л = {а, Ь, с}:
abc — с

ba — cb

ca — ab

Преобразуйте с помощью этой системы слово bacaabc: 1) cbc; 2) ccbcbbc; 3) cbacba; 4) cbabc.

91.  В алгоритмах Маркова дана система подстановок в алфавите А = {а, Ь, с}:
cb — abc

Ьас — ас cab — Ь

Преобразуйте с помощью этой системы слово bcabacab: 1) ccb; 2) cab; 3) cbc; 4) bcaab.

92.  Способ композиции нормальных алгоритмов будет суперпозицией, если:

        1)выходное слово первого алгоритма является входным для второго;

    2)существует алгоритм С, преобразующий любое слово р, содержащееся пересечении областей определения алгоритмов А и В;

    3)алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;

    4)существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С{р) получается в результате
последовательного многократного применения алгоритма А до тех пор,
пока не получится слово, преобразуемое алгоритмом В.

93   Способ композиции нормальных алгоритмов будет объединением, если:

5)       выходное слово первого алгоритма является входным для второго;

6)      существует алгоритм С, преобразующий любое слово р, содержащееся в
пересечении областей определения алгоритмов А и В;

7)       алгоритм В будет суперпозицией трех алгоритмов ABC, причем область
определения D является пересечением областей определения алгоритмов
А В и С, а для любого слова р из этого пересечения D(p) — A(p), если
С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;

8)      существует алгоритм С, являющийся суперпозицией алгоритмов А и Д
такой, что для любого входного слова р С(р) получается в результате
последовательного многократного применения алгоритма А до тех пор,
пока не получится слово, преобразуемое алгоритмом В.

94.  Способ композиции нормальных алгоритмов будет разветвлением, если:

5)         выходное слово первого алгоритма является входным для второго;

6)       существует алгоритм С, преобразующий любое слово р, содержащееся в
пересечении областей определения алгоритмов А и В;

7)       алгоритм D будет суперпозицией трех алгоритмов ABC, причем область
определения D является пересечением областей определения алгоритмов
А В и С, а для любого слова р из этого пересечения D(p) = А(р), если
С(р) = е, D{p) - В{р), если С(р) = е, где е — пустая строка;

8)       существует алгоритм С, являющийся суперпозицией алгоритмов А и В,
такой, что для любого входного слова р С{р) получается в результате
последовательного многократного применения алгоритма А до тех пор,
пока не получится слово, преобразуемое алгоритмом В.

95.  Способ композиции нормальных алгоритмов будет итерацией, если:

4)        выходное слово первого алгоритма является входным для второго;

5)       существует алгоритм С, преобразующий любое слово р, содержащееся в
пересечении областей определения алгоритмов А и В;

6)       алгоритм D будет суперпозицией трех алгоритмов ABC, причем область
определения D является пересечением областей определения алгоритмов
А В к С, а для любого слова р из этого пересечения D{p)= A(p), если
С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка;

4) существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

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

1) понятность; 2) определенность; 3) дискретность; 4) массовость.

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

1) понятность; 2) определенность; 3) дискретность; 4) результативность.

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

1) понятность; 2) определенность; 3) дискретность; 4) результативность.

99.Свойство алгоритма, что при точном исполнении всех предписаний процесс
должен прекратиться за конечное число шагов с определенным ответом на поставленную задачу:

1) понятность; 2) детерминированность; 3) дискретность; 4) результативность.

100. Свойство алгоритма обеспечения решения не одной задачи, а целого класса
задач этого типа:

1) понятность; 2) определенность; 3) дискретность; 4) массовость.

Ключ к тесту