Составление алгоритмов решения несложных задач для управления машиной Поста

• 1 слайд

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

• 2 слайд

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

• 3 слайд

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

• 4 слайд

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

• 5 слайд

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

• 6 слайд

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

• 7 слайд

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

• 8 слайд

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

• 9 слайд

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

• 10 слайд

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

• 11 слайд

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

• 12 слайд

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

• 13 слайд

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

• 14 слайд

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

• 15 слайд

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

• 16 слайд

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

• 17 слайд

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

• 18 слайд

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

• 19 слайд

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

• 20 слайд

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

• 21 слайд

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

• 22 слайд

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

• 23 слайд

  Задание:
  На информационной ленте машины Поста расположен массив из N меток. Каретка расположена под крайней левой меткой. Какое состояние установится на ленте после выполнения следующей программы?
  1 → 2
  2 ↕ 3
  3 → 4
  4? 5, 2
  5 ← 6
  6 V 7
  7 !
  

• 24 слайд

  Задание:
  На ленте поставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.
  

• 25 слайд

  Составить программу перевода информационной ленты из начального состояния в конечное:
  
  Начальное состояние:
  
  
  Конечное состояние:
  
  

• 26 слайд

  Составить программу для прохождения каретки от левой метки к правой. Количество пустых клеток между метками неизвестно.
  Начальное состояние:
  
  
  Конечное состояние:
  
  

• 27 слайд

  Составить программу для заполнения всех клеток от левой метки до правой. Количество пустых клеток между метками неизвестно.
  
  Начальное состояние:
  Конечное состояние: