Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

lineáris algebra, gráfelmélet és algoritmuselmélet alapjai

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

A tantárgy az operációkutatás és a kombinatorikus optimalizálás néhány területére nyújt bevezetést. A téma legfontosabb algoritmusainak, módszereinek és ezek korlátainak ismertetése mellett célul tűzi ki, hogy ezek műszaki alkalmazásaiba is betekintést nyújtson. Így terítékre kerülnek olyan átfogó algoritmikus megközelítéseket kínáló területek, mint  a lineáris és egészértékű programozás és a matroidelmélet, de emellett a tárgy betekintést nyújt a  megbízható hálózatok tervezése során felmerülő problémákba is. A tantárgy további célja, hogy a villamosmérnök BSc képzés A számítástudomány alapjai című tantárgya során korábban megszerzett ismereteket alkalmazza, elmélyítse, azok elméleti hátterét jobban megvilágítsa.

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.

Heti 2 óra előadás és 1 óra gyakorlat.

A félév során három zárthelyi dolgozat lesz. A félév teljesítésének feltétele: minden zárthelyin legalább 40 %-os teljesítmény. A végső jegy (teljesítés esetén) a három zárthelyi átlagából adódik.

A szorgalmi időszakban minden zárthelyi dolgozathoz lesz pótlási (javítási) lehetőség. A pótlási héten írt második pótzárthelyi alkalmával egy tetszőleges zárthelyi dolgozat pótolható.

Egyéni egyeztetés szerint.

Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004.