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