Тест №1 “Алгоритмы” для группы ДКА – 101. Выполняется с 26.11.11 по 15.12.11.

Число попыток – 10.

Время на тест – 2 часа.

Проходной балл – 70.

Нестрогий контроль.

Оценивается в 9 – 15 баллов.

Тест состоит их двух частей: Нормальные алгоритмы и Машина Тьюринга.

Правильные ответы помечены – верно.

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

Задание 1. Дан алфавит{|, *, α, β}и последовательность команд, с помощью которой выполняется умножение натуральных чисел: β| → |β

α| → |βα

α → ˄

|* → *α

*| → *

* → ˄

Β → |

Какая последовательность получится при выполнении операции 2*3 на восьмом шаге?

1. |*|||βββα

2. |*|||βββ - верно

3. |β|βα|βββ

Задание 2.

Дан алфавит А=(^,a,b,c,z,x,v) входное слово R=abcvxazxa, и последовательность команд:

av

v^

cv

x^

найти слово на 10 шаге алгоритма :

1. bvxzx

2. bzx - верно

3. bvxx

4. bvzx

Задание 3.Дан алфавит N=(^,a,b,c,d,α) входное словоH=dbbd, и последовательность команд:

bbα

αa

ddddabcd

^adda

aadd

^α

найти слово на 10 шаге алгоритма :

1. abcd

2. ddbcd - верно

3. dabdc

Задание 4. Дан алфавит А={ |, -, ^}, входное слово ||||||||-|||||||||| и последовательность команд:

|-|-;

-^.^;

^-.-

Какое слово получится после выполнения преобразований?

1. ||-;

2. ||;

3. -|| - верно

Задание 5. Используя алфавит А={X,Y,Z,A,α} и систему команд узнать как будет выглядеть слово XYZ на 14 шаге выполнения алгоритма.

Система команд:

Y ->XZ

XZ ->αX

X -> Z

Z ->α

αα -> Z

α ->· A

Ответ:

1. αA

2. A - верно

3. Aα

Задание 6. Дан алфавит A={a₁, |, a₂, b₁, b₂}, и входное слово S=|a₁a_1. Также, дана система команд:

|  a₁ a₂ a₁ a₁  b₁ a₂ b₂ |a₂|  a₁ b₁ a₂ b₂  | a₁ a₂| b₁|  || | a₁ a₂|  a₂||

Как будет выглядеть слово на выходе? 1. a₁ a₂ a₁ || - верно 2. a₁ a₂ a₁ a₁ 3. a₁ a₂ a₁ b₁|

Задание 7

Дан алфавит А={1,АО,2,F,3,S,4F5,7S,4A,10,7,5,4} и входное слово S=1 AO2F3S

Дана система команд:

12

2AO

35

4F57

7SA

4A10

Найти слово на девятом шаге алфавита:

1.44AOF3S

2.444F5S

3.44A - верно

Задание 8

Дан алфавит A={1,2,3,A,B,C}

Входное слово S=1A2B3C

Дана система команд:

1C

A2B

B1

C3C

Как будет выглядеть слово на выходе?

1. C312AC

2. CCCC - верно

3. 3CCCC

Задание 9

Дан алфавит А={^,1,2,B,C,0,4} и дано и входное слово S=B12COB

Дана система команд:

B1

B1C

112

224

CB

BOB

Каково будет конечное слово?

1.4BOB

2.4BB

3.44 - верно

Задание 10

Дан алфавит: A={1,A,B,Z,8} Входное слово: R=A8B1Z Система команд: 8  AB AAZ BB1 11Z ZZZAB

Ответ: 1)18 2)AB - верно 3)BA

Задание 11.

Дан алфавит {*,x,y,z,n,k,s}. Вxодное слово: M=xyzskxnkx Последовательность команд: x-s s-* z-s k-* Найти слово на 9-ом шаге: 1.ksxynkx 2.ynk 3.yknk - верно 4.yzknk

Задание 12.

Дан алфавит {0, |, 1, ^}

Входное слово: 101

Последовательность команд:

|0 -> 0||

1 -> 0|

0 -> ^

Найти значение на 5-ом шаге:

1) 000||||| - Верно

2) yzknk

3) ||00||

Задание 13.

Дан алфавит {a,b,c,α,β,||}

Входное слово: abc

