Тема 8.3 Уточнения понятия алгоритм.

Существует четыре уточнения понятия алгоритм (тезисы):

1. Тезис Тьюринга: Общий метод (алгоритм) для решения задач из класса финитно-поставленных существует тогда и только тогда, когда кодовая функция , вычисляется на машине Тьюринга.

2. Тезис Чорча: Функция f, определенная на множестве N вычислима тогда и только тогда, когда она является частично рекурсивной.

3. Нормальный алгоритм Маркова:

, где , все р_i, a_i – слова в алфавите А, А – конечный алфавит.

Схема работает следующим образом: пусть - это слово из алфавита А, тогда отыскиваем сверху первую строку, левая часть которой входит по крайней мере 1 раз в слово :

Заменяем самое левое вхождение р_i в слове самым правым вхождением a_i. Если ни одно р_i не входит в слово , то будем считать, что алгоритм не применим к этому слову.

Заменив р_i на a_i, получим новое слово и повторим процесс.

Процесс заканчивается на том шаге, когда .

4. Тезис Маркова: Для того, чтобы класс финитно-поставленных задач имел алгоритм решения необходимо и достаточно, чтобы существовал нормальный алгоритм Маркова, перерабатывающий код условия задачи в код ее ответа.

Итоговая (выходная) контрольная работа.

Вариант 1

1. Сколько существует подмножеств у множества А={2,7,11}?

1. 11

2. 3

3. 8

4. 6

5. 7

6. 5

2. Даны множества М=[2,8] N[4,10]. Найти множество N\M.

1. (8,10]

2. [8,10]

3. (4,10]

4. (4,10]

5. (2,4]

6. [2,4]

7. [2,4)

3. A={1,4}, B{2,3,5}. Определите сколько элементов содержит множество AxB.

1. 5

2. 6

3. 4

4. 7

3. Определите операцию, истинности таблица которой имеет вид

X	Y	?
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

1. дизъюнкция

2. конъюнкция

3. импликация

4. отрицание

3. Установите соответствие:

   I Диструбутивный закон Закон двойного отрицания Закон моргана

   а) ¬ ¬ x ≈ x б) x ∧ (x ∨ z)≈ (x ∧ y)∨ (x ∧ z) в) ¬(x ∧ y) ≈ ¬x∨ ¬y

4. Вставьте пропущенный символ в закон поглощения: x ___ ≈x

1. и

2. л

3. x

4. y

3. Высказывательная форма (¬x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (x ∨ y ∨ ¬z) является:

1. Приведённой

2. СДНФ

3. СКНФ

4. Верны a) и b)

5. Верны a) и с)

3. Является ли высказывательная форма (x→y)→(¬ y→¬x) тавтологией

1. нет

2. да

3. Дан предикат Найти область истинности предиката.

1. R

2. 

3. 

4. 

5. 

6. (-∞,+∞)

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

1. 8

2. 2

3. 4

4. 6

3. Является ли формулой слово (где – одноместный, а - трёхместный предикатные символы).

1. нет

2. да

3. Если подстановку разложить в произведение циклов, то число циклов будет равно:

1. 3

2. 4

3. 6

4. 2

5. 1

3. Декремент подстановки в задании 12 равен:

1. 3

2. 2

3. 1

4. 4

5. 5

3. Подстановка в задании 12 является:

1. четной

2. нечетной

3. Дан граф Г

B

A

C E F

D

У графа Г:

1. 5 ребер и 5 вершин

2. 5 ребер и 6 вершин

3. 6 ребер и 5 вершин

4. 6 ребер и 6 вершин

3. Определить степень вершины А в задании 15.

1. 4

2. 3

3. 2

4. 1

3. Если у графа 3 вершины, причем степень первой равна 1, степень второй равна 2, а степень третьей – 3, то сколько ребер имеет граф?

1. 4

2. 3

3. 2

4. 5

