|
1.
Цель работы
Изучить машину
Поста и способы написания алгоритмов для нее. Получить навыки по написанию
алгоритмов решения различных задача для машины Поста.
2.
Теоретический материал
Абстрактная машина Поста:
бесконечная лента, разделенная на клетки (пустые либо с меткой «V») и головка,
способная перемещаться вдоль ленты на одну клетку вправо или влево, наносить в
клетку ленты метку, если её метки там не было, стирать если была, или проверять
наличие в клетке метки. Информация о заполненных метками клетках ленты
характеризует состояние ленты, которое может меняться в процессе работы машины.
В каждый момент времени головка
(«-») находится над одной из клеток ленты и, как говорят, обозревает ее.
Информация о местоположения
головки вместе с состоянием ленты характеризует состояние машины Поста.
Структура команды:
nKm,
где
n –
порядковый номер команды,
K
– действие, выполняемое
головкой,
т –
номер следующей команды, подлежащей выполнению.
Существует всего шесть команд
машины Поста.
Посмотреть ячейку: если ячейка
пустая, то перейти на команду с номером 3, иначе на команду с номером
1.
Программой для машины Поста
будем называть непустой список команд, такой что
1.
на п-м месте команда с номером
n;
2.
номер т каждой команды совпадает с
номером какой-либо команды списка.
С точки зрения свойств
алгоритмов, изучаемых с помощью машины Поста, наибольший интерес представляют
причины останова машины при выполнении программы:
1.
останов по команде «стоп»; такой останов
называется результативным и указывает на корректность алгоритма
(программы);
2.
останов при выполнении недопустимой
команды; в этом случае останов называется безрезультативным;
3.
машина не останавливается никогда; в этом и
в предыдущем случае мы имеем дело с некорректным алгоритмом (программой).
Будем понимать под начальным
состояние головки против пустой клетки левее самой левой метки на ленте.
Пример №1.
Пусть задано исходное состояние головки и требуется на пустой ленте написать две
метки: одну в секцию под головкой, вторую справа от нее.
Пример №2.
Командой условного перехода можно воспользоваться для организации циклического
процесса. Пусть на ленте имеется запись из нескольких меток подряд и головка
находится над самой крайней меткой справа. Требуется перевести головку влево до
первой пустой позиции.
Пример №3.
Представление чисел на ленте машины Поста и выполнение операций над ними. Число
k представляется на ленте машины Поста идущими подряд k + 1 метками (одна метка
означает число «О»). Между двумя числами делается интервал как минимум из одной
пустой секции на ленте. Например, запись чисел 2 и 4 на ленте машины Поста будет
выглядеть так:
Обратим внимание, что
используемая в машине Поста система записи чисел является непозиционной.
Программа для прибавления к
произвольному числу единицы. Предположим, что на ленте записано только одно
число и головка находится над одной из клеток, в которой находится метка,
принадлежащая этому числу.
Предположим, что головка
расположена на расстоянии нескольких клеток слева от числа, к которому нужно
прибавить единицу. В этом случае программа усложняется. Появится «блок поиска
числа» - две команды, приводящие головку в состояние, рассмотренное в предыдущем
примере:
Программы добавляющие единицу
слева и справа.
Машину Поста можно
рассматривать как упрощенную модель ЭВМ - как ЭВМ, так и машина Поста имеют:
-
неделимые
носители информации (клетки - биты), которые могут быть заполненными или
незаполненными;
-
ограниченный
набор элементарных действий - команд, каждая из которых выполняется за один такт
(шаг).
Обе машины работают на основе
программы. Однако, в машине Поста информация располагается линейно и читается
подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно
шире и выразительнее, чем команды машины Поста и т.д.
3.
Порядок выполнения работы
1.
Изучить предлагаемый теоретический
материал.
2.
Выполнить следующие
задания:
1.
Напишите программу для машины Поста для
увеличения числа на 3.
2.
Напишите программу для сложения целых
неотрицательных чисел а и
b
на машине Поста, когда головка находится над числом а, а число b
находится правее числа а на некоторое число клеток.
4.
Содержание отчета
В отчете следует указать:
-
Цель работы
-
Введение
-
Программно-аппаратные средства, используемые при выполнении работы.
-
Основную часть (описание самой работы), выполненную согласно требованиям к
результатам выполнения лабораторного практикума.
-
Заключение (выводы).
-
Список используемой литературы.
5.
Литература
1.
Могилев А.В., Пак Н.И., Хенкер Е.К.
Информатика. Учебное пособие. – М.: Академия, 2004, 3-е издание.
2.
Могилев А.В., Пак Н.И., Хенкер Е.К.
Практикум по информатике. - М.: Академия, 2005, 2-е изд.
3.
Шауцукова Л.З. Информатика
http://book.kbsu.ru,
2002.
4.
Сырецкий Г.А. Информатика. Фундаментальный курс.
В 2
томах. – БХВ-Петербург,
2007.
5.
Каймин В.А. Информатика. – М.: Инфра-М.
2001, 2-е изд., доп. и перераб.
6.
Острейковский В.А., Полякова И.В.
Информатика. Теория и практика. – М.: Оникс, 2008.
7.
Степанов А.Н. Информатика. Учебник для
вузов. – СПб.: Питер, 2006, 4-е изд.
8.
Рыжиков Ю.И.
Информатика. Лекции и практикум. – СПб.: Корона принт.
2000.
9.
Андреева Е., Фалина И. Информатика. Системы
счисления и компьютерная арифметика. – М.: Лаборатория Базовых Знаний. 1999.
10. Л.З.
Информатика
http://book.kbsu.ru,
2002.
11. В.М.
Введение в информатику http://www.intuit.ru/department/informatics/intinfo,
2006.
12. В.М.
Введение в информатику. Практикум http://www.intuit.ru/department/informatics/intinfopr,
2008.
13. Е.А.
Практическая информатика http://www.intuit.ru/department/se/pinform, 2006
14. Н.Н.
Стили и методы программирования http://www.intuit.ru/department/se/progstyles,
2005
|
