Создание имитационных моделей абстрактных автоматов Тьюринга и Маркова

При создании условного форматирования можно ссылаться на другие ячейки только в пределах одного листа; нельзя ссылаться на ячейки других листов одной и той же книги или использовать внешние ссылки на другую книгу;

При изменении цвета заливки ячеек, цвета шрифта, границ, форматирования текста при помощи условного форматирования - изменения, сделанные при помощи стандартного форматирования не будут отображаться в ячейках, форматы которых были изменены условным форматированием.

Условное форматирование позволяет применять форматирование ячеек избирательно или автоматически на основании их значений.

К примеру, можно задать условное форматирование таким образом, чтобы все ячейки с отрицательными значениями закрашивались в красный цвет. Когда вы вводите или меняете значение в ячейке, Excel проверяет его и сравнивает с условиями, заданными в правилах. Если значение отрицательное, фон ячейки закрасится, иначе останется без изменений.

Условное форматирование - это простой способ определить ячейки с ошибочными записями или значениями определённого типа. Вы можете использовать формат (например, красная заливка), чтобы легко идентифицировать определенные ячейки.

Размещено на http://www.allbest.ru/

12

При нажатии кнопки Условное форматирование, которая находится в группе Стили вкладки Главная, вы появляется выпадающее меню со следующими опциями:

Правила выделения ячеек открывает дополнительное меню с различными параметрами для определения правил форматирования ячеек, содержащих конкретные значения или находится в определенном диапазоне.

Правила отбора первых и последних значений открывает опции, позволяющие задавать формат ячейкам на основании вхождения их в топ первых или последних элементов.

Гистограмма открывает палитру гистограмм различных цветов, которые вы можете задать для выбранных ячеек, для визуализации значений, содержащихся в этих ячейках.

Цветовые шкалы позволяет задавать двух- и трехцветовые шкалы для цвета фона ячейки на основе ее значения относительно других ячеек в диапазоне

Наборы значков отображает значок в ячейке. Какой именно значок отображается, зависит от значения ячейки относительно других ячеек. Excel предоставляет 20 наборов значков на выбор (при этом вы можете смешивать и сочетать значки из разных наборов). Количество значков в наборах колеблется от трех до пяти.

Создать правило открывает диалоговое окно Создание правила форматирования, которое позволяет создать пользовательское условное форматирование для выбранных ячеек.

Удалить правила открывает дополнительное меню, где вы можете удалить правила условного форматирования как для выбранных ячеек, так и на всем листе.

Управление правилами открывает диалоговое окно Диспетчер правил условного форматирования, которое позволяет редактировать и удалять определенные правила, а также задавать приоритет, передвигая вниз и вверх по списку правил.

Рассмотрим пример создания правила изменения формата ячейки на красную заливку с темно-красным шрифтом при условии, если значение ячейки содержит слово Нет.

Размещено на http://www.allbest.ru/

12

Выделим диапазон ячеек, к которому применяется условное форматирование. Переходим по вкладке Главная в группу Стили, щелкаем кнопку Условное форматирование › Правила выделения ячеек › Текст содержит (Рис 3):

В появившемся диалоговом окне Текст, который содержит в левом текстовом поле необходимо задать фрагмент текста, который будет условием для применения формата к ячейке, указанного в правом выпадающем списке. В нашем случае - это Светло-красная заливка и темно-красный текст.

Щелкаем ОК, чтобы наше правило вступило в силу.

Рассмотрим еще один пример:

Применить три различных условных форматирования к одному и тому же диапазону ячеек: первый тип формата, когда ячейка содержит целевое значение, второй - когда больше цели и третий - когда меньше. Желая заливка с темно-желтым текстом для ячеек содержащих значение 95, Зеленая заливка с темно-зеленым текстом для ячеек со значениями больше 95 и Светло-красная заливка и темно-красным текстом для ячеек меньше 95.

Размещено на http://www.allbest.ru/

12

Выделяем диапазон ячеек, к которому мы хотим применить три различных правила условного форматирования. Начнем с создания правила для ячеек, содержащих значение равное 95. Переходим по вкладке Главная в группу Стили, щелкаем кнопку Условное форматирование -> Правила выделения ячеек -> Равно (рис 4).

Excel откроет диалоговое окно Равно, где в левом текстовом поле необходимо указать условие 95, а в правом выпадающем списке выбрать формат для этого условия Желтая заливка с темно-желтым текстом.

Размещено на http://www.allbest.ru/

12

Далее задаем условное форматирование для значений больше 95. Из меню Условное форматирование › Правила выделения ячеек выбираем Больше, в появившемся диалоговом окне Больше указываем значение, выше которого ячейка будет закрашиваться в зеленый цвет, и сам формат (рис 5).

Аналогичную операцию проделываем для ячеек со значениями меньше 95. На этот раз из списка правил необходимо выбрать Меньше и задать формат с красной заливкой.

Размещено на http://www.allbest.ru/

12

По мере того, как вы будете определять все три правила для диапазона, ячейки будут закрашиваться в определенный цвет. В итоге мы получим, примерно такую картину (рис 6).

Обратите внимание, что если ячейка будет пустой, она тоже будет закрашиваться в красный цвет, предполагая, что значение ячейки меньше 95.

Excel предлагает большое количество готовых правил. Но можно задать свое собственное правило на основе формулы. Например, есть таблица с данными по дням и необходимо, чтобы ячейки с выходными днями (суббота и воскресенье) закрашивались.

Выделяем таблицу с данными, к которой мы хотим применить условное форматирование. Переходим по вкладке Главная в группу Стили, щелкаем кнопку Условное форматирование › Создать правило. В появившемся диалоговом окне Создание правила форматирования в поле Выберите тип правила выбираем Использовать формулу для определения форматируемых ячеек.

В поле Измените описание правила задаем условия и формат для нашего правила.

В нашем случае, условием будет формула: =ИЛИ(ДЕНЬНЕД($A2;2)=6;ДЕНЬНЕД($A2;2)=7).

В качестве формата выбираем темно- красную заливку (рис 7).

Размещено на http://www.allbest.ru/

12

Условное форматирование является полезным инструментом для визуализации числовых данных. В ряде случаев условное форматирование является реальной альтернативой создания диаграммы.

Практическая часть лабораторной работы

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).

Размещено на http://www.allbest.ru/

12

Если состоянии головки равно наибольшей строке таблицы+1, то изменяем положение программы на “2” и останавливаемся.

1.3 Определимся (ориентировочно) с информационными ячейками на листе Excel и добавим управляющие формулы. Должно быть следующее:

1. Таблица автомата Тьюринга для всех элементов алфавита и всех состояний головки (кроме состояния останова программы - обычно его не пишут ввиду повторяемости ячеек с одинаковым содержимым). (ячейки A1-J5(по диагонали)) управляющие формулы не нужны (мы будем ссылаться на эту таблицу) (рис 8).

2. Ячейка Пуск (ячейка B11) ›управляющие формулы не нужны (в нее будем вносит 0 или 1 вручную).

3. Ячейка Шаг (ячейка B13)›вносим формулу.

=ЕСЛИ( D11=2;"конец";ЕСЛИ(D11;ЕСЛИ(C11=1;СУММ(B13;1);B13);"начало"))

Размещено на http://www.allbest.ru/

12

Блок-схема действия формулы представлена на рисунке 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));))

Размещено на http://www.allbest.ru/

12

Блок-схема действия формулы представлена на рисунке 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));))

Размещено на http://www.allbest.ru/

12

Блок-схема действия формулы представлена на рисунке 11:

Необходимо заполнить подобными формулами ячейки B21-AH21 с учетом их относительных адресов .

8. Изображение действующей ленты с ячейками числа (для ячейки B22)

Размещено на http://www.allbest.ru/

12

=ЕСЛИ($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))

Размещено на http://www.allbest.ru/

12

Блок-схема действия формулы представлена на рисунке 13:

Необходимо заполнить подобными формулами ячейки B23-AH23 с учетом их относительных адресов .

10.Ячейки номера состояния головки (для ячейки B24)

