Számítástudományi és Információelméleti Tanszék

Információelméleti indíttatásból definiálta Shannon mára klasszikussá vált, 1956-ban megjelent cikkében a róla elnevezett gráfkapacitás fogalmát. Egy gráf Shannon kapacitása lényegében azt méri, hogy milyen ütemben növekedhet egy gráf klikkszáma egy bizonyos gráfhatványozás során. Ennek a gráfparaméternek a meghatározása bizonyos gráfokra egyszerû, másokra rendkívül nehéz, sok esetben máig nem ismert. A fogalom nehézségét mutatja, hogy az is tisztázatlan, létezhet-e olyan algoritmus, ami egy adott bemeneti gráfra meghatározza annak Shannon kapacitását. E nehézség ellenére a fenti fogalom számos, azóta önmagában is fontossá vált témakör kiindulópontjává vált. Példa erre, hogy a perfekt gráfok bevezetését is a Shannon kapacitás bizonyos tulajdonságai inspirálták.

A Shannon kapacitás csak az egyik fontos példa olyan gráfelméleti fogalomra, aminek a bevezetését informacióélméleti vizsgálatok motiválták. Egy másik példa a gráfentrópiának nevezett, egy gráftól és a csúcsain adott valószínûségeloszlástól függô függvény, amit Körner definiált a hetvenes évek elején. Mára errôl is kiderült, hogy a kombinatorika sok, önmagában is érdekes területével van kapcsolatban, egyebek között szintén a perfekt gráfokkal. A gráfentrópia fontos alkalmazása, hogy erre a fogalomra épül a máig ismert egyetlen olyan determinisztikus rendezési algoritmus, mely egy részben rendezést optimális idô alatt terjeszt ki teljes rendezéssé.

A kutatás célja ezen és hasonló gráfokon definiált információelméleti funkcionálok vizsgálata, egymáshoz való viszonyaik mélyebb feltárása, illetve új alkalmazási lehetôségek keresése.

Szükséges nyelvtudás: angol.

Dr. Simonyi Gábor
egyetemi docens
31-56
simonyi@renyi.hu