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 lineáris program célfüggvényének felülről korlátosságának feltételei

04.03.cs
 A lineáris programozás dualitástétele
9. hét 04.07.h
 Egészértékű programozás

04.10.cs
 Totálisan unimoduláris mátrixok
10. hét 04.14.h
 A lineáris és egészértékű programozás alkalmazásai 1.

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)

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

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

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