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, Számítástudományi és Információelméleti Tanszék
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