Статья: ФАКТОРИЗАЦИЯ БУЛЕВЫХ ПОЛИНОМОВ: ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ И ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА

Скачать

Факторизация полиномов – классическая алгоритмическая проблема алгебры, имеюшая широкий спектр приложений. Особый интерес представляет факторизация над конечными полями, среди которых поле порядка два является, вероятно, наиболее важным в связи с представлением булевых функций полиномами Жегалкина. В частности, факторизация булевых полиномов соответствует конъюнктивной декомпозиции булевых функций, заданных в алгебраической нормальной форме. Кроме того, факторизация дает решение проблемы декомпозиции функций, заданных в СДНФ и позитивных ДНФ, а также декартовой декомпозиции реляционых данных. Эти приложения демонстрируют важность разработки быстрых алгоритмов факторизации. В статье мы рассматриваем некоторые недавно предложенные алгоритмы факторизации полиномиальной сложности и описываем параллельную MIMD-реализацию, которая использует как параллелизм уровня задачи, так и параллелизм уровня данных. Мы представляем эксперименты, выполненные на бенчмарках логического синтеза и на синтетических (случайных) полиномах, которые показывают значительное ускорение факторизации. В заключение представлены результаты тестирования параллельной реализации алгоритма на массивнопараллельной многоядерной архитектуре (Redefine).

Информация о документе

Формат документа: PDF
Кол-во страниц: 1 страница
Загрузил(а): Емельянов Павел
Лицензия: —
Доступ: Всем

Информация о статье

ISSN: 0132-3474
Журнал: ПРОГРАММИРОВАНИЕ
Год публикации: 2021
Автор(ы): Емельянов П. Г., Кришна М., Кулкарни В., Нанди С. К., Раха С., Пономарев Д. К.
Ключевые фразы: ФАКТОРИЗАЦИЯ БУЛЕВЫХ ПОЛИНОМОВ, ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ И ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА
УДК: 519.816. Теория принятия решений

Статистика просмотров

Статистика просмотров статьи за 2025 год.

Ранее вы смотрели (10)

01. Статья: К вопросу о совершенствовании организации профилактики ПТСР и психореабилитационных мероприятий в работе психолога с участниками СВО

02. Статья: Опыт реконструкции дорегулярной топонимики города Орла на материале полевых записок генерального межевания 1778 года

03. Книга: Решение задач по медицинской и биологической физике

04. Статья: ДИСТАНЦИОННЫЙ СТЕНД ДЛЯ СИНХРОННОЙ РАБОТЫ С ОБОРУДОВАНИЕМ НА ОСНОВЕ ПЛИС

05. Статья: ОЦЕНИВАНИЕ ПАРАМЕТРОВ ОДНОРОДНОЙ ВЛОЖЕННОЙ КУСОЧНО-ЛИНЕЙНОЙ РЕГРЕССИИ ВТОРОГО ТИПА

06. Статья: Изучение технических наук без границ: применяем навигатор по открытым образовательным ресурсам. Часть 1. Российский опыт

07. Статья: ОЦЕНКА СОРТОВ ЛЮПИНА УЗКОЛИСТНОГО ДЛЯ ЦЕЛЕЙ РЕГЕНЕРАТИВНОГО (ВОССТАНОВИТЕЛЬНОГО) ЗЕМЛЕДЕЛИЯ

08. Статья: РАЗВИТИЕ СМЕХОВОЙ ТРАДИЦИИ В ОТЕЧЕСТВЕННОЙ ЛИТЕРАТУРЕ XX ВЕКА

09. Статья: Изучение технических наук без границ: применяем навигатор по открытым образовательным ресурсам. Часть 1. Российский опыт

10. Статья: ОСОБЕННОСТИ СЕКРЕЦИИ АДИПОНЕКТИНА И ЕГО СВЯЗЬ С НЕКОТОРЫМИ ПОКАЗАТЕЛЯМИ МЕТАБОЛИЗМА У МУЖЧИН ТРУДОСПОСОБНОГО ВОЗРАСТА ПРИ НАЛИЧИИ ОЖИРЕНИЯ

Все права на тексты и товарные знаки принадлежат их законным владельцам. Подробнее...

Сайт https://scinetwork.ru (далее – Сайт) представляет собой платформу, на которой пользователи самостоятельно добавляют и публикуют метаинформацию о материалах разных видов (названия, обложки, аннотации, данные об авторах и т.п.). Администрация Сайта не занимается самостоятельным сбором или первоначальной публикацией этих сведений.

Модерация контента

На Сайте действует постмодерация. Это означает, что материалы, добавляемые пользователями, становятся общедоступными сразу после публикации и проверяются Администрацией Сайта постфактум в разумные сроки.

Использование информации

Администрация Сайта не использует метаданные и обложки документов в коммерческих или рекламных целях для продвижения товаров или услуг и не заявляет о каких-либо правах на представленные объекты интеллектуальной собственности. Все права на документы и сопутствующие материалы принадлежат их законным правообладателям.

Отказ от гарантий

Администрация Сайта не гарантирует точность, полноту и достоверность метаинформации, размещенной пользователями, поскольку не осуществляет ее предварительную проверку.

Ответственность

Сайт носит исключительно информационно-справочный характер. Администрация Сайта не несет ответственности за содержание и достоверность информации, добавленной пользователями, а также за любые убытки, возникшие в связи с использованием или невозможностью использования Сайта и размещенной на нем информации.