Тест "Нормальные алгоритмы Маркова"
тест на тему

Лапшина Ирина Вячеславовна

Тест  по УД "Теория алгоритмов" "Нормальные алгоритмы Маркова"

Скачать:

ВложениеРазмер
Файл test_markov.docx34.56 КБ

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

Тест «Нормальные алгоритмы Маркова» 1 вариант

  1. Результат марковской подстановки 21  3 в слово 521421

a) 52143                b) 5343

c) 531421                d) 533433

  1. Марковская подстановка 21  3 не применима к словам

a) 521421        b) 5241

c) 21                d)12

  1. Результат марковской подстановки 21   в слово 521421

a) 54                b)21521421

c) 5421        d)52142121

  1. Слово 21 является подсловом слова

a) 521421        b) 5241

c) 521                d) 2541

  1. Процесс работы нормального алгоритма считается завершенным, если на данном шаге
  1. Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
  2. Применена заключительная формула подстановки
  3. Ни одна подстановка схемы не подходит
  4. Понятно, что процесс подстановок не сможет остановиться

  1. Нормальный алгоритм не применим к исходным данным, если на данном шаге
  1. Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
  2. Применена заключительная формула подстановки
  3. Ни одна подстановка схемы не подходит
  4. Понятно, что процесс подстановок не сможет остановиться

  1. Каким будет результат применения нормального алгоритма ab ® L, ba ® ab к слову R = bbaabab 

  1. Результат применения нормального алгоритма ab ® bd, db ® ba, bba ® abb, c ® L к слову R = abbc
  1. Алгоритм не применим к этому слову
  2. bb
  3. aa
  4. cc

  1. В алгоритме Маркова ассоциативным исчислением называется:
  1. совокупность всех слов в данном алфавите;
  2. совокупность всех допустимых систем подстановок;
  3. совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;
  4. когда все слова в алфавите являются смежными.

  1. В ассоциативном счислении два слова называются смежными:
  1. если одно из них может быть преобразовано в другое применением подстановок;
  2. если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;
  3. когда существует цепочка от одного слова к другому и обратно;
  4. когда они дедуктивны.

  1. В алгоритмах Маркова дана система подстановок в алфавите
    A = {а, b, с}:  
    abc — с;        ba cb;        ca ab

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

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

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

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

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

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

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

  1. Дать подробное решение и описание алгоритма решения задачи:
  1. A={f,h,p} в слове P заменить все пары ph на f
  2. A={a,b,c} Приписать слово bac слева к слову P

Тест «Нормальные алгоритмы Маркова» 2 вариант

  1. Каким будет результат применения нормального алгоритма ab ® L, ba ® ab к слову R = bbaabab 

  1. Слово 21 является подсловом слова

a) 521421        b) 5241

c) 521                d) 2541

  1. Нормальный алгоритм не применим к исходным данным, если на данном шаге
  1. Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
  2. Применена заключительная формула подстановки
  3. Ни одна подстановка схемы не подходит
  4. Понятно, что процесс подстановок не сможет остановиться

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

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

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

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

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

  1. Процесс работы нормального алгоритма считается завершенным, если на данном шаге
  1. Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
  2. Применена заключительная формула подстановки
  3. Ни одна подстановка схемы не подходит
  4. Понятно, что процесс подстановок не сможет остановиться

  1. Результат марковской подстановки 21  3 в слово 521421

a) 52143                b) 5343

c) 531421                d) 533433

  1. Результат применения нормального алгоритма ab ® bd, db ® ba, bba ® abb, c ® L к слову R = abbc
  1. Алгоритм не применим к этому слову
  2. bb
  3. aa
  4. cc

  1. В алгоритмах Маркова дана система подстановок в алфавите
    A = {а, b, с}:  
    abc — с;        ba cb;        ca ab

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

  1. алгоритме Маркова ассоциативным исчислением называется:
  1. совокупность всех слов в данном алфавите;
  2. совокупность всех допустимых систем подстановок;
  3. совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;
  4. когда все слова в алфавите являются смежными.

  1. В ассоциативном счислении два слова называются смежными:
  1. если одно из них может быть преобразовано в другое применением подстановок;
  2. если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;
  3. когда существует цепочка от одного слова к другому и обратно;
  4. когда они дедуктивны.

  1. Марковская подстановка 21  3 не применима к словам

a) 521421        b) 5241

c) 21                d)12

  1. Результат марковской подстановки 21   в слово 521421

a) 54                b)21521421

c) 5421        d)52142121

17. Дать подробное решение и описание алгоритма решения задачи:

  1. A={a,b,c} в слове P заменить все пары ac на b
  2. A={p,f} Приписать слово fpf слева к слову S


По теме: методические разработки, презентации и конспекты

Презентация "Свойства алгоритмов"

В презентации рассматриваются основные свойства алгоритмов - дискретность, понятность, точность, результативность, массовость...

Основные алгоритмические конструкции. Вспомогательные алгоритмы

Данная разработка способствует:1)      сформировать представление об алгоритме как особой форме записи;2)      повторить основные алгоритмические конс...

тема "Понятие сложности алгоритма" курс "Теория алгоритмов"

При использовании алгоритмов для решения практических задач мы сталкиваемся с проблемой рационального выбора алгоритма решения задачи. Решение проблемы выбора связано с построением системы сравнительн...

Нормальные алгоритмы Маркова

Для дисциплины "Теория алгоритмов"...

Презентация на тему: В чем смысл эквивалентности машин Тьюринга и Поста и нормальных алгоритмов Маркова?

Тьюринг высказал предположение, что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной в предложенной им модели вычислений. Это предположение известно как тез...

Презентация по теме: "Алгоритмы. Свойства алгоритмов."

Презентация по теме: "Алгоритмы. Свойства алгоритмов."...

Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма

Конспект темы по информатике для 1 курсов. Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритмаСамостоятельная работа после изучения темы...