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

1

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

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

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

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

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

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

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

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

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

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

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

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

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

15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36

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

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

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

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

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