Felsőbb matematika villamosmérnököknek - Kombinatorikus optimalizálás

1)      Lineáris és egészértékű programozás: Maximális méretű párosítás feladata páros gráfban: a javító utas algoritmus (ismétlés). Egerváry algoritmusa maximális összsúlyú párosítás és teljes párosítás keresésére páros gráfban.

2)      Lineáris és egészértékű programozás: A lineáris programozás alapfeladata, kétváltozós feladatok megoldása grafikusan módszerrel. Lineáris egyenlőtlenségrendszerek megoldása Fourier-Motzkin eliminációval.

3)      Lineáris és egészértékű programozás: Szükséges és elégséges feltételek lineáris egyenletrendszerek nemnegatív változókkal való, illetve lineáris egyenlőtlenségrendszerek megoldhatóságára: a Farkas-lemma. A lineáris programozás alapfeladata mátrixos alakban.

4)      Lineáris és egészértékű programozás:  Szükséges és elégséges feltételek a lineáris program célfüggvényének korlátosságára. Lineáris program duálisának fogalma általános alakban, illetve nemnegatív változók esetén is.

5)      Lineáris és egészértékű programozás:  A lineáris programozás dualitástétele. A lineáris programozás feladatának algoritmikus bonyolultsága. Az egészértékű programozás alapfeladata, annak bonyolultsága.

6)      Lineáris és egészértékű programozás: Korlátozás és szétválasztás (Branch and Bound) módszer egészértékű programok megoldására. Gyakorlati életben felmerülő problémák formalizálása egészértékű programozási feladatként.

7)      Lineáris és egészértékű programozás: Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazások a páros gráfok párosításainak területéről. Alkalmazások a hálózati folyamproblémák területéről: maximális folyam, minimális költségű folyam, többtermékes folyam feladatok.

8)      Matroidelmélet: Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang). Nevezetes példák. Függetlenségi axiómák, bázisaxiómák és köraxiómák. Mohó algoritmus matroidon. A matroid két definíciójának ekvivalenciája.

9)      Matroidelmélet: Matroid duálisának fogalma, kapcsolata a gráfelméleti duálissal. Elhagyás és összehúzás, kapcsolatuk a duálissal. Matroidok minorjai. Matroidok csonkolása, direkt összege és összege.

10)  Matroidelmélet: Matroidelméleti algoritmusok: partíciós és metszet-algoritmusok. Matroidok megadása orákulummal. Példák és alkalmazások: párosítások páros gráfokban, fenyők, irányított Hamiton-utak.

11)  Matroidelmélet: Nevezetes matroidosztályok: grafikus, ko-grafikus és lineáris matroidok. A grafikus matroidok reprezentálhatósága. A duális matroid és matroid minorjának reprezentálhatósága.

12)  Megbízható hálózatok tervezése: Lokális él- és pontösszefüggőség, illetve globális él- és pontösszefüggőség fogalma, a vonatkozó Menger-tételek (ismétlés). Max-vissza sorrend, Nagamochi-Ibaraki algoritmusa az élösszefüggőség meghatározására.

13)  Megbízható hálózatok tervezése: Algoritmus gráfok 2-élösszefüggővé növelésére, alsó becslés a szükséges élek számára. Algoritmus minimális költségű feszítő fenyő keresésére. Fülfelbontás, gráfok erősen összefüggővé irányítása.

14)  Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése. A szóbeli vizsgára vonatkozó aktuális vizsgatételsor és az egyes vizsgatételekkel kapcsolatos részletes elvárások ismertetése.