Вестник Московского Университета. Математика, Механика - Содержание


УДК 519.7

О времени параллельного сложения нескольких чисел / Жуков Д.А. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2001. N.6 C. 52-54.

Пусть $(n,m)$-преобразование -- это процедура, получающая из $n$ слагаемых $m$ чисел с той же суммой. Показано, что $(n,2)$-преобразование можно реализовать схемой глубины, асимптотически не превышающей $( 1+O(\log\log k/\log k) ) \cdot \log_2n$, в базисе из двуместных функций $k$-значной логики (при растущем $n$).

Библиогр. 3.

К оглавлению номера  Go!