Слайд 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. Такая ситуация называется
циклом. Напомним, что цикл относится к числу основных алгоритмических структур вместе со следованием и ветвлением.