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ó    

    Matroidelmélet és műszaki alkalmazásai

    A tantárgy angol neve: Matroid theory and its engineering applications

    Adatlap utolsó módosítása: 2019. május 13.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar
    Doktori képzés
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZD309   2/0/0/f 3  
    3. A tantárgyfelelős személy és tanszék Dr. Recski András, Számítástudományi és Információelméleti Tanszék
    A tantárgy tanszéki weboldala http://www.cs.bme.hu/matroid/
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Recski András

    egyetemi tanár (emeritus)

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

     

     

     

    Dr. Szeszlér Dávid

    egyetemi docens

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

    Dr. Wiener 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 A Bevezetés a számításelméletbe 2. (BMEVISZAA04)  és az Algoritmuselmélet ( BMEVISZAB03) tárgyak anyaga.
    7. A tantárgy célkitűzése

    A tantárgy célkitűzése bevezetést adni a matroidelméletbe, bemutatni a legfontosabb matroidelméleti algoritmusokat, továbbá ezek legfontosabb műszaki alkalmazásait.

    A tantárgyat sikeresen teljesítő hallgató képes lesz:

    • (K3)  érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket;
    • (K3)  önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat;
    • (K2)  alkalmazni a tárgyban szereplő algoritmusokat;
    • (K3)  későbbi tanulmányai és kutatómunkája során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.
    8. A tantárgy részletes tematikája

    1)      A matroidelmélet szempontjából legfontosabb lineáris algebrai és gráfelméleti ismeretek felelevenítése, ezeken keresztül a matroidok fogalmának a bevezetése. A mohó algoritmus matroidokra. A matroidok alternatív jellemzése a mohó algoritmus jóságának a segítségével.

    2)      Matroidelméleti alapfogalmak: alaphalmaz, független részhalmazok, összefüggő részhalmazok, bázisok, körök, rangfüggvény. A grafikus, a lineáris és az uniform matroidok osztályának bevezetése, ezen osztályok viszonya (a bizonyítások egy része csak később).

    3)      Matroidok jellemzése bázisaival, a duális matroid fogalma. Grafikus és kografikus matroidok. A síkbarajzolhatóság matroidelméleti jelentése (első rész). Duális matroid rangfüggvénye.

    4)      Matroidok jellemzése a rangfüggvényével. Az elhagyás és összehúzás műveletek bevezetése, minorképzés, jelentésük grafikus, lineáris és uniform matroidok esetén. A síkbarajzolhatóság matroidelméleti jelentése (második rész), Kuratowski és Wagner tétele.

    5)      Matroidok reprezentálhatósága. A szükséges testelméleti tételek. A Fano- és anti-Fano matroidok. Bináris, reguláris és grafikus matroidok jellemzése tiltott minorokkal (bizonyítás csak a feltételek szükségességére). Matroidok direkt összege. A Vámos-Higgs matroid.

    6)      Matroidok uniója. A matroid partíciós probléma. Polinom rendű algoritmus a probléma megoldására tetszőleges számú matroid esetén.

     7)      A matroid metszet probléma. Polinom rendű algoritmus a probléma megoldására 2 matroid esetén, a 2-nél nagyobb számú matroidra vonatkozó eset NP-nehéz volta.

    8)      A matroidelméleti algoritmusok adatstruktúrája, az orákulum fogalma. A nevezetes matroidelméleti orákulumok egymáshoz való viszonya.

    9)      A k-polimatroid rangfüggvény fogalma, a k-polimatroid matching probléma nehézsége. Lovász tétele a k=2 eset polinom-idejű megoldhatóságáról bizonyos, a műszaki alkalmazások szempontjából fontos speciális esetben.

    10)  Villamosságtani alkalmazások (első rész): A hálózatanalízis alapfeladata, Kirchhoff klasszikus eredményei, a „topológiai” formulák.

    11)  Villamosságtani alkalmazások (második rész): Kirchhoff eredményeinek általánosítása ideális transzformátorokat és/vagy girátorokat tartalmazó hálózatokra. Az egyértelmű megoldhatóság szükséges feltétele lineáris n-kapukat tartalmazó hálózatokra. A dualitás-elv és kiterjesztései.

    12)  Statikai alkalmazások (első rész): Rúdszerkezetek fogalma, a merevségi mátrix, az infinitezimális merevség fogalma. Maxwell tételei, Laman tétele, a Lovász-Yemini tétel.

    13)  Statikai alkalmazások (második rész): Rúdszerkezetek minimális számú csuklóval való lefogása. „Tensegrity”-szerkezetek. Átlós rúddal vagy kábellel kimerevített síkbeli négyzetrácsok merevsége.

    14)  Tartalék idő. Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése.

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

    A tárgyból heti 2 óra előadás van, melynek során a leadott anyag gyakorlására és feladatokban való alkalmazására is sor kerül.

    10. Követelmények

    A szorgalmi időszakban: A félév folyamán egyetlen zárthelyit íratunk az első nyolc előadás anyagából. Ennek alapján lehet megajánlott jegyet (legfeljebb közepest) szerezni. A jó vagy jeles osztályzathoz az utolsó héten az egész anyagból be kell számolni, azonban a két műszaki alkalmazási terület közül elég, ha a hallgató az általa szabadon választott egyiket sajátítja el.

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

    A szorgalmi időszakban egyetlen pótzárthelyi alkalom lesz, amelyen a zárthelyi eredménye javítható vagy a hiányzás pótolható.

    A pótzárthelyin tehát a korábban megírt, eredményes zárthelyi javítása is megkísérelhető, de csak azzal a feltétellel, hogy ilyenkor mindenképpen az új pontszám lesz érvényes, akkor is, ha az rosszabb, mint az eredeti. Ez alól egy kivétel van: ha egy hallgató a normál zárthelyin legalább 40%-os teljesítményt ért el és így az elégséges osztályzatot megajánlott jegyként már elérte, akkor ezt már nem veszti el.

     Amennyiben a zárthelyi és a pótzárthelyi segítségével sem sikerül az aláírás feltételeit teljesíteni, a vizsgaidőszak előtti pótlási héten lehetőség nyílik a zárthelyi újbóli pótlására. Ennek a második pótzárthelyi alkalomnak a neve “díjköteles pótlás”. A díjköteles pótlás megírásáért különeljárási díjat kell fizetni és azon a korábban megírt, sikeres (vagyis a 40%-os teljesítményt elérő) zárthelyi vagy pótzárthelyi eredménye már nem javítható.

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

    A zárthelyi és a pótzárthelyi előtt konzultációs lehetőséget biztosítunk.

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

    Jordán Tibor - Recski András – Szeszlér Dávid: Rendszeroptimalizálás, TypoTeX Kiadó, Budapest, 2011. ISBN: 978-963-2791-16-6

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra28
    Félévközi készülés órákra16
    Felkészülés zárthelyire16
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés60
    Összesen
    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Recski András

    egyetemi tanár (emeritus)

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