Домашнее задание для 11 тех (группа 1 на пятницу 20.01.23, группа 2 на субботу 21.01.22) класса по информатике:
1. Прочитайте §31 учебника (том 2) (до конца)
Прочитайте краткое описание работы машины Поста в статьях по ссылкам: https://inf1.info/machinepost (машина Поста)
Посмотрите видеоролик, в котором разбираются примеры решения задач в программном эмуляторе универсального исполнителя "Машина Поста".
https://www.youtube.com/watch?v=Bik6-KBwpf8 (описание работы машины Поста и примеры задач на программном эмуляторе)
2. Составьте алгоритмы для задач с использованием только универсальных исполнителей: машина Поста и нормальных алгоримфмов Маркова (НАМ).
Задачи для исполнителя "Машина Поста":
1) На ленте машины Поста записаны два числа в унарной системе счисления, разделённые одним пробелом. Каретка, в начальный момент времени, находится над пробелом, разделяющем два числа. Составьте программу, которая складывает эти два числа;
2) Составьте программу для машины Поста, которая удваивает число, записанное в единичной системе счисления. В начальный момент каретка находится над первой меткой числа.
Задачи для исполнителя "Нормальные алгорифмы Маркова (НАМ)":
1) Составьте НАМ, который переводит число из четверичной системы счисления в двоичную запись (подсказка: вспомните как быстро перевести число из восьмеричной системы счисления в двоичную с помощью триад). Используйте специальную метку (например знак *), который отделяет обработанную часть числа от необработанной;
2) Составьте НАМ, который инвертирует биты в записи двоичного числа (меняет 1 на 0, а 0 на 1 в каждом разряде числа);
3) Составьте НАМ, который вместо слова состящего из произвольного количества букв алфавита {a, b, c} оставляет столько символов "|", сколько букв "c" входит в исходное слово;
4*) Дана последовательность круглых скобок. Составьте НАМ, который проверяет правильность скобочной структуры (парность и вложенность скобок). Например выражение ( )( )( ( ) ) ( ( ) ( ) ) ( ( ) ) ( ) – правильное, а выражения ( )( )( ( ) ) ( ( ) ( ) ) ( ( ) ) ) ( и ( ) ( ) ( ( ) ) ( ( ) ( ) ) ( ( ) ) ) – неправильные. Если скобочное выражение правильное, то после всех подстановок лента окажется пустой, а если выражение неверное, то на ленте должны остаться "неправильные" скобки.
Составленные алгоритмы можно проверить на работу в эмуляторах машины Поста и нормальных алгорифмов Маркова, скачать которые можно по ссылке (внутри архивного файла, работает только под ОС Windows): файл архив в формате zip (внутри исполняемый файл exe).
Составив алгоритм решения задачи в эмуляторе его можно сохранить в виде файла и отправить на проверку по электронной почте (или сдать на флэшке перед уроком).
Если нет возможности использовать программу эмулятор, то решения задач нужно оформить письменно в тетради или на отдельном листе.
