4.8. Схемы алгоритмов

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

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

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

Для этого можно пользоваться логическими схемами (операторными выражениями) , предполагая, что функции операторов и условий заданы, однако не считая, что логическая схема отражает структуру алгоритма. При этом логическая схема является отражением так называемой функциональной структуры алгоритма, задает его "смысл". В такой схеме операторами являются не алгоритмы, а функции, т. е. мы возвращаемся к тому смыслу операторов, который был введен в функциональном анализе, сохраняя форму записи, принятую для логических схем (изображая переходы стрелками, а начало и конец с помощью операторов И_О и Я).

Пример 4.2. Требуется составить семантическую схему алгоритма внесения данных в таблицу и выдачи их из таблицы (по запросу).

Обозначим таблицу через , код, которой может быть либо приказом о включении данных в таблицу, либо запросом - через . Пусть - условие "z - запрос"; - условие "z - приказ о включении данных в t"; - процедура поиска ответа; - процедура внесения данных в таблицу ; θ - процедура выдачи кода "непонятно". При таких обозначениях семантическая схема искомого алгоритма может быть дана в виде

Она же в виде блок-схемы приведена на рис. 4.2.

Рис. 4.2. Логическая схема алгоритма внесения данных в таблицу и их выдачи из нее

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

Формальный язык для записи семантических схем зададим следующим образом:

Метасимволы <функциональный знак> и <предикатный знак>^* оставим неопределенными для того, чтобы при записи схем иметь возможность применять любые удобные нам символы. Метасимволом <число> обозначаем запись числа, произведенную арабскими цифрами. Приведем еще одну метаформулу

^* (Предикатным знаком называется символ, которым обозначено условие.)

При записи схем алгоритмов будем пользоваться правилами, изложенными выше.

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

Формальный язык для записи схем выбран так, чтобы схемы можно было читать на русском языке. При этом знак "→" следует произносить как "перейти к", а знак " : =" как "присвоить значение" (стоящее слева от него - произносить в дательном падеже, а стоящее справа - в родительном).