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

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

Előadások, előadók

Előadó:
 Időpont:
 Helyszín:
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
 Szerda 10.15 - 12.00
 IB028
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
 Csütörtök 8.15 - 10.00
 IB028 IB027

Figyelem! Április 11-étől kezdve a csütörtöki előadások az IB027-es teremben lesznek! (A szerdai előadások maradnak az IB028-ban.)

A szerdai és a csütörtöki előadások anyagai egymástól függetlenek lesznek, egymásra nem épülnek, mindig az előző heti, azonos napon tartott előadás anyagát folytatják. A zárthelyi és a vizsga anyagában természetesen mindkét napon tartott előadások anyaga benne lesz.

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

Feladatsorok, előadáson használt anyagok   

Szerdai előadások:

Csütörtöki előadások:

Jegyzet a csütörtöki előadások anyagához

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.

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): szerdai előadások anyaga (Szeszlér Dávid), csütörtöki előadások anyaga (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ó (és az aktuális, 2024. tavaszi félévre vonatkozó) vizsgatételsor letölthető innen. (Ez tartalmilag azonos a tavalyi, 2023. tavaszi félévre vonatkozó tételsorral.)

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 június 28-án, 8.00-tól 8.05-ig tartó, külön erre a célra megnyitott vizsgaalkalomra. Azok, akik a 2024. 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 június 3-án, 8.00-tól 8.05-ig tartó, 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. Figyelem: Június 3-án (8.00-tól 10.00-ig) van a díjköteles pótlás időpontja is, ezért a Neptunban kiírt két alkalmat, illetve a rájuk való jelentkezést nem szabad összekeverni.

Figyelem: A fentiek miatt kérjük, hogy a vizsgára jelentkezés során mindenki különös körültekintéssel járjon el és pontosan arra az alkalomra jelentkezzen, amire szüksége van! Június 3-án és 28-án tehát valódi szóbeli vizsgákat nem tartunk.

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 29. (hétfő) 18.00 - 20.00
Pótzárthelyi: május 23. (csütörtök) 18.00 - 20.00
Díjköteles pótlás: június 3. (hétfő) 8.00 - 10.00

Az április 29-i zárthelyi feladatai és pontozási útmutatója
A május 23-i pótzárthelyi feladatai és pontozási útmutatója
A június 3-i pótpótzárthelyi feladatai és pontozási útmutatója

A június 3-i pótpótzárthelyik eredménye június 6-án, csütörtökön, (várhatóan) 14.00-kor kerül be a kari Moodle rendszerbe. A dolgozatok megtekintésére ugyanezen a napon (tehát 6-án, csütörtökön), 14.15-től lesz lehetőség a SzIT tanszéken (IB 136/a szoba). A megtekintés végén a dolgozatok eredményei véglegesednek, azokon később már nem változtatunk (de ettől függetlenül a dolgozatokat meg tudjuk mutatni későbbi, külön egyeztetett időpontban is). A megtekintésen természetesen nem kötelező megjelenni: aki a dolgozat után a honlapon közzétett pontozási útmutató alapján úgy érzi, hogy az esetleges hibáit ismeri és a dolgozatának a pontozását reálisnak találja, annak a számára a megjelenés fölösleges.

Az zárthelyi és a pótzárthelyik anyaga az április 25-i előadással bezárólag tart (a szerdai és a csütörtöki előadások anyagából is).

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