Выполнить на машине поста программу

Практическая работа № 7 Автоматическая обработка данных

Просмотр содержимого документа
«Практическая работа № 7 Автоматическая обработка данных»

Практическая работа № 7

Автоматическая обработка данных

Цель работы: знакомство с основами теории алгоритмов на примере решения задач на программное управление алгоритмической машиной Поста.

Используемое программное обеспечение: имитатор машины Поста

Система команд машины Поста: (везде буква n обозначает номер текущей команды):

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

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

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Задание 2
1. Выполните на машине Поста программу:

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

2. Какую задачу решает исполнитель по этой программе?

3. Что произойдёт, если начальное состояние информационной ленты будет иметь следующий вид?

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

В следующих задачах считается, что n расположенных подряд меток обозначают число n (непозиционная система счисления с основанием 1).

Составить программу перевода информационной ленты машины Поста из начального состояния в конечное:

Источник

Программирование на машине Поста

Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и Brainfuck. Думаю, для полноты картины будет интересно сравнить эти эзотерические системы с еще одним важным алгоритмическим примитивом — машиной Поста, которой я как раз занимаюсь.

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.

Пример

Рассмотрим одну из кратчайших реализаций умножения двух натуральных чисел. Числа n и m записываются на ленте в единичной системе счисления, разделяются одной пустой ячейкой. Вход/выход алгоритма может быть таким (отмечено начальное положение каретки):

Идея алгоритма — краткое сложение. В каждом проходе цикла машина «откусывает» один бит от левого множителя и «копирует» самый правый имеющийся блок (сперва это второй множитель, затем — его последняя копия). Когда левый множитель «закончится», на ленте остается n блоков по m единиц. Их слияние дает искомое число n*m.

Проверить корректность алгоритма можно в уме, на листочке, либо с помощью этой программы.

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

P. S. «Большой четверкой» называю машину Тьюрига, Поста, систему Маркова и Brainfuck — самые изучаемые тьюринговые трясины.

Источник

Практическая работа № 7 Автоматическая обработка данных

Просмотр содержимого документа
«Практическая работа № 7 Автоматическая обработка данных»

Практическая работа № 7

Автоматическая обработка данных

Цель работы: знакомство с основами теории алгоритмов на примере решения задач на программное управление алгоритмической машиной Поста.

Используемое программное обеспечение: имитатор машины Поста

Система команд машины Поста: (везде буква n обозначает номер текущей команды):

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

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

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Задание 2
1. Выполните на машине Поста программу:

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

2. Какую задачу решает исполнитель по этой программе?

3. Что произойдёт, если начальное состояние информационной ленты будет иметь следующий вид?

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

В следующих задачах считается, что n расположенных подряд меток обозначают число n (непозиционная система счисления с основанием 1).

Составить программу перевода информационной ленты машины Поста из начального состояния в конечное:

Источник

Практическая работа № 7 Автоматическая обработка данных

Просмотр содержимого документа
«Практическая работа № 7 Автоматическая обработка данных»

Практическая работа № 7

Автоматическая обработка данных

Цель работы: знакомство с основами теории алгоритмов на примере решения задач на программное управление алгоритмической машиной Поста.

Используемое программное обеспечение: имитатор машины Поста

Система команд машины Поста: (везде буква n обозначает номер текущей команды):

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

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

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Задание 2
1. Выполните на машине Поста программу:

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

2. Какую задачу решает исполнитель по этой программе?

3. Что произойдёт, если начальное состояние информационной ленты будет иметь следующий вид?

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

В следующих задачах считается, что n расположенных подряд меток обозначают число n (непозиционная система счисления с основанием 1).

Составить программу перевода информационной ленты машины Поста из начального состояния в конечное:

Источник

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программуВыполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программуВыполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

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

Договоримся о терминологии: под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Опишем архитектуру машины Поста (рис. 2.3).

Имеется бесконечная информационная лента, разделенная на позиции — клетки. В каждой клетке может либо стоять метка (некоторый знак), либо отсутствовать (пусто).

Вдоль ленты движется каретка — считывающее устройство. На рисунке 2.3 она обозначена стрелкой.

Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей.

Каретка является еще и процессором машины.

С ее помощью машина может:

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

Теперь рассмотрим систему команд машины Поста (табл. 2.1). Запись всякой команды начинается с ее порядкового номера в программе — n. Затем следует код операции и после него — номер следующей выполняемой команды программы — m.

