Тест: Теория алгоритмов №4 - Информатика 11 класс

Теория алгоритмов №4

Информатика 11 класс | Автор: Гайнанова Эльвина Назимовна | ID: 9293 | Дата: 21.3.2017

Помещать страницу в закладки могут только зарегистрированные пользователи
Зарегистрироваться

Вопрос № 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

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

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