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

2020/2021. első félév (vizsgakurzus)


Figyelem! A 2020. őszi félévben a vizsgák a tavaszi félévivel azonos módon és azonos feltételekkel zajlanak (beleértve a vizsgatételsort is). A honlapon alább olvasható információk tehát az őszi félévben is érvényesek. A távoktatásban lebonyolított vizsgákra vonatkozó információkat alább piros betűs szedéssel, a távoktatás miatt érvénytelenné vált információkat áthúzással jelöltük.

Előadások:

Hétfő 14.15 - 16.00
IB025
Kedd 10.15 - 12.00
IB025

Előadók:

Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)

Az előadásokat március 17-ig Szeszlér Dávid tartja, valamint a március 24-i és az április 21-i órát is. Március 23-tól kezdve (a március 24-i és április 21-i kivételével) Wiener Gábor tartja az előadásokat.

A két előadó által tartott órák anyagai egymástól függetlenek lesznek, egymásra nem épülnek. A zárthelyi és a vizsga anyagában természetesen mindkét előadó által 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:   


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, ütemezési algoritmusok és megbízható hálózatok tervezése.

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.


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.


Tárgykövetelmények

A tárgykövetelmények mind a Rendszeroptimalizálás (BMEVISZMA02), mind a Kombinatorikus optimalizálás (BMEVISZM029) tárgyra egyformán vonatkoznak.

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 tárgyból vizsgajegyet kétféleképpen lehet szerezni: a zárthelyi eredménye alapján megajánlott jegyként 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: 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. Aki a zárthelyivel nem szerzett (legalább elégséges) vizsgajegyet vagy a zárthelyi eredménye alapján megajánlott jegyén javítani szeretne, az a vizsgaidőszakban szóbeli vizsgát tehet. Ha egy hallgató jelentkezik a Neptunban a vizsgára (pontosabban: a vizsga napján a jelentkezettek listáján van), akkor a zárthelyi eredménye alapján megajánlott jegyét 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 szorgalmi időszakban írt pótzárthelyin vagy a pótlási héten írt díjköteles pótláson 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 a vizsgán 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.

A vizsgán az aktuális félévre érvényes tételsorról minden vizsgázó egy tételt húz kap. (A vizsgatételeket az oktatók fogják meghatározni véletlen szám generátorral.) 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 szóbeli vizsgákat a távoktatásra vonatkozó speciális szabályokra tekintettel a Teams rendszeren keresztül fogjuk lebonyolítani úgy, hogy a vizsgázókat az oktatók a jelentkezés sorrendjében megkeresik. A szóbeli vizsgák közben élő kép- és hangkapcsolatra van szükség, ezért kérjük, hogy ennek a feltételeiről minden vizsgázó előre gondoskodjon. A vizsgák elején külön felkészülési idő nem lesz, de ennek megfelelően természetesen minden vizsgázónak garantáljuk a vizsga közben a szükséges gondolkodási időt. A szóbeli részeként a vizsgázók természetesen írhatnak, szükség esetén rajzolhatnak is. Ennek a formája lehet egyszerűen az, hogy a vizsgázó papírra ír és ezt a kamerának felmutatja, de akár az is, hogy a vizsgázó megosztja a képernyőjét és egy általa választott eszközt (pl. szövegszerkesztő) használ.

A tárgyhoz tartozó vizsgatételsor letölthető innen.

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

Ebben a félévben a díjköteles pótlás ingyenes, azon a zárthelyivel és a pótzárthelyivel azonos feltételekkel lehet részt venni. A Neptunban való jelentkezés azonban a fentiek szerint továbbra is szükséges a díjköteles pótláson való részvételhez - legalábbis azoknak, akik a díjköteles pótlás nélkül még nem szereztek a tárgyból aláírást.

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 29-én, 8.00-tól 8.05-ig tartó, külön erre a célra megnyitott vizsgaalkalomra. Azok számára, akik a 2020. 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 2-á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: 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 2-án tehát valódi szóbeli vizsga nincs, június 29-én viszont a megajánlott jegyek érvényesítésére létrehozott vizsgaalkalmon kívül szóbeli vizsgát is tartunk, így ebben az esetben különösen fontos odafigyelni, hogy a kettő ne keveredjen össze.

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) 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ő, 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!


Zárthelyik:

Zárthelyi: április 29. (szerda) 18:00 - 20:00
Pótzárthelyi: május 12. (kedd) 18:00 - 20:00
Díjköteles pótlás: május 25. (hétfő) 8:00 - 10:00

A május 25-i pótpótzárthelyi eredményei (feladatonkénti bontásban) a kari Moodle rendszerben nézhetők meg.

A kijavított feladatok innen tölthetők le (Neptun-kód és a zárthelyi előtt emailben küldött egyedi jelszó segítségével) május 29-e éjfélig.

A pótpótzárthelyin résztvevők kis létszámára tekintettel a megtekintésre külön időpontot nem jelölünk ki. Akinek kérdése van a dolgozat pontozásával kapcsolatban, az keresse meg a tárgy előadóit: az első három feladat esetében Szeszlér Dávidot emailen, az utolsó kettő esetében pedig Wiener Gábort a Teams chaten.

Az április 29-i zárthelyi feladatsora és pontozási útmutatója
A május 12-i zárthelyi feladatsora és pontozási útmutatója
A május 25-i pótpótzárthelyi feladatsora és pontozási útmutatója

Korábbi évek zárthelyi feladatsorai:

(Minden év esetében az első zárthelyihez megoldásokat is közlünk, a pótzárthelyi esetében 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: