Презентация, доклад по теме Машина Поста

Содержание

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

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

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

Слайд 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Пример программы решения задачи на машине Поста
Исходное состояние показано на рисунке.

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

v

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

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

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

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

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

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

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

Это сайт презентаций, где можно хранить и обмениваться своими презентациями, докладами, проектами, шаблонами в формате PowerPoint с другими пользователями. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами.


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

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

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

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