Dijagrami odluke sa implicitnom nulom
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Dijagram odluke sa implicitnom nulom (DOIN) енгл. Zero-suppressed decision diagram je vrsta binarnog dijagrama odluke komprimovanog tako da predstave bulovih funkcija koje su skoro svuda jednake nuli zauzimaju što manje prostora. Često se koriste za predstavljanje familija skupova.
Definicija
[уреди | уреди извор]Binarni dijagram odluke sa implicitnom nulom je svaki aciklični, orijentisan graf takav da:
- Svaki njegov završni čvor je ili čvor (vrednosti) 0 ili čvor (vrednosti) 1.
- Svaki nezavršni čvor izlaznog je stepena 2, pri čemu se jedna grana zove visokom (pozitivnom) a druga niskom (negativnom) a sinovi koje povezuju analogno tome.
- Svaki nezavršni čvor nosi ime nekog iskaznog slova bulove funkcije koja biva predstavljena, različiti čvorovi mogu biti označeni istim slovom i slova su uređena tako da čvor označen jednim slovom ne može biti predak čvora označenog slovom koji prvom slovu prethodi.
- Nijedna visoka grana ne pokazuje na nulti čvor.
- Ukoliko su dva čvora označena istim slovom, podgrafi koje čine sa svojim potomcima ne smeju biti izomorfni.
- Postoji tačno jedan čvor sa nultim ulaznim stepenom i on se naziva korenom.
Kao alternativna definicija može se dati i rezultat uzastopne primene sledećih redukcionih pravila na potpuno binarno stablo odluke:
- Spojiti izomorfne podgrafove;
- Izbrisati čvorove čiji je viši sin krajnji čvor vrednosti 0.
DOIN sličan je redukovanom binarnom dijagramu. Oni dele redukciono pravilo o spajanju izomorfnih podgrafa, ali se razlikuju u drugom pravilu. Obe strukture mogu se koristiti za kanonsku reprezentaciju bulovih funkcija jer se svaka funkcija jedinstveno predstavlja ovim dijagramima, i svaki dijagram predstavlja tačno jednu funkciju (za dati broj argumenata funkcije).
Primer
[уреди | уреди извор]Leva slika predstavlja redukovano binarno stablo odluke a desna stablo odluke sa implicitnom nulom, obe predstavljaju funkciju F(x1,x2,x3,x4) = x1x2x3. Isprekidane linije predstavljaju putanju ka nižim sinovima, dok neisprekidane predstaljaju putanje ka višim sinovima.
 |
 |
Kao što ovde vidimo, dijagram sa implicitnom nulom može koristiti manje čvorova i grana od redukovanog dijagrama iako je naizgled redundantan (x3 pokazuje sa obe grane na jedinični čvor), pogotovo kada je funkcija uglavnom jednaka nuli na većini domena. Posmatrajući funkcije u potpunoj disjunktnoj normalnoj formi, možemo primetiti da DOIN bolje komprimuje one funkcije sa što manje klauza i što više negiranih literala u njima, dok redukovani dijagram bolje komprimuje one funkcije čije su jedinice 'susedne' odnosno čije su minimalne normalne disjunktne forme značajno manje od potpunih.
Predstavljanje familija skupova
[уреди | уреди извор]Dijagram sa implicitnom nulom se može lako upotrebiti za predstavu skupova koji sadrže skupove. Da bismo uvideli kako se ovo implementira dovoljno je zamisliti familiju skupova kao bulovu funkciju, takvu da se po svaki njen ulazni parametar odnosi na po jedan element skupova (unutar familije) te na njegovo prisustvo (1) ili odsustvo(0) a ulaz odgovara prisustvu ili odsustvu skupa opisanog ovim ulaznim parametrima u familiji.
Na primer, F(x1,x2,x3,x4) = x1x2x3+x1x2x3+x1x2x3, izomorfna je nekoj familiji skupova { {x1}, {x2,x3}, {x2} }.
Da bismo konstruisali DOIN iz proizvoljne familije skupova {math|F} pratimo ove korake:
- Ako je {math|F} prazan skup vraćamo ⊥, ako je skup koji sadrži prazan skup vraćamo ⊤.
- Uzimamo sledeći element {math|x} po unapred određenom redosledu i pravimo čvor sa njegovim imenom.
- Neka je {math|F0} familija skupova koja se dobija iz {math|F} kada odbacimo sve njegove skupove koji sadrže {math|x}, povežimo nižom granom čvor {math|x} sa podstablom koje se dobija rekurzivnom primenom ovih koraka na familiju {math|F0}.
- Neka je {math|F1} familija skupova koja se dobija iz {math|F} kada odbacimo sve njegove skupove koji ne sadrže {math|x} a zatim izbacimo {math|x} iz svih skupova u toj familiji, povežimo višom granom čvor {math|x} sa podstablom koje se dobija rekurzivnom primenom ovih koraka na familiju {math|F1}.
Na kraju je samo potrebno spojiti izomorfne podgrafove ovako dobijenog grafa.
Istorija
[уреди | уреди извор]DOIN osmislio je Šin-Ići Minato u kontekstu kombinatornih problema koji zahtevaju manipulacije familijama skupova.[1] U razgovoru iz 2011-e Donald Knut nazvao je dijagram sa implicitnom nulom najlepšom tvorevinom u računarskoj nauci.[2]
Aplikacije
[уреди | уреди извор]DOIN se intezivno koristi u CAD softveru za sitezu kola (logička sinteza), optimizaciji grafova, minimizaciji logičkih funkcija, i uopšte za predstavljanje familija skupova u raznim situacijama. [3]
Vidi još
[уреди | уреди извор]- Bulova zadovljivost problema
- L/poli, tj. Složenost klasa koja obuhvata kompleksne probleme u polinomijalnoj veličini BDD
- Model checking
- Radiks stablo
- Binary key – metod indetifikacije vrsta u biologiji pomoću binarnih stabla
- Barrington's teorema
Reference
[уреди | уреди извор]- ^ S. Minato: "Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems", In Proc. of 30th ACM/IEEE Design Automation Conference (DAC'93). pp. 272-277, Jun. 1993.
- ^ „"All Questions Answered" by Donald Knuth”. YouTube.com. Приступљено 12. 6. 2013.
- ^ Alan Mishchenko, An Introduction to Zero-Suppressed Binary Decision Diagrams Архивирано на сајту Wayback Machine (8. мај 2014)
Spoljašnje veze
[уреди | уреди извор]Dosupni BOID paketi
- CUDD: BDO paket sa DOIN podrškom , University of Colorado, Boulder
- JDD java implementacija BDO i DOIN.
- JBDD od istog autora koji ima slican API, ali je Java interfejs od BuDDy i CUDD
- Donald Knuth, Fun With Zero-Suppressed Binary Decision Diagrams (ZDDs) (video predavanje, 2008)
- http://crypto.stanford.edu/pbc/notes/zdd/