7
правок
Атрибутное вычисление: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
GPN (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 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> является задачей [[топологическая сортировка|''топологической сортировки'']], допускающей эффективное решение. | ||
| Строка 11: | Строка 11: | ||
Детерминированные алгоритмы, в которых порядок заполнения атрибутного дерева фиксируется до начала вычисления атрибутов, разделяются на алгоритмы ''с жесткой стратегией'', в которых порядок заполнения один и тот же для всех атрибутных деревьев, и алгоритмы ''с гибкой стратегией'', в которых порядок заполнения определяется для конкретного атрибутного дерева. | Детерминированные алгоритмы, в которых порядок заполнения атрибутного дерева фиксируется до начала вычисления атрибутов, разделяются на алгоритмы ''с жесткой стратегией'', в которых порядок заполнения один и тот же для всех атрибутных деревьев, и алгоритмы ''с гибкой стратегией'', в которых порядок заполнения определяется для конкретного атрибутного дерева. | ||
После того как план вычисления <math>T(t)</math> найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов | После того как план вычисления <math>T(t)</math> найден, возможны два варианта его использования: вычислять, начиная с минимальных элементов либо от максимальных элементов в отношении. | ||
Вычислители первого типа называются ''восходящими'' (''снизу вверх'' или ''управляемыми данными''), а второго | Вычислители первого типа называются ''восходящими'' (''снизу вверх'' или ''управляемыми данными''), а второго — ''нисходящими'' (''сверху вниз'' или ''управляемыми | ||
запросами''). | запросами''). | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998. | |||