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ó    

    Hipergráfok, halmazrendszerek kombinatorikája

    A tantárgy angol neve: Combinatorics of Hypergraphs and Set Systems

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

    Tantárgy lejárati dátuma: 2009. november 24.

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

    Villamosmérnöki Szak

    Műszaki Informatika Szak

    Választható tárgy
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMA9372 tavasz 2/0/0/v 3 1/1
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Simonyi Gábor

    egyetemi 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

    Diszkrét matematikai alapfogalmak, gráfelmélet alapjai.

    6. Előtanulmányi rend
    Ajánlott:

    Ajánlott:

    Bevezető gráfelméleti kurzus elvégzése után célszerű 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 : korábban a tárgy azonos címmel, de bmevima9337 kóddal ment

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

    A diszkrét matematikai gondolkodásmód fejlesztése, elmélyítése; hipergráfokkal, illetve véges halmazok részhalmazrendszereivel kapcsolatos tételek megismertetése.

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

    Az alapfogalmak (ezen belül a hipergráfok, halmazrendszerek, 0 – 1 sorozathalmazok fogalmi ekvivalenciájának) tisztázása után tárgyalandó témakörök:

    • Sperner rendszerek (Sperner-tétel, LYM-egyenlőtlenség, Ahlswede-Zhang azonosság),
    • metsző rendszerek (Erdős-Ko-Rado tétel, Frankl-Wilson tétel, Borsuk-sejtés Kahn-Kalai féle cáfolata),
    • halmazrendszerek "árnyéka" (Kruskal-Katona tétel),
    • Turán-tétel hipergráfos analogonjai (Erdős-Katona probléma, Shearer-konstrukció, Tolhuizen-tétel),
    • perfekt gráf tétel bizonyítása hipergráfok segítségével
    • telített és Ä-kritikus rendszerek (Bollobás-egyenlőtlenség és következményei)
    • faktorizációs tételek és alkalmazásaik,
    • többrendszeres egyenlőtlenségek (Ahlswede-Daykin egyenlőtlenség és speciális esetei),
    • extremális halmazelméleti problémák tárgyalása irányított gráfok kapacitáskérdéseiként.
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    Heti két óra előadás

    10. Követelmények

    a. A szorgalmi időszakban: -

    b. A vizsgaidőszakban: szóbeli vizsga

    c. Elővizsga: megállapodás alapján

    11. Pótlási lehetőségek

    -

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

    vizsgák előtt, megbeszélés szerint

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

    A vizsgára való felkészülés fő segédanyaga az előadásokon készített jegyzet. Az előadások anyagának jelentős része megtalálható az alábbi, valószínűleg nehezen hozzáférhető könyvben:

    B. Bollobás: Combinatorics – Set systems, Hypergraphs, Families of Vectors and Combinatorial Probability, Cambridge University Press, Cambridge, 1986

    Háttéranyagként jól használható még: Lovász László: Kombinatorikai problémák és feladatok, Typotex Kiadó, Budapest, 1999,

    illetve ugyane könyv eredeti, angol nyelvű változata: L. Lovász: Combinatorial Problems and Exercises, Akadémiai Kiadó, Budapest, 1993

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

    (a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):

    Kontakt óra

    30

    Félévközi készülés órákra

    10

    Felkészülés zárthelyire

    Házi feladat elkészítése

    Kijelölt írásos tananyag elsajátítása

    ..

    Vizsgafelkészülés

    50

    Összesen

    90

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

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Simonyi Gábor

    egyetemi docens

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

    vima9372.rtf