Тест по Теории вычислительных процессов (часть 1)
1. Выберете все правильные ответы
Трассировочная таблица может использоваться
а) для определения того, что вычисляет программа б) для определения инварианта цикла,
в) для доказательства правильности программы
2. Расположите по усложнению
Для доказательства правильности утверждений и формул используются
а) модифицированная простая индукция б)обобщенная индукция в) строгая индукция
3. Выберете правильный ответ
Принцип простой индукции используется для доказательства высказываний
а) о натуральных числах б) о целых числах в) о вещественных числах г) о неотрицательных числах
4. Дополните, расставив на блок-схеме утверждения
 |
А – утверждение о правильности
B – утверждение о конечности
C – утверждение–инвариант цикла
D – утверждение о входных данных
Ответ: 1 – ..., ..., ...; 2 – ... ..., ..., ...; 3 – ... и т. д.
5. Дополните недостающее слово
При использовании принципа модифицированной простой индукции мы предполагаем, что высказывание истинно для S(n) и на основе этого пытаемся доказать справедливость S(n+1). Это допущение называется......... индукции.
6. Дополните недостающее слово
Фрагмент определения принципа строгой индукции имеет вид:
« ... требуется доказать, что S(n) справедливо для всех положительных n. Для этого необходимо:
1) доказать, что справедливо S(1);
2) доказать, что если справедливо ............... для всех положительных n, то справедливо и S(n + 1).»
7. Выберете неправильный ответ
Существуют следующие виды индукции, используемые для доказательства высказываний
а) простая б) модифицированная простая в) простая нисходящая г) строгая нисходящая д) строгая е) модифицированная строгая
|
8. Дополните, фрагмент блок-схемы
|
9. Выберете правильный ответ
а) метод индукции является обобщением метода индуктивных утверждений при доказательстве правильности
б) метод индуктивных утверждений является обобщением метода индукции при доказательстве правильности
в) метод индукции и метод индуктивных утверждений являются самостоятельными и независимыми
10. Дополните два недостающих слова
Метод индуктивных утверждений используется для доказательства......... .......... программ
11. Выберете правильный ответ
При использовании метода индуктивных утверждений на блок-схему не выносятся
а) утверждение о правильности б) утверждение о конечности в) утверждение–инвариант цикла г) утверждение о входных данных
12. Выберете правильный ответ
Действия, предусмотренные методом индуктивных утверждений являются..... для доказательства правильности
а) необходимыми б)достаточными в) необходимыми и достаточными г) избыточными
13. Дополните недостающее слово
При доказательстве правильности программ методом индуктивных утверждений утверждения записываются в качестве..........
14. Выберете неправильные ответы
В методе индуктивных утверждений рассматриваются замкнутые пути в программе из точки i в точку j. При этом
а) точки i и j не могут совпадать (быть одной точкой)
б) между ними не могут находиться другие точки с индуктивными утверждениями
в) с точками i и j должны быть связаны индуктивные утверждения
г) между ними не могут находиться другие точки
15. Выберете правильный ответ
а) тестирование гарантирует правильность программы
б) доказательство методом индуктивных утверждений гарантирует правильность программы
в) тестирование и доказательство методом индуктивных утверждений гарантирует правильность программы
г) ни тестирование ни доказательство методом индуктивных утверждений не гарантирует правильность программы
16. Выберете наиболее правильный ответ
Высказываний о переменных, изменяющихся в теле цикла и являющихся инвариантом цикла должно быть
а) 1 б) 2 в) несколько г) фиксированное число д) в зависимости от условий задачи
17. Выберете все правильные ответы
а) на блок-схеме порядок выполнения явно определяется стрелками
б) в программах порядок выполнения явно определяется использованными управляющими структурами языка
в) в программах порядок выполнения неявно определяется использованными управляющими структурами языка
г) на блок-схеме порядок выполнения неявно определяется стрелками
18. Выберете правильный ответ
Для данной блок-схемы инвариантом цикла будет
 |
