Дијаграми одлуке са имплицитном нулом
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Dijagram odluke sa implicitnom nulom (DOIN) енгл. Zero-suppressed decision diagram је врста бинарног дијаграма одлуке компримованог тако да представе булових функција које су скоро свуда једнаке нули заузимају што мање простора. Често се користе за представљање фамилија скупова.
Дефиниција
[уреди | уреди извор]Бинарни дијаграм одлуке са имплицитном нулом је сваки ациклични, оријентисан граф такав да:
- Сваки његов завршни чвор је или чвор (вредности) 0 или чвор (вредности) 1.
- Сваки незавршни чвор излазног је степена 2, при чему се једна грана зове високом (позитивном) а друга ниском (негативном) а синови које повезују аналогно томе.
- Сваки незавршни чвор носи име неког исказног слова булове функције која бива представљена, различити чворови могу бити означени истим словом и слова су уређена тако да чвор означен једним словом не може бити предак чвора означеног словом који првом слову претходи.
- Ниједна висока грана не показује на нулти чвор.
- Уколико су два чвора означена истим словом, подграфи које чине са својим потомцима не смеју бити изоморфни.
- Постоји тачно један чвор са нултим улазним степеном и он се назива кореном.
Као алтернативна дефиниција може се дати и резултат узастопне примене следећих редукционих правила на потпуно бинарно стабло одлуке:
- Спојити изоморфне подграфове;
- Избрисати чворове чији је виши син крајњи чвор вредности 0.
ДОИН сличан је редукованом бинарном дијаграму. Они деле редукционо правило о спајању изоморфних подграфа, али се разликују у другом правилу. Обе структуре могу се користити за канонску репрезентацију булових функција јер се свака функција јединствено представља овим дијаграмима, и сваки дијаграм представља тачно једну функцију (за дати број аргумената функције).
Пример
[уреди | уреди извор]Лева слика представља редуковано бинарно стабло одлуке а десна стабло одлуке са имплицитном нулом, обе представљају функцију Ф(x1,x2,x3,x4) = x1x2x3. Испрекидане линије представљају путању ка нижим синовима, док неиспрекидане предстаљају путање ка вишим синовима.
 |
 |
Као што овде видимо, дијаграм са имплицитном нулом може користити мање чворова и грана од редукованог дијаграма иако је наизглед редундантан (x3 показује са обе гране на јединични чвор), поготово када је функција углавном једнака нули на већини домена. Посматрајући функције у потпуној дисјунктној нормалној форми, можемо приметити да ДОИН боље компримује оне функције са што мање клауза и што више негираних литерала у њима, док редуковани дијаграм боље компримује оне функције чије су јединице 'суседне' односно чије су минималне нормалне дисјунктне форме значајно мање од потпуних.
Представљање фамилија скупова
[уреди | уреди извор]Дијаграм са имплицитном нулом се може лако употребити за представу скупова који садрже скупове. Да бисмо увидели како се ово имплементира довољно је замислити фамилију скупова као булову функцију, такву да се по сваки њен улазни параметар односи на по један елемент скупова (унутар фамилије) те на његово присуство (1) или одсуство(0) а улаз одговара присуству или одсуству скупа описаног овим улазним параметрима у фамилији.
На пример, Ф(x1,x2,x3,x4) = x1x2x3+x1x2x3+x1x2x3, изоморфна је некој фамилији скупова { {x1}, {x2,x3}, {x2} }.
Да бисмо конструисали ДОИН из произвољне фамилије скупова {матх|Ф} пратимо ове кораке:
- Ако је {матх|Ф} празан скуп враћамо ⊥, ако је скуп који садржи празан скуп враћамо ⊤.
- Узимамо следећи елемент {матх|x} по унапред одређеном редоследу и правимо чвор са његовим именом.
- Нека је {матх|Ф0} фамилија скупова која се добија из {матх|Ф} када одбацимо све његове скупове који садрже {матх|x}, повежимо нижом граном чвор {матх|x} са подстаблом које се добија рекурзивном применом ових корака на фамилију {матх|Ф0}.
- Нека је {матх|Ф1} фамилија скупова која се добија из {матх|Ф} када одбацимо све његове скупове који не садрже {матх|x} а затим избацимо {матх|x} из свих скупова у тој фамилији, повежимо вишом граном чвор {матх|x} са подстаблом које се добија рекурзивном применом ових корака на фамилију {матх|Ф1}.
На крају је само потребно спојити изоморфне подграфове овако добијеног графа.
Историја
[уреди | уреди извор]ДОИН осмислио је Шин-Ићи Минато у контексту комбинаторних проблема који захтевају манипулације фамилијама скупова.[1] У разговору из 2011-е Доналд Кнут назвао је дијаграм са имплицитном нулом најлепшом творевином у рачунарској науци.[2]
Апликације
[уреди | уреди извор]ДОИН се интезивно користи у ЦАД софтверу за ситезу кола (логичка синтеза), оптимизацији графова, минимизацији логичких функција, и уопште за представљање фамилија скупова у разним ситуацијама. [3]
Види још
[уреди | уреди извор]- Булова задовљивост проблема
- L/поли, тј. Сложеност класа која обухвата комплексне проблеме у полиномијалној величини БДД
- Модел цхецкинг
- Радикс стабло
- Бинарy кеy – метод индетификације врста у биологији помоћу бинарних стабла
- Баррингтон'с теорема
Референце
[уреди | уреди извор]- ^ С. Минато: "Зеро-Суппрессед БДДс фор Сет Манипулатион ин Цомбинаториал Проблемс", Ин Проц. оф 30тх АЦМ/ИЕЕЕ Десигн Аутоматион Цонференце (ДАЦ'93). пп. 272-277, Јун. 1993.
- ^ „"Алл Qуестионс Ансwеред" бy Доналд Кнутх”. YоуТубе.цом. Приступљено 12. 6. 2013.
- ^ Алан Мисхцхенко, Ан Интродуцтион то Зеро-Суппрессед Бинарy Децисион Диаграмс Архивирано на сајту Wayback Machine (8. мај 2014)
Спољашње везе
[уреди | уреди извор]Досупни БОИД пакети
- ЦУДД: БДО пакет са ДОИН подршком , Университy оф Цолорадо, Боулдер
- ЈДД јава имплементација БДО и ДОИН.
- ЈБДД од истог аутора који има слицан АПИ, али је Јава интерфејс од БуДДy и ЦУДД
- Доналд Кнутх, Фун Wитх Зеро-Суппрессед Бинарy Децисион Диаграмс (ЗДДс) (видео предавање, 2008)
- http://crypto.stanford.edu/pbc/notes/zdd/