Оптимальное упорядочение деревьев: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Оптимальное упорядочение деревьев''' (''[[Optimal ordering for trees]]'') -
'''Оптимальное упорядочение деревьев''' (''[[Optimal ordering for trees]]'')
Существует простой [[алгоритм]] определения оптимального порядка, в котором
Существует простой [[алгоритм]] определения оптимального порядка, в котором
следует осуществлять вычисления, образующие линейный участок
следует осуществлять вычисления, образующие линейный участок
Строка 7: Строка 7:


Алгоритм состоит из двух частей. Первая помечает каждую [[вершина|вершину]] дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для
Алгоритм состоит из двух частей. Первая помечает каждую [[вершина|вершину]] дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для
вычисления [[поддерево|поддерева]] с данным [[корень|корнем]] при условии, что не делается запоминаний промежуточных результатов. Вторая часть --- это [[обход графа|обход дерева]], порядок которого управляется вычисленными [[метка|метками]] вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который
вычисления [[поддерево|поддерева]] с данным [[корень|корнем]] при условии, что не делается запоминаний промежуточных результатов. Вторая часть это [[обход графа|обход дерева]], порядок которого управляется вычисленными [[метка|метками]] вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который
требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым.
требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым.


Строка 15: Строка 15:
регистров являются ''[[NP-Полная задача|<math>\mathcal NP</math>-Полными]]''.
регистров являются ''[[NP-Полная задача|<math>\mathcal NP</math>-Полными]]''.
==Литература==
==Литература==
[Евстигнеев-Касьянов/98]
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.

Навигация