=ЕСЛИ($D$11=2;B24;ЕСЛИ($D$11=1;ЕСЛИ($C$11=2;ЕСЛИ(A21=1;A20;ЕСЛИ(C21=-1;C20;));B24);B17))

Блок-схема действия формулы представлена на рисунке 14:

Размещено на http://www.allbest.ru/

12

Необходимо заполнить подобными формулами ячейки B24-AH24 с учетом их относительных адресов .

11. Ячейка для промежуточной информации о положении программы (ячейка D11) =ЕСЛИ(B11;ЕСЛИ(МАКС(B24:AH24)=МАКС($A$3:$A$7)+1;2;B11);)

Блок-схема действия формулы представлена на рисунке 15:

Размещено на http://www.allbest.ru/

12

12. Ячейка для промежуточной информации о шаге выполнения (ячейка С11) =ЕСЛИ(D11;ЕСЛИ(C11=4;1;C11+1);1)

Размещено на http://www.allbest.ru/

12

Блок-схема действия формулы представлена на рисунке 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

Изменять положения ячеек после ввода управляющих формул и условного форматирования недопустимо.

2. Создать имитационную модель нормального алгоритма Маркова (НАМ).

2.1. Выбираем задачу:

Дан алфавит А={a,b}. Требуется приписать символ “a” к концу слова Р.

Например: bbab >bbaba

Решение этой задачи рассмотрено в примере 4 теоретической части (см. выше).

По условиям задачи слово может быть любой размерности в пределах ограничения ячейки Excel (обычно до 256 символов).

Поэтому необходимо задаться небольшими словами по своему усмотрению, чтобы задача решалась.

Сама задача решена, то есть составлен список формул подстановки нормального алгоритма Маркова (НАМ).

Нам осталось создать имитационную модель с помощью программы Excel.

Сложность реализации будет заключаться в отказе от встроенного языка программирования VBA.Поставленную задачу необходимо реализовать с помощью встроенных функций и условного форматирования ячеек электронной таблицы Excel Microsoft Office.

Но даже ограниченные средства реализации позволяют построить действующую имитационную модель НАМ.

2.2. Составляем текстовый алгоритм выполнения задачи по шагам:

1. Начальное положение программы “0” >вводим исходное слово заполняем таблицу формул подстановки (последовательность формул не менять, иначе измениться алгоритм).

2. Запускаем программу >положение программы “1”.

3. Проверяем вхождение (совпадение) левой части первой формулы подстановки и какой-то части исходного слова (а может быть и всего слова). Проверка осуществляется в исходном слове слева направо до момента первого совпадения (таких совпадений может быть несколько или ни одного, но нас интересует пока только первое совпадение).

4. Если нет совпадений в первой формуле , тогда переходим ко второй формуле подстановки.

5. Если ни одна формула подстановки не подошла, тогда останов и вывод конечного слова.

6. Если есть совпадение, тогда заменяем левую часть использованной формулы на правую часть этой же формулы в исходном слове (всю правую часть на всю левую независимо от количества символов). Возможно подстановка “пустоты”, то есть отсутствия левой и/или правой части, что равносильно удалению символов (если правая часть “пустота”) или вставке новых символов (если левая часть-“пустота”).

7. Если было совпадение, тогда проверяем маркер останова у использованной формулы подстановки в таблице НАМ - если есть (символ “!”), тогда останавливаем программу и выводим конечное слово, если нет (“символ пустота”), тогда продолжаем программу алгоритма подстановки.

8. Проверяем совпадение, начиная опять с первой формулы в модифицированном слове (результат от предыдущего шага подстановки).

9. Если нет совпадений в первой формуле, тогда переходим ко второй формуле подстановки.

10. Если ни одна формула подстановки не подошла, тогда останов и выводим конечное слово.

11. Если есть совпадение, тогда заменяем левую часть использованной формулы на правую часть этой же формулы в исходном слове (всю правую часть на всю левую независимо от количества символов). Возможно подстановка “пустоты”, то есть отсутствия левой и/или правой части, что равносильно удалению символов (если правая часть “пустота”) или вставке новых символов (если левая часть-“пустота”).

