- •Министерство образования и науки Украины
- •О.Н. Паулин
- •Приложение г Сравнение методов сортировки массивов
- •1. Содержание и порядок выполнения курсовой работы
- •1.1. Общие положения
- •Разработка эффективных алгоритмов.
- •1.2. Задания на разработку
- •Образец заполнения
- •Образец титульного листа
- •1.3. Рекомендации к выполнению курсовой работы
- •2. Примеры выполнения курсовой работы
- •2.I. Разработка эффективных алгоритмов
- •2.2. Построение машины Тьюринга
- •2.2.1. Вычисления на машине Тьюринга
- •Словесное описание алгоритма
- •Пример 2.3.
- •2.2.2. Примеры построения машин Тьюринга
- •В алгоритме имеются две операции выбора:
Словесное описание алгоритма
1. Головка МТ движется вправо вдоль исходной последовательности “1”, пока не встретит пустую ячейку.
2. Затем головка возвращается влево на одну ячейку, инвертирует “1”, находящуюся в текущей ячейке, и сдвигается вправо на одну ячейку.
3. Если в текущей ячейке записана “1” (a’’ 0 - частично копирование уже выполнено), то головка движется вправо, пропуская ячейки с “1”, пока не встретит пустую ячейку; иначе (обрабатывается первая “1” исходного числа) выполняется п.2).
4. Головка сдвигается вправо, пропуская пустую ячейку.
5. Если в текущей ячейке записана “1” (a’’’ 0 частично результат уже сформирован), то головка движется вправо, пропуская ячейки с “1”, пока не встретит пустую ячейку; иначе (обрабатывается первая “1” исходного числа, обработка ведётся с конца) выполняется переход к следующей операции.
6. Инвертируется значение текущей ячейки (копируется очередная “1”) и головка сдвигается влево на одну ячейку.
7. Если в текущей ячейке “1”, то головка движется влево, пропуская “1”, до пустой ячейки; (пропуская число a’’’); иначе выполняется следующая операция.
8. Головка движется влево, пропуская пустую ячейку.
9. Если в текущей ячейке “1”, то головка движется влево до ячейки с “0” (проходит число a’’); иначе выполняется переход к следующей операции.
10. Инвертируется значение текущей ячейки (восстанавливается “1”) и головка движется влево на одну ячейку.
11. Если в текущей ячейке “0” (обработаны все “1” исходного числа а; a’ = ), то головка сдвигается вправо и МТ останавливается; иначе значение текущей ячейки инвертируется, головка сдвигается вправо на одну ячейку, и вновь выполняется последовательность операций из пп. 3 – 11.
21
В табл. 2.3 представлена работа машины М1, т. е. расписаны по тактам её конфигурации; исходное число на ленте n=2.
Таблица 2.3
|
Такт |
Состояние |
Ситуация на ленте |
|
0 |
q1 |
. . . 0 1 1 1 0 0 . . . |
|
1 |
q1 |
. . . 0 1 1 1 0 0 . . . |
|
2 |
q1 |
. . . 0 1 1 1 0 0 . . . |
|
3 |
q1 |
. . . 0 1 1 1 0 0 . . . |
|
4 |
q2 |
. . . 0 1 1 1 1 0 . . . |
|
5 |
q2 |
. . . 0 1 1 1 1 0 . . . |
|
6 |
q2 |
. . . 0 1 1 1 1 0 . . . |
|
7 |
q2 |
. . . 0 1 1 1 1 0 . . . |
|
8 |
q2 |
. . . 0 1 1 1 1 0 . . . |
|
9 |
! |
. . . 0 1 1 1 1 0 . . . |