Ассоциативные исчисления

Begin

Begin

lel:=c; rel:=A[i+1];

if lel<rel then invel(lel,rel);

c:=rel

end;

minel:=c;

Этот же фрагмент можно упростить, исключив процедуру invel и соответственно переменные lel и rel (на каждом шаге запоминается мини-мальное значение с пары элементов):

c:=A[1];

for i:=2 to n do

if c³a[i] then c:=a[i]; (*текущий минимальный элемент*)

end;

minel:=c;

Реализация операторов while...do и repeat...until в виде СА приведена на рис. 1.15,в и г. Смысл этих операторов заключается в следующем: для первого - пока выполняется условие W, делать S1, S2,..., а для второго - повторять S1, S2,..., пока не выполнится условие U. Раз-личие этих условных операторов заключается в том, что при организации одного и того же вычислительного процесса (S1; S2;..., Sn) условия W и U должны быть противоположны, U=; кроме того, во втором случае после-

довательность операторов выполняется по меньшей мере один раз. Дос-тоинством этих операторов является то, что можно строить циклические алгоритмы с заранее неизвестным числом итераций (повторений) в цикле.

Эти операторы можно использовать и при известном числе повторе-ний; при этом в теле цикла должен быть предусмотрен счётчик, а усло-вием выхода из цикла будет его конечное значение.

Операторы while...do и repeat...until так же, как и оператор if, соз-дают простое разветвление, но в отличие от операторов if они предназ-начены для многократного выполнения одного и того же вычислительного процесса (S1;S2;...Sn).

Отметим, что организация цикла на рис. 1.11 соответствует опера-тору repeat..until для первого варианта СА и оператору while..do - для второго (в обоих вариантах со встроенным счётчиком).

Под термином ² организация цикла ² понимается правильное выпол-нение начала цикла, его завершения и собственно тела цикла.

При организации начала цикла надо обеспечить точное определе-ние начальных значений локальных переменных и параметра цикла, согласование данного цикла с предыдущим фрагментом алгоритма по глобальным переменным и т. д.

При продумывании реализации тела цикла необходимо понять, ка-кие операторы не зависят от параметра цикла, и вынести их из цикла либо обозначить простой переменной, что сократит время выполнения алго-ритма. Если переменная X[I], зависящая от параметра цикла I, встре-чается в теле цикла более двух раз, то имеет смысл переобозначить её (например, Y:=X[I]), с тем чтобы не тратить время (кроме первого раза!) на вычисление адреса этой переменной в оперативной памяти; при выходе из итерации (цикла) следует вернуться к старому обозначению. Важно обнаружить и использовать рекуррентные связи между переменными.

При организации завершения цикла необходимо решить вопрос о том, каким должен быть выход из цикла (когда и как: с использованием предусловия или постусловия)? При этом должно быть гарантировано, что для встроенного счётчика все итерации имеют место. Установить, что выход из цикла осуществляется с нужными значениями параметра цикла. Разобраться, с какими значениями переменных циклический алгоритм заканчивает работу, точнее, надо так организовать цикл, чтобы это были нужные для следующего фрагмента СА значения.

Стыковка вложенных циклов предполагает передачу переменных и параметров, их переобозначение, вспомогательные вычисления (напри-мер, начальных значений параметров внутреннего цикла) и т. д.

Ошибки в организации цикла связаны обычно с неправильным выполнением начала цикла или его конца; именно этим моментам и следует уделить особое внимание.

Обычно для проверки правильности организации цикла рассмат-ривают вычислительный процесс по шагам, каждому из которых соответ-ствует своё значение параметра цикла; это можно сделать как на бумаге, так и на компьютере. Операторы тела цикла выполняют пошагово, причём в случае использования бумаги принимаются следующие упрощения: малое число повторов, данные только целого типа, количество варьиру-емых данных уменьшается до предела, после которого задача теряет смысл, и т.п. Эти упрощения можно сделать при глубоком понимании сути задачи. На рис. 1.11,в приведен образец анализа правильности организа-ции цикла (верификация алгоритма).

1.3. Логические алгоритмы