3. Определите длину пути от вершины А до вершины F в задании 15:

1. 3

2. 5

3. 4

4. ∞

3. Является ли ребро <АВ> мостом?

1. нет

2. да

3. Граф

1. эйлеров

2. не эйлеров

3. Пусть Г1 – плоский связный граф без перегородок с 3 гранями и 5 ребрами. Сколько вершин у графа Г1?

1. 2

2. 8

3. 4

4. 6

3. A C

B

D

Найти S(AB).

1. 2

2. 3

3. ∞

4. 1

3. У дерева 8 вершин. Сколько ребер имеет дерево?

1. 8

2. 7

3. 9

4. 4

Вариант 2

1. Сколько существует подмножеств у множества А={12,17,21,22}?

1. 22

2. 4

3. 16

4. 14

5. 12

6. 20

2. Даны множества М=[1,6] N[2,11]. Найти множество N\M.

1. (6,11]

2. [6,11]

3. [1,11]

4. (1,11]

5. (2,6]

6. [2,6]

7. [2,6)

3. A={1,3,4}, B{5,8}. Определите сколько элементов содержит множество AxB.

1. 5

2. 6

3. 4

4. 7

4. Определите операцию, истинности таблица которой имеет вид

X	Y	?
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

1. дизъюнкция

2. конъюнкция

3. импликация

4. отрицание

5. Установите соответствие:

II Диструбутивный закон Закон двойного отрицания Закон Моргана

а) ¬ ¬ x ≈ x б) x ∨ (x ∧ z)≈ (x ∨ y) ∧ (x ∨ z) в) ¬(x ∨ y) ≈ ¬x ∧ ¬y

6. Вставьте пропущенный символ в закон поглощения: x ___ ≈x

1. и

2. л

3. x

4. y

7. Высказывательная форма (¬x ∨ y ) ∧ (x ∨ ¬y ) является:

1. Приведённой

2. СДНФ

3. СКНФ

4. Верны a) и b)

5. Верны a) и с)

8. Является ли высказывательная форма (x→y) ∨ (¬ y→¬x) тавтологией

1. нет

2. да

9. Дан предикат Найти область истинности предиката.

1. Z

2. 

3. 

4. 

5. 

6. среди ответов нет верного.

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

1. 8

2. 2

3. 4

4. 6

11. Является ли формулой слово (где – одноместный, а - двуместный предикатные символы).

1. нет

2. да

12. Если подстановку разложить в произведение циклов, то число циклов будет равно:

1. 3

2. 4

3. 6

4. 2

5. 1

13. Декремент подстановки в здании 12 равен:

1. 3

2. 2

3. 1

4. 4

5. 5

14. Подстановка в здании 12 является:

1. четной

2. нечетной

15. Дан граф Г

B

A

C E F

D

У графа Г:

1. 5 ребер и 5 вершин

2. 7 ребер и 6 вершин

3. 6 ребер и 5 вершин

4. 6 ребер и 6 вершин

16. Определить степень вершины А в здании 15.

1. 4

2. 3

3. 2

4. 1

17. Если у графа 3 вершины, причем степень первой равна 1, степень второй равна 2, а степень третьей – 3, то сколько ребер имеет граф?

1. 4

2. 3

3. 2

4. 5

18. Определите длину пути от вершины А до вершины F в здании 15:

1. 3

2. 5

3. 4

4. ∞

19. Является ли ребро <АВ> мостом?

1. нет

2. да

20. Граф

1. эйлеров

2. не эйлеров

21. Пусть Г1 – плоский связный граф без перегородок с 3 гранями и 5 ребрами. Сколько вершин у графа Г1?

1. 2

2. 8

3. 4

4. 6

22. A C

B

D

Найти S(AB).

1. 2

2. 3

3. ∞

4. 1

23. У дерева 8 вершин. Сколько ребер имеет дерево?

1. 8

2. 7

3. 9

4. 4