Rendszeroptimalizálás
Kombinatorikus optimalizálás
BMEVISZMA10
BMEVISZM029
(informatikus MSc hallgatóknak)
(matematikus MSc vagy alkalmazott matematikus MSc hallgatóknak)

2024/2025. második félév

Előadások, előadó

Előadó:
 Időpont:
 Helyszín:
Kaszanitzky Viktória (email: kaszanitzky_KUKAC_cs.bme.hu)
 Hétfő 8:15 - 10:00
 E1B QBF09

Csütörtök 8:15 - 10:00
 E1B QBF09


Mindegyik előadás második felében önálló feladatmegoldás zajlik.


A tárgy anyaga

Ez a tárgy a kombinatorikus optimalizálás néhány területére kíván bevezetést nyújtani. A téma néhány fontos algoritmusának, módszerének és azok korlátainak ismertetése mellett célul tűzi ki, hogy ezek gyakorlati életbeli alkalmazási lehetőségeit is bemutassa. A tárgy által érintett témakörök: lineáris- és egészértékű programozás, közelítő algoritmusok és ütemezési algoritmusok.

A tárgy épít a mérnökinformatikus BSc képzés Bevezetés a számításelméletbe 1, Bevezetés a számításelméletbe 2 és Algoritmuselmélet című tárgyaira és célul tűzi ki, hogy az ezekben megszerzett ismereteket alkalmazza, elmélyítse, azok elméleti hátterét jobban megvilágítsa.

A 2023. tavaszi félévtől kezdve a kari MSc képzés megújult. Ez a Rendszeroptimalizálás tárgy anyagát érdemben nem érintette, csak a tárgy kódja változott és (kis mértékben) a tárgykövetelmények. Így a honlapon szereplő korábbi segédanyagok és zárthelyi feladatsorok továbbra is használhatók a készüléshez.


A félév ütemterve   


1. hét
 02.10.h
 Bonyolultságelméleti alapfogalmak

02.13.cs
 NP-nehéz problémák polinom időben megoldható spec. esetei: maximális független ponthalmaz, pont-, illetve élszínezés
2. hét 02.17.h
 Additív hibával közelítő algoritmusok: egyszerű gráfok élszínezése, síkgráfok színezése, a leghosszabb kör nem közelíthető additív hibával

02.20.cs
 Multiplikatív hibával közelítő algoritmusok, minimális lefogó ponthalmaz keresése és maximális élszámú páros részgráf keresése
3. hét 02.24.h
 Approximációs algoritmus a halmazfedési feladatra

02.27.cs
 Steiner-fa
4. hét 03.03.h
 Az utazóügynök probléma

03.06.cs
 A metrikus utazóügynök probléma, Christofides algoritmusa
5. hét 03.10.h
 Polinomiális és teljesen polinomiális approximációs sémák

03.13.cs
 Teljesen polinomiális approximációs séma a részösszeg problémára
6. hét 03.17.h
 Az optimális hozzárendelés problémája, címkézés

03.20.cs
 Egerváry algoritmusa
7. hét 03.24.h
 Kétváltozós lineáris programozási feladatok grafikus megoldása

03.27.cs
 Farkas-lemma
8. hét 03.31.h
 A Farkas-lemma 2. alakja

04.03.cs
 A lineáris program célfüggvényének felülről korlátosságának feltételei
9. hét 04.07.h
 A lineáris programozás dualitástétele

04.10.cs
 Folyamokkal kapcsolatos feladatok
10. hét 04.14.h
 Totálisan unimoduláris mátrixok

04.17.cs
 Tavaszi szünet, nincs előadás.

04.21.h
 Tavaszi szünet, nincs előadás.

04.24.cs
 Tavaszi szünet, nincs előadás.
11. hét 04.28.h
 Konzultáció