12. Если было совпадение, тогда проверяем маркер останова у использованной формулы подстановки в таблице НАМ - если есть (символ “!”), тогда останавливаем программу и выводим конечное слово, если нет (“символ пустота”), тогда продолжаем программу алгоритма подстановки.

13. Повторяем пункты 8-12 до полного останова (нет ни одного совпадения в модифицированном слове).

Внимание! Каждая новая проверка начинается с первой формулы подстановки (так требует алгоритм НАМ).

Остается уточнить детали алгоритма и составить формулы для нужных ячеек электронной таблицы.

1.3 Определимся (ориентировочно) с информационными ячейками на листе Excel и добавим управляющие формулы. Должно быть следующее:

Размещено на http://www.allbest.ru/

12

1. Оформить таблицу формул алгоритма (рис 17).

В столбике Номер (адреса A1чA5) пересчитать построчно, начиная с 1, все номера используемых формул .

В столбике Левая часть (адреса B1чB5) указать левые части используемых формул по мере их использования (порядок важен).

В столбике Правая часть (адреса C1чC5) указать правые части используемых формул , соответствующих левым частям.

В столбике Маркер останова (адреса D1чD5) останова указать символ “!”, если формула после выполнения должна остановиться (может быть несколько маркеров или не одного).

Для других задач количество строк (формул) может быть больше или меньше. Поэтому для других задач необходимо таблицу откорректировать.

2. Оформить вспомогательную таблицу запуска программы.

Ячейка F1-содержимое “ запуск программы”

Ячейка G1-содержимое “ старт”

Ячейка G2-содержимое “0” (при запуске программы оно меняется вручную на 1)

Ячейка H1-содержимое “ шаг”

Ячейка F2(информационная(начало,конец))-содержимое

=ЕСЛИ($G$2;ЕСЛИ(СЧЁТЕСЛИ(F10:F40;"Конечное слово");"конец";"начало");"'' 1>старт''")

Блок-схема действия формулы представлена на рисунке 18:

Размещено на http://www.allbest.ru/

12

Ячейка H2-содержимое

=ЕСЛИ(G2;ЕСЛИ(H2=100;1;H2+1);0)

Блок-схема действия формулы представлена на рисунке 19:

Размещено на http://www.allbest.ru/

12

Ячейка F2-(информационная (начало,конец))

Первое правило>Условное форматирование> Использовать формулу для форматируемых ячеек ›

=$F$2=”начало”

и выбрать цвет и шрифт (цвет желтый и шрифт по умолчанию ) ,

в графе Применяется к добавить

=$F$2

Второе правило>Условное форматирование>Использовать формулу для форматируемых ячеек >набрать формулу =$F$2=”конец”

и выбрать цвет и шрифт (у нас цвет красный и шрифт по умолчанию ) , а также в графе Применяется к добавить

=$F$2

3. Создаем таблицу исходной задачи.

Создается таблица на любом пустом месте листа Excel в виде двух столбиков (Задано слово и Получить слово).

В единственной строке указываем данные задачи (у нас bbab и bbaba).

4. Оформляем таблицу решений.

Ячейка F9-содержимое “Исходное слово”

Ячейка G9-содержимое “Метка останова”

Ячейка F10-содержимое “bbab”

Ячейка G10-содержимое “0”

Ячейка F11-

Размещено на http://www.allbest.ru/

12

Блок-схема действия формулы представлена на рисунке 20:

содержимое 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);"стоп")))));"")

Необходимо повторить с некоторыми изменениями содержание этой ячейки в ячейках F12-F18 (воспользоваться приемом Excel “протаскивание”).

Необходимо помнить, что адреса ячеек со знаками $ не меняются от протаскивания.

Ячейка 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)))))

Размещено на http://www.allbest.ru/

12

Блок-схема действия формулы представлена на рисунке 21:

Заполняем ячейки методом протаскивания для G11чG18 .

Ячейка E11(шаг с номером)-содержимое

=ЕСЛИ($H$2>=1;"шаг " & ЕСЛИ(ЕПУСТО(F11);"";СЧЁТЗ($F$11:F11));"")

Блок-схема действия формулы представлена на рисунке 22:

Размещено на http://www.allbest.ru/

12