А – 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 – среди предложенных вариантов
нет правильного
19. Выберете правильный ответ
Для доказательства инварианта цикла блок-схем из п.18 используем индукцию по
а) значению переменной I в точке 2 б) значению переменной J в точке 2
в) числу проходов n через точку 2 г) значению переменной M в точке 2
Задания на определение зависимости одних явлений от других.
В заданиях 20 и 21 Выберете правильный ответ, используя схему
ответ | 1 | 2 | вывод |
A | + | + | + |
B | + | + | – |
C | + | – | – |
D | – | + | – |
E | – | – | – |
20. Для доказательства правильности программ можно использовать метод индуктивных утверждений ПОТОМУ ЧТО в программе порядок управления неявно определяется управляющими структурами.
21. Метод индуктивных утверждений нельзя использовать для доказательства правильности программ ПОТОМУ ЧТО они, в отличие от блок-схем, могут содержать обращение к подпрограммам.
22. Выберете правильный ответ
Для доказательства инварианта цикла используют
а) восходящую индукцию б) модифицированную индукцию в) простую индукцию г) нисходящую индукцию
23. Выберете правильный ответ
Доказывая конечность программы (при доказательстве правильности программы методом индуктивных утверждений)
используем следующие индуктивные утверждения:
а) утверждение о правильности б) утверждение о конечности в) инвариант цикла г) утверждение о входных данных
Ответник
... – вставить букву ответа
... (и т. д.) – вставить несколько букв
........... – вставить слово
......... ......... – вставить два слова
... , ... , ... – перечислить все буквы в нужном порядке
__________________________
1. ... (и т. д.)
2. ... , ... , ...
3. ...
4. 1 – ..., ..., 2 – ..., ..., ...; 3 – ... и т. д.
5. ..............
6. ...
7. ...
8. ........... ..........
9. ...
10. ...... .........
11. ...
12. ...
13. .........
14. ... (и т. д.)
15. ...
16. ...
17. ... (и т. д.)
18. ...
19. ...
20. ...
21. ...
22. ...
23. ...
Ответник
... – вставить букву ответа
... (и т. д.) – вставить несколько букв
........... – вставить слово
......... ......... – вставить два слова
... , ... , ... – перечислить все буквы в нужном порядке
__________________________
1. ... (и т. д.)
2. ... , ... , ...
3. ...
4. 1 – ..., ..., 2 – ..., ..., ...; 3 – ... и т. д.
5. ..............
6. ...
7. ...
8. ........... ..........
9. ...
10. ...... .........
11. ...
12. ...
13. .........
14. ... (и т. д.)
15. ...
24. ...
25. ... (и т. д.)
26. ...
27. ...
28. ...
29. ...
30. ...
23. ...
Ответник
... – вставить букву ответа
... (и т. д.) – вставить несколько букв
........... – вставить слово
......... ......... – вставить два слова
... , ... , ... – перечислить все буквы в нужном порядке
__________________________
1. ... (и т. д.)
2. ... , ... , ...
3. ...
4. 1 – ..., ..., 2 – ..., ..., ...; 3 – ... и т. д.
5. ..............
6. ...
7. ...
8. ........... ..........
9. ...
10. ...... .........
11. ...
12. ...
13. .........
14. ... (и т. д.)
15. ...
31. ...
32. ... (и т. д.)
33. ...
34. ...
35. ...
36. ...
37. ...
23. ...
Ответник
... – вставить букву ответа
... (и т. д.) – вставить несколько букв
........... – вставить слово
......... ......... – вставить два слова
... , ... , ... – перечислить все буквы в нужном порядке
__________________________
1. ... (и т. д.)
2. ... , ... , ...
3. ...
4. 1 – ..., ..., 2 – ..., ..., ...; 3 – ... и т. д.
5. ..............
6. ...
7. ...
8. ........... ..........
9. ...
10. ...... .........
11. ...
12. ...
13. .........
14. ... (и т. д.)
15. ...
38. ...
39. ... (и т. д.)
40. ...
41. ...
42. ...
43. ...
44. ...
23. ...
