Составление имитационной модели нормального алгоритма Маркова (НАМ).
Для моделирования задачи используем средства программы Excel Microsoft Office.
Необходимо построить модель на листе табличного редактора, используя возможности встроенных функций и условного форматирования.
 |
Возможный вариант модели представлен на рисунке 12. (адреса ячеек не менять иначе неправильно будет работать программа) .
Необходимо выполнить следующее:
1. Оформить таблицу формул алгоритма (рис 26).
В столбике Номер(адреса A1÷A5) пересчитать построчно ,начиная с 1 ,все номера используемых формул . У нас 1-2-3-4.
В столбике Левая часть (адреса B1÷B5) указать левые части используемых формул по мере их использования (порядок важен) У нас %a-%b-%-пусто (ячейка остается пустой. Если есть 0 , то его надо убрать клавишей Delete).
В столбике Правая часть (адреса C1÷C5) указать правые части используемых формул , соответствующих левым частям. У нас a%-b%-a-%
В столбике Маркер останова (адреса D1÷D5) останова указать символ “!”, если формула после выполнения должна остановиться (может быть несколько маркеров или не одного).У нас пусто-пусто-!-пусто.
Для других задач количество строк (формул) может быть больше или меньше. Поэтому для других задач необходимо таблицу откорректировать.
Для повышения наглядности необходимо выделить контуры ячеек таблицы толщиной и цветом по своему вкусу. Это делается командой Меню→Главная→Шрифт→Границы.
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. Создаем таблицу исходной задачи.
Создается таблица на любом пустом месте в виде двух столбиков (Задано слово и Получить слово).В единственной строке указываем данные задачи(у нас bbab и bbaba).Оформляем таблицу по своему вкусу согласно предыдущим настройкам.
4. Оформляем таблицу решений.
Ячейка F9-содержимое “Исходное слово”
Ячейка G9-содержимое “Метка останова”
Ячейка F10-содержимое “bbab”
Ячейка 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.
Общий вид модели показан на рисунке 27:
 |
