ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6581
Скачиваний: 50
41
КОН
При построении новых алгоритмов могут использоваться алгоритмы, составленные ранее.
Алгоритмы, целиком используемые в составе других алгоритмов, называют вспомогательными
алгоритмами. Вспомогательным может оказаться любой алгоритм из числа ранее составленных.
Не исключается также, что вспомогательным в определенной ситуации может оказаться алгоритм,
сам содержащий ссылку на вспомогательные алгоритмы.
Очень часто при составлении алгоритмов возникает необходимость использования в каче-
стве вспомогательного одного и того же алгоритма, который к тому же может быть весьма слож-
ным и громоздким. Было бы нерационально, начиная работу, каждый раз заново составлять и за-
поминать такой алгоритм для его последующего использования. Поэтому в практике широко ис-
пользуют, так называемые, встроенные (или стандартные) вспомогательные алгоритмы, т.е. такие
алгоритмы, которые постоянно имеются в распоряжении исполнителя. Обращение к таким алго-
ритмам осуществляется так же, как и к «обычным» вспомогательным алгоритмам. У исполнителя-
робота встроенным вспомогательным алгоритмом может быть перемещение в склад из любой
точки рабочего поля; у исполнителя-язык программирования Бейсик это, например, встроенный
алгоритм «SIN».
Алгоритм может содержать обращение к самому себе как вспомогательному и в этом слу-
чае его называют
рекурсивным.
Если команда обращения алгоритма к самому себе находится в
самом алгоритме, то такую рекурсию называют прямой. Возможны случаи, когда рекурсивный
вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алго-
ритме имеется обращение. Такая рекурсия называется
косвенной.
Пример прямой рекурсии:
АЛГ движение
НАЧ
вперед
вперед
вправо
движение
КОН
Алгоритмы, при исполнении которых порядок следования команд определяется в зависи-
мости от результатов проверки некоторых условий, называют
разветвляющимися.
Для их описа-
ния в алгоритмическом языке используют специальную составную команду - команда
ветвления.
Она соответствует блок-схеме «альтернатива» и также может иметь полную или сокращенную
форму. Применительно к исполнителю-роботу условием может быть проверка нахождения робота
у края рабочего поля (край/не_край); проверка наличия объекта в текущей клетке (есть/нет) и не-
которые другие:
ЕСЛИ условие
ЕСЛИ условие
ЕСЛИ край
ТО серия 1
ТО серия
ТО вправо
ИНАЧЕ серия2
ВСЕ
ИНАЧЕ вперед
ВСЕ
ВСЕ
Ниже приводится запись на алгоритмическом языке команды выбора (см. рис. 1.14, б), яв-
ляющейся развитием команды ветвления:
ВЫБОР
ПРИ условие 1:
серия 1
ПРИ условие 2:
серия 2
…
ПРИ условие N:
серия N
ИНАЧЕ
серия N+1
ВСЕ
Алгоритмы, при исполнении которых отдельные команды или серии команд выполняются
42
неоднократно, называют циклическими. Для организации циклических алгоритмов в алгоритми-
ческом языке используют специальную составную команду цикла. Она соответствует блок-схемам
типа «итерация» и может принимать следующий вид:
ПОКА условие
НЦ
НЦ
серия
Серия
ДО условие
КЦ
КЦ
В случае составления алгоритмов работы с величинами можно рассмотреть и другие воз-
можные алгоритмические конструкции, например, цикл с параметром или выбор. Подробно эти
конструкции будут рассматриваться при знакомстве с реальными языками программирования.
В заключение данного параграфа приведем алгоритм, составленный для исполнителя-
робота, по которому робот переносит все объекты со склада в левый нижний угол рабочего поля
(поле может иметь произвольные размеры):
АЛГ перенос
АЛГ в_угол3
АЛГ до_края
НАЧ
НАЧ
НАЧ
в_угол3
до_края
ПОКА не_край
ЕСЛИ есть
вправо
НЦ
ТО
до_края
вперед
взять
вправо
КЦ
в_угол3
КОН
КОН
установить
перенос
ИНАЧЕ
в_угол3
ВСЕ
КОН
Контрольные вопросы
1. Каковы возможные подходы к определению понятия алгоритм?
2. Кто (что) может быть исполнителем алгоритма?
3. В чем особенности графического способа представления алгоритмов?
4. Каковы основные алгоритмические структуры?
5. Чем определяются свойства алгоритмов «дискретность», «определенность», «понят-
ность», «результативность», «массовость»?
6. Что такое алгоритмический язык?
§7. ФОРМАЛИЗАЦИЯ ПОНЯТИЯ «АЛГОРИТМ»
7.1. ПОСТАНОВКА ПРОБЛЕМЫ
Понятие алгоритма, введенное в предыдущем параграфе, можно назвать понятием алго-
ритма в интуитивном смысле. Оно имеет нечеткий, неформальный характер, ссылается на некото-
рые точно не определенные, но интуитивно понятные вещи. Например, при определении и обсуж-
дении свойств алгоритма мы исходили из возможностей некоторого исполнителя алгоритма. Его
наличие предполагалось, но ничего определенного о нем не было известно. Говоря языком мате-
матики, ни аксиоматического, ни исчерпывающего конструктивного определения исполнителя мы
так и не дали.
Установленные в предыдущем параграфе свойства алгоритмов следует называть эмпириче-
скими. Они выявлены на основе обобщения свойств алгоритмов различной природы и имеют при-
кладной характер. Этих свойств достаточно для практического программирования, для создания
обширного круга программ для компьютеров, станков с ЧПУ, промышленных роботов и т.д. Од-
нако, как фундаментальное научное понятие алгоритм требует более обстоятельного изучения.
43
Оно невозможно без уточнения понятия «алгоритм», более строгого его описания или, как еще го-
ворят, без его
формализации.
Известно несколько подходов к формализации понятия «алгоритм»:
• теория конечных и бесконечных автоматов;
• теория вычислимых (рекурсивных) функций;
• λ-исчисление Черча.
Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии
эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению про-
блемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос,
может ли быть построен алгоритм, приводящий к решению задачи. Мы рассмотрим постановку
этой проблемы и некоторые результаты теории алгоритмической разрешимости задач, но вначале
обсудим формализацию понятия алгоритма в теории автоматов на примере машин Поста, Тьюрин-
га, а также нормальных алгоритмов Маркова, а затем - основы теории рекурсивных функций. Идеи
λ-исчислений Черча реализованы в языке программирования LISP (глава 3).
Вместе с тем, формально определенный любым из известных способов алгоритм не может
в практическом программировании заменить то, что мы называли алгоритмами в предыдущем па-
раграфе. Основная причина состоит в том, что формальное определение резко сужает круг рас-
сматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения.
7.2. МАШИНА ПОСТА
Абстрактные (т.е. существующие не реально, а лишь в воображении) машины Поста и
Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для
них, были предложены независимо друг от друга (и практически одновременно) в 1936 г. амери-
канским математиком Эмилем Постом и английским математиком Алланом Тьюрингом. Эти ма-
шины представляют собой универсальных исполнителей, являющихся полностью детерминиро-
ванными, позволяющих «вводить» начальные данные, и после выполнения программ «читать» ре-
зультат. Машина Поста менее популярна, хотя она значительно проще машины Тьюринга. С ее
помощью можно вести обучение первым навыкам составления программ для ЭВМ.
Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одина-
ковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V», и го-
ловки, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в
клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, или прове-
рять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует
состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени
головка («-») находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о
местоположения головки вместе с состоянием ленты характеризует состояние машины Поста, рис.
1.16.
Рис. 1.16.
Абстрактная машина Поста
Команда машины Поста имеет следующую структуру:
п Km,
где
п -
порядковый номер команды,
K
-действие, выполняемое головкой,
т -
номер следую-
щей команды, подлежащей выполнению.
Существует всего шесть команд машины Поста, рис. 1.17:
44
Рис. 1.17.
Команды машины Поста
Ситуации, в которых головка должна наносить метку там, где она уже имеется, или, наобо-
рот, стирать метку там, где ее нет, являются аварийными (недопустимыми).
Программой для машины Поста будем называть непустой список команд, такой что 1) на
п-
м месте команда с номером
n
; 2) номер
т
каждой команды совпадает с номером какой-либо ко-
манды списка.
С точки зрения свойств алгоритмов, изучаемых с помощью машины Поста, наибольший
интерес представляют причины останова машины при выполнении программы:
1) останов по команде «стоп»; такой останов называется результативным и указывает на
корректность алгоритма (программы);
2) останов при выполнении недопустимой команды; в этом случае останов называется без-
результативным;
3) машина не останавливается никогда; в этом и в предыдущем случае мы имеем дело с не-
корректным алгоритмом (программой).
Будем понимать под начальным состояние головки против пустой клетки левее самой ле-
вой метки на ленте.
Рассмотрим реализацию некоторых типичных элементов программ машины Поста.
1. Пусть задано исходное состояние головки и требуется на пустой ленте написать две мет-
ки: одну в секцию под головкой, вторую справа от нее. Это можно сделать по следующей про-
грамме (справа от команды показан результат ее выполнения):
45
Рис. 1.18.
Пример элемента программы машины Поста
2. Покажем, как можно воспользоваться командой условного перехода для организации
циклического процесса. Пусть на ленте имеется запись из нескольких меток подряд и головка на-
ходится над самой крайней меткой справа. Требуется перевести головку влево до первой пустой
позиции.
Программа будет иметь следующий вид:
Команда условного перехода является одним из основных средств организации цикличе-
ских процессов, например, для нахождения первой метки справа (или слева) от головки, располо-
женной над пустой клеткой; нахождение слева (или справа) от головки пустой клетки, если она
расположена над меткой и т.д.
3. Остановимся на представлении чисел на ленте машины Поста и выполнении операций
над ними.
Число
k
представляется на ленте машины Поста идущими подряд
k
+ 1 метками (одна метка
означает число «О»). Между двумя числами делается интервал как минимум из одной пустой сек-
ции на ленте. Например, запись чисел 3 и 5 на ленте машины Поста будет выглядеть так:
Обратим внимание, что используемая в машине Поста система записи чисел является непо-
зиционной.
Составим программу для прибавления к произвольному числу единицы. Предположим, что
на ленте записано только одно число и головка находится над одной из клеток, в которой находит-
ся метка, принадлежащая этому числу:
Для решения задачи можно переместить головку влево (или вправо) до первой пустой клет-