Автоматическая обработка информации
Цель урока: дать учащимся представление об автоматической
обработке информации
Задачи урока:
- изучить
и закрепить основные понятия: машина Поста, каретка
- сформировать
понятие о принципе работы машины Поста на примерах
- развитие
логического мышления, расширение кругозора;
- воспитание
информационной культуры учеников.
Тип урока: изучение нового материала.
План урока:
- Организационный
момент (1 мин.).
- Актуализация
знаний. (5 мин.)
- Объяснение
и закрепление нового материала. (20 мин.)
- Практическая
работа. (10 мин.)
- Подведение
итогов урока. (2 мин.)
- Домашнее
задание. (2 мин.)
• В 30-х годах XX века
возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта
наука: для всякой ли задачи обработки информации может быть построен алгоритм
решения? Но чтобы ответить на этот вопрос, надо сначала договориться об
исполнителе, на которого должен быть ориентирован алгоритм.
• Английский ученый Алан
Тьюринг предложил модель такого исполнителя, получившую название «машина
Тьюринга». По замыслу Тьюринга, его «машина» является универсальным
исполнителем обработки любых символьных последовательностей в любом алфавите.
• Практически одновременно с
Тьюрингом (1936-1937 гг.) другую модель алгоритмической машины описал Эмиль
Пост. Машина Поста работает с двоичным алфавитом и несколько проще в своем
«устройстве». Можно сказать, что машина Поста является частным случаем машины
Тьюринга. Однако именно работа с двоичным алфавитом представляет наибольший
интерес, поскольку, как вы знаете, современный компьютер тоже работает с
двоичным алфавитом.
• Алгоритм, по которому
работает машина Поста, будем называть программой.
• Договоримся о терминологии:
под словом «программа» мы всегда будем понимать алгоритм, записанный по строгим
правилам языка команд исполнителя — на языке программирования для данного
исполнителя.
Опишем
архитектуру машины Поста. Имеется бесконечная информационная лента,
разделенная на позиции — клетки. В каждой клетке может либо стоять метка
(некоторый знак), либо отсутствовать (пусто).
Вдоль ленты движется каретка —
считывающее устройство. На рисунке она обозначена стрелкой. Каретка может
передвигаться шагами: один шаг — смещение на одну клетку вправо или влево.
Клетку, под которой установлена каретка, будем называть текущей.
Каретка является еще и процессором
машины. С ее помощью машина может:
• распознать, пустая
клетка или помеченная знаком;
• стереть знак в текущей
клетке;
• записать знак в пустую
текущую клетку.
Если произвести замену меток на
единицы, а пустых клеток — на нули, то информацию на ленте можно будет
рассматривать как аналог двоичного кода телеграфного сообщения или данных в
памяти компьютера. Существенное отличие каретки-процессора машины Поста от
процессора компьютера состоит в том, что в компьютере возможен доступ
процессора к ячейкам памяти в произвольном порядке, а в машине Поста — только
последовательно.
Назначение машины Поста —
производить преобразования на информационной ленте. Исходное состояние ленты
можно рассматривать как исходные данные задачи, конечное состояние ленты —
результат решения задачи. Кроме того, в исходные данные входит информация о
начальном положении каретки.
Система команд машины Поста
Пример программы решения задачи на
машине Поста
Исходное
состояние показано на рисунке. Машина должна стереть знак в текущей клетке и
присоединить его слева к группе знаков, расположенных справа от каретки.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.