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