Тест по Теории вычислительных процессов

Тест по Теории вычислительных процессов

1. Выберите все правильные ответы Трассировочная таблица может использоваться:

а) для определения того, что вычисляет программа, б) для определения инварианта цикла, в) для доказательства правильности программы

2. Расположите по усложнению Для доказательства правильности утверждений и формул используются

а) модифицированная простая индукция б) обобщенная индукция в) строгая индукция

3. Выберите правильный ответ Принцип простой индукции используется для доказательства высказываний

а) о натуральных числах б) о любых целых числах в) о вещественных числах

4. Дополните, расставив на блок-схеме
утверждения

А – утверждение о правильности

B – утверждение о конечности

C – утверждение–инвариант цикла

D – утверждение о входных данных

Ответ: 1 – ..., ..., ...; 2 – , ..., ...; 3 – ... и т. д.

5. Выберите правильный ответ

Для данной блок-схемы инвариантом цикла будет

А – J = 2*J

B – J = 2J

C – J = 2I+1

D – J = 2I–1

E – J = 2M

F – J = 2M+I

G – J = 2M–I

H – среди предложенных вариантов нет правильного

6. Дополните недостающее слово

При использовании принципа простой индукции мы предполагаем, что высказывание истинно для S(n) и на основе этого пытаемся доказать справедливость S(n+1). Это допущение называется......... индукции.

7. Дополните недостающее слово Фрагмент определения принципа строгой индукции имеет вид:

« ... требуется доказать, что S(n) справедливо для всех положительных n. Для этого необходимо:

1) доказать, что справедливо S(1);

2) доказать, что если справедливо ............... для всех положительных n, то справедливо и S(n + 1).»

8. Выберите правильный ответ

а) метод индукции является обобщением метода индуктивных утверждений при доказательстве правильности

б) метод индуктивных утверждений является обобщением метода индукции при доказательстве правильности

в) метод индукции и метод индуктивных утверждений являются самостоятельными и независимыми

9. Выберите неправильный ответ При использовании метода индуктивных утверждений на блок-схему выносятся

а) утверждение о правильности, б) утверждение о конечности, в) утверждение–инвариант цикла, г) утверждение о входных данных

10. Выберите правильный ответ

Действия, предусмотренные методом индуктивных утверждений являются........... для доказательства правильности

а) необходимыми б) достаточными в) необходимыми и достаточными г) избыточными

11. Дополните недостающее слово

При доказательстве правильности программ методом индуктивных утверждений утверждения записываются в качестве..........

12. Выберите неправильные ответы

В методе индуктивных утверждений рассматриваются замкнутые пути в программе из точки i в точку j. При этом

а) точки i и j не могут быть одной точкой, б) между ними не могут находиться другие точки с индуктивными утверждениями

в) с точками i и j должны быть связаны индуктивные утверждения, г) между ними не могут находиться другие точки

13. Выберите правильный ответ а) тестирование гарантирует правильность программы

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

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

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

14. Выберите наиболее правильный ответ

Высказываний о переменных, изменяющихся в теле цикла и являющихся инвариантом цикла должно быть

а) 1 б) 2 в) несколько г) фиксированное число д) в зависимости от условий задачи

15. Выберите все правильные ответы

а) на блок-схеме порядок выполнения явно определяется стрелками

б) в программах порядок выполнения явно определяется использованными управляющими структурами языка

в) в программах порядок выполнения неявно определяется использованными управляющими структурами языка

г) на блок-схеме порядок выполнения неявно определяется стрелками

16. Выберите правильный ответ Для доказательства инварианта цикла блок-схем из п.5 используем индукцию по

а) значению переменной I в точке 2 б) значению переменной J в точке 2
в) числу проходов n через точку 2 г) значению переменной M в точке 2

Задания на определение зависимости одних явлений от других.

В заданиях 17 и 18 Выберите правильный ответ, используя схему

ответ	1	2	вывод	17. Для доказательства правильности программ можно использовать метод индуктивных утверждений, ПОТОМУ ЧТО в программе порядок управления неявно определяется управляющими структурами. 18. Метод индуктивных утверждений нельзя использовать для доказательства правильности программ, ПОТОМУ ЧТО они, в отличие от блок-схем, могут содержать обращение к подпрограммам.
A	+	+	+
B	+	+	–
C	+	–	–
D	–	+	–
E	–	–	–

