Составление имитационной модели нормального алгоритма Маркова (НАМ).

 

Для моделирования задачи используем средства программы 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 в единичной системе, получить в этой же системе число 2ⁿ.

33.A={ | }. Пусть слово Р является записью числа 2ⁿ (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 в единичной системе, получить в этой же системе число 2ⁿ.

41.A={ | }. Пусть слово Р является записью числа 2ⁿ (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.