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

Fleiner Tamás

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 hálózati folyamok elmélete és a lineáris és egészértékű programozás, de emellett a tárgy betekintést nyújt a megbízható hálózatok tervezése során felmerülő magasabb összefüggőséggel kapcsolatos problémák mellett a közelítő algoritmusok és az ütemezéselmélet világába 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. Hálózati folyamok, Ford-Fulkerson-algoritmus, egészértékűségi lemma, a folyamprobléma egyszerű általánosításai.

2. Páros gráfok karakterizációja, maximális méretű párosítás páros gráfban. Kőnig, Frobenius és Hall tételei.

3. Gráfszínezések. Alsó és felső korlát a kromatikus számra. Gráfok élszínezése, Vizing tétele. Páros gráfok élszínezése az egészértékűségi lemma segítségével

4. Egerváry algoritmusa maximális összsúlyú párosítás és teljes párosítás keresésére páros gráfban.

5. Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata, kétváltozós feladatok megoldása grafikus módszerrel. Lineáris egyenlőtlenségrendszerek megoldása Fourier-Motzkin eliminációval. 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.

6. A lineáris programozás alapfeladata mátrixos alakban. 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, különféle alakban felírt lineáris programok duálisai.

7. 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. Optimalizálási problémák formalizálása egészértékű programozási feladatként.

8. 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 és a hálózati folyamproblémák területéről: maximális folyam, minimális költségű folyam, ill. többtermékes folyam feladatok.

9. 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.

10. 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.

11. Közelítő algoritmusok. Élkromatikus szám, síkgráf kromatikus szám közelítése additív hibával, leghosszabb kör additív hibával való közelíthetetlensége. 2-közelítés a lefogó ponthalmaz méretére, logaritmikus közelítés a halmazfedési problémára.

12. Ütemezési problémák. Alapfogalmak, jelölésrendszer, hasznos módszerek: SPT sorrend és listás ütemezés. FD és FFD heurisztikák a ládapakolási problémára.

13. 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.

A tárgyhoz előadások és gyakorlatok tartoznak.

Mindkét zárthelyi dolgozathoz egy pótlási/javítási alkalmat biztosítunk. A szóbeli vizsga javítása a hatályos TVSZ szerint történik.

A ZH előtti gyakorlaton konzultációs lehetőséget biztosítunk. További konzultáció egyeztetés szerint.

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

• Előadás diasorok

Fleiner Tamás