Belépés címtáras azonosítással
magyar nyelvű adatlap
Kombinatorikus optimalizálás
A tantárgy angol neve: Combinatorial Optimisation
Adatlap utolsó módosítása: 2009. szeptember 22.
Doktori választható tárgy
Név:
Beosztás:
Tanszék, Int.:
Dr. Recski András
egyetemi tanár
Számítástudományi és Információelméleti Tanszék
Szeszlér Dávid
egyetemi tanársegéd
Wiener Gábor
egyetemi adjunktus
A Bevezetés a Számításelméletbe I. és II. , valamint az Algoritmuselmélet tárgyak anyaga.
: -
Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat: BMEVIMA5311 vagy BMEVISZM117 Rendszeroptimalizálás
A kombinatorikus optimalizálás legfontosabb algoritmusainak, módszereinek, korlátainak ismertetése, valamint betekintés ezek műszaki alkalmazásaiba (megbízható hálózatok tervezése, villamos hálózatok klasszikus elmélete, VLSI tervezés, statika területeken).
A lineáris programozás alapfeladata, megoldási módszerek, Farkas-lemma, dualitás, egészértékű programozás. Totális unimodularitás, alkalmazás páros gráfokra, Egerváry algoritmusa, alkalmazás hálózati folyamokra.
Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang), dualitás, minorok, direkt összeg, összeg. Matroidelméleti algoritmusok (mohó algoritmus, matroid partíciós és metszet-algoritmusok, orákulumok). Matroid párosítási probléma. Matroidok és gráfok kapcsolata, vektorreprezentáció, geometriai reprezentáció. Tutte tételei (biz. nélkül).
Közelítő algoritmusok, halmazfedési feladat, Steiner-fák, utazó ügynök probléma, nevezetes heurisztikák az utazó ügynök probléma euklideszi esetére.
Ütemezési feladatok, egygépes ütemezések, listás ütemező algoritmus párhuzamos gépek esetén, Hu algoritmusa, Coffman és Graham algoritmusa .
Alkalmazások a megbízható hálózatok tervezésében, az összefüggőség kiszámítása, Nagamochi és Ibaraki algoritmusa, Karger algoritmusa. Többszörösen összefüggő részgráfok, Khuller és Vishkin algoritmusa, Cheriyan és Thurimella algoritmusa. Az összefüggőség növelése, Plesnik algoritmusa.
Alkalmazások a VLSI hálózatok huzalozásában (Gallai tétele és az egyetlen pontsor huzalozhatósága a Manhattan-modellben, csatornahuzalozás 2 és több rétegen, ˛switchbox˛-huzalozás több rétegen, Frank A. tétele az éldiszjunkt huzalozásra és ennek következményei).
Alkalmazások a villamos hálózatok klasszikus elméletében, hálózatok egyértelmű megoldhatósága, a szabadsági fokok száma. Általánosítás többpólusú lineáris alkatrészeket is tartalmazó hálózatokra. Dualitás.
Alkalmazások a rúdszerkezetek merevségének vizsgálatában, a probléma kitűzése, átfogalmazása lineáris algebrai feltétellé, a merevség definíciója, generikus merevség, Laman tétele, Lovász és Yemini tétele, a 3-dimenziós analógia nehézségei, kapcsolat a poliéderek vetületből való rekonstrukciójával, minimális számú csuklóval való rögzítés. Négyzetrácsok merevítése étlós rudakkal.
(előadás, gyakorlat, laboratórium):
előadás
a. A szorgalmi időszakban: egy zárthelyi, egy beadandó házi feladat
b. A vizsgaidőszakban: szóbeli vizsga
Az elégtelen zárthelyi javítására, vagy a zárthelyi pótlására lehetőséget biztosítunk a szorgalmi időszak végén.
Egyéni megbeszélés alapján.
Dr. Jordán Tibor - Dr. Recski András –- Szeszlér Dávid: Rendszeroptimalizálás, Typotex, Budapest, 2004
(a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):
Kontakt óra
56
Félévközi készülés órákra
9
Felkészülés zárthelyire
Házi feladat elkészítése
36
Kijelölt írásos tananyag elsajátítása
..
Vizsgafelkészülés
40
Összesen
150