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

Graphs, Capacities, Entropies: Introduction to Information Theoretic Combinatorics

A tantárgyleírás hatályossága

Hatályosság kezdete:

2026. March 21.

Hatályosság vége:

—

Tantárgy neve (magyarul, angolul)

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

Graphs, Capacities, Entropies: Introduction to Information Theoretic Combinatorics

Tantárgykód

BMEVISZD306

Tantárgyjelleg

—

Képzési szint

—

Kurzustípusok és óraszámok (heti/féléves)

Kurzustípus	elmélet	gyakorlat	laboratóriumi gyakorlat
óraszám (heti)	4	0	0
jelleg (kapcsolt/önálló)	—	—	—

Tanulmányi teljesítmény/értékelés típusa

vizsga

Tantárgy kreditértéke

Tantárgyfelelős

Dr. Simonyi Gábor

elérhetőség: simonyi@math-inst.hu

Tantárgyat gondozó oktatási szervezeti egység

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

Kar

Villamosmérnöki és Informatikai Kar

Tantárgy weboldala

—

Tantárgy elsődleges mintatantervi jellege

—

Közvetlen előkövetelmények – Erős előkövetelmény

nincs

Közvetlen előkövetelmények – Gyenge előkövetelmény

nincs

Közvetlen előkövetelmények – Párhuzamos előkövetelmény

nincs

Közvetlen előkövetelmények – Mérföldkő előkövetelmény

nincs

Közvetlen előkövetelmények – Kizáró feltétel

nincs

Célkitűzés

Tantárgyprogram

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.

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.

Tanulmányi eredmények

Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:

Tudás

Nincsenek rögzített tanulási eredmények.

Képességek

Nincsenek rögzített tanulási eredmények.

Attitűd

Nincsenek rögzített tanulási eredmények.

Autonómia és felelősség

Nincsenek rögzített tanulási eredmények.

Oktatási módszertan

Heti 4 óra előadás.

Tanulástámogató anyagok

Online források

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

A tantárgy teljesítéséhez ajánlott előzetes ismeretek

Tudás típusú kompetenciák

(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)

Gráfelmélet, lineáris algebra, valószínűségszámítás alapjai

Képesség típusú kompetenciák

(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)

nincs

Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák

(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)

Gráfelmélet, lineáris algebra, valószínűségszámítás alapjai

Általános szabályok

Követelmények: szóbeli vizsga

Teljesítményértékelési módszerek

Szorgalmi időszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Szorgalmi időszakban végzett teljesítményértékelések részaránya

Nincs megadva részarány.

Vizsgaidőszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Vizsgarészek részaránya

Nincs megadva részarány.

Érdemjegy megállapítása

Nincs megadva érdemjegy határ.

Jelenléti és részvételi követelmények

Nincs megadva jelenléti követelmény.

Javítás, ismétlés és pótlás különös szabályai

Nincs megadva.

Rövid leírás

Nincs megadva.

Részletes leírás

Nincs megadva.

Ajánlott tantárgyak

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.

A tantárgy elvégzéséhez szükséges tanulmányi munka

Nincs megadva munkaidő bontás.

Tantárgykövetelmények hatályossága

Tantárgykövetelmények hatályosságának kezdete:

—

Tantárgykövetelmények hatályosságának vége:

—

Tantervi elhelyezés

Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.