Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

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

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

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

Презентация по информатике "Машина поста" (10-11 классы)

библиотека
материалов
Автома Автоматическая обработка информации. Машина Поста 11 класс Губарь Викт...
Цели урока: 1) способствовать углублению знаний учащихся об алгоритмах обрабо...
«Сами машины - это пустые перчатки,  Но их надевает человеческая рука,  Кото...
Теория Алгоритмов В 30-х годах XX века возникает новая наука — теория алгорит...
Английский ученый Алан Тьюринг предложил модель такого исполнителя, получивш...
 Машина Тьюринга Бесконечная лента Каретка Программа
МАШИНА ПОСТА Практически одновременно с Тьюрингом (1936-1937 гг.) другую мод...
 Машина Поста Бесконечная лента Программа Каретка
Ал­горитм, по которому работает машина Поста, будем на­зывать программой. По...
Опишем архитектуру машины Поста. Име­ется бесконечная информационная лента,...
Машина Поста Существенное отличие каретки-процессора машины Поста от процессо...
Машина Поста Назначение машины Поста — производить преобразования на инфор­ма...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста Пример программы решения задачи на машине Поста Пример программы...
Машина Поста В процессе выполнения приведенной программы многократно повторя­...
Машина Поста Назначение машины Поста — производить преобразования на инфор­ма...
Машина Поста Назначение машины Поста — производить преобразования на инфор­ма...
Машина Поста Назначение машины Поста — производить преобразования на инфор­ма...
Машина Поста Назначение машины Поста — производить преобразования на инфор­ма...
Домашнее задание: § 45, отвечать на вопросы, задачи № 1-8 2. Подготовьте сооб...
30 1

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


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

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

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

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

№ слайда 1 Автома Автоматическая обработка информации. Машина Поста 11 класс Губарь Викт
Описание слайда:

Автома Автоматическая обработка информации. Машина Поста 11 класс Губарь Виктория Александровна

№ слайда 2 Цели урока: 1) способствовать углублению знаний учащихся об алгоритмах обрабо
Описание слайда:

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

№ слайда 3 «Сами машины - это пустые перчатки,  Но их надевает человеческая рука,  Кото
Описание слайда:

«Сами машины - это пустые перчатки,  Но их надевает человеческая рука,  Которая может быть хорошей или плохой» Р. Брэдбери.

№ слайда 4 Теория Алгоритмов В 30-х годах XX века возникает новая наука — теория алгорит
Описание слайда:

Теория Алгоритмов В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

№ слайда 5 Английский ученый Алан Тьюринг предложил модель такого исполнителя, получивш
Описание слайда:

Английский ученый Алан Тьюринг предложил модель такого исполнителя, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина» является универсальным исполнителем обработки любых символьных последовательностей в лю­бом алфавите. МАШИНА ТЬЮРИНГА

№ слайда 6  Машина Тьюринга Бесконечная лента Каретка Программа
Описание слайда:

Машина Тьюринга Бесконечная лента Каретка Программа

№ слайда 7 МАШИНА ПОСТА Практически одновременно с Тьюрингом (1936-1937 гг.) другую мод
Описание слайда:

МАШИНА ПОСТА Практически одновременно с Тьюрингом (1936-1937 гг.) другую модель алгорит- мической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Можно сказать, что машина Поста является частным слу­чаем машины Тьюринга.

№ слайда 8  Машина Поста Бесконечная лента Программа Каретка
Описание слайда:

Машина Поста Бесконечная лента Программа Каретка

№ слайда 9 Ал­горитм, по которому работает машина Поста, будем на­зывать программой. По
Описание слайда:

Ал­горитм, по которому работает машина Поста, будем на­зывать программой. Под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя. Машина Поста

№ слайда 10 Опишем архитектуру машины Поста. Име­ется бесконечная информационная лента,
Описание слайда:

Опишем архитектуру машины Поста. Име­ется бесконечная информационная лента, разделенная на позиции — клетки. В каждой клетке может либо сто­ять метка (некоторый знак), либо отсутствовать (пусто). Вдоль ленты движется каретка — считывающее устройство. На рисун­ке она обозначена стрелкой. Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей. Каретка является еще и процессором машины. С ее помощью машина может: • распознать, пустая клетка или помеченная знаком; • стереть знак в текущей клетке; • записать знак в пустую текущую клетку. v v v v v

№ слайда 11 Машина Поста Существенное отличие каретки-процессора машины Поста от процессо
Описание слайда:

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

№ слайда 12 Машина Поста Назначение машины Поста — производить преобразования на инфор­ма
Описание слайда:

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

№ слайда 13 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 14 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины v v v v

№ слайда 15 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 16 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 17 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 18 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 19 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 20 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 21 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 22 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 23 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 24 Машина Поста Пример программы решения задачи на машине Поста Пример программы
Описание слайда:

Машина Поста Пример программы решения задачи на машине Поста Пример программы решения задачи на машине Поста Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки. v v v v v Команда Действие 1↕2 Стирание метки;переход к следующей команде 2→3 Сдвиг вправо на один шаг 3?2,4 Если клетка пустая, то переход к команде 2, иначе – к команде 4 4←5 Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы) 5v6 Запись метки в пустую клетку 6! Остановка машины

№ слайда 25 Машина Поста В процессе выполнения приведенной программы многократно повторя­
Описание слайда:

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

№ слайда 26 Машина Поста Назначение машины Поста — производить преобразования на инфор­ма
Описание слайда:

Машина Поста Назначение машины Поста — производить преобразования на инфор­мационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат реше­ния задачи. Кроме того, в исходные данные входит информация о началь­ном положении каретки. На информационной ленте машины Поста расположен массив из N меток. Каретка расположена под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы? 1 → 2 2 ↕ 3 3 → 4 4? 5, 2 5 ← 6 6 V 7 7 ! Закрепление материала Задание 1

№ слайда 27 Машина Поста Назначение машины Поста — производить преобразования на инфор­ма
Описание слайда:

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

№ слайда 28 Машина Поста Назначение машины Поста — производить преобразования на инфор­ма
Описание слайда:

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

№ слайда 29 Машина Поста Назначение машины Поста — производить преобразования на инфор­ма
Описание слайда:

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

№ слайда 30 Домашнее задание: § 45, отвечать на вопросы, задачи № 1-8 2. Подготовьте сооб
Описание слайда:

Домашнее задание: § 45, отвечать на вопросы, задачи № 1-8 2. Подготовьте сообщение: «Какие бывают машины Тьюринга?» «Эзотерические языки программирования» «Рекурсивные функции»


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


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

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

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

Автор
Дата добавления 10.02.2016
Раздел Информатика
Подраздел Презентации
Просмотров323
Номер материала ДВ-439736
Получить свидетельство о публикации
Похожие материалы

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