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

2018/2019. 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)
Hétfő 14.15 - 16.00
IB025
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
Kedd 10.15 - 12.00
IB025

A hétfői és a keddi 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:   

Hétfői előadások:

Keddi előadások:


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 (a 2019. tavaszi félévtől kezdve) 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ás a megszerzését követő hatodik félév vizsgaidőszakjának végéig érvényes. 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. 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ó vizsgatételsor innen lesz letölthető a szorgalmi időszak utolsó hetétől. Addig tájékoztató jelleggel innen letölthető a 2018. tavaszi félévben érvényes vizsgatételsor, de felhívjuk a figyelmet arra, hogy az aktuális félévre vonatkozó tételsor ettől kis mértékben eltérhet.

Információk a megajánlott jegy megszerzéséről, a pótzárthelyiről és az aláíráspótló vizsgáró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.)

Azoknak, akik a tárgyból megajánlott jegyet szereztek és ezt érvényesíteni kívánják, a Neptunban jelentkezniük kell egy erre a célra külön megnyitott vizsgaalkalomra, ami a vizsgaidőszak legvégén lesz. Azok számára, akik a 2019. 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, egy további, speciálisan erre a célra létrehozott vizsgaalkalmat is megnyitunk majd, ami a vizsgaidőszak elején lesz; kérjük, hogy erre csak olyanok jelentkezzenek, akik valóban ebben a félévben záróvizsgáznak. Hogy ez a két vizsgaalkalom pontosan melyik, azt egyrészt a Neptunban is lehet majd látni a vizsgához tartozó "leírás" rovatban, másrészt ez az információ itt, a tárgy honlapján is megjelenik majd. 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!

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 24. (szerda) 18:00 - 20:00
Pótzárthelyi: május 7. (kedd) 18:00 - 20:00
Díjköteles pótlás: május 20. (hétfő)

A zárthelyik terembeosztása, valamint a megtekintés időpontja és helyszíne itt lesz olvasható a megfelelő dolgozat előtt néhány nappal.

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á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: