Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
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.
Villamosmérnöki szak, MSc képzés
Felsőbb matematika
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
lineáris algebra, gráfelmélet és algoritmuselmélet alapjai
A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.
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.