|
Автоматика и телемеханика, 2016, выпуск 4, страницы 84–98
(Mi at14433)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Системный анализ и исследование операций
Об одном классе решающих диаграмм
А. А. Семенов, И. В. Отпущенников Институт динамики систем и теории управления СО РАН, Иркутск
Аннотация:
Вводится класс решающих диаграмм, предназначенных для представления нормальных форм булевых функций. В частности, рассматриваются дизъюнктивные диаграммы, представляющие дизъюнктивные нормальные формы (ДНФ). В отличие от двоичных решающих диаграмм (BDD, ROBDD), для произвольной ДНФ представляющая ее дизъюнктивная диаграмма строится за полиномиальное от объема двоичного кода ДНФ время. Описаны соответствующие алгоритмы. Приведены результаты вычислительных экспериментов, в которых предложенные диаграммы используются для уменьшения объема информации, накапливаемой в процессе решения трудных вариантов задачи о булевой выполнимости (SAT).
Образец цитирования:
А. А. Семенов, И. В. Отпущенников, “Об одном классе решающих диаграмм”, Автомат. и телемех., 2016, № 4, 84–98; Autom. Remote Control, 77:4 (2016), 617–628
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at14433 https://www.mathnet.ru/rus/at/y2016/i4/p84
|
Статистика просмотров: |
Страница аннотации: | 209 | PDF полного текста: | 49 | Список литературы: | 43 | Первая страница: | 22 |
|