RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2006, том 18, выпуск 4, страницы 84–98 (Mi dm81)

Об одном классе клеточных схем

Д. А. Жуков


Аннотация: В работе предложен класс клеточных схем, $T$-схем, для которого удалось связать нижнюю оценку площади с глубиной: чем меньше глубина схемы, тем больше должна быть ее площадь. Приведены примеры $T$-схем логарифмической глубины для задач вычисления $n$ префиксных сумм, суммы и разности двух $n$-разрядных чисел. Показано, что площадь этих схем есть $O(n\log n)$ и оптимальна по порядку.

УДК: 519.7

Статья поступила: 22.07.2003

DOI: 10.4213/dm81


 Англоязычная версия: Discrete Mathematics and Applications, 2006, 16:5, 499–512

Реферативные базы данных:


© МИАН, 2024