Логическими принято называть алгоритмы, которые содержат пред-писания (операции) относительно объектов нечисловой природы. Харак-терной особенностью логических алгоритмов является выбор на каждом шаге по определенным правилам альтернативной операции, осуществля-емой при переходе к следующему шагу. К логическим задачам относят многие игры. Однако выделение логических задач из множества математи-ческих задач достаточно условно - в большинстве случаев задачи являются смешанными: в них присутствуют и числовые, и логические операции. Так, машинные алгоритмы игры в шахматы используют на каждом шаге вычис-ление значения некоторой функции, учитывающей оценку позиции после каждого следующего хода (точнее, полухода) и стоимость размена фигур.

Ниже рассматриваются две задачи, носящие выраженный логичес-кий характер.

1.3.1. Задача “Поиск пути в лабиринте”

Эта задача восходит к греческой мифологии, в которой, в частности, описывается подвиг Тезея, проникшего в лабиринт, где обитал чудовищный Минотавр (полубык, получеловек), пожиравший местных красавиц. Тезей разыскал в лабиринте Минотавра и убил его. Выбраться из лабиринта ему помогла Ариадна (А), дав ему вначале клубок ниток, один конец которых держала она сама. По мере углубления Тезея в лабиринт клубок разматы-вался; наматывая потом нитки, Тезей благополучно вернулся к выходу.

Рассмотрим задачу поиска пути в лабиринте в общем случае (для класса подобных задач) и приведём словесное описание алгоритма.

Представим лабиринт в виде конечной системы площадок, от кото-рых расходятся коридоры, причём каждый коридор соединяет две площад-ки (будем называть их смежными); возможно существование таких пло-щадок, из которых можно пройти только в один коридор (такие площадки будем называть тупиками). Геометрически лабиринт можно представить в виде системы точек А, В, С,..., изображающих площадки, и совокупности отрезков АВ, ВС,..., изображающих коридоры, которые соединяют опре-делённые пары данных точек (рис. 1.16). Смежными являются, например, площадки В и С, К и М и т. д., а тупиковыми - площадки А, D, I, J.

Рис. 1.16. Геометрическое представление лабиринта

Будем говорить, что площадка Y достижима из площадки X, если существует путь от X к Y через промежуточные коридоры и площадки. Точ-нее: либо X и Y - смежные площадки, либо существует последователь-ность площадок X1, X2,..., Xn таких, что X и X1, X1 и Х2..., и т.д., и, нако-нец, Xn и Y являются смежными. Отметим, что если Y достижима из X, то она достижима и посредством простого пути, т.е. такого пути, в котором каждая площадка (а тем более и каждый коридор) проходится лишь один раз. Например, путь ABCD является простым, а путь ABCFECD - нет.

Тезей должен был решить задачу: узнать, достижима ли площадка М, на которой находится Минотавр, из площадки А, на которой находится Ариадна, или нет? Если да, то к М можно было добраться по любому пути, но вернуться к площадке А нужно уже по простому пути. Поскольку заранее устройство лабиринта неизвестно, решение задачи должно быть представлено в виде общего метода поиска для любого лабиринта и при любом расположении площадок А и М, т. е. требуется построить алгоритм поиска пути в лабиринте.

Будем условно помечать коридоры следующими красками: непрой-денные ни разу - зелёной, пройденные один раз - жёлтой, пройденные дважды - красной.

Находясь на начальной площадке, Тезей может попасть на одну из смежных площадок посредством одного из следующих двух ходов:

1. Разматывание нити. Прохождение от данной площадки по любому зелёному коридору до смежной площадки. После прохождения этого коридора он считается жёлтым.

2. Наматывание нити. Возвращение от данной площадки по послед-нему пройденному жёлтому коридору до смежной площадки. При этом нить наматывается обратно на клубок, а этот коридор становится красным.

Предполагается, что Тезей делает какие-то пометки, позволяющие ему впоследствии отличать красные коридоры от зёленых; жёлтые разли-чимы тем, что по ним протянута нить Ариадны.

Обстановка на данной площадке характеризуется такими призна-ками.

1. Минотавр. Он обнаружен.

2. Петля. Через данную площадку уже протянута нить Ариадны (иначе: от данной площадки расходятся по крайней мере два жёлтых коридора).

