Bináris Döntési Diagramok és alkalmazásaik

A tétel rövid nézete
dc.contributor.advisorVárterész, Magda
dc.contributor.authorLengyel, Zoltán
dc.contributor.departmentDE--TEK--Informatikai Karen
dc.date.accessioned2006-06-19T17:17:39Z
dc.date.available2006-06-19T17:17:39Z
dc.date.created2005
dc.date.issued2006-06-19T17:17:39Z
dc.description.abstractAzon algoritmusok, melyek hatékonyan képesek kezelni a valós életben felmerülő Boole-függvényeket, egyre népszerűbbek a nagymértékben integrált (VLSI) rendszerek számítógéppel támogatott tervezése és hitelesítése területén. Az egyik ilyen algoritmus-csoportba a bináris döntési diagramokat (BDD-ket) előállító és manipuláló algoritmusok tartoznak. Ilyen algoritmusok egy másik osztálya a SAT-fejtők 1 csoportja , melyről dolgozatomban csak érintőlegesen esik szó. A BDD-k, pontosabban annak egy szűkebb csoportja, a redukált rendezett BDD-k (OBDD-k) gyakran kerülnek előtérbe rendszerek szintézisénél és hitelesítésénél felmerülő problémák terjedelmes megoldásterének bemutatásakor. A BDD egy irányított körmentes gráf (DAG), melynek irányított élei egy-egy változó értékelését jelölik. Habár a BDD-kben az utak száma exponenciális függvénye a csúcsok és élek számának, azaz a gráf méretének, ezen gráfok olyan algoritmusok segítségével manipulálhatóak, melyek a bejárás során az BDD minden csúcsán és élén legfeljebb egyszer haladnak át, ezáltal a futásidő a gráf aktuális méretével polinomiális arányban növekszik. Azonban egy BDD előállítása során, napjaink algoritmusait használva, jelentősen megnő, majd általában csökken a BDD csúcsainak száma, mely exponenciális tár és futásidőt igényel. A SAT fejtők és a BDD-k közös tulajdonsága, hogy az ítéletváltozók sorrendje különösen fontos szerepet játszik az algoritmusok hatékonyságában. Különféle BDD rendezési módszerek léteznek, melyek között vannak statikus valamint dinamikus megközelítések. Erről bővebben a 3.2. fejezetben lesz szó. A BDD-k szerepének felfedezése óta több jelentős programcsomag is készült, mint például a CUDD vagy a BuDDy csomagok. Ezekről csak röviden ejtünk szót a 4. fejezet bevezetőjében.en
dc.description.correctorN.I.
dc.description.degreeBaen
dc.format.extent38en
dc.format.extent329855 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2437/117
dc.language.isohuen
dc.rightsno_restrictionen
dc.subjectBDDen
dc.subjectOBDDen
dc.subjectdöntési diagramoken
dc.subjectCADen
dc.subjectVISICADen
dc.subjectBMCen
dc.subjectModell-ellenőrzésen
dc.titleBináris Döntési Diagramok és alkalmazásaiken
Fájlok
Eredeti köteg (ORIGINAL bundle)
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
szakdolgozat_602.pdf
Méret:
322.12 KB
Formátum:
Adobe Portable Document Format
Leírás:
Szakdolgozat
Megjelenítés
Engedélyek köteg
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
license.txt
Méret:
2.72 KB
Formátum:
Item-specific license agreed upon to submission
Leírás:
Letöltés
Gyűjtemények
Hallgatói dolgozatok (Informatikai Kar)