Рассмотрим пример программы решения задачи на машине Поста. Исходное состояние показано на рис. 2.3. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. Программа приведена в табл. 2.2.

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

В процессе выполнения приведенной программы многократно повторяется выполнение команд с номерами 2 и 3. Такая ситуация называется циклом. Напомним, что цикл относится к числу основных алгоритмических структур вместе со следованием и ветвлением.

А теперь научим машину Поста играть в интеллектуальную игру, которая называется «Игра Баше».

Опишем правила игры.

Играют двое. Перед ними 21 (или 16, или 11 и т. д.) фишка. Игроки берут фишки по очереди. За один ход можно взять от 1 до 4 фишек. Проигрывает тот, кто забирает последнюю фишку.

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

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

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

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

Программа управления машиной Поста в игре Баше против человека приведена в табл. 2.3.

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Действуя по данной программе и начиная стирать метки второй после человека, машина всегда будет выигрывать, если правильно задано начальное число меток, которое должно быть равно 5n + 1, где n — любое натуральное число. В противном случае машина может проиграть.

Подведем итог.

Автоматическая обработка информации возможна, если:

1) информация представлена в формализованном виде — в конечном алфавите некоторой знаковой системы;
2) реализован исполнитель, обладающий конечной системой команд, достаточной для построения алгоритмов решения определенного класса задач обработки информации;
3) реализовано программное управление работой исполнителя. Машина Поста — пример автоматического исполнителя обработки информации с ограниченными возможностями. Компьютер удовлетворяет всем вышеперечисленным свойствам. Он является универсальным автоматическим исполнителем обработки информации.

Система основных понятий

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Вопросы и задания

1. На информационной ленте машины Поста расположен массив из N меток. Каретка находится под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

2. На информационной ленте на некотором расстоянии справа от каретки, стоящей под пустой клеткой, находится непрерывный массив меток. Требуется присоедршить к правому концу массива одну метку.

4. На ленте расположен массив из 2n меток. Составить программу, по которой машина раздвинет на расстояние в одну клетку две половины данного массива.

Практикум

Практическая работа № 2.2 «Автоматическая обработка данных»

Цель работы: знакомство с основами теории алгоритмов на примере решения задач на программное управление алгоритмической машиной Поста.

Используемое программное обеспечение: имитатор машины Поста, (который можно скачать отсюда).

Система команд машины Поста: (везде буква n обозначает номер текущей команды):

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Задание 1

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

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Задание 2

1. Выполнить на машине Поста программу:

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

2. Какую задачу решает исполнитель по этой программе?

3. Что произойдет, если начальное состояние информационной ленты будет иметь следующий вид?

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

В следующих задачах считается, что n расположенных подряд меток обозначают число n (непозиционная система счисления с основанием 1).

Задание 3

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

Задание 4

Написать для машины Поста программу вычитания двух чисел, разделенных одной пустой клеткой. Уменьшаемое не меньше вычитаемого. Начальное положение каретки — под пустой клеткой, отделяющей уменьшаемое от вычитаемого.

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

Задание 5

Используя программу вычитания, проверить, что получится, если:

а) уменьшаемое равно вычитаемому;
б) уменьшаемое меньше вычитаемого.

Задание 6

Написать для машины Поста программу деления числа, записанного метками, на 2. Исходное число должно делиться на 2 без остатка.

Указание. Стереть каждую вторую метку; уплотнить оставшиеся метки.

Задание 7

Используя программу деления числа на 2: а) проверить, что получится для числа 2; б) модифицировать программу с учетом числа 2.

Указание. Справа от пустой клетки поставить метку, а слева стереть две метки. Так поступать до тех пор, пока слева остаются метки.

Задание 8

На информационной ленте машины Поста на расстоянии в га клеток друг от друга расположены две помеченные метками клетки. Начальное положение каретки — под левой из помеченных клеток. Какую работу выполнит Машина Поста по программе?

Выполнить на машине поста программу. Смотреть фото Выполнить на машине поста программу. Смотреть картинку Выполнить на машине поста программу. Картинка про Выполнить на машине поста программу. Фото Выполнить на машине поста программу

Задание 9

Написать для машины Поста программу умножения на 2 числа, записанного метками на ленте.

Указание. Через одну пустую клетку поставить две метки, а в исходном числе стереть одну. Так поступать, пока в исходном числе остаются метки.

Задание 10*

Написать для машины Поста программу, проверяющую, делится ли записанное метками число на 5.

Задание 11*

Задание 12*

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

Источник

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *