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

• 1 слайд

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

• 2 слайд

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

• 3 слайд

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

• 4 слайд

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

• 5 слайд

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

• 6 слайд

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

• 7 слайд

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

• 8 слайд

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

• 9 слайд

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

• 10 слайд

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

• 11 слайд

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

• 12 слайд

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

• 13 слайд

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

• 14 слайд

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

• 15 слайд

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

• 16 слайд

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

• 17 слайд

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

• 18 слайд

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

• 19 слайд

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

• 20 слайд

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

• 21 слайд

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