Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов
 Скачать 3.39 Mb.
|
Практическая работа №13. Составление программ для машины ПостаЦель работы: Формирование представления учащихся об универсальном исполнителе алгоритмов. Получение навыков построения программ для машины Поста. Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы. В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста. Машина Поста состоит из … бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак), головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку. Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы. Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис: i K j, где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка). Всего для машины Поста существует шесть типов команд: V j - поставить метку, перейти к j-й строке программы. X j - стереть метку, перейти к j-й строке программы. <- j - сдвинуться влево, перейти к j-й строке программы. -> j - сдвинуться вправо, перейти к j-й строке программы. ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы. ! – конец программы (стоп). У команды «стоп» отсылки нет. Варианты окончания выполнения программы на машине Поста: Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми). Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией). Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга. Почему достаточно лишь два различных символа (есть метка, нет метки)? Дело в том, что любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита. Порядок работы Запустить программу Algo2000.exe и при помощи команды ИНТЕРПРЕТАТОР перевести ее в режим работы Машина Поста. Используя файл add.pst, изучить принцип программирования на машине Algo2000.exe. Порядок работы машины Поста Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки. Чтобы машина Поста работала, надо задать некоторую программу и некоторое состояние машины (т.е. нужно как-то расставить метки по секциям ленты, в частности, можно все секции оставить пустыми, и поставить каретку против одной из секций). Работа машины на основании заданной программы происходит следующим образом. Машина приводится в начальное состояние и приступает к выполнению первой команды программы. Эта команда выполняется за один шаг, после чего машины приступает к выполнению той команды, номер которой равен отсылке первой команды. Эта команда также выполняется за один шаг, после чего начинается выполнение той команды, номер команды которой равен отсылке предыдущей команды. Вообще каждая команда выполняется за один шаг, а переход от выполнения одной команды к выполнению другой происходит по следующему правилу: пусть на k-ом шаге выполнялась команда с номером a, тогда: 1) если эта команда имеет единственную отсылку b, то на (k + 1)-ом шаге выполняется команда с номером b; 2) если эта команда имеет две отсылки b1 и b2, то на (k + 1)-ом шаге выполняется одна из двух команд - с номером b1 или с номером b2; 3) если же выполняющаяся на k-ом шаге команда вовсе не имеет отсылки, то на (k +1) - ом шаге и на всех последующих шагах не выполняется никакая команда – машина останавливается. Возможные случаи останова машины Поста: 1) в ходе выполнения программы машина дойдет до выполнения невыполнимой команды; выполнение программы прекращается, машина останавливается - происходит безрезультатная остановка. 2) в ходе выполнения программы машина дойдет до выполнения команды остановки; программа в этом случае считается выполненной, машина останавливается - происходит результативная остановка. 3) в ходе выполнения программы машина не дойдет до выполнения ни одной из команд, указанных в первых двух вариантах; выполнение программы при этом никогда не прекращается, машина никогда не останавливается - процесс работы машины происходит бесконечно. 3.2. Информационная лента машины Поста Лента состоит из 1999 ячеек, нумерация от -999 до 999. Ячейка с толстой рамкой, находящаяся в центре ленты - каретка. Всплывающее меню ленты вызывается при щелчке правой кнопкой мыши на ленте. При получении фокуса лентой на ней появляется курсор (синий прямоугольник). Его можно сдвигать по ленте вправо и влево клавишами управления курсором. Удерживая клавишу Shift и нажимая клавиши "Влево"/ "Вправо" можно выделить несколько ячеек. Также ячейки можно выделить мышью: удерживая левую кнопку и выделив нужные. Метки ставятся/ удаляются в ячейках, которые выделены. Это можно сделать несколькими способами (лента должна быть сфокусирована): • клавишей "Пробел" • щелкнуть мышью на кнопку "V" на панели инструментов • выбрать пункт главного или всплывающего меню "поставить/ удалить метки" • двойным щелчком мыши (в этом случае изменение происходит только в одной ячейке). Клавиши управления курсором "Вверх" или "Вниз" ставят курсор в каретку. "Home" - курсор в начало видимой части ленты. "End" - курсор в конец видимой части ленты. "Ctrl" + "Влево" - сдвиг каретки влево "Ctrl" + "Вправо" - сдвиг каретки вправо Кнопки со стрелкой слева и справа от ленты - прокрутить каретку соответственно влево и вправо. Кнопки со стрелкой и вертикальной палочкой слева и справа от ленты - прокрутить каретку соответственно до крайней левой отмеченной ячейки и до крайней правой отмеченной ячейке. Номера этих ячеек указываются в строке состояния как мин и макс соответственно. Можно непосредственно поставить каретку в нужную ячейку, указав ее номер в редакторе над кареткой. Ленту можно запомнить (пункт меню Команда/ Запомнить ленту) и затем восстановить (Команда/ Восстановить ленту). 3.3. Исполнение алгоритма машины Поста Запуск алгоритма на исполнение осуществляется: • пунктом главного меню Пуск/ Запустить • кнопкой Запустить на панели инструментов При этом выполнение программы будет идти до тех пор, пока не встретиться команда стоп или не возникнет какая-нибудь ошибка. Приостановить выполнение можно: • пунктом главного меню Пуск/ Пауза; • кнопкой Пауза на панели инструментов. Если выполнение не было приостановлено, то оно всегда начинается с первой команды алгоритма. Если была нажата пауза, то можно продолжить выполнение с той команды, на которой машина остановилась. Программу можно выполнить по шагам: • пунктом главного меню Пуск/ Пошагово; • кнопкой Пошагово на панели инструментов. При этом выполнится очередная команда и выполнение приостановится. Полностью прервать выполнение программы можно: • пунктом главного меню Пуск/ Прервать; • кнопкой Прервать на панели инструментов. Регулировать скорость выполнения можно: • пунктом главного меню Скорость 3.4. Ошибки машины Поста При возникновении этих ошибок происходит прерывание исполнения алгоритма. • Не указана команда • Не указана отсылка • Неверно указан номер отсылки • Команды с таким номером не существует • Нельзя поставить метку, где она уже есть • Нельзя стереть метку, где ее нет • Ошибка чтения файла • Ошибка записи файла Пример Увеличить число 3 на единицу (изменить значение в памяти с 3 на 4). Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д. Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так: 1 -> 2 2 ? 1;3 3 <- 4 4 V 5 5 ! А процесс выполнения может быть таким:  Приведем программу для сложения целых неотрицательных чисел a и b на машине Поста, когда головка находится над числом a, а число b находится правее числа a на некоторое количество клеток. Эта программа реализует следующий алгоритм: первое число постепенно придвигается ко второму до их слияния, а потом стирается одна метка (иначе результат оказался бы на единицу больше правильного).  В случае более сложных начальных условий, когда неизвестно, справа или слева от головки (и на какое число клеток) находится число, можно применить такой принцип поиска числа: двигая головку поочередно вправо и влево и отмечая метками степень удаления головки от исходного положения, найти число, а потом уже применить известную программу сложения. При этом проверяется, находится ли головка над одной из меток числа и если да, то такая задача уже решена, иначе проверяется пуста ли секция справа от головки и следующая за ней; если обе пусты, то делается возврат головки на один шаг и ставится метка, а затем такая же операция выполняется слева и по отмеченной дорожке головка возвращается вправо и т.д. до тех пор, пока головка не натолкнется на число, после чего можно применить ранее рассмотренные выше программы:  Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют: - неделимые носители информации (клетки - биты), которые могут быть заполненными или незаполненными; - ограниченный набор элементарных действий - команд, каждая из которых выполняется за один такт (шаг). Обе машины работают на основе программы. Однако, в машине Поста информация располагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно шире и выразительнее, чем команды машины Поста и т.д. Задание Пояснения к условиям задач 1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками. 2) Если в задаче говорится, что на ленте задано число в унарной системе, то имеется в виду, что натуральное число n закодировано с помощью массива длины n. 3) В задачах при описании начального состояния ленты будем указывать то, что записано начиная с самой левой непустой ячейки и заканчивая самой правой непустой ячейкой. При этом будем использовать следующие обозначения: n подряд идущих меток будем обозначать 1n, а m пустых ячеек — 0m. При обозначении одной заполненной или пустой ячейки будем писать просто 1 или 0, соответственно. К примеру, запись “12012” будет соответствовать записи “11011” на ленте. 4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой. 1. Составьте и проверьте программу для машины Поста, создающую на ленте копию заданной последовательности меток справа от нее. 2. На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки. 3. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива. 4. Даны два массива меток, которые находятся на не котором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива. Дополнительные задания 1. Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение. 2. На ленте машины Поста расположен массив из n меток (метки расположены через пробел). Нужно сжать массив так, чтобы все n меток занимали n расположенных подряд ячеек. 3. Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом. |