Belépés címtáras azonosítással
magyar nyelvű adatlap
Rendszeroptimalizálás
A tantárgy angol neve: System Optimisation
Adatlap utolsó módosítása: 2006. július 1.
Tantárgy lejárati dátuma: 2015. január 31.
Műszaki Informatika Szak
5. évfolyam - Elágazó II.
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.
-
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
Kontakt óra
60
Félévközi készülés órákra
15
Felkészülés zárthelyire
Házi feladat elkészítése
10
Kijelölt írásos tananyag elsajátítása
..
Vizsgafelkészülés
50
Összesen
150