04.28.h 18-20 ZH (az anyag az ápr. 14-i előadás anyagát még tartalmazza) Terem: KF51(AUD.MAX): A-K; CHFMAX: L-Zs a vezetéknév kezdőbetője szerint

05.01.cs
 Nemzeti ünnep, nincs előadás.
12. hét 05.05.h
 A lineáris és egészértékő programozás alkalmazásai 1.

05.08.cs
 A lineáris és egészértékű programozás alkalmazásai 2.
13. hét 05.12.h
 A lineáris és egészértékű programozás alkalmazásai 3.

05.12.h 18-20 PZH

05.15.cs
 Tartalék
14. hét 05.19.h
 Ütemezési feladatok 1.

05.22.cs
 Ütemezési feladatok 2.
1. vizsgahét
 06.02.h
 PPZH

Segédanyagok

A tárgyhoz kapcsolódó tankönyv:

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

A fenti könyv javított, elektronikus változatban is megvásárolható itt.

A (2004-es, nyomtatott kiadásban) eddig talált, értelemzavaró sajtóhibák listája itt megnézhető. (Ezeket az elektronikus változatban már kijavítottuk.)

A közelítő algoritmusok és ütemezéselmélet részeket tartalmazó elektronikus jegyzet letölthető innen.

Az LP/IP anyagrész végéhez tartozó, "Egészértékű programozás totálisan unimoduláris együtthatómátrixszal" című jegyzet letölthető innen. (Ez az anyagrész szerepel a fenti tankönyvben is, de mivel a tárgy anyaga a könyv megjelenése óta eltelt időben sokat változott, ez a jegyzet jobban illeszkedik a tárgy mostani felépítéséhez.)

A tárgy előadásaiból a 2021. tavaszi félévben, a távoktatás során videófelvétel készült. (Ezek a felvételek csak az órák első felét tartalmazzák, a második, feladatmegoldással töltött részét nem.) Ezek a videók elérhetők a következő linkeken (MS STREAM, edu.bme.hu hozzáféréssel): lineáris programozás (Szeszlér Dávid), közelítő algoritmusok (Wiener Gábor). Felhívjuk azonban a figyelmet arra, hogy ebben a félévben az előadások anyaga a videókon látottól (kis mértékben) eltérhet.

Figyelem! Az MS Stream elérése május közepén véglegesen megszűnt. A tárgyból készült és eddig itt tárolt videófelvételek archiválását és az elérésük biztosítását a Hallgatói Tudásbázis nevű szervezet válallta magára. Ennek a munkának az elvégzését még márciusban ajánlották fel a tárgy oktatóinak - és ezt mi örömmel el is fogadtuk (azzal a kikötéssel, hogy a videók továbbra is valamilyen BME címtáras hozzáférés által védett, belső felületen fognak megjelenni). Sajnos nem tudjuk megmondani, hogy ez a projekt mikor zárul le és a videók mikor válnak megint elérhetővé, de amint érdemi tájékoztatást kapunk a Hallgatói Tudásbázistól, azt itt is közzé fogjuk tenni.

Tárgykövetelmények

A félév során egy zárthelyi dolgozat lesz. Az aláírás megszerzésének feltétele a zárthelyin legalább 40%-os eredmény elérése (vagyis 60-ból legalább 24 pont megszerzése).

A Rendszeroptimalizálás (BMEVISZMA10) tárgy hallgatói számára lesz ezen kívül két nagy házi feladat is: egy a lineáris- és egészértékű programozás, egy pedig az ütemezési algoritmusok témából. A nagy házi feladatok beadása és azoknak az elfogadása a tárgyból kapható megajánlott jegy megszerzéséhez szükséges (az aláírás megszerzéséhez és a szóbeli vizsgához tehát nem). A Kombinatorikus optimalizálás (BMEVISZM029) tárgy hallgatói számára a nagy házi feladatok beadása nem kötelező, anélkül is kaphatnak megajánlott jegyet.

A tárgyból vizsgajegyet kétféleképpen lehet szerezni: megajánlott jeggyel vagy szóbeli vizsgával.

Megajánlott jegyet az kaphat, aki a zárthelyin legalább 55%-os, vagyis 33 pontos eredményt ér el és - amennyiben a Rendszeroptimalizálás (BMEVISZMA10) tárgy hallgatója - a nagy házi feladatokat beadja és azok elfogadásra kerülnek. Azoknak, akik ezeket teljesítik, a zárthelyin elért eredményük alapján ajánlunk meg vizsgajegyet: 33-41 pontos eredményért elégséges, 42-50 pontos eredményért közepes, 51-60 pontos eredményért jó vizsgajegyet ajánlunk meg. (Mivel a megajánlott jegy a zárthelyi eredményétől függ, ezért ilyet vizsgakurzuson szerezni nem lehet.)

Szóbeli vizsgát az tehet, aki a tárgyból aláírással rendelkezik és vagy nem szerzett megajánlott jegyet, vagy szerzett ugyan, de azon javítani szeretne. A szóbeli vizsgák természetesen a vizsgaidőszakban zajlanak. Ha egy hallgató jelentkezik a Neptunban egy szóbeli vizsgára (pontosabban: a vizsga napján a jelentkezettek listáján van), akkor a megajánlott jegyét elveszíti, azt a továbbiakban nem tekintjük érvényesnek - akkor sem, ha a szóbeli vizsgán végül nem jelenik meg. Aki szóbeli vizsgát tesz, annak a vizsgajegyben a zárthelyi eredményét 40%-os, a szóbelin mutatott teljesítményét 60%-os súllyal vesszük figyelembe.

Az érvényes TVSz-nek megfelelően a tárgyból korábban megszerzett aláírások érvényesek. Azok a hallgatók, akik egy korábbi félévből érvényes aláírással rendelkeznek, megkísérelhetik újból megírni a zárthelyit, hogy a korábbi zárthelyi eredményein javítsanak. Erre az esetre az alábbi feltételek vonatkoznak:
A zárthelyit a pótzárthelyin vagy a pótlási héten írt díjköteles pótláson (avagy pótpótzárthelyin) lehet pótolni. Ezeken korábban megírt, eredményes zárthelyi javítása is megkísérelhető, de csak azzal a feltétellel, hogy ilyenkor mindenképpen az új pontszám lesz érvényes, akkor is, ha az rosszabb, mint az eredeti. Ez alól egy kivétel van: ha a hallgató az aláíráshoz szükséges 40%-os eredményt elérte, de a javítónak szánt zárthelyi új pontszáma 40% alatti, akkor a hallgató az aláírást megkapja, de a zárthelyi eredményét 40%-osként vesszük figyelembe. Figyelem: a fentiekből következően, ha egy hallgató egy zárthelyin legalább 55%-os eredményt ér el, majd egy javítónak szánt új zárthelyin 55% alatti eredményt ér el, akkor a megajánlott jegyét elveszíti. Ha valaki a pót- vagy pótpótzárthelyin megjelenik (és a feladatsort átveszi), azt úgy tekintjük, hogy az illető kísérletet tett a dolgozat megírására (és így rá a fenti feltételek vonatkoznak).

A vizsgán az aktuális félévre érvényes tételsorról minden vizsgázó egy tételt húz. A vizsgán az elégséges osztályzat megszerzéséhez a tanult bizonyításokat nem kell tudni, de ismerni és érteni kell minden tanult fogalmat, tételt és algoritmust. (Az, hogy a vizsgázó az anyagot érti, magában foglalja azt is, hogy szükség esetén a fogalmakat, tételeket, algoritmusokat példán tudja illusztrálni, illetve hogy a legegyszerűbb - az anyagból rögtön következő, összetettebb bizonytást nem igénylő - összefüggéseket átlátja.) Közepes vagy annál jobb jegyre az a vizsgázó számíthat, aki az anyagban rejlő mélyebb összefüggéseket is átlátja, a bizonyításokat (vagy azoknak legalább egy részét) megtanulta és megértette.

