Ребята, сегодня вы познакомитесь с «игрушечной» машиной, которой в реальной жизни нет, но ее можно построить. Изобрел эту машину более 70-ти лет назад американский математик Эмиль Пост.

Эмиль Пост Американский математик, предложивший в 1937 году свою абстрактную машину, известную под названием «машина Поста», все вычисления на которой отражали многие черты вычислений на реальных компьютерах.

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

Алгоритм Это надо знать… - это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Программа - это алгоритм, записанный на языке программирования. Федеральный банк экзаменационных материалов – ИНФОРМАТИКА 2008

Три Буквы П хранят секрет, Нажми скорей узнай ответ!!!

Рассмотрим ленту

Она разбита на клеточки. Рассмотрим ленту

С работой машины вам поможет познакомиться - ослик. Привет!

Ослик может двигаться вправо по одной клеточке. Смотрите!

Ослик может двигаться вправо по одной клеточке. Смотрите!

И еще на одну клетку вправо... Так точно

И еще на одну клетку вправо... Так точно

Он может также двигаться влево - по одной клетке.

Ослик видит то, что находится в клетке, если сидит напротив нее. Все вижу, но там пусто!

Прислушайтесь к ослику! А если я сяду так, между клеток, то ничего не увижу

Сейчас клетка пуста.

А в данный момент в этой клетке лежит морковка, ослик видит ее.

Ослик может не только видеть морковку, но и съесть ее.

Очень вкусно !!!

Он может вложить в пустую клетку морковку. Сделай шаг вправо Но необходимо всегда проверять пуста ли клетка.

Он может вложить в пустую клетку морковку. Но необходимо всегда проверять пуста ли клетка. Сделай шаг вправо Проверь клетку ?

Проверяем пуста ли клетка ? Если пусто,то он может смело оставить в этой клетке морковку !

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

Вот что умеет наш ослик. I J ДЕЙСТВИЯ : Шаг вправо Шаг влево Съесть морковку Вложить морковку Размышлять ОБОЗНАЧЕНИЯ: V ?

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

Что же должен сделать ослик, чтобы выполнить задание и безошибочно?! Давайте думать вместе, ребята!!!

Две морковки лежат в ячейках. Давайте думать вместе, ребята!!!

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

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

Две морковки лежат в ячейках. Проверим пуста ли следующая ячейка. Да, она пуста, значит оставляем морковку. ?

Теперь у нас в ячейках три морковки. Машина Поста умеет складывать: складывать: = = 3

I J Какие действия выполнял ослик ? Проверил ячейку ? Занята Двигаемся вправо Проверил ячейку ? Пусто Вложим морковку Конец. V

Вопрос 1. Из чего состоит наша машина Поста? Проверь себя Ответы В. Лента и Ослик A.Лента Лента Б. Ослик Ослик

Проверь себя Вопрос 2. Как может двигаться Ослик в машине Поста? Ответы В. Вправо Вправо A.Влево Влево Б. Влево и Вправо Влево и Вправо

Проверь себя Вопрос 3. Что может быть в клетке на ленте в машине Поста? Ответы В. Только пусто Только пусто A.Морковка или пусто Морковка или пусто Б. Морковка Морковка

П ост П ост (Post) Эмиль Леон ( – ) – американский математик и логик. Читал лекции по математике и логике в Колумбийском, Нью-йоркском и других университетах США. Им получен ряд фундаментальных результатов в математической логике.

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

Можно ли любой алгоритм представить в форме машины Поста? Ответ на этот вопрос дается в виде так называемого тезиса П оста: всякий алгоритм представим в форме машины Поста. Это тезис потому, что его невозможно доказать, так как в нем фигурируют с одной стороны, интуитивное понятие «всякий алгоритм», а с другой стороны - точное понятие «машина Поста».