4624
правки
Оптимальное упорядочение деревьев: различия между версиями
Материал из WikiGrapp
Оптимальное упорядочение деревьев (посмотреть исходный код)
Версия от 15:03, 31 мая 2011
, 31 мая 2011нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Оптимальное упорядочение деревьев''' (''[[Optimal ordering for trees]]'') | '''Оптимальное упорядочение деревьев''' (''[[Optimal ordering for trees]]'') — | ||
Существует простой [[алгоритм]] определения оптимального порядка, в котором | Существует простой [[алгоритм]] определения оптимального порядка, в котором | ||
следует осуществлять вычисления, образующие линейный участок | следует осуществлять вычисления, образующие линейный участок | ||
| Строка 7: | Строка 7: | ||
Алгоритм состоит из двух частей. Первая помечает каждую [[вершина|вершину]] дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для | Алгоритм состоит из двух частей. Первая помечает каждую [[вершина|вершину]] дерева, двигаясь снизу вверх, некоторым числом, которое обозначает минимальное количество регистров, необходимое для | ||
вычисления [[поддерево|поддерева]] с данным [[корень|корнем]] при условии, что не делается запоминаний промежуточных результатов. Вторая часть | вычисления [[поддерево|поддерева]] с данным [[корень|корнем]] при условии, что не делается запоминаний промежуточных результатов. Вторая часть — это [[обход графа|обход дерева]], порядок которого управляется вычисленными [[метка|метками]] вершин. Выходной код генерируется во время указанного обхода дерева. Содержательно алгоритм, обрабатывая два операнда бинарной операции, сначала работает над вычислением того из них, который | ||
требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым. | требует больше регистров (более трудный операнд). Если потребность в регистрах у обоих операндов совпадает, то каждый из операндов может быть обработан первым. | ||
| Строка 15: | Строка 15: | ||
регистров являются ''[[NP-Полная задача|<math>\mathcal NP</math>-Полными]]''. | регистров являются ''[[NP-Полная задача|<math>\mathcal NP</math>-Полными]]''. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998. | |||
