Similar presentations:
Устройство и система команд алгоритмической машины Поста
1. Устройство и система команд алгоритмической машины Поста.
2. Машина Поста – это абстрактная вычислительная машина, созданная для уточнения понятия алгоритма. Представляет собой
Машина Поста – это абстрактнаявычислительная машина, созданная для
уточнения понятия алгоритма. Представляет
собой универсальный исполнитель,
позволяющий вводить начальные данные и
читать результат выполнения программы.
3. История создания
В 1936 г. американскийматематик Эмиль Пост в
статье описал систему,
обладающую
алгоритмической простотой
и способную определять,
является ли та или иная
задача алгоритмически
разрешимой.
4. Устройство машины
Бесконечнаялента
Машина
Поста
Каретка
5. Принцип действия
Текущее состояние машины Поста описываетсясостоянием ленты и положением каретки.
Состояние ленты – информация о том, какие секции
пусты, а какие отмечены.
Шаг – это движение каретки на одну ячейку влево или
вправо.
Кареткой управляет программа, состоящая из строк
команд. Каретка - считывающее устройство и процессор
машины.
6.
Каждая команда имеет следующийсинтаксис:
i K j,
где i - номер команды,
K – действие каретки,
j - номер следующей команды
(отсылка).
7.
Всего для машины Поста существует шестьтипов команд:
V j - поставить метку, перейти к j-й строке
программы.
↕ j - стереть метку, перейти к j-й строке
программы.
← j - сдвинуться влево, перейти к j-й строке
программы.
→ j - сдвинуться вправо, перейти к j-й строке
программы.
? j1; j2 - если в ячейке нет метки, то перейти к j1-й
строке программы, иначе перейти к j2-й строке
программы.
! – конец программы (стоп).
8. Варианты окончания выполнения программы:
Команда «стоп»;Выполнение недопустимой команды;
Уход в бесконечность, зацикливание.
9.
Программой машины Поста будемназывать конечный список команд машины
Поста, обладающий следующими двумя
свойствами:
• На первом месте в этом списке стоит команда
с номером 1, на втором месте - команда с
номером 2 и т.д.;
• Отсылка любой из команд списка совпадает с
номером некоторой команды списка.
10. Пример работы машины Поста:
Задача 1: увеличить число 3 на единицу.(изменить значение в памяти с 3 на 4).
Решение:
Целое положительное число на ленте машины Поста представимо
идущими подряд метками, которых на одну больше, чем
кодируемое число. Это связано с тем, что одна метка обозначает
ноль, а уже две – единицу, и т.д.
Предположим, что точно известно, что каретка стоит где-то слева от
меток и направлена на пустую ячейку.
11. Пример работы машины Поста:
1. → 22. ? 1;3
3. ←4
4. V 5
5. !
12. Пример работы машины Поста:
Задача 2: стереть метку в текущей клетке иприсоединить ее слева к группе меток,
расположенных справа от каретки
стирание метки, переход к следующей команде
Решение: 1. ↕2
2. → 3
смещение каретки на шаг вправо
3. ? 2;4
если клетка пустая, то перейти к команде 2,
иначе – к команде 4
4. ←5
сдвиг каретки влево
5. V 5
Запись метки в пустую клетку
6. !
Стоп, остановка машины
13. Задача 3
.–поставить метку
14. Задача 4
Решение:1. ←2
2. V 3
3. ←4
4. ↕5
5. ←6
6. V 7
7. ←8
8. ←9
9. !
15. Вывод
Автоматическая обработка информации возможна,если:
Информация представлена в формализованном виде
– в конечном алфавите некоторой знаковой системы;
Реализован исполнитель, обладающий конечной
системой команд;
Реализовано программное управление работой
исполнителя.
Машина Поста – пример автоматического исполнителя
обработки информации с ограниченными
возможностями.
16. Домашнее задание
УчебникВыучить п 10
Задачник
Выполнить письменно стр 186 №1, стр 187 №5
17. Дополнительные источники информации:
Википедия:https://ru.wikipedia
Интернет-ресурс «Планета информатики» :
http://www.inf1.info/machinepost.