Строение алгоритмического процесса.
Алгоритмич. процесс есть процесс последовательного
преобразования конструктивных объектов (к. о.), происходящий дискретными
"шагами"; каждый шаг состоит в смене одного к. о. другим. Так, при применении
А. С к слову baaba возникают последовательно baaba, abaaba, baabab и т.
д. А при применении, скажем, А. вычитания столбиком к паре (307, 49) последовательно
возникнут такие к. о.:
При этом в
ряду сменяющих друг друга к. о. каждый последующий полностью определяется
(в рамках данного А.) непосредственно предшествующим. При более строгом
подходе предполагается также, что переход от каждого к. о. к непосредственно
следующему достаточно "элементарен" - в том смысле, что происходящее за
один шаг преобразование предыдущего к. о. в следующий носит локальный характер
(преобразованию подвергается не весь к. о., а лишь нек-рая, заранее ограниченная
для данного А. его часть и само это преобразование определяется не всем
предыдущим к. о., а лишь этой ограниченной частью).
Т. о., наряду
с совокупностями возможных исходных данных и возможных результатов, для
каждого А. имеется ещё совокупность промежуточных результатов (п. р.),
представляющая собой ту рабочую среду, в к-рой развивается алгоритмич.
процесс. Для ? все три совокупности совпадают, а для А. вычитания столбиком
- нет; возможными исходными данными служат пары чисел, возможными результатами
- числа (все в десятичной системе), а промежуточные результаты
суть "трёхэтажные"
записи вида
, где
q - есть запись
числа в десятичной системе, r - такая запись или пустое слово, ар - запись
числа в десятичной системе с допущением точек над нек-рыми цифрами. Работа
А. начинается подготовительным шагом, на к-ром возможное исходное данное
преобразуется в начальный член ряда сменяющих друг друга промежуточных
результатов; это преобразование происходит на основе специального, входящего
в состав рассматриваемого А. "правила начала". Это правило для
состоит
в применении тождественного преобразования, а для А. вычитания - в замене
пары
на запись -
,
Затем применяется "правило непосредственной переработки", осуществляющее
последоват. преобразования каждого возникающего промежуточного результата
в следующий. Эти преобразования происходят до тех пор, пока нек-рое испытание,
к-рому подвергаются все промежуточные результаты по мере их возникновения,
не покажет, что данный промежуточный результат является заключительным;
это испытание производится на основе спец. "правила окончания". Напр.,
для С правило окончания состоит в проверке, не начинается ли промежуточный
результат на ая. (Если ни для какого из возникающих промежуточных результатов
правило окончания не даёт сигнала остановки, то либо к каждому из возникающих
промежуточных результатов применимо правило непосредственной переработки,
и алгоритмич. процесс продолжается неограниченно, либо же к нек-рому промежуточному
результату правило непосредств. переработки оказывается неприменимым, и
процесс оканчивается безрезультатно.) Наконец, из заключительного промежуточного
результата - также на основе спец. правила - извлекается окончательный
результат; для С это извлечение состоит в отбрасывании первых двух букв
а, а для А. вычитания - в отбрасывании всего, кроме самой нижней строчки
цифр. (Во многих важных случаях правило начала и правило извлечения результата
задают тождественные преобразования и потому отдельно не формулируются.)
Т. о., для каждого А. можно выделить 7 характеризующих его (не независимых!)
параметров: 1) совокупность возможных исходных данных, 2) совокупность
возможных результатов, 3) совокупность промежуточных результатов, 4) правило
начала, 5) правило непосредств. переработки, 6) правило окончания, 7) правило
извлечения результата.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я