3. Зелёная улица. От данной площадки есть вход по крайней мере в один зелёный коридор.

4. Ариадна. Она на данной площадке.

5. Особый случай. Отсутствие всех предыдущих признаков (например тупик).

Поставим в соответствие каждой обстановке на площадке свой ход.

Признак	Ход
1. Минотавр	Остановка
2. Петля	Наматывание нити
3. Зеленая улица	Разматывание нити
4. Ариадна	Остановка
5. Особый случай	Наматыване нити

Находясь на некоторой площадке, Тезей делает очередной ход следующим образом: он проверяет по порядку номеров в соответствии с левым столбцом таблицы, какой из перечисленных признаков имеет место; обнаружив первый такой признак, он (уже не проверяя остальные признаки) делает соответствующий ход из правого столбца. Такие ходы делаются до тех пор, пока не наступит остановка.

Приведём (без доказательства) утверждения, которые являются обоснованием предложенного метода поиска пути в лабиринте.

1. При любом расположении А и М в лабиринте после конечного числа ходов обязательно наступит остановка либо на площадке Минотавра, либо на площадке Ариадны.

2. Если остановка наступила на М, то Минотавр достижим. Более того, в этом случае нить Ариадны оказывается протянутой по простому пути, ведущему от А к М. Наматывая нить, Тезей может теперь вернуться по этому пути к Ариадне.

3. Если остановка наступила на площадке Ариадны, то Минотавр не достижим.

Отметим, что в случае признака “зелёной улицы” ход не определён однозначно - нарушается свойство детерминированности алгоритма. Этот случай легко исправляется, если ввести дополнительное правило о том, что при наличии нескольких зелёных коридоров Тезей обходит площадку по часовой (против часовой) стрелке, выбирая очередной коридор. Ясно, что в общем случае алгоритм основан на переборе вариантов обхода площадок и коридоров.

1. 3.2. Задача “Ханойские башни”

Эта задача формулируется следующим образом. Имеется три стерж-ня, на одном из которых (назовём его занятым) находятся диски разных диаметров, расположенные на стержне в порядке убывания диаметров снизу вверх; второй стержень назовём свободным, а третий - вспомога-тельным (рис 1.17). Требуется, производя одиночные перемещения дисков, переместить всю “стопку” дисков с занятого стержня на свобод-ный, используя вспомогательный стержень; при этом на любом шаге диски должны быть расположены на каждом стержне в порядке убывания их диаметров.

Рис. 1.17. Ханойские башни

В табл. 1.5 приведен результат решения задачи для случая четырех дисков. Здесь А - занятый в начальный момент (нулевой шаг) стержень, В - свободный, а С - вспомогательный стержень. Цифрами обозначен “номер” диска, причём большему номеру соответствует больший диаметр. Отметим, что в середине процесса решения в качестве вспомогательного выступает то стержень А, то стержень С.

Видно, что процесс перемещения стопки дисков можно разбить на фазы (1-я фаза - шаги 1-8; 2-я фаза - шаги 9-12; 3-я фаза - шаги 13 и 14; 4-я фаза - шаг 15). К началу каждой фазы на вспомогательном (занятом) стержне собирается стопка дисков (в табл. 1.5 номера этих дисков подчёркнуты), затем в течение данной фазы самый нижний диск стопки перемещается на свободный стержень

Таблица 1.5.

Шаг
А	4-1	4-2	4,3	4,3		4,1	4,1		Æ	Æ		2,1	2,1		Æ	Æ
В	Æ	Æ		2,1	2,1		Æ	Æ		4,1	4,1		4,3	4,3	4-2	4-1
С	Æ			Æ			3,2	3-1	3-1	3,2			Æ		1	Æ

Анализ перемещений дисков позволяет выявить определённые зако-номерности, составить словесное описание алгоритма перемещений для общего случая (количество дисков произвольно), а затем перейти к разра-ботке схемы алгоритма.

Чтобы переместить самый нижний диск на стержень В, необходимо 2^n-1 перемещений. Общее число перемещений равно 2ⁿ-1.

Эти утверждения можно доказать по индукции.

Заключение

