Rendszeroptimalizálás

System Optimisation

A tantárgyleírás hatályossága

Hatályosság kezdete:

2026. March 21.

Hatályosság vége:

—

Tantárgy neve (magyarul, angolul)

Rendszeroptimalizálás

System Optimisation

Tantárgykód

BMEVISZM117

Tantárgyjelleg

—

Képzési szint

—

Kurzustípusok és óraszámok (heti/féléves)

Kurzustípus	elmélet	gyakorlat	laboratóriumi gyakorlat
óraszám (heti)	4	0	0
jelleg (kapcsolt/önálló)	—	—	—

Tanulmányi teljesítmény/értékelés típusa

vizsga

Tantárgy kreditértéke

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

http://cs.bme.hu/rendszeropt/

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

Tantárgyprogram

1. 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.

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 korlátainak ismertetése mellett célul tűzi ki, hogy ezek műszaki alkalmazásaiba is betekintést nyújtson. A szemeszter első felében olyan átfogó, általános módszereket mutat be, amelyek a gyakorlati élet számtalan területén eredményesen alkalmazhatónak bizonyultak. Így terítékre kerül a lineáris programozás, a matroidelmélet, a közelítő algoritmusok, valamint az ütemezési algoritmusok témaköre. A félév második felében négy olyan műszaki esettanulmányt tárgyal, amelyek részben a fenti általános módszerek, részben a kombinatorikus szemléletű megközelítés eredményességét és hatékonyságát illusztrálják. Így betekintést nyújt a megbízható hálózatok tervezése, a villamos hálózatok klasszikus elmélete, a nagy bonyolultságú hálózatok huzalozása és a statika területén felmerülő kombinatorikus jellegű feladatokba. A tantárgy további célja, hogy a mérnökinformatikus BSc képzés Bevezetés a számításelméletbe I. és II., valamint Algoritmuselmélet című tárgyai során korábban megszerzett ismereteket alkalmazza, elmélyítse, azok elméleti hátterét jobban megvilágítsa.

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

előadás

Tanulástámogató anyagok

Online források

Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004.

A tantárgy teljesítéséhez ajánlott előzetes ismeretek

Tudás típusú kompetenciák

(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)

lineáris algebra, gráfelmélet és algoritmuselmélet alapjai

Képesség típusú kompetenciák

(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)

nincs

Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák

(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)

lineáris algebra, gráfelmélet és algoritmuselmélet alapjai

Általános szabályok

Követelmények: szorgalmi időszakban: az aláírás feltétele egy nagyzárthelyi sikeres megírása, továbbá a lineáris programozás anyagrészből egy beadandó házi feladat elkészítése. A házi feladatot névre szólóan adjuk ki, ezek hallgatónként különbözők.vizsgaidőszakban: szóbeli vizsga Pótlási lehetőségek: A nagyzárthelyit a szorgalmi időszakban írt pótzárthelyin, vagy a pótlási héten írt pótpótzárthelyin (ez a Neptunban aláíráspótló vizsga néven szerepel) lehet pótolni. A házi feladat késedelmes leadásának határideje a pótlási időszak vége.

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

Tantárgykövetelmények hatályosságának kezdete:

—

Tantárgykövetelmények hatályosságának vége:

—

Tantervi elhelyezés

Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.