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.

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