5. Запускаем программу вводом в ячейку G2 цифры “1” и нажать клавишу Enter. В соседней ячейке H2 появиться цифра 1 (выполниться первый цикл итераций).
Для продолжения шагов необходимо нажимать многократно клавишу F9 в верхней части клавиатуры компьютера .
Если при оформлении модели программа Excel выдаст предупреждение и недопустимых циклических ссылках, необходимо в Главное меню→Параметры→Формулы→Включить итеративные вычисления (установить шаг итерации 1 (за одно нажатие клавиши F9 будет совершаться один шаг)).
Содержание отчета:
(отчет предоставить индивидуально в бумажном и электронном виде на носителе).
1.Решение 2-х задач для самостоятельного решения.
2.Текстовый алгоритм работы Машины Тьюринга для конкретной задачи.
3.Текстовый алгоритм работы нормального алгоритма Маркова (НАМ) для конкретной задачи.
4.Скриншоты имитационной модели машины Тьюринга с описанием управляющих формул.
5.Скриншоты имитационной модели нормального алгоритма Маркова (НАМ) с описанием управляющих формул.
6.Действующие модели в электронном виде в программе Microsoft Office Excel .
7.Рекомендации по оптимизации предложенных моделей.
Контрольные вопросы:
1. Абстрактный автомат - машина Тьюринга.
2.Определение нормального алгоритма Маркова.
3.Электронные таблицы Excel Microsoft Office.
4.Встроенные и пользовательские функции Excel.
5.Условное форматирование в Excel.
6.Принципы составления текстовых алгоритмов.
7.Составление управляющих вложенных формул в Excel.
8.Имитационные модели абстрактных автоматов.
9.Организация итерационных вычислений в Excel.
10.Достоинство и недостатки программирования с использованием
ресурсов Excel.
11.Способы корректировки моделей для решения различных задач.
Задачи для самостоятельного решения по автомату Тьюринга.
Замечания:
В задачах рассматриваются только целые неотрицательные числа.
Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа; например: 2→ | | , 5 → | | | | | , 0 → <пустое слово>.
1.A={a,b}. Для непустого слова Р определить, входит ли в него ещё раз его первый символ. Ответ: а (да) или пустое слово.
2.A={a,b}. В непустом слове Р поменять местами его первый и последний символы.
3.A={a,b}. Заменить в Р каждое вхождение а на bb.
4. A={a,b}. Перевернуть слово P (например: abb → bba).
5.A={a,b,c}. Заменить в Р каждое вхождение ab на с.
6.A={a,b,c}. Заменить на а каждый второй символ в слове Р.
7. A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять).
8. A={a,b}. Пусть слово Р имеет нечётную длину. Удалить из него средний символ.
9. A={a,b,c}. Оставить в слове P только последний символ (пустое слово не менять).
10. A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.
11. A={a,b,c}. Пусть P имеет нечётную длину. Оставить в P только средний символ.
12. A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет).
13. A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.
14. A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).
15. A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово 0.
16. A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть.
17. A={0,1}. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, в двоичной системе счисления. Ответ: слово 1 (является) или слово 0.
18. A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.
19. A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: 101 → 10100).
20. A={a,b,c}. Если P - слово чётной длины (0, 2, 4,…), то выдать ответ a, иначе - пустое слово.
21. A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.)
22. A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём только левую половину.
23. A={0,1}. Считая непустое слово Р записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.)
24. A={0,1,2,3}. Считая непустое слово Р записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе.
25. A={ | }. Считая слово Р записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.)
26. A={0,1,2}. Считая непустое слово Р записью числа в троичной системе счисления, получить запись этого числа в единичной системе.
27. A={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.
28. A={a,b,c}. Удвоить каждый символ в слове P (например: bacb → bbaaccbb).
29. A={0,1,2}. Считая непустое слово P записью положительного троичного числа, уменьшить это число на 1.
30. A={a,b}. Определить, является ли слово Р палиндромом (перевёртышем, симметричным словом). Ответ: слово а, если является, или пустое слово иначе.
31. A={ | }. Считая слово Р записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27,…). Ответ: пустое слово, если является, или слово из одной палочки иначе.
32. A={ | }. Считая слово Р записью числа n в единичной системе, получить в этой же системе число 2n.
33.A={ | }. Пусть слово Р является записью числа 2n (n=0, 1, 2, в единичной системе. Получить в этой же системе число n.
34. Пусть P имеет вид Q=R, где Q и R - любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.
35. Пусть P имеет вид Q=R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
36. Пусть P имеет вид Q>R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.
Задачи для самостоятельного решения по НАМ.
Замечания:
В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.
Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа; например: 2→| | , 5 →| | | | | , 0 →<пустое слово>.
1.A={f,h,p}. В слове P заменить все пары ph на f.
2.A={f,h,p}. В слове P заменить на f только первую пару ph, если такая есть.
3. A={ | }. Считая слово Р записью положительного числа в единичной системе счисления, уменьшить это число на 1.
4. A={ | }. Считая слово Р записью числа в единичной системе счисления, увеличить это число на 2.
5. A={a,b,c}. Определить, входит ли символ а в слово Р. Ответ (выходное слово): словоа, если входит, или пустое слово, если не входит.
6. A={a,b}. Если в слово Р входит больше символов а, чем символов b, то в качестве ответа выдать слово из одного символа а, если в Р равное количество а и b, то в качестве ответа выдать пустое слово, а иначе выдать ответ b.
7. A={0,1,2,3}. Преобразовать слово Р так, чтобы сначала шли все чётные цифры (0 и 2), а затем - все нечётные.
8. A={a,b,c}. Преобразовать слово Р так, чтобы сначала шли все символы а, затем - все символы b и в конце - все символы с.
A={a,b,c}. Определить, из скольких различных символов составлено слово Р; ответ получить в единичной системе счисления (например: асаас → | | ).
9. A={a,b,c}. В непустом слове Р удвоить первый символ, т.е. приписать этот символ слева к Р.
10. A={a,b,c}. За первым символом непустого слова Р вставить символ с.
11. A={a,b,c}. Из слова Р удалить второй символ, если такой есть.
12. A={a,b,c}. Если в слове Р не менее двух символов, то переставить два первых символа.
13. A={0,1,2}. Считая непустое слово Р записью троичного числа, удалить из этой записи все незначащие нули.
14. A={a,b,c}. Удалить из непустого слова Р его последний символ.
15. A={a,b}. В словеР все символы а заменить на b, а все (прежние) символы b - на а.
16. A={a,b,c}. Удвоить каждый символ в слове P (например: bacb → bbaaccbb).
17. A={a,b}. Приписать справа к слову P столько палочек, сколько всего символов входит в P (например: babb → babb |).
18. A={a,b}. Пусть словоP имеет чётную длину (0, 2, 4, _). Удалить правую половину этого слова. (Рекомендация: использовать решение предыдущей задачи.)
19. A={a,b}. Пусть длина слова P кратна 3. Удалить правую треть этого слова.
20. A={a,b}. Приписать справа к слову P столько палочек, со скольких подряд идущих символов a начинается это слово (например: aababa →aababa| | ).
21. A={a,b,c}. Удалить из слова P второе вхождение символа a, если такое есть.
22. A={a,b,c}. Удалить из слова P третье вхождение символа a, если такое есть.
23. A={a,b,c}. Оставить в слове P только первое вхождение символа a, если такое есть.
24. A={a,b}. Если слово P содержит одновременно символы a и b, то заменить P на пустое слово.
25. A={a,b,c}. Если буквы в непустом слове P не упорядочены по алфавиту, то заменить P на пустое слово, а иначе P не менять.
26. A={a,b,c}. ЕслиP отлично от слова abaca, то заменить его на пустое слово.
27. A={0,1,2,3}. Считая непустое слово P записью четверичного числа, проверить, чётно оно или нет. Ответ: слово 0, если чётно, и слово 1 иначе.
28. A={0,1,2}. Считая непустое слово P записью троичного числа, увеличить это число на 1.
29. A={0,1,2}. Считая непустое слово P записью положительного троичного числа, уменьшить это число на 1.
30. A={ | }. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.)
31. A={0,1,2}. Считая непустое слово Р записью числа в троичной системе, получить запись этого числа в единичной системе.
32. A={a,b,c}. Определить, входит ли первый символ непустого слова Р ещё раз в это слово. Ответ: слово а, если входит, или пустое слово иначе.
33. A={a,b}. Перенести первый символ непустого слова Р в конец слова.
34. A={a,b}. Перенести последний символ непустого слова Р в начало слова.
35. A={a,b}. В непустом слове Р переставить первый и последний символы.
36. A={a,b}. Если в непустом слове Р совпадают первый и последний символы, то удалить оба этих символа, а иначе слово не менять.
37. A={a,b}. Определить, является ли слово Р палиндромом (перевёртышем, симметричным словом). Ответ: слово а, если является, или пустое слово иначе.
38. A={a,b}. Пусть слово Р имеет нечётную длину. Удалить из него средний символ.
39. A={ | }. Считая слово Р записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27,…). Ответ: пустое слово, если является, или слово из одной палочки иначе.
40. A={ | }. Считая слово Р записью числа n в единичной системе, получить в этой же системе число 2n.
41.A={ | }. Пусть слово Р является записью числа 2n (n=0, 1, 2, в единичной системе. Получить в этой же системе число n.
42. A={a,b}. Перевернуть слово P (например: abb → bba).
43. Пусть P имеет вид Q=R, где Q и R - любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.
44. Пусть P имеет вид Q=R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
45. Пусть P имеет вид Q>R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.
Рекомендуемая литература.
1. Н.Т.Когабаев, Лекции по теории алгоритмов. учебное пособие-Новосибирск, Издательство Новосибирского государственного университета, 2009г - 107с.
2. Л.В.Рудикова, Microsoft Word для студента- Санкт-Петербург, Издательство БХВ,2011– 400с.
3. И.Пащенко, Word 2007 (Шаг за шагом).- Санкт-Петербург, Издательство Питер,2008– 464с.
4. З.В.Алферова, Теория алгоритмов - Москва,Издательство “Статистика”, 1973г-137с.
5. В.С. Пташинский, Самоучитель Office 2013– Москва, Издательство Эксмо, 2013. – 288с.
6. О.В.Спиридонов, Microsoft Office для пользователя– Москва, Издательство Эксмо, 2013– 350с.
7. Н.В.Макарова, В.Б. Волков, Информатика – Санкт-Петербург, Издательство Питер, 2011– 576с.
8. Г.Н.Хубаев, С.М. Патрушина, Н.Г. Савельева, Е.Г. Веретенникова, Информатика– Ростов-на-Дону, Издательство Феникс, 2010– 288с.
9. Ю.И.Кудинов, Ф.Ф. Пащенко, А.Ю. Келина, Практикум по основам современной информатики – Санкт-Петербург, Издательство Лань, 2011– 352 с.
10. Ю.И. Кудинов ,Ф.Ф. Пащенко, Основы современной информатики– Санкт-Петербург, Издательство Лань , 2011– 256 с.
11.А.В. Гураков, Информатика. Введение в Microsoft Office –Томск, издательство Эль Контент, 2012– 120с.
12. А.С.Грошев, Информатика. учебник для вузов - Архангельск, издательство Архангельского государственного технического университета,2010-470с.
13. Э.З. Любимский, В.В. Мартынюк, Н.П. Трифонов. Программирование. - М., "Наука", 1980.
14. Л.С. Корухова, М.Р. Шура-Бура. Введение в алгоритмы (учебное пособие для студентов 1 курса) - М., Издательский отдел факультета ВМК МГУ, 1997.
15. А. А. Марков, Н.М. Нагорный. Теория алгоритмов. - М., ФАЗИС, 1996.