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

Доступен только на StudyGur

Тема:
Скачиваний: 1
Страниц: 24
Опубликован:
ЧИТАЙТЕ ПОЛНЫЙ ТЕКСТ ДОКУМЕНТА

ПРЕДПРОСМОТР

Автоматическая
обработка
информации
Информатика 10 класс
• В 30-х годах XX века возникает новая наука —
теория алгоритмов. Вопрос, на который ищет
ответ эта наука: для всякой ли задачи обработки
информации может быть построен алгоритм
решения? Но чтобы ответить на этот вопрос, надо
сначала договориться об исполнителе, на
которого должен быть ориентирован алгоритм.
• Английский ученый Алан Тьюринг
предложил модель такого исполнителя, получившую название «машина
Тьюринга». По замыслу Тьюринга, его
«машина» является универсальным
исполнителем обработки любых
символьных последовательностей в
любом алфавите.
• Практически одновременно с
Тьюрингом (1936-1937 гг.) другую
модель алгоритмической
машины описал Эмиль Пост.
Машина Поста работает с
двоичным алфавитом и
несколько проще в своем
«устройстве». Можно сказать, что
машина Поста является частным
случаем машины Тьюринга.
Однако именно работа с двоичным алфавитом представляет
наибольший интерес, поскольку,
как вы знаете, современный
компьютер тоже работает с
двоичным алфавитом.
• Алгоритм, по которому работает машина Поста,
будем называть программой.
• Договоримся о терминологии: под словом
«программа» мы всегда будем понимать
алгоритм, записанный по строгим правилам
языка команд исполнителя — на языке
программирования для данного исполнителя.
• Опишем архитектуру машины Поста. Имеется
бесконечная информационная лента, разделенная на
позиции — клетки. В каждой клетке может либо стоять
метка (некоторый знак), либо отсутствовать (пусто).
v
v
v
v
v
Вдоль ленты движется каретка — считывающее устройство. На рисунке она
обозначена стрелкой. Каретка может передвигаться шагами: один шаг —
смещение на одну клетку вправо или влево. Клетку, под которой
установлена каретка, будем называть текущей.
Каретка является еще и процессором машины. С ее помощью машина
может:
•
распознать, пустая клетка или помеченная знаком;
•
стереть знак в текущей клетке;
•
записать знак в пустую текущую клетку.
• Если произвести замену меток на единицы, а
пустых клеток — на нули, то информацию на
ленте можно будет рассматривать как аналог
двоичного кода телеграфного сообщения или
данных в памяти компьютера. Существенное
отличие каретки-процессора машины Поста от
процессора компьютера состоит в том, что в
компьютере возможен доступ процессора к
ячейкам памяти в произвольном порядке, а в
машине Поста — только последовательно.
• Назначение машины Поста — производить
преобразования на информационной ленте.
Исходное состояние ленты можно
рассматривать как исходные данные задачи,
конечное состояние ленты — результат решения
задачи. Кроме того, в исходные данные входит
информация о начальном положении каретки.
Система команд
машины Поста
Команда
Действие
n←m
Сдвиг каретки на шаг влево и переход к
выполнению команды с номером m
n→m
Сдвиг каретки на шаг вправо и переход к
выполнению команды с номером m
nvm
Запись метки в текущую пустую клетку и переход к
выполнению команды с номером m
n↕m
Стирание метки в текущей клетке и переход к
выполнению команды с номером m
n!
Остановка выполнения программы
n ? m,k
Переход в зависимости от содержимого текущей
клетки: если текущая клетка пустая, то следующей
будет выполняться команда с номером m, если
непустая – команда с номером k
Пример программы решения
задачи на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения задачи
на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
V
v V
v V
v V
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения задачи
на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения задачи
на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения задачи на
машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения
задачи на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения
задачи на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения
задачи на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения
задачи на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения
задачи на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения
задачи на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
Пример программы решения
задачи на машине Поста
•
Исходное состояние показано на рисунке. Машина должна
стереть знак в текущей клетке и присоединить его слева к группе
знаков, расположенных справа от каретки.
v
v
v
v
v
Команда
Действие
1↕2
Стирание метки; переход к следующей команде
2→3
Сдвиг вправо на один шаг
3 ? 2,4
Если клетка пустая, то переход к команде 2, иначе – к команде 4
4←5
Сдвиг влево на шаг (команда выполнится , когда каретка выйдет на
первый знак группы)
5v6
Запись метки в пустую клетку
6!
Остановка машины
• В процессе выполнения приведенной
программы многократно повторяется
выполнение команд с номерами 2 и 3. Такая
ситуация называется циклом. Напомним, что
цикл относится к числу основных алгоритмических структур вместе со следованием и
ветвлением.
Домашнее задание:
Учебник стр. 74 №1, 2
Источники
• http://images.yandex.ru/yandsearch?rpt=simage&
ed=1&text=%D0%90%D0%BB%D0%B0%D0%BD%20%D
0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0
%B3&p=11&img_url=www.mathcomp.leeds.ac.uk%2
Fturing2012%2FImages%2FTuring7.jpg
• http://ru.wikipedia.org/wiki/Файл:Emil_Leon_Post.jp
g
• Семакин И.Г., Хеннер Е.К., Информатика и ИКТ
10-11. Издательство БИНОМ Лаборатория знаний,
2009
ЗАРЕГИСТРИРУЙТЕСЬ - ЭТО БЕСПЛАТНО

Похожие документы

Машина Поста Доклад по курсу «Системы Искусственного Интеллекта» Шариповой А.Ф. ИУ4-93

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

ppt | 3.3 MB | 29 страниц

умного мячика

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

ppt | 208.4 kB | 14 страниц