Dovoľujeme si oznámiť, že dňa
26. augusta 2022 o 10.00 hod.
sa uskutoční na Fakulte informatiky a informačných technológií STU v Bratislave
Ilkovičova 2, v miestnosti 2.06 obhajoba dizertačnej práce
Ing. Jána Lúčanského
Názov dizertačnej práce:
Nové metódy redukcie rozhodovacích diagramov
Novel reduction methods for decision diagrams
Odbor: 9.2.9. Aplikovaná informatika
Školiteľ: prof. Ing. Ivan Kotuliak, PhD. – FIIT STU v Bratislave
Oponenti dizertačnej práce:
prof. Ing. Hana Kubátová, Ph.D. – FIT ČVUT v Prahe
prof. Ing. Juraj Gazda, PhD. – FEI TU v Košiciach
Abstrakt:
V práci uvádzame nové metódy redukcie rozhodovacích diagramov (DD) na binárnej báze využívajúcich podobnosti medzi Booleovými funkciami. Tradičné metódy sú schopné odstrániť redundantné časti diagramu, reprezentujúce identické štruktúry. Navrhovaný postup sa snaží redukovať nielen identické, ale aj ekvivalentné časti diagramu, ktoré vedú k identickým výsledkom po malej zmene v usporiadaní premenných. Základné typy DD, akými sú binárne DD (BDD) alebo funkcionálne DD (FDD), neumožňujú redukciu ekvivalentných častí z dôvodu straty informácie o zmene poradia. Práca preto opisuje návrh nového typu diagramu schopného obsiahnuť rôzne poradia premenných a týmto spôsobom umožniť redukciu ekvivalentných častí – rozhodovací diagram s viacnásobnými premennými (Multi-Variable Decision Diagram - MVDD). Jediným problémom vyplývajúcim z MVDD je určenie ekvivalencie 2 funkcií. Ako riešenie je navrhnutá nová heuristika vyhodnocovania podobnosti funkcií s ohľadom na problematiku DD. Práca tiež zobrazuje optimalizáciu Kroneckerových FDD (KFDD) a MVDD s ohľadom na viacero parametrov, pričom algoritmus optimalizácie využíva evolučné algoritmy a reziduálnu premennú. Priemerná pridaná hodnota k redukcii počtu uzlov pri MVDD bola 26,13 % pri porovnaní s BDD a 12,27 % pri porovnaní s KFDD.
We propose a novel method of reduction for binary-based decision diagrams (DD) exploiting the similarities between Boolean functions. Conventional methods are able to remove redundant parts of DD that adhere to (or represent) identical structures. The proposed approach tries to take advantage of not only identical, but also equivalent parts of diagram, which produce identical results after a change in variable ordering. Basic types of DD, like Binary DD (BDD) or Functional DD (FDD) do not allow for reduction of equivalent parts of diagram as the notation of change in ordering would be lost. Therefore we propose a new type of decision diagram able to incorporate different orders of variables and thus allowing for the reduction of equivalent diagram parts – Multi-Variable Decision Diagram (MVDD). The only remaining obstacle is the determination of equivalency, for which we also propose a new heuristic. The paper also presents reduction of Kronecker Functional DD (KFDD) and MVDD with regard to multiple parameters, where the optimization process relies heavily on evolutionary algorithms and Residual Variable (RV). The average added value of MVDD to the reduction of size was 26,13% when compared to BDD and 12,27% compared to KFDD while preserving similar values of power consumption and average path length in diagram.
Dizertačná práca je k nahliadnutiu na Študijnom oddelení FIIT STU.