Széles Tibor: Kombinatorikai problémák megoldása bináris döntési diagrammok (BDD-k) segítségével
szemináriumi elõadás lesz.
Tematika: Az utóbbi idõkben egyre növekvõ számban oldanak meg gráfelméleti, kombinatorikai es számítástudományi problémákat számítógépek segítségével. (Pl.: 4-szín Tétel planáris gráfokra, bizonyos Ramsey számok megadása, stb.) Érdekes módon a BDD-k és variánsaik - amelyek mint a Boole-függvények hatékony reprezentációjaként, valamint hardware verifikációk és számítógépes tervezés eszközeként ismertek leginkább - alkalmasak leszámolási és egyéb kombinatorikus problémák megoldására is. A cikk, amelyre az elõadás épül és I. Wegener és M. Löbbing jegyez, többek között megadja a 8*8-as sakktáblán a huszár(ló)-bejárások számát úgy, hogy a leszámoláshoz BDD-ket és variánsaikat hívja segítségül.
Minden érdeklõdõt szeretettel várunk!
Péter