|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
On the complexity of parallel prefix circuitsстатья Электронная публикация
- Автор: Sergeev I.S.
- Журнал: Electronic Colloquium on Computational Complexity (ECCC)
- Номер: 41
- Год издания: 2013
- Первая страница: 1
- Последняя страница: 47
- Аннотация: Показано, что сложность реализации системы префиксных сумм m переменных схемой глубины ]log_2 m[ не превосходит (3,5-o(1))m. В случае m=2^n установлено точное значение сложности 3,5*2^n - (8,5+3,5(n mod 2))2^[n/2] + n + 5. Для сложности префиксной схемы минимальной глубины с операцией сложения по модулю 2 получена верхняя оценка (36/11-o(1))m. Кроме того, новые верхние оценки сложности получены при различных ограничениях на глубину схем.
- Добавил в систему: Сергеев Игорь Сергеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | TR13-041.pdf | 633,2 КБ | 24 марта 2013 [isserg] | |
| 2. | предварительная русскоязычная версия | prefix3.pdf | 510,6 КБ | 24 марта 2013 [isserg] |