Аннотация:
Сравнивается нескольких алгоритмов вычисления транзитивного замыкания графа и умножения матриц в булевом полукольце и кольцах вычетов. Приведены оценки сложности и глубины соответствующих булевых схем.
Ключевые слова:транзитивное замыкание графа, булево умножение матриц, умножение матриц над кольцами, битовая сложность, булевы схемы, их сложность и глубина, модулярные сложение и умножение.
Полный текст:
PDF файл (343 kB)