Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Другие методич. материалы / Изучение машины Поста в школьном курсе информатики
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Информатика

Изучение машины Поста в школьном курсе информатики

Выбранный для просмотра документ Изучение машины Поста в школьном курсе информатики.docx

библиотека
материалов

Изучение машины Поста в школьном курсе информатики


Одним из центральных понятий информатики является понятие алгоритма. В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

Несмотря на “примитивность” машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый “тезис Поста”: “Всякий алгоритм представим в форме машины Поста”. Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.

Тезис Поста является гипотезой. Его невозможно строго доказать (так же, как и тезис Тьюринга), потому что в нем фигурируют, с одной стороны, интуитивное понятие “всякий алгоритм”, а с другой стороны — точное понятие “машина Поста”. Для того чтобы опровергнуть гипотезу Поста, необходимо придумать алгоритм, который невозможно записать в виде программы для машины Поста. На сегодняшний день такого алгоритма не существует.

Машина Поста — это абстрактная (т.е. не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию. Разработка программ для машин Поста — достаточно эффективный этап в обучении алгоритмизации, т.к. в процессе написания этих программ учащиеся учатся разбивать интуитивно понятные вычислительные процедуры на элементарные действия. Изучение машины Поста полезно как школьникам, интересующимся информатикой и математикой, так и студентам младших курсов, обучающимся по специальности “прикладная математика и информатика”. При этом теоретический материал доступен даже школьникам младших классов, но требует в этом случае некоторых методических поправок.


Теоретическая часть. Состав машины Поста

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера — ячейки.

04-00

Рис. 1. В каждый момент времени каретка указывает на одну из ячеек

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как “1”, а отсутствие — “0”. Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

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

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

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. останов;

6. если 0, то перейти к i, иначе перейти к j.

Приведем список недопустимых действий, ведущих к аварийной остановке машины:

  • попытка записать 1 (метку) в заполненную ячейку;

  • попытка стереть метку в пустой ячейке;

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

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

04-01

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

Пример программы, которая не применима ни к одному состоянию машины Поста:

04-02

Рассмотрим задачу для машины Поста и ее решение.

Задача. На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.

Решение. Сначала попробуем описать алгоритм обычным языком. Поскольку нам известно, что каретка стоит напротив пустой ячейки, но неизвестно, сколько шагов нужно совершить до пустой ячейки, мы можем сразу сделать шаг вправо; проверить, заполнена ли ячейка; если она пустая, то повторять эти действия до тех пор, пока не наткнемся на заполненную ячейку. Как только мы ее найдем, мы выполним операцию стирания, после чего нужно будет лишь сместить каретку влево и остановить выполнение программы.

Программа для машины Поста:

04-03

Начинать знакомство с машиной Поста рекомендуется с первой темы “Применимость программ. Определение результата выполнения программ”.

Пояснения к условиям задач

1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками.

2) Если в задаче говорится, что на ленте задано число в унарной системе, то имеется в виду, что натуральное число n закодировано с помощью массива длины n.

3) В задачах при описании начального состояния ленты будем указывать то, что записано начиная с самой левой непустой ячейки и заканчивая самой правой непустой ячейкой. При этом будем использовать следующие обозначения: n подряд идущих меток будем обозначать 1n, а m пустых ячеек — 0m. При обозначении одной заполненной или пустой ячейки будем писать просто 1 или 0, соответственно.

К примеру, запись “12012” будет соответствовать записи “11011” на ленте.

4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой.


1. Применимость программ. Определение результата выполнения программ

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

04-04

04-05

Ответы:

a) 1) 1110011000

    2) зацикливание

    3) 1001011000

b) 1) зацикливание

    2) 010011

    3) 01010110

c) 1) зацикливание (…111)

    2) зацикливание (…1111001)

    3) зацикливание (1010111…)

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

Пояснение: выделенная цифра, например 1, означает, что эту ячейку каретка обозревает в начальный момент времени.

04-06

Решение. Выделенная цифра показывает, на какой ячейке остановится машина.

a) 1) 110000001

    2) 11000001

b) 1) 1100101

     2) 10001

     3) 111111

3. Написать программы для машины Поста, которые обладают следующими свойствами:

  • программа применима к любому состоянию машины Поста;

  • программа не применима ни к какому состоянию машины Поста, и зона работы для любого начального состояния — бесконечная;

  • программа не применима ни к какому состоянию машины Поста, и зона работы для любого начального состояния ограничена одним и тем же числом ячеек, не зависящим от выбранного начального состояния ленты;

  • программа применима к состояниям 13n (n MoreQ1) и не применима к состояниям 13n+a, где a = 1, 2 и n MoreQ1;

  • программа применима к состояниям 1a01a, где a MoreQ1, и не применима к 1a01b, a NotQb (a и bMoreQ1).

Решение

  • программа, применимая к любому состоянию машины Поста:

! 1

  • программа, не применимая ни к какому состоянию машины Поста, и зона работы для любого начального состояния бесконечна:

> 1

  • машина, не применимая ни к какому состоянию машины Поста, и зона работы для любого начального состояния ограничена одним и тем же числом ячеек, не зависящим от выбранного начального состояния ленты:

1. –> 2

2. <– 1

  • программа, применимая к состояниям 13n, и не применимая к состояниям 13n+a, где a = 1, 2 и n MoreQ1:

