Атрибутное вычисление: различия между версиями

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

Навигация