A tárgyhoz tartozó (2024. tavaszi félévre vonatkozó) vizsgatételsor letölthető innen. (A 2025. tavaszi félévre vonatkozó tételsor ehhez nagyon hasonló lesz.)

Információk a megajánlott jegy megszerzéséről, a pótzárthelyiről és a díjköteles pótlásról

Megajánlott jegyet szerezni a normál zárthelyi mellett a pótzárthelyin és a díjköteles pótláson is lehet, a zárthelyiről írtakkal azonos feltételekkel (lásd fentebb).

A pótzárthelyire jelentkezni nem kell. A díjköteles pótlásra a Neptunban kell jelentkezni - de csak azoknak, akik a korábbi zárthelyikkel (vagy korábbi félévben) nem szereztek aláírást. Akik az aláírást már megszerezték és csak javító célzattal vagy a megajánlott jegy megszerzése érdekében vesznek részt a díjköteles pótláson, azok számára a Neptunban való jelentkezés nem szükséges (sőt, nem is tanácsos, mert pénzbe kerül). Ha viszont valaki az aláírást kívánja megszerezni a díjköteles pótláson (és emellett esetleg megajánlott jegyet is), az feltétlen jelentkezzen a Neptunban; aki ezt elmulasztja, annak az ezen az alkalmon megszerzett aláírását nem tudjuk beírni a Neptunba. (Így nincs is lehetőségünk arra, hogy a díjköteles pótláson olyan hallgatónak engedélyezzük a részvételt, akinek aláírása még nincs és a Neptunban a jelentkezést elmulasztotta.) Figyelem: Aki a díjköteles pótlásra a Neptunban jelentkezik, figyeljen rá oda, hogy ne keverje össze ezt az alkalmat az ugyanazon a napon és azonos kezdési időponttal kiírt vizsgaalkalommal (amit azoknak kell felvenni, akik a megajánlott jegyüket szeretnék érvényesíteni és ebben a vizsgaidőszakban záróvizsgáznak).

Azoknak, akik a tárgyból megajánlott jegyet szereztek és ezt érvényesíteni kívánják, a Neptunban jelentkezniük kell a későbbiekben kijelölt, külön erre a célra megnyitott vizsgaalkalomra. Azok, akik a 2025. tavaszi félévben záróvizsgáznak és ezért a megajánlott jegyük bejegyzésére hamarabb szükségük van, a későbbiekben kijelölt, speciálisan erre a célra létrehozott vizsgaalkalomra jelentkezzenek; kérjük, hogy erre csak olyanok jelentkezzenek, akik valóban ebben a félévben záróvizsgáznak.

A megajánlott jegyeket mindkét esetben (tehát az ebben a félévben záróvizsgázó hallgatóknak és a többieknek is) azon a napon írjuk be a Neptunba, amikorra ez a két vizsga ki van írva - mégpedig a fentiek szerint pontosan azoknak a hallgatóknak, akik a következő három feltétel mindegyikének megfelelnek:
  1. a megajánlott jegyet (bármelyik zárthelyi alkalmon, illetve a Rendszeroptimalizálás tárgy hallgatóinak esetében a nagy házi feladatok teljesítésével) megszerezték és azt későbbi zárthelyi alkalmon nem veszítették el;
  2. az erre a célra nyitott vizsgaalkalomra a Neptunban jelentkeztek;
  3. egyetlen szóbeli vizsga alkalmával sem fordult elő (ebben a félévben), hogy a vizsga napján szerepeltek a vizsgalapon a jelentkezettek listáján.
