Тест "Нормальные алгоритмы Маркова"
тест на тему
Тест по УД "Теория алгоритмов" "Нормальные алгоритмы Маркова"
Скачать:
Вложение | Размер |
---|---|
test_markov.docx | 34.56 КБ |
Предварительный просмотр:
Тест «Нормальные алгоритмы Маркова» 1 вариант
- Результат марковской подстановки 21 3 в слово 521421
a) 52143 b) 5343
c) 531421 d) 533433
- Марковская подстановка 21 3 не применима к словам
a) 521421 b) 5241
c) 21 d)12
- Результат марковской подстановки 21 в слово 521421
a) 54 b)21521421
c) 5421 d)52142121
- Слово 21 является подсловом слова
a) 521421 b) 5241
c) 521 d) 2541
- Процесс работы нормального алгоритма считается завершенным, если на данном шаге
- Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
- Применена заключительная формула подстановки
- Ни одна подстановка схемы не подходит
- Понятно, что процесс подстановок не сможет остановиться
- Нормальный алгоритм не применим к исходным данным, если на данном шаге
- Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
- Применена заключительная формула подстановки
- Ни одна подстановка схемы не подходит
- Понятно, что процесс подстановок не сможет остановиться
- Каким будет результат применения нормального алгоритма ab ® L, ba ® ab к слову R = bbaabab
- Результат применения нормального алгоритма ab ® bd, db ® ba, bba ® abb, c ® L к слову R = abbc
- Алгоритм не применим к этому слову
- bb
- aa
- cc
- В алгоритме Маркова ассоциативным исчислением называется:
- совокупность всех слов в данном алфавите;
- совокупность всех допустимых систем подстановок;
- совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;
- когда все слова в алфавите являются смежными.
- В ассоциативном счислении два слова называются смежными:
- если одно из них может быть преобразовано в другое применением подстановок;
- если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;
- когда существует цепочка от одного слова к другому и обратно;
- когда они дедуктивны.
- В алгоритмах Маркова дана система подстановок в алфавите
A = {а, b, с}: abc — с; ba — cb; ca — ab
Преобразуйте с помощью этой системы слово bacaabc
- В алгоритмах Маркова дана система подстановок в алфавите
А= {а, b, с}:cb — abc; bас — ас; cab — b
Преобразуйте с помощью этой системы слово bcabacab
- Способ композиции нормальных алгоритмов будет суперпозицией, если:
- выходное слово первого алгоритма является входным для второго;
- существует алгоритм С, преобразующий любое слово р, содержащееся I пересечении областей определения алгоритмов А и В;
- алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;
- существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
- Способ композиции нормальных алгоритмов будет объединением, если:
- выходное слово первого алгоритма является входным для второго;
- существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
- алгоритм В будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) — A(p), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;
- существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
- Способ композиции нормальных алгоритмов будет разветвлением, если:
- выходное слово первого алгоритма является входным для второго;
- существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
- алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) – В(р), если С(р) = е, где е — пустая строка;
- существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
- Способ композиции нормальных алгоритмов будет итерацией, если:
- выходное слово первого алгоритма является входным для второго;
- существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
- алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В к С, а для любого слова р из этого пересечения D(p)= A(p), если С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка;
- существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
- Дать подробное решение и описание алгоритма решения задачи:
- A={f,h,p} в слове P заменить все пары ph на f
- A={a,b,c} Приписать слово bac слева к слову P
Тест «Нормальные алгоритмы Маркова» 2 вариант
- Каким будет результат применения нормального алгоритма ab ® L, ba ® ab к слову R = bbaabab
- Слово 21 является подсловом слова
a) 521421 b) 5241
c) 521 d) 2541
- Нормальный алгоритм не применим к исходным данным, если на данном шаге
- Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
- Применена заключительная формула подстановки
- Ни одна подстановка схемы не подходит
- Понятно, что процесс подстановок не сможет остановиться
- В алгоритмах Маркова дана система подстановок в алфавите
А= {а, b, с}:cb — abc; bас — ас; cab — b
Преобразуйте с помощью этой системы слово bcabacab
- Способ композиции нормальных алгоритмов будет итерацией, если:
- выходное слово первого алгоритма является входным для второго;
- существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
- алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В к С, а для любого слова р из этого пересечения D(p)= A(p), если С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка;
- существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
- Способ композиции нормальных алгоритмов будет объединением, если:
- выходное слово первого алгоритма является входным для второго;
- существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
- алгоритм В будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) — A(p), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;
- существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
- Способ композиции нормальных алгоритмов будет суперпозицией, если:
- выходное слово первого алгоритма является входным для второго;
- существует алгоритм С, преобразующий любое слово р, содержащееся I пересечении областей определения алгоритмов А и В;
- алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;
- существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
- Способ композиции нормальных алгоритмов будет разветвлением, если:
- выходное слово первого алгоритма является входным для второго;
- существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
- алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) – В(р), если С(р) = е, где е — пустая строка;
- существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
- Процесс работы нормального алгоритма считается завершенным, если на данном шаге
- Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
- Применена заключительная формула подстановки
- Ни одна подстановка схемы не подходит
- Понятно, что процесс подстановок не сможет остановиться
- Результат марковской подстановки 21 3 в слово 521421
a) 52143 b) 5343
c) 531421 d) 533433
- Результат применения нормального алгоритма ab ® bd, db ® ba, bba ® abb, c ® L к слову R = abbc
- Алгоритм не применим к этому слову
- bb
- aa
- cc
- В алгоритмах Маркова дана система подстановок в алфавите
A = {а, b, с}: abc — с; ba — cb; ca — ab
Преобразуйте с помощью этой системы слово bacaabc
- алгоритме Маркова ассоциативным исчислением называется:
- совокупность всех слов в данном алфавите;
- совокупность всех допустимых систем подстановок;
- совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;
- когда все слова в алфавите являются смежными.
- В ассоциативном счислении два слова называются смежными:
- если одно из них может быть преобразовано в другое применением подстановок;
- если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;
- когда существует цепочка от одного слова к другому и обратно;
- когда они дедуктивны.
- Марковская подстановка 21 3 не применима к словам
a) 521421 b) 5241
c) 21 d)12
- Результат марковской подстановки 21 в слово 521421
a) 54 b)21521421
c) 5421 d)52142121
17. Дать подробное решение и описание алгоритма решения задачи:
- A={a,b,c} в слове P заменить все пары ac на b
- A={p,f} Приписать слово fpf слева к слову S
По теме: методические разработки, презентации и конспекты
Презентация "Свойства алгоритмов"
В презентации рассматриваются основные свойства алгоритмов - дискретность, понятность, точность, результативность, массовость...
Основные алгоритмические конструкции. Вспомогательные алгоритмы
Данная разработка способствует:1) сформировать представление об алгоритме как особой форме записи;2) повторить основные алгоритмические конс...
тема "Понятие сложности алгоритма" курс "Теория алгоритмов"
При использовании алгоритмов для решения практических задач мы сталкиваемся с проблемой рационального выбора алгоритма решения задачи. Решение проблемы выбора связано с построением системы сравнительн...
Нормальные алгоритмы Маркова
Для дисциплины "Теория алгоритмов"...
Презентация на тему: В чем смысл эквивалентности машин Тьюринга и Поста и нормальных алгоритмов Маркова?
Тьюринг высказал предположение, что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной в предложенной им модели вычислений. Это предположение известно как тез...
Презентация по теме: "Алгоритмы. Свойства алгоритмов."
Презентация по теме: "Алгоритмы. Свойства алгоритмов."...
Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма
Конспект темы по информатике для 1 курсов. Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритмаСамостоятельная работа после изучения темы...