Kombinatorikus optimalizálás
A tantárgyleírás hatályossága
| Tantárgy neve (magyarul, angolul) |
Kombinatorikus optimalizálás
Combinatorial Optimization
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tantárgykód | BMEVISZM029 | ||||||||||||
| Tantárgyjelleg | — | ||||||||||||
| Képzési szint | — | ||||||||||||
| Kurzustípusok és óraszámok (heti/féléves) |
|
||||||||||||
| Tanulmányi teljesítmény/értékelés típusa | vizsga | ||||||||||||
| Tantárgy kreditértéke | 5 | ||||||||||||
| Tantárgyfelelős |
DR. Szeszlér Dávid
beosztás: egyetemi docens
elérhetőség:
szeszler.david@vik.bme.hu
|
||||||||||||
| Tantárgyat gondozó oktatási szervezeti egység |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Kar | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Tantárgy weboldala | — | ||||||||||||
| Tantárgy elsődleges mintatantervi jellege | — | ||||||||||||
| Közvetlen előkövetelmények – Erős előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Gyenge előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Párhuzamos előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Mérföldkő előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Kizáró feltétel | nincs |
Célkitűzés
. 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ága3. 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.
Nincs megadott célkitűzés.
Tanulmányi eredmények
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Tudás
Nincsenek rögzített tanulási eredmények.
Képességek
Nincsenek rögzített tanulási eredmények.
Attitűd
Nincsenek rögzített tanulási eredmények.
Autonómia és felelősség
Nincsenek rögzített tanulási eredmények.
Oktatási módszertan
Tanulástámogató anyagok
Online források
A tantárgy teljesítéséhez ajánlott előzetes ismeretek
Általános szabályok
Teljesítményértékelési módszerek
Szorgalmi időszakban végzett teljesítményértékelések részletes leírása
Nincs megadva részletes értékelés.
Szorgalmi időszakban végzett teljesítményértékelések részaránya
Nincs megadva részarány.
Vizsgaidőszakban végzett teljesítményértékelések részletes leírása
Nincs megadva részletes értékelés.
Vizsgarészek részaránya
Nincs megadva részarány.
Érdemjegy megállapítása
Nincs megadva érdemjegy határ.
Jelenléti és részvételi követelmények
Nincs megadva jelenléti követelmény.
Javítás, ismétlés és pótlás különös szabályai
Nincs megadva.
Rövid leírás
Nincs megadva.
Részletes leírás
Nincs megadva.
Ajánlott tantárgyak
Nincs megadva.
A tantárgy elvégzéséhez szükséges tanulmányi munka
Nincs megadva munkaidő bontás.
Tantárgykövetelmények hatályossága
Tantervi elhelyezés
Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.