Курсовая работа - Теория алгоритмов. Разработка эффективных алгоритмов
Подождите немного. Документ загружается.
указать конечное и начальное состояния, начальную конфигурацию на ленте и
расположение головки машины.
Задание на построение машины Тьюринга
1)2(
6)2(
)'1(
2'7)1(
419
М
М
ММ
ММТ
Функциональная схема
M4 0 1
D1 0RD2 1SD0(1)
D2 1LD1 1SD0(2)
M7 0 1
G1 1RG1 0LG2
G2 0RG2 1SG0
M2 0 1
B1 0RB1 1SB0(1)
B2 1LB2 1SB0(2)
M1 0 1
A1 0RA1 0SA2
A2 0SA0 1RA2
M6 0 1
F1 0LF1 1RF2
F2 1RF1 0SF0
МТ19 0 1
D1 0RD2 1SDG1
D2 1LD1 1SA1
G1 1RG1 0LG2
G2 0RG2 1SB1
B1 0RB1 1SG1
B2 1LB2 1SF1
A1 0RA1 0SA2
A2 0SA0 1RA2
F1 0LF1 1RF2
F2 1RF1 0SF0
МТ19 0 1
D1 0RD2 1SD0(1)
D2 1LD1 1SD0(2)
G1 1RG1 0LG2
G2 0RG2 1SG0
B1 0RB1 1SB0(1)
B2 1LB2 1SB0(2)
A1 0RA1 0SA2
A2 0SA0 1RA2
F1 0LF1 1RF2
F2 1RF1 0SF0
Змн. Арк.
Арк.
№ докум. Підпис Дата
Арк.
25
КР.КС.39.19.00.ПЗ
Змн. Арк.
Арк.
№ докум. Підпис Дата
Арк.
26
КР.КС.39.19.00.ПЗ
Начало
x=0
x=0,R x=1,S
x=0
x=1,Sx=1,L
x=0
x=0,R x=0,S
x=0
x=0,S
x=1,R
конец
x=0
x=1,R x=0,L
x=0
x=0,R x=1,S
x=0
x=0,R x=1,S
да
нет
да
нет
да нет
да
нет
да
нет
да нет
да
нет
D1
D2
A1
A2
G1
G2
B1
Схема алгоритма
D1
A2
F1 F2
A0
A1
F0
B2
G1
B1
G2
D2
1L
0 0R
0
1
1S
1
1
0
0R
1
0L
0
1R
1S
1
0
0R
1S
1
0
1L
1S
1
0
0R
1
1R
0S
0
1
1S
0
1R
0
0L
0S
0S
1
1R
Граф переходов
Змн. Арк.
Арк.
№ докум. Підпис Дата
Арк.
27
КР.КС.39.19.00.ПЗ
Словесное описание к машине Тьюринга
В начальный момент времени машина находится в D1, если x≠0, то остается 0 и
передвигаемся вправо и переходим в D2, если x=0, то 1, влево и переходим в D1,
если x≠0, то 1, стоп и переходим в A1, если x=0, то остается 0, вправо и переход в
A1,если x≠0, то 0, стоп и переходим в A2, если x=0, то 0, стоп и конец, а если x=0,
то 1, вправо и переход в A2.
Если же x≠0 (в состоянии D1) , то меняем на 1, останавливаемся и переходим в
G1, если x=0, то меняем на 1, вправо и переходим в G1, если x=0, то остается 0,
двигаемся влево и переходим в G2, если x=0, то остается 0, вправо и переход в G2,
если x≠0, то 1, стоп и переходим в B1, если x=0, то 0, вправо и переходим в B1,
если x=0, то 1, останавливаемся и переходим в G1.
Змн. Арк.
Арк.
№ докум. Підпис Дата
Арк.
28
КР.КС.39.19.00.ПЗ
ЗАКЛЮЧЕНИЕ
В данной курсовой работе мы рассмотрели такие темы: опрелеление
алгоритма, его значение, виды алгоритмов, типы алгоритмов, эффективность
алгоритмов и методы её достижения. Также я научился построению линейных,
циклических и алгоритмов с разветвлением. Показал примеры решения задачи
с помощью алгоритма.
Научился построению машины Тьюринга со всеми схемами и описанием.
Рассмотрел устройство машины Тьюринга и описание.
Машина Тьюринга представляет собой конечный автомат с бесконечной
лентой памяти для чтения записи и является реалистичной моделью
вычислений.
Алгори́́тм— точный набор инструкций, описывающих порядок действий
исполнителя для достижения результата решения задачи за конечное время.
В конце работы указал используемые источники информации.
Змн. Арк.
Арк.
№ докум. Підпис Дата
Арк.
29
КР.КС.39.19.00.ПЗ
Использованная литература:
1. http://www.lessons-tva.info/edu/e-inf1/e-inf1-4-2.html
2. http://ru.wikipedia.org/wiki/Алгоритм
3. http://www.teacher.dn-ua.com/old_version/algoritm/
4. http://www.algoritmy.info/
5. http://www.twirpx.com/
6. http://www.mstu.edu.ru/education/materials/zelenkov/ch_1_1.html
7. http://ru.wikipedia.org/wiki/Машина_Тьюринга
Змн. Арк.
Арк.
№ докум. Підпис Дата
Арк.
30
КР.КС.39.19.00.ПЗ