RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2011, номер 5, страницы 48–51 (Mi vmumm720)

Краткие сообщения

О минимальных параллельных префиксных схемах

И. С. Сергеев

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Найдено точное значение сложности минимальной префиксной схемы $m$ переменных глубины $\lceil\log_2 m\rceil$ в случае, когда $m$ является степенью двойки. Получены новые верхние оценки сложности префиксных схем при различных ограничениях на глубину и отдельно для случая схем с операцией сложения по модулю $2$.

Ключевые слова: префискные схемы, сложность, глубина.

УДК: 519.714

Поступила в редакцию: 19.09.2010



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


© МИАН, 2024