Последовательность команд:

1. a->αα

2. α->||

3. c->β

4. b->β||

5. ||->a|

Найти значение на 5-ом шаге:

1. ||||β||β - верно

2. ||βa|α

3. ||β||α

Задание 14.

Дан алфавит {0,1,2,3,4,5,6,7,8,9}

Входное слово: 213759846

Последовательность команд:

1. 2->1

2. 3->55

3. 8->77

4. 9->22

5. 55->88

6. 444->1

7. 777->0

Найти значение на 8-ом шаге:

1)110775117746 - Верно

2)11557597746

3)118875117746

Задание 15.

Дан алфавит {α,β,γ,Δ,ε}

Входное слово: Δεβαγ

Последовательность команд:

1. βα->αβ

2. γα->αγ

3. Δα->αΔ

4. εα->αε

5. γβ->βγ

6. Δβ->βΔ

7. Εβ->βε

8. Δγ->γΔ

9. Εγ->γε

10. εΔ->Δε

Найти значение после окончания выполнения алгоритма:

1. εΔγβα

2. γεΔαβ

3. αβγΔε - верно

Задание 16

Дан алфавит {ABCDE}

Список команд:

1) A->E

2)C->ABC

3)B->ECD

Найти значение на шестом шаге алгоритма

1)ABCDE

2)EBEBEBABCDE - верно

3)ABEBEBCDEA

4)EBEBCDEAEB

Задание 17.

Дан алфавит {a,b,c,1,2,3,^}

Входное слово: 1a2b3c

Последовательность команд:

1. 1->a

2. a->c

3. cc->b

4. b2->2b

5. bb->1

6. ^->a

Найти значение после 10 шага:

1. 2с3с

2. 223с

3. a2c3c - верно

Задание 18.

Дан алфавит {α,β,a,/ ,b,c,d}

Входное слово: abcd

Последовательность команд:

1. a->αα

2. β->α

3. b->//

4. α->β

5. ^->ββ

6. d->/

7. /->a

Найти значение после 5 шага:

1. ααβaα

2. βββ//cd - верно

3. ββββ

Машина Тьюринга

Задание 1. Дан набор правил для машины Тьюринга

A/Q	q0	q1	q2
0	q1αH	q20L	q30H
|	q0αL	q0αL	q2|H
α	q0αL	q1αR	q2|L

На ленту записывается слово K=|. Какая последовательность получится на 5 шаге выполнения операций?

1)αα

2)αα0 - верно

3)α|0

Задание 2

Дан алфавит А={1,2,3,4,5,6,7,8,9,0,a₀}

a₀ –пустой символ

q₀-состояние стопа

На ленту вводится слово 120800. Обзор числа начинается с крайнего правого элемента

Дан набор правил для МТ

q/a	0	1	2	3	4	5	6	7	8	9	a0
q1	q20 R	q21 R	q22 R	q23 R	q24 R	q25 R	q26 R	q27 R	q2 8 R	q2 9 R	q2 a0L
q2	q29 L	q00 H	q01 H	q02 H	q01 H	q0 4 H	q05 H	q06 H	q07 H	q08H	q0 a0H

Определить какое число будет выведено после завершения программы.

1) 120799 - Верно

2) 120790

3) 2070

Задание 3. Дан набор правил для машины Тьюринга

A/Q	q0	q1	q2
0	q2αR	q20R	q30H
|	q0|L	q0αL	q00H
α	q2|L	q1|H	q1αR

На ленту записывается слово H=|α|. Какая последовательность получится на 6 шаге выполнения операций?

1)|||

2)αααα - верно

3)α|α

Задание 4

Дан алфавит А={1,2,3,4,5,6,7,8,9,0,a₀}

a₀ –пустой символ

q₀-состояние стопа

На ленту вводится слово 6661299. Обзор числа начинается с крайнего правого элемента

Дан набор правил для МТ

q/a	0	1	2	3	4	5	6	7	8	9	a0
q1	q20 R	q21 R	q22 R	q23 R	q24 R	q25 R	q26 R	q27 R	q2 8 R	q2 9 R	q2 a0L
q2	q21 H	q02 H	q03 H	q04 H	q05 H	q0 6 H	q07 H	q08 H	q09 H	q00L	q0 a0H

Определить какое число будет выведено после завершения программы.