19. Выберите правильный ответ Для доказательства инварианта цикла используют

а) восходящую индукцию, б) модифицированную индукцию, в) простую индукцию, г) нисходящую индукцию

20. Дополните недостающее слово Сети Петри применяются исключительно в.........

21. Вставьте пропущенные слова

Сеть Петри состоит из 4 элементов: множество........ Р, множество........ Т, ........ функция I и ............ функция О.

22. Дополните недостающее слово

Число появлений позиции во входном комплекте переходов #(pi, I(tj)) называется......... входной позиции pi для перехода tj.

23. Вставьте пропущенные слова

Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф. Для данного графа напишите, что обозначено каждой буквой

24. Выберите все верные варианты ответов: «да» или «нет»

Начальная маркировка m сети Петри С = (Р, Т, I, О)

1) ... есть присвоение фишек позициям сети Петри да / нет

2) ... управляет выполнением сети Петри да / нет

3) ... определяется только количеством фишек да / нет

4) ... содержит только разрешающие фишки
для каждого перехода сети да / нет

5) ... изменяется при запуске любого перехода да / нет

6) ... не может повторяться в процессе выполнения
сети Петри да / нет

7) зависит от постановки задачи да / нет

8) ... влияет на свойства сети Петри да / нет

25. Дополните недостающие слова

Граф сети Петри можно записать как G = (V, A), где V = {v1, v2, ..., vs} – ......... вершин, А = {а1, а2, ..., аr} – ......... дуг.

26. Выберите наиболее правильный ответ

а) если сеть Петри безопасна, то она ограничена; б) безопасность – частный случай более общего свойства (ограниченности);

в) безопасность и ограниченность – два независимых свойства сети Петри; г) если сеть Петри ограничена, то она безопасна;

д) ограниченность – частный случай более общего свойства (безопасности).

27. Выберите правильный ответ

С помощью сетей Петри нельзя промоделировать задачу

а) ... о взаимном исключении; б) ... о чтении/записи; в) ... о чтении/записи с ограниченным количеством процессов чтения;
г) ... о чтении/записи с не ограниченным количеством процессов чтения; д) ... о производителе/потребителе;
е) ... о нескольких производителях / нескольких потребителях ж) ... о производителе/потребителе с ограниченным буфером

28. Выберите правильный ответ

В правильно построенном дереве достижимости сети Петри не может быть... вершины.

а) терминальной б) корневой в) граничной в) дублирующей г) внутренней

29. Выберите неправильные ответы

В с помощью дерева достижимости всегда можно решить задачи сети Петри :

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

30. Дополните недостающее слово

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

31. Выберите правильный ответ, используя схему Невозможно использовать сети Петри для моделирования параллельных процессов, ПОТОМУ ЧТО запуск перехода (и соответствующее ему событие) в сети Петри рассматривается как мгновенное событие, занимающее нулевое время.	ответ	1	2	вывод
A	+	+	+
B	+	+	–
C	+	–	–
D	–	+	–
E	–	–	–

32. Установите соответствие (ответов может быть несколько)

Способы задания сети Петри Понятия сети Петри

А. Теоретико-формальное 1. Комплект дуг

Б. Теоретико-графовое 2. Множество переходов

В. Матричное 3. Кратность позиций

4. Вектор последовательности запусков

33. Установите соответствие между фрагментами блок-схем и подграфами сетей Петри

А Б

34. Выберите по одному переходу сети Петри 35. Вставьте пропущенное
соответствующего уровня активности граф сети Петри дерево достижимости

0 – 1 – 2 – 3 – 4 –

36. Выберите правильный ответ

При переводе блок-схемы в сеть Петри 1 узел блок-схемы заменяется на

1) ... 1 переходпереходаили 2 переходапозициюпозицииили 2 позиции

37. Выберите правильные ответы

Расширение модели сети Петри приводит к:

а) уменьшению мощности разрешения б) увеличению мощности разрешения в) уменьшению мощности моделирования
г) увеличению мощности моделирования д) не влияет на мощность разрешения е) ограничению модели сети Петри