О сложности линейных булевых операторов с редкими матрицами

Авторы: Гашков С.Б., Сергеев И.С.
Журнал: Дискретный анализ и исследование операций
Том: 17
Номер: 3
Год издания: 2010
Издательство: Изд-во Ин-та математики
Местоположение издательства: Новосибирск
Первая страница: 3
Последняя страница: 18
Аннотация: Рассматривается задача построения булевой (n х n)-матрицы A без <<прямоугольников>> (т.е. в которой пересечение любых двух строк и любых двух столбцов не образует матрицу из единиц), линейное преобразование по модулю два, определяемое которой, имеет сложность o(ν(A)-n) над базисом { + (mod 2) }, где ν(A) - вес матрицы A, т.е. число единиц. Приведено две конструкции, решающих данную задачу. Рассмотрены обобщения указанной задачи.
Добавил в систему: Сергеев Игорь Сергеевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ЦЭМИ РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА