Презентация по информатике на тему Автоматическая обработка информации. Машина Поста
Автоматическая обработкаинформации10 класс
В 30-х годах XX века возникает новая наука — теория алгоритмов. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов
Основоположниками теории алгоритмов являются: английский ученый Алан Тьюринг (рис 1)американский ученый Эмиль Пост (рис 2)русский ученый Андрей Марков (рис 3)рис 1рис 2рис 3
Машина постаМашина Поста - абстрактная вычислительная машина, позволяющая решать алгоритмические задачи.Алгоритм, по которому работает машина Поста, будем называть программой.Под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим правилам языка команд исполнителя — на языке программирования для данного исполнителя.
Архитектура машины постаИмеется бесконечная информационная лента, разделенная на позиции — клетки. В каждой клетке может либо стоять метка (некоторый знак), либо отсутствовать (пусто).{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvvvВдоль ленты движется каретка — считывающее устройство. На рисунке она обозначена стрелкой. Каретка может передвигаться шагами: один шаг — смещение на одну клетку вправо или влево. Клетку, под которой установлена каретка, будем называть текущей.Каретка является еще и процессором машины. С ее помощью машина может:• распознать, пустая клетка или помеченная знаком;• стереть знак в текущей клетке;• записать знак в пустую текущую клетку.
Назначение машины Поста — производить преобразования на информационной ленте. Исходное состояние ленты можно рассматривать как исходные данные задачи, конечное состояние ленты — результат решения задачи. Кроме того, в исходные данные входит информация о начальном положении каретки.
Система команд машины Поста {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействиеn ← mСдвиг каретки на шаг влево и переход к выполнению команды с номером mn → mСдвиг каретки на шаг вправо и переход к выполнению команды с номером mn v mЗапись метки в текущую пустую клетку и переход к выполнению команды с номером mn ↕ mСтирание метки в текущей клетке и переход к выполнению команды с номером mn !Остановка выполнения программыn ? m,kПереход в зависимости от содержимого текущей клетки: если текущая клетка пустая, то следующей будет выполняться команда с номером m, если непустая – команда с номером k
Пример программы решения задачи на машине ПостаИсходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машиныv
Исходное состояние показано на рисунке. Машина должна стереть знак в текущей клетке и присоединить его слева к группе знаков, расположенных справа от каретки. {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}vvvvv{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}КомандаДействие1 ↕ 2Стирание метки; переход к следующей команде2 → 3Сдвиг вправо на один шаг3 ? 2,4Если клетка пустая, то переход к команде 2, иначе – к команде 44 ← 5Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на первый знак группы)5 v 6Запись метки в пустую клетку6 !Остановка машины
В процессе выполнения приведенной программы многократно повторяется выполнение команд с номерами 2 и 3. Такая ситуация называется циклом.
Задачи для практической работыНаписать программу, которая ставит три метки подряд.2) Написать программу, которая ставит три метки через одну клетку.3) Написать программу, которая вычисляет сумму двух чисел.VVVVVV