Заполняем ячейки методом протаскивания для E11чE18.

Для ячеек F11чF18 применим условное форматирование цветом и шрифтом.

Условное форматирование>Использовать формулу для форматируемых ячеек›

=$F$11=”Конечное слово”

и выбрать цвет и шрифт (цвет красный и шрифт по умолчанию ) ,

в графе Применяется к добавить

=$F$11:$F$18)

Ячейки G9чG18 сделать невидимыми для пользователя(это служебная информация для самой программы)> Формат ячеек›Цвет>установить “Белый” (они сольются с фоном ячеек)>Enter.

5. Запускаем программу вводом в ячейку G2 цифры “1” и нажатием клавиши Enter. В соседней ячейке H2 появиться цифра 1 (выполниться первый цикл итераций).

Для продолжения шагов необходимо нажимать многократно клавишу F9 в верхней части клавиатуры компьютера .

Если при оформлении модели программа Excel выдаст предупреждение и недопустимых циклических ссылках, необходимо в Главное меню>Параметры>Формулы>Включить итерационные вычисления (установить шаг итерации 1 (за одно нажатие клавиши F9 будет совершаться один шаг)).

Ход работы.

1. Составление имитационной модели программы автомата Тьюринга.

Для моделирования задачи используем средства программы Excel Microsoft Office.

Необходимо построить модель на листе табличного редактора, используя возможности встроенных функций и условного форматирования.

Размещено на http://www.allbest.ru/

12

Возможный вариант модели представлен на рисунке 23. (адреса ячеек не менять иначе неправильно будет работать программа) .

Необходимо выполнить следующее:

Размещено на http://www.allbest.ru/

12

1. Оформить таблицу машины Тьюринга согласно рисунка.(обязательно в заданных ячейках)(рис 11).Исходные данные таблицы взяты из задачи 1 и сведены в таблицу (рисунок 24) (см выше теоретическую часть).

Для других задач количество строк и столбцов может быть больше или меньше. Поэтому для решения новых задач необходимо таблицу откорректировать.

Для повышения наглядности необходимо выделить контуры ячеек таблицы толщиной и цветом по своему вкусу. Это делается командой Меню-Главная-Шрифт-Границы.

2. Оформить поясняющие ячейки программы согласно рисунка 23.

Ячейка A11-содержимое “ Пуск”

Ячейка A13-содержимое “ Шаг”

Ячейка A16-содержимое “ Исходная лента”

Ячейка A17-содержимое “ Головка”

Ячейка A20-содержимое “ Головка”

Ячейка A21-содержимое “Движение”

Ячейка A2-содержимое “Ячейка”

Ячейка I15 -содержимое “Исходные данные”

Ячейка I19 -содержимое “Машина Тьюринга”

Для повышения наглядности необходимо выделить контуры ячеек таблицы толщиной и цветом по своему вкусу. Это делается командой Меню>Главная>Шрифт>Границы.

3. Заполнить формулами управляющие ячейки (ОШИБКИ НЕДОПУСТИМЫ!!!):

3.1 Ячейка Пуск (ячейка B11) >управляющие формулы не нужны (в нее будем вносит 0 или 1 вручную).

3.2. Ячейка Шаг (ячейка B13)>вносим формулу.

=ЕСЛИ( D11=2;"конец";ЕСЛИ(D11;ЕСЛИ(C11=1;СУММ(B13;1);B13);"начало"))

3.3. Изображение ленты с заданным на ней числом> указываем вручную заданное число в любом месте ленты (ячейки B16-AH16).

3.4. Изображение начального положения головки (обязательно над числом в любом месте) цифрой “1”(указываем вручную) (ячейки B17-AH17).

3.5. Изображение действующей ленты с ячейками состояния (для ячейки 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));))

Необходимо заполнить формулами ячейки B20-AH20.

Для упрощения ввода используем метод протаскивания.

Для этого необходимо к заполненной формулой ячейке B20 подвести мышку к правому нижнему углу ячейки. После появления крестика нажать левую клавишу мышки и протащить вправо до ячейки AH20 и отпустить кнопку мышки. Ячейки будут заполнены.

У адресов ячеек где проставлен знак $ при протаскивании адреса не изменяться.

