Онлайн-тест по информатике для 11 класса «Теория алгоритмов

Вопрос 1

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

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

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

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

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

Вопрос 2

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

cbc;

ccbcbbc;

cbacba;

cbabc.

Вопрос 3

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

ccb;

cab;

cbc;

bcaab.

Вопрос 4

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

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

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

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

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

Вопрос 5

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

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

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

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

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

Вопрос 6

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

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

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

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

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

Вопрос 7

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

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

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

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

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

Вопрос 8

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

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

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

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

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

Вопрос 9

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

2

4

6

8

Вопрос 10

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

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

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

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

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

Пройти тест «Теория алгоритмов — Вариант 2» по информатике

Вам помог этот тест?