Belépés címtáras azonosítással
magyar nyelvű adatlap
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.
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
Dr. Wiener Gábor
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:
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.
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.
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.
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ó.
A zárthelyi és a pótzárthelyi előtt konzultációs lehetőséget biztosítunk.
Jordán Tibor - Recski András – Szeszlér Dávid: Rendszeroptimalizálás, TypoTeX Kiadó, Budapest, 2011. ISBN: 978-963-2791-16-6
