Отношение - предшествование
Cтраница 1
Отношение предшествования называется входящим лесом, если каждая вершина в графе предшествования имеет не более одного непосредственного преемника. Аналогично, является выходящим лесом, если каждая вершина в графе предшествования имеет не более одного непосредственного предшественника. В данном параграфе мы рассмотрим эффективные алгоритмы отыскания оптимальных расписаний для задач, в которых ограничения предшествования являются входящими либо выходящими лесами. Вначале рассматривается задача с входящим лесом, а затем для получения алгоритмов составления расписаний в случае выходящего леса используются соображения двойственности. Мы также представим алгоритм для случая, когда задача составления расписания может быть разделена на две или более независимых задачи. [1]
 |
Моделирование процессов сетями Петри. [2] |
Отношение предшествования рассматривается как базовое, и, используя его, вводят отношения следствия, параллелизма, конкуренции и альтернативы. [3]
 |
Граф вывода. [4] |
Блок 2 проверяет отношение предшествования между верхним символом магазина Ri и очередным символом входного текста L &. Если между символами Ri и Lfe отношение вида i - i ( пусто), значит, во входном тексте допущена ошибка. [5]
Однако требование единственности отношений предшествования между каждой парой символов вызывает необходимость перестройки грамматики языка. [6]
 |
Стек и входная строка до редукции. [7] |
Первое условие обеспечивает единственность отношения предшествования для каждой упорядоченной пары соседних символов в приводимой строке. Если между какими-либо двумя символами нет отношения предшествования, то это означает, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной сентенциальной формы. [8]
Вообше говоря, неоднозначность отношений предшествования, встречающаяся в грамматиках языков программирования, следствие того, что для выделения основы в методе предшествования используется минимальный контекст: сравниваются лишь пары символов. Для устранения неоднозначности, если она появляется, нужно либо изменить грамматику ( подробнее об этом будет сказано ниже), либо использовать более далекий контекст. [9]
Каждое из предусмотренных аксиомой У отношений предшествования называется ориентацией прямой. Прямая с заданной на ней ориентацией называется ориентированной прямой или осью. [10]
Ясно, что если - - отношение предшествования, то - - также отношение предшествования. [11]
В грамматике с операторным предшествованием существует однозначное отношение предшествования между операторами ( терминальными символами), не зависящее от операндов ( нетерминалов), находящихся между операторами. Только операторы определяют, принадлежат ли они одной и той же основе сентенциальной формы или нет; принадлежащие операторам операнды не влияют на грам-матический разбор. [12]
Необходимо отметить, что раздельное изучение отношений предшествования - следования и управления - подчинения является лишь промежуточным этапом структурного анализа системы на третьем уровне. Оно оказывается особенно эффективным для систем большой сложности. Однако раздельное исследование не дает цельного представления о структуре системы и потоках информации в ней. Общие методы структурного анализа графов такого типа еще недостаточно разработаны, хотя в них ощущается очевидная практическая потребность. Об этом свидетельствует не только ряд проблем структурного анализа систем на третьем уровне, не получивших до настоящего времени удовлетворительного решения. [13]
В дальнейшем будет введено формальное определение отношений предшествования и дан алгоритм их определения. [14]
Метод Мак-Кимана освобождает от ограничения однозначности отношений предшествования, накладываемого методом Бирса, но он требует, естественно, больших объемов памяти для записи матриц и функции. Каждый элемент занимает 2 бита. [15]
Страницы: 1 2 3 4 5