3.6. Изображение действующей ленты с ячейками движения(для ячейки 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));))

Необходимо заполнить формулами ячейки ячейки B21-AH21 методом протаскивания.

3.7. Изображение действующей ленты с ячейками числа (для ячейки 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)))

Необходимо заполнить формулами ячейки B22-AH22 методом протаскивания.

3.8. Изображение действующей ленты с ячейками текущего числа ленты (для ячейки B23)

=ЕСЛИ($D$11=2;B23;ЕСЛИ($D$11;ЕСЛИ($C$11=3;B22;B23);B22))

Необходимо заполнить формулами ячейки B23-AH23 методом протаскивания.

3.9.Ячейки номера состояния головки (для ячейки B24)

=ЕСЛИ($D$11=2;B24;ЕСЛИ($D$11=1;ЕСЛИ($C$11=2;ЕСЛИ(A21=1;A20;ЕСЛИ(C21=-1;C20;));B24);B17))

Необходимо заполнить формулами ячейки B24-AH24 методом протаскивания.

3.10. Ячейка для промежуточной информации о положении программы (ячейка D11) =ЕСЛИ(B11;ЕСЛИ(МАКС(B24:AH24)=МАКС($A$3:$A$7)+1;2;B11);)

3.11. Ячейка для промежуточной информации о шаге выполнения (ячейка С11) =ЕСЛИ(D11;ЕСЛИ(C11=4;1;C11+1);1)

Ячейки D11 и C11 являются служебными, поэтому информацию желательно скрыть. Для этого выделяем ячейки›правая клавиша мышки до появления всплывающего меню (контекстное меню)›Формат ячеек›Шрифт›Белый.

Также в дальнейшем можно скрыть вспомогательную информацию ячеек (головки, движения и ячейки).Для этого выделяем вертикальные ячейки левого края листа Excel с номерами 20,21,22 и нажав левую клавишу мышки в контекстом меню выбираем Скрыть. Обратно можно восстановить информацию, выделив граничные ячейки левого края листа Excel и в контекстном меню активировать Показать.

Ячейки сольются с фоном листа, но информация в них сохраниться. Это можно наблюдать в строке формул меню.

Изменять положения ячеек после ввода управляющих формул и условного форматирования недопустимо.

4. Применить условное форматирование для выделения ячеек цветом и придание анимационного эффекта работы действующей модели.

4.1. Ячейка B11(старт)- Выделяем ячейку с данными, к которой мы хотим применить условное форматирование. Переходим по вкладке Главная в группу Стили, щелкаем кнопку Условное форматирование › Создать правило. В появившемся диалоговом окне Создание правила форматирования в поле Выберите тип правила выбираем Использовать формулу для определения форматируемых ячеек.

В поле Измените описание правила задаем условия и формат для нашего правила.

В нашем случае, условием будет формула:

=$B$13="конец"

В разделе “Применяется к” добавим:

=$B$13:$C$13;$B$11

В качестве формата выбираем красную заливку.

Создаем здесь же второе правило>Создать правило. В появившемся диалоговом окне Создание правила форматирования в поле Выберите тип правила выбираем Использовать формулу для определения форматируемых ячеек.

В поле Измените описание правила задаем условия и формат для нашего правила.

В нашем случае, условием будет формула:

=$B$13="начало"

В разделе “Применяется к” добавим:

=$B$13:$C$13;$B$11

В качестве формата выбираем желтую заливку.

Нажимаем ОК. Правило готово.

4.2. Ячейка B13(счетчик тактов) Для ячейки B13 можно не вводить данные, так как они автоматически подставляются, когда для B11 написали =$B$13:$C$13;$B$11

Но если бы мы начинали с ячейки B13, тогда необходимо следующее:

Выделяем ячейку с данными, к которой мы хотим применить условное форматирование. Переходим по вкладке Главная в группу Стили, щелкаем кнопку Условное форматирование›Создать правило. В появившемся диалоговом окне Создание правила форматирования в поле Выберите тип правила выбираем Использовать формулу для определения форматируемых ячеек.

В поле Измените описание правила задаем условия и формат для нашего правила.

