Cтраница 4
Узлам такого графа соответствуют некоторые предикаты-признаки; ветвям, исходящим из узла - возможные значения этих признаков. Все ветви заканчиваются листьями, которые ставятся соответственно номеру классов. Каждая ветвь, заканчивающаяся листом, содержит такую совокупность внутренних узлов, среди которых нет узлов, соответствующих одному и тому же значению предикатов. [46]
Предикатный информационный граф можно рассматривать как обобщение контактных схем и АДВ-модели, причем от контактных схем заимствована структура в виде сети с нагрузкой ребер функциями и использование функций проводимости, а от АДВ-модели - способ введения сложности сети. Кроме того, вводится алгоритм обхода сети, похожий на алгоритм разметки графа [51, 61], который можно рассматривать как соответствующий сети алгоритм поиска. Причем в каждой вершине сети, до которой на некотором запросе х дошел алгоритм поиска, каждое из ребер, исходящее из этой вершины, задает возможное направление поиска, и если на этом запросе х значение предиката, соответствующего ребру, равно 1, то в направлении данного ребра поиск продолжается, а если равно 0, то по этому направлению поиск прекращается. Таким образом, из одной вершины сети может возникнуть сразу несколько направлений, по которым поиск продолжается. Но в задачах поиска часто встречается ситуация, когда из нескольких направлений поиска выбирается точно одно, например, так как это происходит в вершине ветвления алгебраического дерева вычислений, когда в зависимости от результата сравнения выбирается одно из двух направлений движения. В таких случаях гораздо удобнее приписать вершине функцию-переключатель и в зависимости от ее значения на запросе выбрать то направление, на которое указывает значение переключателя. [47]
Предикатный информационный граф можно рассматривать как обобщение контактных схем и АДВ-модели, причем от контактных схем заимствована структура в виде сети с нагрузкой ребер функциями и использование функций проводимости, а от АДВ-модели - способ введения сложности сети. Кроме того, вводится алгоритм обхода сети, похожий на алгоритм разметки графа [51, 61], который можно рассматривать как соответствующий сети алгоритм поиска. Причем в каждой вершине сети, до которой на некотором запросе х дошел алгоритм поиска, каждое из ребер, исходящее из этой вершины, задает возможное направление поиска, и если на этом запросе х значение предиката, соответствующего ребру, равно 1, то в направлении данного ребра поиск продол жнется, а если равно 0, то по этому направлению поиск прекращается. Таким образом, из одной вершины сети может возникнуть сразу несколько направлений, по которым поиск продолжается. Но в задачах поиска часто встречается ситуация, когда из нескольких направлений поиска выбирается точно одно, например, так как это происходит в вершине ветвления алгебраического дерева вычислений, когда в зависимости от результата сравнения выбирается одно из двух направлений движения. В таких случаях гораздо удобнее приписать вершине функцию-переключатель и в зависимости от ее значения на запросе выбрать то направление, на которое указывает значение переключателя. [48]
Операторы условного перехода определяют выполнение последовательности двух операций: 1) вычисления предиката и 2) перехода к операторам, обладающим заданными метками. Операция вычисления предиката использует в качестве исходных операндов содержимое ячейки признака результата и некоторую константу, определяемую символическим обозначением оператора, и представляет собой проверку отношения равенства между этими операндами. Результат равен единице, если равенство соблюдается, и нулю в противном случае. Вторая операция использует в качестве операндов значение предиката и два символических адреса, один из которых обязательно задан в адресной конструкции, а второй либо задан в адресной конструкции, либо является неявной меткой оператора, следующего за рассматриваемым. [49]
Таким образом, по отношению к потоку данных программа прежде всего выполняет функцию разделения пространства исходных данных на области, каждая из которых соответствует одному исполняемому маршруту. Ошибки в программе могут быть обусловлены модификацией границы области определенного маршрута, приводящей к расширению или сужению пространства исходных данных соответствующего маршрута. Кроме того, деформация границ областей может приводить к ошибкам уничтожения некоторых областей и потере соответствующих им маршрутов. Причинами таких ошибок могут быть искажения операторов анализа условий или искажения в процессе вычисления значений предикатов при правильном содержании оператора условия. [50]