Теория алгоритмов.doc
Оценка 4.7

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

Оценка 4.7
doc
13.05.2020
Теория алгоритмов.doc
Теория алгоритмов.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)        А = {а40 О, ЬА0 1, с40 2, ..., w40 ?};

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

3)       Л = {а40 0, а41 0, о42 0, ..., а41 0};

4)    Л = {а,0 0, а20 0, о3о 0, ■•■, «ад 0}.

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

                1){a40 0, a40 1,a402, …,a40 t};

                2) {q41, q42, q43, …, q4s};

          3){q41, q42, q43, …, q4s, a40 0, a40 1, a40 2,…,a40 t};   

           4){q40, q41, q42, …, q4s}.

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.   В алгоритме Маркова дана цепочка Р Р, Р2 ... Р„. Если слова P1f Р2..................................... Рк_!

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

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

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

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

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

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

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) существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

 

39

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

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

40

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

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

41

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

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

42

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

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

43

Свойство алгоритма обеспечения решения не одной задачи, а целого класса  задач этого типа; 1) понятность; 2) детерминированность; 3) дискретность; 4) массовость.

44

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

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

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

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

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

45

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

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

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

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

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

46

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

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

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

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

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

47

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

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

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

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

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

48

Сколько существует команд у машины Поста: 1) 2; 2) 4; 3) 6; 4) 8?

49

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

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

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

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

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

50

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

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

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

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

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

51

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

1) А = {a40 0, b40 1, c40 2, … , w40 t};                  2) А = {a40 0, a40 1, a40 2, … , a40 t};

3) А = {a40 0, a41 0, a42 0, … , a4t 0};                   4) А = {a10 0, a20 0, a30 0, … , a90 0}

52

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

1){a40 0, a40 1,a402, …,a40 t};                                      2) {q41, q42, q43, …, q4s};

3){q41, q42, q43, …, q4s, a40 0, a40 1, a40 2,…,a40 t};     4){q40, q41, q42, …, q4s}.

53

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

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

54

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

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

55

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

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

56

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

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

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

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

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

57

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

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

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

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

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

58

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

1)     ассоциативной;     2) эквивалентной;   3) индуктивной;    4)   дедуктивной.

59

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

1)    ассоциативными;   2)  эквивалентными;   3)  индуктивными;   4)  дедуктивными.

60

В алгоритмах Маркова дана система подстановок в алфавите А = {а, b, с}:

abc — с;                 bacb;       са — аb.

Преобразуйте с помощью этой системы слово bacaabc:

1) cbc;             2) ccbcbbc;                3) cbacba;                4) cbabc.

61

В алгоритмах Маркова дана система подстановок в алфавите А = {а, b, с}:

cb — abс;                     bac — ac;                        саb — b.

Преобразуйте с помощью этой системы слово bcabacab:

1) ccb; 2) cab; 3) cbc; 4) bcaab.

62

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

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

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

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

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

63

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

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

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

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

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

64

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

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

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

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

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

65

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

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

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

3)         алгоритм D будет суперпозицией трех алгоритмов A B C, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения
D(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.   В алгоритме Маркова дана цепочка Р Р, Р2 ... Р„. Если слова P1f Р2..................................... Рк_!

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

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

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

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

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

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

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) массовость.

 

 

 

Ключ к тесту

 

 

 

 

1

2

3

4

1

2

3

4

1

2

3

4

1

 

X

 

 

14

X

 

 

 

27

X

 

 

 

2

 

 

X

 

15

 

 

 

X

28

 

 

X

 

3

X

 

 

 

16

 

 

 

X

29

 

 

X

 

4

 

 

 

X

17

 

X

 

 

30

 

X

 

 

5

X

 

 

 

18

 

 

X

 

31

 

 

 

X

6

 

 

X

 

19

X

 

 

 

32

 

X

 

 

7

 

 

X

 

20

 

X

 

 

33

 

X

 

 

8

 

X

 

 

21

 

 

X

 

34

 

 

 

X

9

X

 

 

 

22

 

 

 

X

35

X

 

 

 

10

 

 

X

 

23

 

 

X

 

36

 

X

 

 

11

 

 

 

X

24

 

 

X

 

37

 

 

X

 

12

 

 

X

 

25

 

 

 

X

38

 

 

 

X

13

X

 

 

 

26

 

X

 

 

39

 

 

Х

 

 

1

2

3

4

1

2

3

4

1

2

3

4

40

 

Х

 

 

60

Х

 

 

 

80

 

Х

 

 

41

 

 

 

Х

61

 

Х

 

 

81

 

 

Х

 

42

 

Х

 

 

62

 

Х

 

 

82

 

 

 

Х

43

 

 

 

Х

63

 

 

Х

 

83

 

Х

 

 

44

 

Х

 

 

64

 

 

 

Х

84

Х

 

 

 

45

 

 

Х

 

65

 

 

Х

 

85

 

 

Х

 

46

Х

 

 

 

66

 

Х

 

 

86

 

 

Х

 

47

 

Х

 

 

67

 

 

Х

 

87

Х

 

 

 

48

 

 

Х

 

68

 

 

 

Х

88

 

 

 

Х

49

 

 

 

Х

69

 

 

Х

 

89

 

Х

 

 

50

Х

 

 

 

70

 

Х

 

 

90

 

Х

 

 

51

 

 

Х

 

71

Х

 

 

 

91

 

 

 

Х

52

 

 

 

Х

72

 

 

Х

 

92

Х

 

 

 

53

 

Х

 

 

73

 

 

Х

 

93

 

Х

 

 

54

Х

 

 

 

74

 

 

 

Х

94

 

 

Х

 

55

 

 

Х

 

75

 

 

 

Х

95

 

 

 

Х

56

 

 

Х

 

76

 

Х

 

 

96

 

 

Х

 

57

 

 

Х

 

77

 

Х

 

 

97

 

Х

 

 

58

 

 

 

Х

78

 

 

 

Х

98

Х

 

 

 

59

 

 

 

Х

79

 

Х

 

 

99

 

 

 

Х

 

 

 

 

 

 

 

 

 

 

100

 

 

 

Х

 


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

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

На рисунке представлена часть блок-схемы

На рисунке представлена часть блок-схемы

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

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

В алгоритме Маркова дана цепочка

В алгоритме Маркова дана цепочка

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

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

А = {a 40 0, b 40 1, c 40 2, … , w 40 t}; 2)

А = {a 40 0, b 40 1, c 40 2, … , w 40 t}; 2)

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

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

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

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

R bcaab 7 9. Задание Вобери правильный ответ

R bcaab 7 9. Задание Вобери правильный ответ

А до тех пор, пока не получится слово, преобразуемое алгоритмом

А до тех пор, пока не получится слово, преобразуемое алгоритмом

В алгоритмах Маркова дана система подстановок в алфавите

В алгоритмах Маркова дана система подстановок в алфавите

С, являющийся суперпозицией алгоритмов

С, являющийся суперпозицией алгоритмов

Х 69 Х 89

Х 69 Х 89
Скачать файл