МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образовании
“Ижевский государственный технический университет имени М.Т.Калашникова” (ИжГТУ)
Кафедра «Конструирование радиоэлектронной аппаратуры»
Приборостроительный факультет
Лабораторная работа № 1
Создание имитационных моделей абстрактных автоматов Тьюринга и Маркова средствами Excel MS Office.
Выполнил работу: Симанов В.В.
Проверил работу: О.Я. Шамсиахметов
Группа:Б21-071-1
Цель работы: Создать имитационную модель абстрактных автоматов Тьюринга и Маркова средствами Excel MS Office.
Машина Тьюринга
Название задачи: A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть.
Ход работы: Составил таблицу для нахождения всех решений данной задачи. В Microsoft Excel создал имитационную модель машины Тьюринга для решения данной задачи.
Алгоритм решения: 1) Перетащим головку в левую сторону до пустой клетки.
1.1) Перетащим головку на 1 клетку вправо на конец слова
2) Если последний символ не единица то удаляем цифры до первой появившейся единицы
3) Все последующие элементы оставить без изменения 
Основные формулы:
1) B13 Ячейка Шаг
=ЕСЛИ(
D11=2;"конец";ЕСЛИ(D11;ЕСЛИ(C11=1;СУММ(B13;1);B13);"начало"))
2) C11 Ячейка для промежуточной информации о шаге выполнения
=ЕСЛИ(D11;ЕСЛИ(C11=4;1;C11+1);1)
3) D11 Ячейка для промежуточной информации о положении программы
=ЕСЛИ(B11;ЕСЛИ(МАКС(B24:AH24)=МАКС($A$3:$A$7)+1;2;B11);)
4) B20-AH20 Изображение действующей ленты с ячейками состояния
=ЕСЛИ($D$11=2;B20;ЕСЛИ($D$11;ЕСЛИ($C$11=4;;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$M$5;ПОИСКПОЗ(B23;$A$1:$M$1;)+1;);B20);B20));))
5) B21-AH21 Изображение действующей ленты с ячейками движения
=ЕСЛИ($D$11=2;B21;ЕСЛИ($D$11;ЕСЛИ($C$11=4;;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$M$5;ПОИСКПОЗ(B23;$A$1:$M$1;)+2;);B21);B21));))
6) B22-AH22 Изображение действующей ленты с ячейками числа
=ЕСЛИ($D$11=2;B22;ЕСЛИ($D$11;ЕСЛИ($C$11=4;B22;ЕСЛИ($C$11=1;ЕСЛИ(B24;ВПР(B24;$A$3:$M$5;ПОИСКПОЗ(B23;$A$1:$M$1;););B22);B22));ЕСЛИ(B16="";"x";B16)))
7) B23-AH23 Изображение действующей ленты с ячейками текущего числа ленты
=ЕСЛИ($D$11=2;B23;ЕСЛИ($D$11;ЕСЛИ($C$11=3;B22;B23);B22))
8) B24-AH24 Ячейки номера состояния головки
=ЕСЛИ($D$11=2;B24;ЕСЛИ($D$11=1;ЕСЛИ($C$11=2;ЕСЛИ(A21=1;A20;ЕСЛИ(C21=-1;C20;));B24);B17))
Нормальные алгоритмы Маркова (НАМ)
Название задачи: A={f,h,p}. В слове P заменить все пары «ph» на «f».
Алгоритм решения:
1) Начальное положение программы “0” →вводим исходное слово заполняем таблицу формул подстановки (последовательность формул не менять, иначе измениться алгоритм).
2) Запускаем программу →положение программы “1”.
3) Проверяем вхождение (совпадение) левой части первой формулы подстановки и какой-то части исходного слова (а может быть и всего слова). Проверка осуществляется в исходном слове слева направо до момента первого совпадения (таких совпадений может быть несколько или ни одного, но нас интересует пока только первое совпадение).
4) Если нет совпадений в первой формуле, тогда переходим ко второй формуле подстановки.
5) Если ни одна формула подстановки не подошла, тогда останов и вывод конечного слова.
6) Если есть совпадение, тогда заменяем левую часть использованной формулы на правую часть этой же формулы в исходном слове (всю правую часть на всю левую независимо от количества символов). Возможно подстановка “пустоты”, то есть отсутствия левой и/или правой части, что равносильно удалению символов (если правая часть “пустота”) или вставке новых символов (если левая часть-“пустота”).
7) Если было совпадение, тогда проверяем маркер останова у использованной формулы подстановки в таблице НАМ - если есть (символ “!”), тогда останавливаем программу и выводим конечное слово, если нет (“символ пустота”), тогда продолжаем программу алгоритма подстановки.
8) Проверяем совпадение, начиная опять с первой формулы в модифицированном слове (результат от предыдущего шага подстановки).
9) Если нет совпадений в первой формуле, тогда переходим ко второй формуле подстановки.
10) Если ни одна формула подстановки не подошла, тогда останов и выводим конечное слово.
11) Если есть совпадение, тогда заменяем левую часть использованной формулы на правую часть этой же формулы в исходном слове. Возможно подстановка “пустоты”, то есть отсутствия левой и/или правой части, что равносильно удалению символов (если правая часть “пустота”) или вставке новых символов (если левая часть-“пустота”).
12) Если было совпадение, тогда проверяем маркер останова у использованной формулы подстановки в таблице НАМ - если есть (символ “!”), тогда останавливаем программу и выводим конечное слово, если нет (“символ пустота”), тогда продолжаем программу алгоритма подстановки.
13) Повторяем пункты 8-12 до полного останова (нет ни одного совпадения в модифицированном слове).
Ход работы:
1. Оформить таблицу формул алгоритма:
В столбике Номер (адреса A1÷A3) пересчитать построчно,начиная с 1,все номера используемых формул. У нас 1-2.
В столбике Левая часть (адреса B1÷B3) указать левые части используемых формул по мере их использования (порядок важен) У нас ph-пусто (ячейка остается пустой. Если есть 0, то его надо убрать клавишей Delete).
В столбике Правая часть (адреса C1÷C3) указать правые части используемых формул, соответствующих левым частям. У нас f-пусто.
В столбике Маркер останова (адреса D1÷D3) останова указать символ “!”, если формула после выполнения должна остановиться (может быть несколько маркеров или не одного).У нас пусто-!.
Для повышения наглядности необходимо выделить контуры ячеек таблицы толщиной и цветом по своему вкусу. Это делается командой Меню→Главная→Шрифт→Границы.
2. Оформить вспомогательную таблицу запуска программы:
Ячейка F1-содержимое “запуск программы”
Ячейка G1-содержимое “старт”
Ячейка G2-содержимое “0” (первоначально. Далее при запуске программы оно меняется вручную на 1)
Ячейка H1-содержимое “шаг”
Ячейка F2-содержимое
=ЕСЛИ($G$2;ЕСЛИ(СЧЁТЕСЛИ(F10:F40;"Конечное слово");"конец";"начало");"'' 1--> старт''")
(набирать в ячейке по нажатию клавиши =,(тогда = в самой формуле не нужно набирать) и закончит набор клавишей Enter).
Ячейка H2-содержимое
=ЕСЛИ(G2;ЕСЛИ(H2=100;1;H2+1);0)
Для повышения наглядности необходимо выделить контуры ячеек таблицы толщиной и цветом по своему вкусу. Это делается командой Меню→Главная→Шрифт→Границы.
Для ячейки F2 ввести первое условное форматирование цветом и шрифтом.Для этого выделяем ячейку F2 и в меню выполняем команды Главная→Условноеформатирование→Управлениеправилами→Создатьправило→Использовать формулу для форматируемых ячеек →набрать формулу =$F$2=”начало”
и выбрать цвет и шрифт (у нас цвет желтый и шрифт по умолчанию), а также в графе Применяется к добавить
=$F$2
Для ячейки F2 ввести второе условное форматирование цветом и шрифтом.Для этого выделяем ячейку F2 и в меню выполняем команды Главная→Условноеформатирование→Управлениеправилами→Создатьправило→Использовать формулу для форматируемых ячеек →набрать формулу =$F$2=”конец”
и выбрать цвет и шрифт (у нас цвет красный и шрифт по умолчани ю), а также в графе Применяется к добавить
=$F$2
3. Создаем таблицу исходной задачи.
Создается таблица на любом пустом месте в виде двух столбиков (Задано слово и Получить слово).В единственной строке указываем данные задачи(у нас pphhhphp и pfhhfp). Оформляем таблицу по своему вкусу согласно предыдущим настройкам.
4. Оформляем таблицу решений.
Ячейка F9 -содержимое “ Исходное слово ”
Ячейка G9 -содержимое “ Метка останова ”
Ячейка F10 -содержимое “ pphhhphp ”
Ячейка G10 -содержимое “ 0 ”
Ячейка F11 -содержимое =ЕСЛИ($H$2>=СЧЁТЗ($F$11:F11);ЕСЛИ(G10=1;"Конечное слово";ЕСЛИ(ЕЧИСЛО(ПОИСК($B$2;F10;1));ЗАМЕНИТЬ(F10;ПОИСК($B$2;F10;1);ДЛСТР($B$2);$C$2);ЕСЛИ(ЕЧИСЛО(ПОИСК($B$3;F10;1));ЗАМЕНИТЬ(F10;ПОИСК($B$3;F10;1);ДЛСТР($B$3);$C$3);ЕСЛИ(ЕЧИСЛО(ПОИСК($B$4;F10;1));ЗАМЕНИТЬ(F10;ПОИСК($B$4;F10;1);ДЛСТР($B$4);$C$4);ЕСЛИ(ЕЧИСЛО(ПОИСК($B$5;F10;1));ЗАМЕНИТЬ(F10;ПОИСК($B$5;F10;1);ДЛСТР($B$5);$C$5);"стоп")))));"")
Так как ячейка F11 содержит много формул, ее необходимо тщательно проверить на предмет ошибок. Дальше необходимо повторить с некоторыми изменениями содержание этой ячейки в ячейках F12-F**( количество определяется шагами программы (взять по своему усмотрению с запасом (запас можно легко отрегулировать добавлением или удалением ячеек))).
Чтобы избежать ошибок необходимо воспользоваться приемом Excel протаскивание.
Для этого надо выделить ячейку F11 и за правый нижний край (при появление на углу крестика нажать левую клавишу мышки) протащить до желаемой нижней ячейки и отпустить кнопку мышки. Все ячейки будут заполнены с требуемыми изменениями. Необходимо помнить, что адреса ячеек со знаками $ не меняются от протаскивания. У нас необходимо заполнить ячейки по F18.
Ячейка G11-содержимое
=ЕСЛИ(F11="Конечное слово";1;ЕСЛИ(ЕЧИСЛО(ПОИСК($B$2;F10;1));ЕСЛИ(И(ЕЧИСЛО(ПОИСК($B$2;F10;1));ЕТЕКСТ($D$2));1;0);ЕСЛИ(ЕЧИСЛО(ПОИСК($B$3;F10;1));ЕСЛИ(И(ЕЧИСЛО(ПОИСК($B$3;F10;1));ЕТЕКСТ($D$3));1;0);ЕСЛИ(ЕЧИСЛО(ПОИСК($B$4;F10;1));ЕСЛИ(И(ЕЧИСЛО(ПОИСК($B$4;F10;1));ЕТЕКСТ($D$4));1;0);ЕСЛИ(ЕЧИСЛО(ПОИСК($B$5;F10;1));ЕСЛИ(И(ЕЧИСЛО(ПОИСК($B$5;F10;1));ЕТЕКСТ($D$5));1;0);0)))))
Заполняем ячейки методом протаскивания для G11÷G18.
Ячейка E11 -содержимое
=ЕСЛИ($H$2>=1;"шаг " & ЕСЛИ(ЕПУСТО(F11);"";СЧЁТЗ($F$11:F11));"")
Заполняем ячейки методом протаскивания для E11÷E18.
Для ячеек F11÷F18 применим условное форматирование цветом и шрифтом.
Для этого выделим ячейку F11 и в меню выполняем команды Главная→Условноеформатирование→Управлениеправилами→Создатьправило→Использовать формулу для форматируемых ячеек →набрать формулу
=$F$11=”Конечное слово”
и выбрать цвет и шрифт (у нас цвет красный и шрифт по умолчанию), а также в графе Применяется к добавить
=$F$11:$F$18)
Для наглядности вспомогательные ячейки G9÷G18 сделаем невидимыми для пользователя. Для этого надо выделить эти ячейки и нажать правую клавишу мышки→ Форматячеек → Цвет →установить “ Белый ” (то есть они сольются с фоном ячеек)→ Enter.
5. Запускаем программу вводом в ячейку G2 цифры “ 1 ” и нажать клавишу Enter. В соседней ячейке H2 появиться цифра 1 (выполниться первый цикл итераций).
Для продолжения шагов необходимо нажимать многократно клавишу F9 в верхней части клавиатуры компьютера.
Если при оформлении модели программа Excel выдаст предупреждение и недопустимых циклических ссылках, необходимо в Главное меню→Параметры→Формулы→Включить итеративные вычисления (установить шаг итерации 1 (за одно нажатие клавиши F9 будет совершаться один шаг)).
Вывод:
Мы научились создавать имитационные модели абстрактных автоматов Тьюринга и Маркова средствами ExcelMSOffice. Эти абстрактные автоматы не требуют оптимизации, так как они являются простейшими.