Любой вычислительный процесс может быть представлен компо-зицией следующих его фрагментов: линейный, ветвящийся, циклический.

Для организации разветвлений и циклов могут быть использованы различные операторы; выбор того или иного оператора в конкретном случае остаётся за программистом.

При организации разветвлений необходимо стремиться миними-зировать логическое выражение, описывающее выбор альтернатив.

При организации циклов особенно важны два момента: правиль-ное построение начала цикла и его конца. Важно также обеспечить стыковку цикла с остальной частью алгоритма или циклов друг с другом при их вложенности.

СА может быть представлена с разной степенью подробности. Так, предопределённый процесс, например блок ввода/вывода, может вклю-чать в себя несколько циклов; визуально фрагмент СА, включающий в себя этот блок, будет выглядеть линейным. В действительности линей-ными могут быть только очень простые алгоритмы или их некоторые фрагменты.

СА допускают эквивалентные преобразования, что может быть использовано для повышения эффективности алгоритмов. Например, имеет смысл выносить, если это возможно, из тела цикла все операторы, не связанные с параметром данного цикла.

Необходимо повышенное внимание уделять особым случаям, которые встречаются в данных либо в формулах (например, в алгоритме нахождения минимального числа множества - это случай, когда входное множество содержит один элемент либо оно пустое; при некоторых вычислениях возникает необходимость деления на 0 и т.п.).

Контрольные вопросы. Упражнения

1. Какие соединения вершин СА являются допустимыми? Предло-жите несколько вариантов произвольных СА, содержащих 8...10 вершин разных типов.

2. Вы сможете доказать, что каждый из рассмотренных в данной главе вычислительных процессов является алгоритмом?

3. Как надо скорректировать СА решения квадратного уравнения (рис 1.4), чтобы при преобразовании уравнения общего вида (1.7) к приведённому учесть случай а = 0 (при этом вычисление p и q связано с делением на 0, что недопустимо)?

4. Как изменится СА для процедуры MIN_A (пример 1.7), которая встроена в некий вычислительный процесс (модуль), если при обращении к этой процедуре возможны случаи, когда сформированный в основном процессе массив А содержит всего один элемент либо пуст?

5. Каким требованиям должны удовлетворять размерности матриц A, B и C, чтобы корректно выполнить матричную операцию D = A + B х C? Сколько циклов понадобится для вычисления матрицы D?

6. Почему некоммутативна в общем случае операция перемножения двух квадратных матриц одинаковой размерности? В каком частном случае коммутативность имеет место?

7. Составьте фрагменты СА для формул (1.16)... (1.19) и сравните попарно фрагменты для формул (1.16), (1.18) и (1.17), (1.19). В каком случае вычисления рациональнее и почему?

8. В чём отличие вариантов с использованием от вариантов без использования оператора case... of? Рассмотрите эти варианты для примера 1.5.

9. Чем отличаются операторы for, while … do, repeat … until?

10. Постройте схему алгоритма выбора, реализующую логическую функцию &, где B1, B2, B3 - некотоpые условия (булевы переменные).

Указание. Ввести промежуточную переменную &.

11. Постройте СА, реализующую предикат p(x) ï a£x<b.

Указание. Учесть, что предикат включает в себя 2 условия.

12. Составьте СА определения максимального элемента множества, содержащего 12 чисел. Какое количество сравнений и перестановок эле-ментов понадобится в случае, если массив отсортирован в порядке возра-стания элементов? Выведите формулу для определения количества срав-нений и перестановок в случае произвольного количества элементов.

13. Составьте словесное описание алгоритма перемножения двух матриц.

14. Для функции y=F(x), представленной разложением в ряд (1.20), постройте схему алгоритма, позволяющего вычислить значение y в точках разбиения с погрешностью e при равномерном разбиении области опре-деления функции [ a,b ] на m частей.

15. Составьте СА поиска пути в лабиринте.

16. Докажите, что в задаче “Ханойские башни” для перемещения n -го (самого нижнего) диска на свободный стержень необходимо 2 ^n-1 одиночных перемещений. Докажите также, что общее число перемещений на свобод-ный диск определяется числом 2 ⁿ -1.

Дата добавления: 2014-01-14