04-08

  • программа применима к состояниям 1a01a, где a MoreQ1, и не применима к 1a01b, a NotQb (a MoreQ1 и b MoreQ1):

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

2. Арифметические задачи

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

4. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.

Решение.

1. ? 2; 3 (команды 1 и 2 — передвигаем каретку к массиву)

2. –> 1

3. –> 4 (команды 3 и 4 — передвигаем каретку к концу массива)

4. ? 5; 3

5. V 6 (команды 5–7 — ставим 2 метки в конце массива)

6. –> 7

7. V 8

8. !

5. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

Решение.

04-09


Выбранный для просмотра документ изучение машины Поста.pptx

библиотека
материалов
Изучение машины Поста в школьном курсе информатики
В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предло...
«Тезис Поста»: всякий алгоритм представим в форме машины Поста. Этот тезис яв...
Теоретическая часть. Состав машины Поста Бесконечная лента каретка
Команды машины Поста Команда Действие n ← m Сдвиг каретки на шаг влево и пере...
Пример программы, которая неприменима к любому состоянию машины Поста 1 → 1 2 !
Пояснения к условиям задач 1) В задачах под массивом понимается последователь...
Применимость программ. Определение результата выполнения программ Выяснить, п...
Арифметические задачи На ленте задан массив меток. Увеличить длину массива на...
Ориентация на ленте На ленте имеется некоторое множество меток (общее количес...
10 1

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Описание презентации по отдельным слайдам:

№ слайда 1 Изучение машины Поста в школьном курсе информатики
Описание слайда:

Изучение машины Поста в школьном курсе информатики

№ слайда 2 В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предло
Описание слайда:

В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста

№ слайда 3 «Тезис Поста»: всякий алгоритм представим в форме машины Поста. Этот тезис яв
Описание слайда:

«Тезис Поста»: всякий алгоритм представим в форме машины Поста. Этот тезис является формальным определением алгоритма. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.

№ слайда 4 Теоретическая часть. Состав машины Поста Бесконечная лента каретка
Описание слайда:

Теоретическая часть. Состав машины Поста Бесконечная лента каретка

№ слайда 5 Команды машины Поста Команда Действие n ← m Сдвиг каретки на шаг влево и пере
Описание слайда:

Команды машины Поста Команда Действие n ← m Сдвиг каретки на шаг влево и переходк выполнению команды с номеромm n → m Сдвиг каретки на шаг вправо и переходк выполнению команды с номеромm n v m Запись метки втекущую пустую клетку и переход к выполнению команды с номеромm n ↕ m Стирание метки втекущей клетке и переход к выполнению команды с номеромm n ! Остановка выполнения программы n?m,k Переход в зависимости от содержимого текущей клетки: если текущая клетка пустая, то следующей будет выполняться команда с номеромm,если непустая – команда с номеромk

№ слайда 6 Пример программы, которая неприменима к любому состоянию машины Поста 1 → 1 2 !
Описание слайда:

Пример программы, которая неприменима к любому состоянию машины Поста 1 → 1 2 !

№ слайда 7 Пояснения к условиям задач 1) В задачах под массивом понимается последователь
Описание слайда:

Пояснения к условиям задач 1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками. 2) Если в задаче говорится, что на ленте задано число в унарной системе, то имеется в виду, что натуральное число n закодировано с помощью массива длины n. 3) В задачах при описании начального состояния ленты будем указывать то, что записано начиная с самой левой непустой ячейки и заканчивая самой правой непустой ячейкой. При этом будем использовать следующие обозначения: n подряд идущих меток будем обозначать 1n, а m пустых ячеек — 0m. При обозначении одной заполненной или пустой ячейки будем писать просто 1 или 0, соответственно. К примеру, запись “12012” будет соответствовать записи “11011” на ленте. 4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой.

№ слайда 8 Применимость программ. Определение результата выполнения программ Выяснить, п
Описание слайда:

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

№ слайда 9 Арифметические задачи На ленте задан массив меток. Увеличить длину массива на
Описание слайда:

Арифметические задачи На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива. На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.

№ слайда 10 Ориентация на ленте На ленте имеется некоторое множество меток (общее количес
Описание слайда:

Ориентация на ленте На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками. Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее. Решение. Этот алгоритм решения заимствован из замечательной книги В.А. Успенского “Машина Поста”. Мы не знаем, в какую сторону нам надо двигаться, но, в какую бы сторону мы ни пошли, может случиться, что метка стоит в другой стороне. Очевидно, что нам надо двигаться попеременно, то в одну сторону, то в другую, постоянно увеличивая размах своих колебаний. Но как определить момент, когда надо поворачивать, т.е. менять направление? Выход из положения есть. Вначале работы выставим метки слева и справа от исходного положения каретки, а затем будем ходить между ними и передвигать их.

Краткое описание документа:

В данном  материале  рассмотрено изучение темы  "Автоматическая обработка информации"  на примере  машины  Поста.  Здесь рассмотрен как теоретический так и практический материал,  представлено подробное описание программы и работа с ней. Для удобства  теоретический материал представлен в виде  презентации, которую  можно использовать  для объяснения материала  на уроке.  Также  рассмотрены  несколько  задач с решениями  в порядке увеличения  их сложности. 

Автор
Дата добавления 28.11.2014
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров456
Номер материала 159601
Получить свидетельство о публикации

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru

Похожие материалы

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