В нашем случае, условием будет формула:

=$B$13="конец"

В разделе “Применяется к” добавим:

=$B$13:$C$13;$B$11

В качестве формата выбираем красную заливку.

Создаем здесь же второе правило>Создать правило. В появившемся диалоговом окне Создание правила форматирования в поле Выберите тип правила выбираем Использовать формулу для определения форматируемых ячеек.

В поле Измените описание правила задаем условия и формат для нашего правила.

В нашем случае, условием будет формула:

=$B$13="начало"

В разделе “Применяется к” добавим:

=$B$13:$C$13;$B$11

В качестве формата выбираем желтую заливку.

Нажимаем ОК. Правило готово.

4.3. Ячейка B23(лента)› Выделяем ячейку с данными, к которой мы хотим применить условное форматирование. Переходим по вкладке Главная в группу Стили, щелкаем кнопку Условное форматирование › Создать правило. В появившемся диалоговом окне Создание правила форматирования в поле Выберите тип правила выбираем Форматировать только ячейки, которые содержат.

В поле Измените описание правила задаем условия и формат для нашего правила.

В первом разделе выберем: Значение ячейки

Во втором разделе выберем: Равно

В нашем случае, условием будет формула:

="x"

В качестве формата выбираем серую заливку.

В разделе “Применяется к” добавим:

=$B$23:$AH$23

Нажимаем ОК. Правило готово.

4.4. Ячейка B24 (головка)

Выделяем ячейку с данными, к которой мы хотим применить условное форматирование. Переходим по вкладке Главная в группу Стили, щелкаем кнопку Условное форматирование › Создать правило. В появившемся диалоговом окне Создание правила форматирования в поле Выберите тип правила выбираем Использовать формулу для определения форматируемых ячеек.

В поле Измените описание правила задаем условия и формат для нашего правила.

В нашем случае, условием будет формула:

=B24=МАКС($A$3:$A$10)+1

В разделе “Применяется к” добавим:

=$B$24:$AH$24

В качестве формата выбираем красную заливку.

Создаем здесь же второе правило>Создать правило. В появившемся диалоговом окне Создание правила форматирования в поле Выберите тип правила выбираем Форматировать только ячейки, которые содержат.

В поле Измените описание правила задаем условия и формат для нашего правила.

В первом разделе выберем: Значение ячейки

Во втором разделе выберем: Больше

В нашем случае, условием будет формула:

=0

В качестве формата выбираем темно-красную заливку.

В разделе “Применяется к” добавим:

=$B$24:$AH$24

Нажимаем ОК. Правило готово.

5 .Необходимо включить итерационный режим вычисления (циклические по шагам), иначе появиться сообщение о недопустимости циклических ссылок (компьютер может зациклиться и зависнуть).

Поэтому необходимо выполнить Главное меню (верхний левый угол листа Excel)>Параметры›Формулы›Включить итерационные вычисления.

При этом необходимо указать шаг итераций. Если выбрать 1,тогда за каждый такт будет выполняться одна итерация (подробный режим работы машины Тьюринга). Если выбрать 4, тогда за один такт будет выполняться 4 итерации (машина будет работать по классической схеме).

6. Для запуска программы необходимо ввести в ячейку B11 цифру “1” и нажать клавишу Enter. В соседней ячейке D11 появиться цифра 1 (выполниться первый цикл итераций)(если ячейка не скрыта).

Для продолжения шагов необходимо нажимать многократно клавишу F9 в верхней части клавиатуры компьютера до окончания работы программы.

Вернуться на исходную позицию можно путем ввода в ячейку B11 цифру “0” и нажать клавишу Enter.

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

Для моделирования задачи используем средства программы Excel Microsoft Office.

Необходимо построить модель на листе табличного редактора, используя возможности встроенных функций и условного форматирования.

Размещено на http://www.allbest.ru/

12

Возможный вариант модели представлен на рисунке 12. (адреса ячеек не менять иначе неправильно будет работать программа) .

Необходимо выполнить следующее:

Размещено на http://www.allbest.ru/

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:

Размещено на http://www.allbest.ru/

12

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 иначе.

...