Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Таранина И.В. "Гражданский процесс в схемах " (Юриспруденция)

Смоленский М.Б. "Адвокатская деятельность и адвокатура российской федерации" (Юриспруденция)
Реклама

Машина поста - Успенский В.А.

Успенский В.А. Машина поста — М.: Наука, 1988. — 96 c.
ISBN 5-02-013735-9
Скачать (прямая ссылка): mashinaposta1988.djvu
Предыдущая << 1 .. 6 7 8 9 10 11 < 12 > 13 14 15 16 17 18 .. 38 >> Следующая

объединение классов. Dn
и D'n, а класс Вп - пересечение этих классов. В символах:
DnUD'n = En, Da fl D'n = Bn.
§ 5. Прибавление единицы в самом общем случае
Не будем теперь налагать никаких ограничений на взаимное расположение
каретки и машинной записи числа в начальном состоянии. Требуется,
следовательно, составить программу, которая осуществляла бы прибавление
единицы при условии, что запись исходного числа находится в произвольном
участке ленты и каретка стоит где угодно. Соответствующее требование
формулируется в задаче 5.
Задача 5. Написать такую программу машины Поста, которая для любого п,
будучи применена к произвольному состоянию из класса Еп, дает
результативную остановку в каком-то состоянии из класса Еп+\.
Очевидно, что каждая программа, являющаяся решением задачи 5, будет
одновременно служить решением каждой из предшествующих задач. Однако ни
одно из приведенных выше решений задач 1, Г, 2, 3, 3', 4, 4' не является
решением задачи 5 (проверьте это).
Начальные состояния для задачи 5 показаны на рис. 18, 19 и 20: ведь любое
состояние из Еп принадлежит либо Bnf либо Спу либо С'. Однако теперь
нужно
составить единую программу, приводящую к цели для каждого из видов
начального состояния, показанных на рис. 18, 19, 20. Попытайтесь найти
такую программу самостоятельно. Вы увидите, что это не так просто. А
может быть, требуемой программы не существует вовсе? Тогда попытайтесь
доказать, что ее не существует. Ответ на вопрос, имеет ли задача 5
решение, будет дан в следующей главе.
ГЛАВА ТРЕТЬЯ
АНАЛИЗ И СИНТЕЗ ПРОГРАММ МАШИНЫ ПОСТА
В предшествующих главах мы уже встречались как с задачей синтеза программ
(состоящей в построении Программ, осуществляющих заданные действия), так
и с задачей анализа (состоящей в описании тех преобразований, которые
совершают программы). В данной главе эти задачи будут решаться для более
сложных и содержательных ситуаций: анализ программ будет рассматриваться
в связи с одной задачей, оставшейся нерешенной в предыдущей главе, а
синтез - в связи с задачей о сложении чисел.
§ 1. Диаграммы и блок-схемы
Программы, с которыми мы встречались в предшествующих двух главах,
посвященных машине Поста, были простыми.
Поэтому мы без труда могли как проанализировать заданную программу, т. е.
понять, как она работает, так и синтезировать нужную программу, т. е.
построить программу с требуемыми свойствами.
Но предположим, что дана программа посложнее, например, такая:
Программа V
, /2 2. ^4 ,/5
\3 3. ' '\з
37
V6 <=7 /8 ? 11. 12. => 12 /13 *\19 17. 18. 19. /23 ?\18 116 *?=20
\15 13. ¦ф= 14 20. <=21
=> 9 АО г 14. /5 У \l3 21. /23 ¦\22
'\8 15. =4-16 22. 120
V 11 16. =>17 23. стоп.
Как проанализировать эту программу?
Мы поступим так: разобьем нашу программу на части (которые назовем
блоками) и постараемся понять, как работает каждый блок в отдельности и
как отдельные блоки взаимодействуют между собой. Чтобы найти удобное
разбиение программы V на блоки, составим так называемую диаграмму этой
программы.
На диаграмме программы команды изображаются кружками, а переходы от одной
команды к другой - стрелками. Чтобы построить диаграмму программы V,
нарисуем 23 кружка и пометим их числами от 1 до 23. Проведем от кружка №
i к кружку № / стрелку в том и только в том случае, если i-я команда (т.
е. команда с номером /) имеет отсылку, равную /. В частности, если
i-я команда есть команда остановки, то от /-го кружка не будет отходить
ни одной стрелки, а если /-я команда есть команда передачи управления, то
от /-го кружка будут отходить две стрелки - одна к кружку, отвечающему
верхней отсылке команды, и вторая к кружку, отвечающему нижней отсылке.
Вся наша программа изобразится тогда фигурой, показанной на рис. 21. Эту
фигуру и назовем диаграммой программы V, а составляющие ее кружки -
узлами диаграммы.
Изложенным способом можно построить диаграмму для любой программы.
Последовательная смена выполняемых команд данной программы наглядно
иллюстрируется движением по диаграмме этой программы в направлении
стрелок.
Разобьем теперь нашу программу V на группы команд - блоки, Тем самым на
блоки (группы узлов)
23
разобьется и диаграмма. Нагляднее задавать разбиение на блоки именно как
разбиение диаграммы.
Для наших целей - целей анализа программы V - удобно разбить диаграмму
рис. 21, а вместе с нею и саму программу V на следующие восемь блоков:
1-й блок - назовем его "блоком начала" - состоит из узлов (команд) № 1,
2,
3, 4;
2-й блок - назовем его "блоком проверки влево"- состоит из узлов
(команд)
Кя 5, 6, 7;
3-й блок - назовем его "блоком движения вправо" - состоит из узлов
(команд) № 8, 9;
4-й блок -- назовем его "блоком проверки вправо" - состоит из узлов
(команд) № 10, 11, 12;
5-й блок - назовем его "блоком движения влево"- состоит из узлов
(команд) № 13, 14;
6-й блок - назовем его "блоком стирания вправо"- состоит из узлов
(команд) № 15, 16, 17, 18;
7-й блок - назовем его Рис. 21 "блоком стирания влево" - состоит из
Предыдущая << 1 .. 6 7 8 9 10 11 < 12 > 13 14 15 16 17 18 .. 38 >> Следующая