4624
правки
Атрибутное вычисление: различия между версиями
Материал из WikiGrapp
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Атрибутное вычисление''' (''[[Attribute evaluation]]'') | '''Атрибутное вычисление''' (''[[Attribute evaluation]]'') — эффективность использования [[атрибутная грамматика|''атрибутных грамматик'']] во многом зависит от способа решения задачи '''А.в.''' — нахождения значений атрибутов <math>W(t)</math> для [[атрибутное дерево|''атрибутного дерева'']] <math>t</math> заданной атрибутной грамматики. Первый шаг, | ||
который нужно при этом сделать, состоит в определении ''порядка'' (''плана'' или ''стратегии'') ''вычисления'' | который нужно при этом сделать, состоит в определении ''порядка'' (''плана'' или ''стратегии'') ''вычисления'' — такого линейного порядка <math>T(t)</math> на <math>W(t)</math>, который не | ||
противоречит [[графу зависимости атрибутов]] [[дерево|дерева]] <math>t</math>. В | противоречит [[граф зависимости атрибутов|графу зависимости атрибутов]] [[дерево|дерева]] <math>t</math>. В | ||
случае, когда [[грамматика]] ''[[корректная атрибутная грамматика|корректна]]'', указанная задача | случае, когда [[грамматика]] ''[[корректная атрибутная грамматика|корректна]]'', указанная задача | ||
для заданного <math>t</math> является задачей [[топологическая сортировка|''топологической сортировки'']], допускающей эффективное решение. | для заданного <math>t</math> является задачей [[топологическая сортировка|''топологической сортировки'']], допускающей эффективное решение. | ||
| Строка 12: | Строка 12: | ||
После того как план вычисления <math>T(t)</math> найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов, либо от максимальных элементов в отношении. | После того как план вычисления <math>T(t)</math> найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов, либо от максимальных элементов в отношении. | ||
Вычислители первого типа называются ''восходящими'' (''снизу вверх'' или ''управляемыми данными''), а второго | Вычислители первого типа называются ''восходящими'' (''снизу вверх'' или ''управляемыми данными''), а второго — ''нисходящими'' (''сверху вниз'' или ''управляемыми | ||
запросами''). | запросами''). | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. | * Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998. | ||