Ha valaki jelentkezik a megajánlott jegy beírására kiírt speciális vizsgaalkalmak egyikére és a fenti három feltétel bármelyikének nem felel meg, az "nem jelent meg" bejegyzést kap a Neptunban erre a vizsgaalkalomra. Figyelem: ha valaki teljesítette a megajánlott jegy feltételeit, de a két speciális vizsgaalkalom egyikére sem jelentkezik, annak a megajánlott jegyét beírni nem tudjuk!

Beadandó nagy házi feladat

A nagy házi feladatok a megfelelő, tanult anyagrészek gyakorlati alkalmazását kívánják meg és a terveink szerint nem jelentenek komolyabb terhelést: legföljebb néhány órai munkával teljesíthetők. Mindkét nagy házi feladat esetében csak a félév legvégén (az utolsó egy-két szorgalmi héten) jutnak el az előadások a feladatok megoldását közvetlenül támogató órákig. Ez azonban nem okoz problémát, mert a feladatok beadására ez után még bőven marad idő (a beadási határidőt lásd lentebb). Ennek ellenére, annak sincs akadálya hogy valaki akár korábban is dolgozzon a nagy házi feladatokon, ha önállóan felkészül az ezek megoldásához szükséges ismeretekből. Mindkét nagy házi feladathoz rendelkezésre áll egy segédanyag, ami kidolgozott mintafeladatokat tartalmaz (és az LP+IP anyagrész esetében a feladat megoldásával kapcsolatos elvárásokat is ismerteti és a megoldáshoz tanácsokat ad): A feladatokat a Rendszeroptimalizálás tárgy hallgatói a kari Moodle felületen érhetik el (április 21-étől kezdve folyamatosan). A feladatokban feltett kérdésekre a válaszokat is a Moodle-ben kell megadni, majd a rendszer a feladatok helyes megoldását automatikusan ellenőrzi és a megfelelő feladat elfogadásáról visszajelzést ad. Ha egy megoldás nem tökéletes és így a Moodle nem fogadja el, akkor az tetszőleges számú alkalommal újra beadható. A két nagy házi feladatot nem szükséges egyszerre beadni, különböző időpontokban is lehet rajtuk dolgozni.

A feladatok beadásának a határideje a megajánlott jegy beírásának kívánt napja előtti nap éjfél. (Pontosabban ez nyilván azt jelenti, hogy eddig kell a Moodle által elfogadott, helyes megoldást beadni.) Figyelem: mivel ez a dátum a fentiek szerint az ebben a félévben záróvizsgázóknak eltér a többiekétől, ezért a Moodle-ban beállított beadási határidő (ami a vizsgaidőszak legvége) csak formális, nem a valóságot tükrözi. Természetesen nem tudjuk beírni a megajánlott jegyet, ha a feladatok beadása és elfogadása nem történik meg határidőre.

Zárthelyik

Zárthelyi: április 28.
 18-20
Pótzárthelyi: május 12.
 18-20
Díjköteles pótlás: június 2.
 ???


Kérjük, hogy a zárthelyikkel kapcsolatos technikai információkat alább mindenki gondosan olvassa el. A zárthelyikkel kapcsolatos adminisztratív tudnivalók itt olvashatók.

Figyelem! A zárthelyik és pótzárthelyik technikai lebonyolításával kapcsolatban az alábbiakra hívjuk fel a figyelmet.

Korábbi évek zárthelyi feladatsorai

(Minden év esetében az első zárthelyihez megoldásokat is közlünk, a pótzárthelyik esetében a 2020-nál korábbi féléveknél csak a feladatsorok olvashatók.)
A tárgy anyagának átalakulása miatt a 2018. tavaszi félévnél korábbi zárthelyik 3-as és 4-es feladatainak az anyaga már nem tartozik a tárgy anyagához. Az 1-es, 2-es, 5-ös és 6-os feladatok használhatók a zárthelyire való készüléshez, de ezek között is előfordulnak olyanok, amelyeknek a témája már nincs benne a tárgy anyagában.

Hasznos linkek