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

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

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

Благодаря этой рекламе сайт может продолжать свое существование, спасибо за просмотр.

Основоположниками теории алгоритмов являются: английский ученый Алан Тьюринг (рис 1) американский ученый Эмиль Пост (рис 2) русский ученый Андрей Марков (рис 3) рис 1 рис 2 рис 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задачи для практической работы Написать программу, которая ставит три метки подряд. 2) Написать программу, которая ставит три метки через одну клетку. 3) Написать программу, которая вычисляет сумму двух чисел. V V V V V V