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

A tantárgy angol neve: Advanced Mathematics for Electrical Engineers - Combinatorial Optimization

Adatlap utolsó módosítása: 2014. szeptember 22.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Villamosmérnöki szak, MSc képzés

Felsőbb matematika

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZMA06 1 2/1/0/f 3  
3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid,
A tantárgy tanszéki weboldala http://cs.bme.hu/villkombopt
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr. Szeszlér Dávid

egyetemi docens

Számítástudományi  Információelméleti Tanszék

5. A tantárgy az alábbi témakörök ismeretére épít

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

6. Előtanulmányi rend
Kötelező:
NEM ( TárgyEredmény( "BMETE90MX38" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMETTE90MX38", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rendek grafikus formában itt láthatók.

7. A tantárgy célkitűzése

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.

8. A tantárgy részletes tematikája

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.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

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

10. Követelmények

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.

11. Pótlási lehetőségek

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

12. Konzultációs lehetőségek

Egyéni egyeztetés szerint.

13. Jegyzet, tankönyv, felhasználható irodalom

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

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra42
Félévközi készülés órákra9
Felkészülés zárthelyire9
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés30
Összesen90
15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Dr. Szeszlér Dávid

egyetemi docens

Számítástudományi  Információelméleti Tanszék