Аннотация:
Рассматривается сложность реализации линейных булевых операторов неветвящимися программами с условной остановкой. Для почти всех таких операторов найдены точные по порядку оценки среднего времени вычисления их значений.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 96–01–01068, и ФЦП «Интеграция», проект 473.
Полный текст:
PDF файл (539 kB)