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

Презентация по информатике на тему "Машина поста"



57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


  • Информатика
Автоматическая обработка информации Информатика 10 класс
Английский ученый Алан Тьюринг предложил модель такого исполни­теля, получивш...
Практически одновременно с Тьюрингом (1936-1937 гг.) другую модель алгоритмич...
Ал­горитм, по которому работает машина Поста, будем на­зывать программой. Дог...
Опишем архитектуру машины Поста. Име­ется бесконечная информационная лента, р...
Если произвести замену меток на единицы, а пустых клеток — на нули, то информ...
Назначение машины Поста — производить преобразования на инфор­мационной ленте...
Система команд машины Поста Команда	Действие n ← m	Сдвиг каретки на шаг влево...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
Пример программы решения задачи на машине Поста Исходное состояние показано н...
В процессе выполнения приведенной программы многократно повторя­ется выполнен...
Источники http://images.yandex.ru/yandsearch?rpt=simage&ed=1&text=%D0%90%D0%B...
1 из 22

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

№ слайда 1 Автоматическая обработка информации Информатика 10 класс
Описание слайда:

Автоматическая обработка информации Информатика 10 класс

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

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

№ слайда 3 Практически одновременно с Тьюрингом (1936-1937 гг.) другую модель алгоритмич
Описание слайда:

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

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

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

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

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

№ слайда 6 Если произвести замену меток на единицы, а пустых клеток — на нули, то информ
Описание слайда:

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

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

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

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

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

№ слайда 9 Пример программы решения задачи на машине Поста Исходное состояние показано н
Описание слайда:

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

№ слайда 10 Пример программы решения задачи на машине Поста Исходное состояние показано н
Описание слайда:

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

№ слайда 11 Пример программы решения задачи на машине Поста Исходное состояние показано н
Описание слайда:

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

№ слайда 12 Пример программы решения задачи на машине Поста Исходное состояние показано н
Описание слайда:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№ слайда 22 Источники http://images.yandex.ru/yandsearch?rpt=simage&ed=1&text=%D0%90%D0%B
Описание слайда:

Источники http://images.yandex.ru/yandsearch?rpt=simage&ed=1&text=%D0%90%D0%BB%D0%B0%D0%BD%20%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3&p=11&img_url=www.mathcomp.leeds.ac.uk%2Fturing2012%2FImages%2FTuring7.jpg http://ru.wikipedia.org/wiki/Файл:Emil_Leon_Post.jpg Семакин И.Г., Хеннер Е.К., Информатика и ИКТ 10-11. Издательство БИНОМ Лаборатория знаний, 2012



57 вебинаров для учителей на разные темы
ПЕРЕЙТИ к бесплатному просмотру
(заказ свидетельства о просмотре - только до 11 декабря)


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

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