Pszeudo-Boole problémák és műszaki alkalmazásaik

OData támogatás
Konzulens:
Dr. Mann Zoltán Ádám
Számítástudományi és Információelméleti Tanszék

Szakdolgozatomban a pszeudo-Boole problémák különböző változataival, megáldási technikáival és alkalmazási területeivel foglalkoztam.

A pszeudo-Boole problémák az egészértékű lineáris programozási (ILP) feladatok azon speciális esetei, melyekben minden változó csak a 0 vagy az 1 értéket veheti fel. Ugyanakkor a pszeudo-Boole problémák magukban hordozzák a SAT (Boolean Satisfiability Problem) problémák Boole természetét is, így valójában ezen problémák az ILP és SAT problémák keverékének tekinthetőek.

Az ILP és SAT megoldó programok több, mint fél évszázados múltjával szemben a pszeudo-Boole megoldó programok intenzív fejlesztése csak néhány éve kezdődött. A fejlődést elősegítette, hogy a pszeudo-Boole megoldó algoritmusoknál nagyon jól felhasználhatóak a korábbi ILP és SAT solverekhez alkotott eljárások. A pszeudo-Boole megoldó programok előnye, hogy képesek egyszerre megközelíteni a SAT solverek teljesítményét és az ILP modellezőképességét. Éppen ezért a pszeudo-Boole technikák ígéretesnek bizonyulnak műszaki területeken is.

Dolgozatom elején bemutatom a pszeudo-Boole problémák megoldási módszereit mind eldöntési mind optimalizálási esetben, ismertetem a különböző SAT-on és ILP-n alapuló megoldási technikákat és gyorsítási heurisztikákat.

Szakdolgozatom második felében a pszeudo-Boole problémák műszaki alkalmazhatóságát két gyakorlati problémán keresztül szemléltetem. A műszaki alkalmazások és gráfszínezési benchmarkok segítségével empirikus méréseket is végeztem. Ehhez pszeudo-Boole és ILP solvereket integráltam a BCAT keretrendszerbe, melyek segítségével hardver/szoftver particionálás, frekvenciatervezés és gráfszínezés területén összehasonlítottam különböző pszeudo-Boole és ILP technikák hatékonyságát.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.