Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Gráfok, kapacitások, entrópiák: Bevezetés az információelméleti kombinatorikába

    A tantárgy angol neve: nincs megadva

    Adatlap utolsó módosítása: 2022. június 10.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar
    PhD képzés
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZD306   4/0/0/v 5  
    4. A tantárgy előadója dr. Simonyi Gábor, egyetemi tanár, Számítástudományi és Információelméleti Tanszék
    5. A tantárgy az alábbi témakörök ismeretére épít Gráfelmélet, lineáris algebra, valószínűségszámítás alapjai  
    6. Előtanulmányi rend
    Ajánlott:

    A gráfelmélet, a lineáris algebra, illetve a valószínűségszámítás alapvető ismereteit tartalmazó kurzusok elvégzése után célszerű felvenni.

    7. A tantárgy célkitűzése

    Annak bemutatása, hogy az információelmélet eszköztára és problémafelvetései hogyan váltak gyümölcsözővé a kombinatorikában és a gráfelméletben. Ezzel kapcsolatos alapvető eredmények megismertetése és ennek keretében a diszkrét matematikai gondolkodás további fejlesztése. 

    8. A tantárgy részletes tematikája

    1. Gráfok Shannon kapacitása, e paraméter legegyszerűbb korlátai (klikkszám és kromatikus szám), az ötszögprobléma, a problémakör gráfelméleti hatása: perfekt gráfok bevezetése.

    2. Néhány fontosabb gráfosztály perfektsége, Perfekt Gráf Tétel és Erős Perfekt Gráf Tétel, Helyettesítési Lemma.

    3. További érdekes gráfcsaládok: Kneser gráfok, Mycielski gráfok, normális gráfok, normális gráfok perfektsége.

    4. Frakcionális kromatikus szám fogalma, kapcsolata a lineáris programozással, a hagyományos kromatikus számtól való lehetséges eltérése, értéke csúcstranzitív gráfokon. Gráfhomomorfizmus fogalma, színezési paraméterek jellemzése gráfhomomorfizmusok segítségével.

    5. Csatorna zéró-hiba kapacitása visszacsatolás mellett, ennek kapcsolata a frakcionális kromatikus számmal, Lovász tétele a frakcionális és a hagyományos kromatikus szám lehetséges arányáról, McEliece-Posner tétel.

    6. Lovász-féle theta függvény, az ötszögprobléma megoldása.

    7. Bohman-Holzman tétel a páratlan körök Shannon kapacitásáról, Shannon kapacitás és Ramsey számok kapcsolata.

    8. Gráfok Witsenhausen hányadosa, ennek kapcsolata a Shannon kapacitással.

    9. Irányított gráfok Sperner kapacitása, ennek korlátai.

    10. Gráfcsaládok kapacitása, információelméleti interpretáció irányítatlan és irányított gráfok esetén, kapcsolat az extremális halmazelmélettel.

    11. Kapacitásparaméterek valószínűségi finomítása, Gargano-Körner-Vaccaro tétel.

    12. Gráfentrópia fogalma, információelméleti interpretációja, főbb tulajdonságai,  szubadditivitásának alkalmazása. 

    13. Additivitási kérdések, perfekt gráfok jellemzése a gráfentrópia segítségével.

    14. Kahn és Kim gráfentrópián alapuló algoritmusa részben rendezés teljes rendezéssé történő kiterjesztésére. 

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    Heti 4 óra előadás.

    10. Követelmények

    szóbeli vizsga

    12. Konzultációs lehetőségek

    Személyes egyeztetés alapján, fogadóórákon

    13. Jegyzet, tankönyv, felhasználható irodalom

    Imre Csiszár, János Körner: Information Theory. Coding Theorems for Discrete Memoryless Systems, Second Edition, Cambridge University Press, 2011

    László Lovász: Graphs and Geometry, American Mathematical Society, 2019

    Edward R. Scheinermann, Daniel H. Ullman: Fractional Graph Theory, Wiley 1997

    internetes források
    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra56
    Félévközi készülés órákra28
    Felkészülés zárthelyire
    Házi feladat elkészítése14
    Kijelölt írásos tananyag elsajátítása14
    Vizsgafelkészülés38
    Összesen150
    15. A tantárgy tematikáját kidolgozta dr. Simonyi Gábor, egyetemi tanár, Számítástudományi és Információelméleti Tanszék