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 és információelmélet

    A tantárgy angol neve: Graphs and Information Theory

    Adatlap utolsó módosítása: 2006. július 1.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    Doktori képzés

    Választható tárgy

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMAD056 ősz 2/0/0/v 3 1/1
    3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Simonyi Gábor

    egy. docens

    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 4. pontban felsorolt területek alapismereteit tárgyaló kurzusok után ajánlott felvenni,.

    Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat:

    Neptun-kód Cím: nincs ilyen

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

    Különböző matematikai területek egymásra hatásának bemutatása, különös tekintettel az információelmélet eszköztárának hatékonyságára a gráfelméletben. Ennek keretében a diszkrét matematikai gondolkodás további fejlesztése.

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

    A kurzus olyan gráfelméleti eredményeket tárgyal, amelyek valamilyen – olykor egészen laza, máskor szorosabb – kapcsolatba hozhatók az információelmélettel. Egyebek között a következőkről lesz szó:

    • Gráfok Shannon-kapacitása
    • Gráfszorzatok és frakcionális gráfparaméterek
    • A Shannon-kapacitás és a Ramsey számok kapcsolata
    • Lovász-féle theta-függvény
    • Irányított gráfok kapacitása (Sperner-kapacitás)
    • Gráfparaméterek valószínűségi finomításai
    • Gráfcsaládok kapacitása
    • Gráfentrópia és tulajdonságai, kapcsolata perfekt gráfokkal
    • Kahn és Kim gráfentrópián alapuló rendezési algoritmusa
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    (heti 2 óra) előadás

    10. Követelmények

    a. A szorgalmi időszakban: -

    b. A vizsgaidőszakban: vizsga

    c. Elővizsga: -

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

    A kurzus anyaga különböző szakkönyvekben, összefoglaló cikkekben szétszórva található meg, ezért elsődleges írott segédanyagként az előadáson írt jegyzet szolgálhat.

    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Simonyi Gábor

    egy. docens

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

    vimad056.rtf