Разделы презентаций


Автоматическая обработка информации. Машина Поста

Содержание

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

Слайды и текст этой презентации

Слайд 1Автоматическая обработка информации.
Машина Поста

Автоматическая обработка информации.Машина Поста

Слайд 2Теория Алгоритмов
В 30-х годах XX века возникает

новая наука — теория алгоритмов. Вопрос, на который ищет ответ

эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения?





Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

Теория Алгоритмов   В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на

Слайд 3 Английский ученый Алан Тьюринг предложил модель такого

исполнителя, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина»

является универсальным исполнителем обработки любых символьных последовательностей в лю­бом алфавите.

МАШИНА ТЬЮРИНГА

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

Слайд 4МАШИНА ПОСТА
Практически одновременно с Тьюрингом (1936-1937

гг.) другую модель алгоритмической машины описал Эмиль Пост. Машина Поста

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

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

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

Слайд 6 Ал­горитм, по которому работает машина Поста, будем

на­зывать программой.
Под словом «программа» мы всегда будем

понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.

Машина Поста

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

Слайд 7 Опишем архитектуру машины Поста. Име­ется

бесконечная информационная лента, разделенная на позиции — клетки. В каждой

клетке может либо сто­ять метка (некоторый знак), либо отсутствовать (пусто).

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

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

Слайд 8Машина Поста
Существенное отличие каретки-процессора

машины Поста от процессора компьютера состоит в том, что в

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

Слайд 9 Назначение машины Поста — производить преобразования

на инфор­мационной ленте.
Исходное состояние

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

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

Слайд 10Машина Поста
Система команд машины Поста

Машина ПостаСистема команд машины Поста

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

рисунке. Машина должна стереть знак в текущей клетке и присоединить

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

Слайд 12Машина Поста
Пример программы решения задачи на машине Поста
Пример программы решения

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

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

задачи на машине Поста
Исходное состояние показано на рисунке. Машина должна

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

Слайд 23Машина Поста

В процессе выполнения приведенной

программы многократно повторя­ется выполнение команд с номерами 2 и 3.

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

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

Слайд 24Определить состояние, в котором окажется машина Поста в результате выполнения

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

что эту ячейку каретка обозревает в начальный момент времени.

Закрепление материала

Задание 1

b) 1) 1100101
     2) 10001

Ответ: Выделенная цифра показывает, на какой ячейке остановится машина.
a) 1) 110000001
    2) 11000001

РЕШЕНИЕ:

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

Слайд 25Закрепление материала
Задание 2
Даны два массива меток,

которые находятся на некотором расстоянии друг от друга. Требуется соединить

их в один массив. Каретка находится над крайней левой меткой первого массива.

ОТВЕТ:

Закрепление материалаЗадание 2    Даны два массива меток, которые находятся на некотором расстоянии друг от

Слайд 26Закрепление материала
Задание 3
На ленте имеется массив из n отмеченных ячеек. Каретка обозревает

крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек

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

ОТВЕТ:

Закрепление материалаЗадание 3На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива

Слайд 27Домашнее задание:
§ 10, № 1, 2
ОТВЕТЫ:
№1: Останется 1 и последняя

метка

Домашнее задание:§ 10, № 1, 2ОТВЕТЫ:№1: Останется 1 и последняя метка

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика