Презентация, доклад по информатике Автоматическая обработка информации

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

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

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

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

— клетки. В каждой клетке может либо сто­ять метка (некоторый знак), либо отсутствовать (пусто).

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

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

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

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

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

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

клетке и присоединить его слева к группе знаков, расположен­ных справа от каретки.

Пример программы решения задачи на машине Поста

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