Применимость программ. Определение результата выполнения программ
1. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста для каждого состояния.
2. Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.
Пояснение: выделенная цифра, например 1, означает, что эту ячейку каретка обозревает в начальный момент времени.
Арифметические задачи
Программы для решения всех задач этого раздела могут быть интерпретированы как выполнение элементарных арифметических операций. Важно показать, как с помощью простейших операций, которыми располагает машина Поста, можно выполнять арифметические операции — основу любого современного процессора.
3. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.
4. Даны два массива меток, которые находятся на не-
котором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
5. На ленте задана последовательность массивов, включающая в себя один и более массивов. При этом два соседних массива отделены друг от друга одной пустой ячейкой. Необходимо на ленте оставить один массив длиной равной сумме длин массивов, присутствовавших изначально. Каретка находится над крайней левой меткой первого (левого) массива.
Ориентация на ленте
6. На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.
7. На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.
8. Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.
Решение. Этот алгоритм решения заимствован из замечательной книги В.А. Успенского “Машина Поста”. Мы не знаем, в какую сторону нам надо двигаться, но, в какую бы сторону мы ни пошли, может случиться, что метка стоит в другой стороне. Очевидно, что нам надо двигаться попеременно, то в одну сторону, то в другую, постоянно увеличивая размах своих колебаний. Но как определить момент, когда надо поворачивать, т.е. менять направление? Выход из положения есть. Вначале работы выставим метки слева и справа от исходного положения каретки, а затем будем ходить между ними и передвигать их.
Машина Поста
Цель работы: ввести понятие о машине Поста, показать принцип её работы, разобрать решение задачи по теме.
Просмотр содержимого документа
«Машина Поста»
«Машина Поста» автор: Камалова Татьяна Ивановна учитель высшей категории МАОУ СОШ№10 город Березники Пермский край
В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
Машина Тьюринга(МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Художественное представление машины Тьюринга
Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой.
Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты. Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд
V Записать отметку
Известно, что на ленте Машины Поста записан массив из 3 меток. Необходимо увеличить массив еще на одну метку. Так же известно, что каретка стоит слева от меток и обозревает пустую ячейку.
На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.
На ленте заданы два массива. Найти модуль разности длин массивов. Каретка располагается над первой ячейкой левого массива.
На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.
Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.
Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.
Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.
Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.
На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов
Презентация на тему «Машина Поста»
Описание презентации по отдельным слайдам:
В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
Машина Тьюринга Машина Тьюринга(МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Художественное представление машины Тьюринга
Машина Поста Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой.
Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Принцип работы Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты. Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд
Устройство машины: Метка Каретка Лента
Пример Известно, что на ленте Машины Поста записан массив из 3 меток. Необходимо увеличить массив еще на одну метку. Так же известно, что каретка стоит слева от меток и обозревает пустую ячейку.
Задача 1 На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.
Задача 2 На ленте заданы два массива. Найти модуль разности длин массивов. Каретка располагается над первой ячейкой левого массива.
Задача 3 На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.
Задача 4 Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.
Задача 5 Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
Задача 6 На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.
Задача 7 На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.
Задача 8 Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.
Задача 9 Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.
Задача 10 На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов
Курс повышения квалификации
Дистанционное обучение как современный формат преподавания
Курс повышения квалификации
Педагогическая деятельность в контексте профессионального стандарта педагога и ФГОС
Курс повышения квалификации
Современные педтехнологии в деятельности учителя
Ищем педагогов в команду «Инфоурок»
Номер материала: ДБ-1160809
Не нашли то что искали?
Вам будут интересны эти курсы:
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Учителям предлагают 1,5 миллиона рублей за переезд в Златоуст
Время чтения: 1 минута
Путин поручил не считать выплаты за классное руководство в средней зарплате
Время чтения: 1 минута
Петербургский Политех перевел студентов на дистанционку
Время чтения: 1 минута
При детском омбудсмене в России создадут платформу для взаимодействия с родителями
Время чтения: 2 минуты
НИУ ВШЭ откроет первую в России магистратуру по управлению низкоуглеродным развитием
Время чтения: 2 минуты
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Подарочные сертификаты
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.
Дифференцированные тренировочные упражнения по решению задач на применение Машины Поста в школьном курсе Информатики 10 класса
Дифференцированные тренировочные упражнения по решению задач на применение Машины Поста в школьном курсе Информатики 10 класса.
Учитель МОУ «СШ №1 города Кировское» Арзамасцева И.А.
Машина Поста, несмотря на внешнюю простоту, может производить различные вычисления, для чего надо задать начальное состояние каретки и программу, которая эти вычисления сделает. Машиной эта математическая конструкция названа потому, что при ее построении используются некоторые понятия реальных машин (ячейка памяти, команда и др.). Условимся каждый шаг программы обозначать номером. Команды машины будем обозначать следующим образом:
На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.
Даны два массива меток, которые находятся на не-
котором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
На ленте задана последовательность массивов, включающая в себя один и более массивов. При этом два соседних массива отделены друг от друга одной пустой ячейкой. Необходимо на ленте оставить один массив длиной равной сумме длин массивов, присутствовавших изначально. Каретка находится над крайней левой меткой первого (левого) массива.
На ленте заданы два массива. Найти модуль разности длин массивов. Каретка располагается над первой ячейкой левого массива.
На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.
На ленте задан массив. Вычислить остаток от деления длины заданного массива на 3. Каретка располагается над первой ячейкой массива.
На ленте машины Поста расположен массив из n меток. Составить программу, действуя по которой машина выяснит, делится ли число n на 3. Если да, то после массива через одну пустую ячейку поставить метку.
На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.
На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке
Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.
Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение
На ленте машины Поста расположен массив из n меток (метки расположены через пробел). Нужно сжать массив так, чтобы все n меток занимали n расположенных подряд ячеек.
Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.
На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов.
На ленте машины Поста расположен массив из 2 n – 1 меток. Составить программу удаления средней метки массива.
На ленте машины Поста расположен массив из 2 n ячеек. Составить программу, по которой машина Поста раздвинет на расстояние в одну ячейку две половины данного массива.
Написать программу, которая осуществляет преобразование 1 n 01 m –> 1 m 01 n ( n 
1 и m 1).
На ленте расположены два массива разной длины. Каретка обозревает крайний элемент одного из них. Составьте программу для машины Поста, сравнивающую длины массивов и стирающую больший из них. Отдельно продумайте случай, когда длины массивов равны.
На ленте машины Поста находятся два массива в m и n меток. Составить программу выяснения, одинаковы ли массивы по длине.
Дано N массивов меток. Массивы разделены тремя пустыми ячейками. Количество меток в массиве не меньше двух. Если количество меток в массиве кратно трем, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.
Удвоить данный массив справа от него, через ячейку, и затем стереть исходный. Каретка находится над крайней левой меткой.
Дано N массивов меток. После последнего массива на расстоянии более трёх пустых ячеек находится одна метка. Массивы разделены тремя пустыми ячейками. Количество меток в массиве >=2. Если количество меток в массиве кратно трём, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.
Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.
3. Успенский В.А. Машина Поста. Серия “Популярные лекции по математике”, выпуск 54. М.: Наука, 1988.
Урок по теме: «Составление алгоритмов решения задач для управления машиной Поста»
Тема «Автоматическая обработка информации. Машина Поста»
повторить пройденный материал по теме: «Автоматическая обработка информации»;
научить работать с имитатором машины Поста
закрепить знания по теме при выполнении практического задания.
формировать аналитическое и логическое мышление учащихся;
развивать умение выделять главное, находить ошибку;
развивать способности сравнивать, сопоставлять.
воспитывать бережное отношение к компьютеру;
формировать умение преодолевать трудности;
способствовать развитию умения оценивать свои возможности.
Вид занятий (тип урока): практическое занятие.
Методы обучения: выполнение практического задания.
Средства обучения: персональные компьютеры, имитатор машины Поста.
1. Организационный момент.
— Здравствуйте! Все готовы к уроку?
— Садитесь. Кто сегодня дежурный? Кто отсутствует на уроке?
2. Актуализация знаний.
Проверка домашнего задания.
3. Сообщение темы и цели урока.
— Сегодня мы с вами поработаем за компьютерами. Прошу занять свои места. И открыть имитатор машины Поста. Сегодня будем разбирать задачи.
4. Практическая работа.
— И так, давайте разберем один пример вместе на доске. А потом вы попробуете порешить задачи самостоятельно. Откройте свои записи в тетради, где записали команды для работы на машине Поста.
Сдвиг каретки на шаг влево и переход к выполнению команды с номером m
Сдвиг каретки на шаг вправо и переход к выполнению команды с номером m
Запись метки в текущую пустую клетку и переход к выполнению команды с номером m
Стирание метки в текущей клетке и переход к выполнению команды с номером m
Остановка выполнения программы
Система команд машины Поста
— А сейчас давайте, рассмотрим один пример вместе. Рассмотрим программу:
Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4). Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д. Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
На доске вместе с учениками разбирается пример.
— Всем понятно решение этого примера?
Задачи для самостоятельной работы:
1. Пусть задано исходное состояние головки и требуется на пустой ленте написать две метки: одну в секцию под головкой, вторую справа от нее.
2. На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.
Пример программы, которая не применима ни к одному состоянию машины Поста:
Программа для машины Поста:
Пояснения к условиям задач
1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками.
К примеру, запись “12012” будет соответствовать записи “11011” на ленте.
4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой.
1. Применимость программ. Определение результата выполнения программ
1. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста для каждого состояния.