Практическая часть лабораторной работы.
1. Создать имитационную модель машины Тьюринга.
1.1. Выбираем задачу:
Прибавить единицу к существующему целому положительному двоичному числу.
Решение этой задачи рассмотрено в примере 1 теоретической части (см. выше).
По условиям задачи число может быть любой размерности в пределах ограничения
ленты автомата (у нас ограничения в пределах листа программы Excel).
Поэтому необходимо задаться определенной длиной ленты по своему усмотрению, чтобы задача решалась.
Сама задача решена, то есть составлена таблица автомата Тьюринга.
Нам осталось создать имитационную модель с помощью программы Excel.
Сложность реализации будет заключаться в отказе от встроенного языка программирования VBA.Поставленную задачу необходимо реализовать с помощью встроенных функций и условного форматирования ячеек электронной таблицы Excel Microsoft Office.
Но даже ограниченные средства реализации позволяют построить действующую имитационную модель автомата Тьюринга.
1.2. Составляем текстовый алгоритм выполнения задачи по шагам:
1. Начальное положение программы “0” →вводим исходные данные на ленту и определяем положение головки цифрой “1” в клетке под записанными данными на ленте .
2. Запускаем программу →положение программы “1”.
3. Оцениваем содержимое ячейки ленты над головкой и состояние головки.
4. По результатам оценки находим в таблице автомата Тьюринга данные о новом состоянии, новом движении головки и новом содержимом ячейки над головкой.
|
|
5. Сдвигаем головку в нужном направлении, одновременно изменяя ее состояние. При этом записываем нужную информацию в ячейку ленты.
6. Если состоянии головки равно наибольшей строке таблицы+1, то изменяем положение программы на “2” и останавливаем программу выполнения.
Остается уточнить детали алгоритма и составить формулы для нужных ячеек электронной таблицы.
Составим подробный текстовый алгоритм по минимальным шагам выполнения программы, так как некоторые описанные выше пункты не решаются за один шаг в силу ограниченности формул Excel:
1. Начальное положение программы “0” →вводим исходные данные на ленту и определяем положение головки цифрой “1” (Ручной ввод информации).
2. Запускаем программу →положение программы “1”.(добавляем в определенную ячейку “1” вместо “0”)
3. Оцениваем содержимое ячейки ленты над головкой, состояние головки и находим в таблице автомата Тьюринга данные о новом состоянии головки, новом движении головки и новом содержимом ячейки числа (“0” или “1” или пустота (обозначим ее “х”) над головкой (добавляем три новых ячейки информации для каждого положения головки, помимо ячеек информации ленты) (это Шаг 1)
|
|
4. Сдвигаем головку в нужном направлении, одновременно изменяя ее состояние. (это Шаг 2).
5. Переписываем содержимое новой ячейки числа в ячейку ленты там, где была головка.
6. Обнуляем ячейки состояния головки и состояния движения. Ячейки состояния числа сохраняем(там остаточная информация (ее не обнуляем)).
7. Далее повторяем пункты 3÷6 пока состояние головки не станет максимальным (равным наибольшей строке таблицы автомата Тьюринга +1).
8. Если состоянии головки равно наибольшей строке таблицы+1, то изменяем положение программы на “2” и останавливаемся.
1.3 Определимся (ориентировочно) с информационными ячейками на листе Excel и добавим управляющие формулы. Должно быть следующее:
1. Таблица автомата Тьюринга для всех элементов алфавита и всех состояний головки (кроме состояния останова программы - обычно его не пишут ввиду повторяемости ячеек с одинаковым содержимым). (ячейки A1-J5(по диагонали)) управляющие формулы не нужны (мы будем ссылаться на эту таблицу) (рис 8).
2. Ячейка Пуск (ячейка B11) →управляющие формулы не нужны (в нее будем вносит 0 или 1 вручную).
3. Ячейка Шаг (ячейка B13)→вносим формулу.
|
|
=ЕСЛИ( D11=2;"конец";ЕСЛИ(D11;ЕСЛИ(C11=1;СУММ(B13;1);B13);"начало"))
Блок-схема действия формулы представлена на рисунке 9:
4. Изображение ленты с заданным на ней числом→ указываем вручную заданное число в любом месте ленты (ячейки B16-AH16).
5. Изображение начального положения головки (обязательно над числом в любом месте) цифрой 1-указываем вручную. (ячейки B17-AH17)
6. Изображение действующей ленты с ячейками состояния (для ячейки B20)
=ЕСЛИ($D$11=2;B20;ЕСЛИ($D$11;ЕСЛИ($C$11=4;;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$J$5;ПОИСКПОЗ(B23;$A$1:$J$1;)+1;);B20);B20));))
Блок-схема действия формулы представлена на рисунке 10:
Необходимо заполнить подобными формулами ячейки B20-AH20с учетом их относительных адресов.
У адресов ячеек где проставлен знак $ при протаскивании адреса не изменяться.
7. Изображение действующей ленты с ячейками движения(для ячейки B21)
=ЕСЛИ($D$11=2;B21;ЕСЛИ($D$11;ЕСЛИ($C$11=4;;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$J$5;ПОИСКПОЗ(B23;$A$1:$J$1;)+2;);B21);B21));))
Блок-схема действия формулы представлена на рисунке 11:
Необходимо заполнить подобными формулами ячейки B21-AH21 с учетом их относительных адресов .
8. Изображение действующей ленты с ячейками числа (для ячейки B22)
=ЕСЛИ($D$11=2;B22;ЕСЛИ($D$11;ЕСЛИ($C$11=4;B22;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$J$5;ПОИСКПОЗ(B23;$A$1:$J$1;););B22);B22));ЕСЛИ(B16="";"x";B16)))
|
|
Блок-схема действия формулы представлена на рисунке 12.
Необходимо заполнить подобными формулами ячейки B22-AH22с учетом их относительных адресов.
9. Изображение действующей ленты с ячейками текущего числа ленты (для ячейки B23)
=ЕСЛИ($D$11=2;B23;ЕСЛИ($D$11;ЕСЛИ($C$11=3;B22;B23);B22))
Блок-схема действия формулы представлена на рисунке 13:
Необходимо заполнить подобными формулами ячейки B23-AH23 с учетом их относительных адресов.
10.Ячейки номера состояния головки (для ячейки B24)
=ЕСЛИ($D$11=2;B24;ЕСЛИ($D$11=1;ЕСЛИ($C$11=2;ЕСЛИ(A21=1;A20;ЕСЛИ(C21=-1;C20;));B24);B17))
Блок-схема действия формулы представлена на рисунке 14:
Необходимо заполнить подобными формулами ячейки B24-AH24 с учетом их относительных адресов.
11. Ячейка для промежуточной информации о положении программы (ячейка D11) =ЕСЛИ(B11;ЕСЛИ(МАКС(B24:AH24)=МАКС($A$3:$A$7)+1;2;B11);)
Блок-схема действия формулы представлена на рисунке 15:
12. Ячейка для промежуточной информации о шаге выполнения (ячейка С11) =ЕСЛИ(D11;ЕСЛИ(C11=4;1;C11+1);1)
Блок-схема действия формулы представлена на рисунке 16:
1.4 Применим условное форматирование для выделения ячеек цветом и придание анимационного эффекта работы действующей модели.
1.4.1 Ячейка B11(старт)- Условное форматирование → Создать правило→ Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат правила:
=$B$13="конец"
В разделе “Применяется к” добавим:=$B$13:$C$13;$B$11
В качестве формата выбираем красную заливку.
Создаем здесь второе правило→Создать правило→Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат правила.
В нашем случае, условием будет формула: =$B$13="начало"
В разделе “Применяется к” добавим:=$B$13:$C$13;$B$11
В качестве формата выбираем желтую заливку.
1.4.2.Ячейка B13 (Счетчик тактов) Условное форматирование → Создать правило→ Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат для правила.
В нашем случае, условием будет формула: =$B$13="конец"
В разделе “Применяется к” добавим:=$B$13:$C$13;$B$11
В качестве формата выбираем красную заливку.
Создаем здесь второе правило→Создать правило→Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат для нашего правила.
В нашем случае, условием будет формула: =$B$13="начало"
В разделе “Применяется к” добавим:=$B$13:$C$13;$B$11
В качестве формата выбираем желтую заливку.
3. Ячейка B23 (лента)→ Условное форматирование → Создать правило→ Форматировать только ячейки, которые содержат.
В поле Измените описание правила задаем условия и формат для правила.
В первом разделе выберем: Значение ячейки
Во втором разделе выберем: Равно
В нашем случае, условием будет формула: ="x"
В качестве формата выбираем серую заливку.
В разделе “Применяется к” добавим:=$B$23:$AH$23
4. Ячейка B24 (головка). Условное форматирование → Создать правило→ Использовать формулу для определения форматируемых ячеек.
В поле Измените описание правила задаем условия и формат для правила.
В нашем случае, условием будет формула: =B24=МАКС($A$3:$A$10)+1
В разделе “Применяется к” добавим:=$B$24:$AH$24
В качестве формата выбираем красную заливку.
Создаем второе правило→Создать правило→Форматировать только ячейки, которые содержат.
В поле Измените описание правила задаем условия и формат для правила.
В первом разделе выберем: Значение ячейки
Во втором разделе выберем: Больше
В нашем случае, условием будет формула: =0
В качестве формата выбираем темно-красную заливку.
В разделе “Применяется к” добавим:=$B$24:$AH$24
Дата добавления: 2018-08-06; просмотров: 381; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!