BME VIK - Kombinatorikus optimalizálás

3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid,

4. A tantárgy előadója

Dr. Recski András

Dr. Szeszlér Dávid

Salamon Gábor

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

. Lineáris programozás (16 óra):

A lineáris programozás alapfeladata, megoldási módszerek, a probléma bonyolultsága. Farkas-lemma, a lineáris programozás dualitástétele. Egészértékű programozás, a feladat bonyolultsága, korlátozás és szétválasztás (Branch and Bound). Totálisan unimoduláris mátrixok és alkalmazásuk páros gráfokra, Egerváry algoritmusa, alkalmazás hálózati folyamokra.

2. Matroidelmélet (12 óra):

Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang). Mohó algoritmus matroidon. Dualitás, minorok, direkt összeg, összeg. Matroidelméleti algoritmusok (partíciós és metszet-algoritmusok, orákulumok). Grafikus, kografikus, reguláris, bináris és lineáris matroid fogalma, ezek kapcsolata. Bináris, reguláris és grafikus matroidok jellemzése tiltott minorokkal, Tutte tételei, Seymour tétele. A k-polimatroid rangfüggvény fogalma. A 2‑polimatroid-matching probléma, ennek bonyolultsága

3. Közelítő algoritmusok (4 óra):Additív és relatív hibával közelítő algoritmus fogalma. Halmazfedési feladat, a Steiner-fa probléma, utazó ügynök probléma, nevezetes heurisztikák az utazó ügynök probléma euklideszi esetére. Polinomiális approximációs séma, a részösszeg probléma.

4. Ütemezési algoritmusok (4 óra):

Ütemezési feladatok típusai. Egygépes ütemezések, listás ütemező algoritmus párhuzamos gépek esetén, Hu algoritmusa, Coffman és Graham algoritmusa.

5. Megbízható hálózatok tervezése (4 óra):

Lokális élösszefüggőség és élösszefüggőségi szám fogalma. Nagamochi és Ibaraki algoritmusa, Karger algoritmusa. Minimális méretű 2-élösszefüggő, illetve 2-összefüggő részgráfok keresése, Khuller és Vishkin algoritmusa, Cheriyan és Thurimella algoritmusa. Gráfok 2-élösszefüggővé növelése, Plesnik algoritmusa.

6. Nagybonyolultságú hálózatok huzalozása (4 óra):

A részletes huzalozás feladata. Egyetlen pontsor huzalozása a Manhattan modellben, Gallai algoritmusa. Csatornahuzalozás 2 rétegen a megszorítás nélküli, illetve több rétegen a Manhattan modellben. Switchboxhuzalozás több rétegen. Éldiszjunkt huzalozás, Frank tétele.

7. Hálózatelméleti alkalmazások (4 óra):

Klasszikus villamos hálózatok egyértelmű megoldhatósága, Kirchhoff tételei. Általánosítás a transzformátorokat vagy girátorokat is tartalmazó hálózatokra, algoritmusok a feltételek ellenőrzésére. Általánosítás lineáris sokkapukat tartalmazó hálózatokra. Villamos hálózatok duálisa. 8. Statikai alkalmazások (4 óra)

Rúdszerkezetek merevségének vizsgálata, a probléma lineáris algebrai megfogalmazása. A rudakban ébredő erők kiszámítása, Maxwell-Cremona diagram. A generikus merevség fogalma, Laman tétele, Lovász és Yemini tétele. Síkbeli négyzetrácsok és egyszintes épületek átlós merevítése.

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

10. Követelmények Egy félévközi ZH, ennek legalább elégséges teljesítése a vizsgára bocsátás feltétele

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

12. Konzultációs lehetőségek Egyéni igény alapján

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

Jordán Tibor, Recski András és Szeszlér Dávid: Kombinatorikus optimalizálás, Typotex

Kiadó, Budapest, 2004

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	56
Félévközi készülés órákra	14
Felkészülés zárthelyire	20
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés	60
Összesen	150

15. A tantárgy tematikáját kidolgozta Dr. Recski András és Dr. Szeszlér Dávid