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

2020/2021. második félév

Információk a zárthelyik és a vizsgák lebonyolításával kapcsolatban:
A jelenlegi információink szerint ebben a félévben mind a zárthelyik, mind a vizsgák távolléti formában zajlanak. Ennek ellenére, a tárgykövetelményekkel kapcsolatos legalapvetőbb információk nem változnak: nem változik sem a zárthelyik időpontja, sem azok jellege, sem a megajánlott jegyre, illetve a vizsgára vonatkozó információk, az ezekkel kapcsolatban a honlapon alább írtak változatlanul érvényesek. A számonkérések távolléti formában való lebonyolításával kapcsolatos speciális tudnivalók alább olvashatók.
Zárthelyik:
A zárthelyiket a kari Moodle rendszerben bonyolítjuk le, innen lesznek letölthetők a feladatsorok és ide kell feltölteni a dolgozatokat is.

A zárthelyik írásának ideje alatt a két előadó elérhető lesz Teams-en. (A nagy létszámra tekintettel kérünk mindenkit, hogy ezt a lehetőséget valóban csak akkor vegye igénybe, ha erre feltétlen szükség van.) Amennyiben a dolgozat írása közben bármilyen, mindenki figyelmére számot tartó (akár szakmai, akár technikai tárgyú) közlendőnk lenne, azt a tárgy Teams csoportjában tesszük közzé. Így az előadók közvetlen megkeresése előtt érdemes megnézni ezt a csoportot, hogy a felteendő kérdésre vagy jelzendő problémára nem érkezett-e már válasz.

A zárthelyik anyagába beletartozik minden, ami április 23-áig az előadásokon elhangzott. A pót- és pótpótzárthelyi anyaga megegyezik a normál zárthelyi anyagával. A készüléshez felhasználhatók az elmúlt évek zárthelyi feladatsorai, illetve természetesen a félév során az órák második felében elhangzott feladatmegoldások.

A zárthelyiken a munkaidő 90 perc, ezen felül 20 percet biztosítunk a dolgozatokból készülő pdf-ek előállítására (lásd alább) és a dolgozatok feltöltésére. Így a dolgozatok feltöltésének határideje 110 perccel a kezdési időpont után lesz.

Figyelem! Késve (például emailben vagy Teams-en) érkező dolgozatokat nem fogadunk el, semmilyen technikai vagy egyéb jellegű indoklással sem; kérjük szépen ezért, hogy ilyet senki ne is küldjön. Aki a 110 perces határidő leteltéig nem tölti fel a dolgozatát a Moodle-ba, azt úgy tekintjük, hogy az illető nem vett részt a számonkérésen. Kérjük, hogy senki ne hagyja a feltöltést az utolsó percekre, hanem a 90 perces munkaidő leteltével valóban fejezze be a munkát és ezután már csak a pdf generálásával és a feltöltéssel foglalkozzon. Meggyőződésünk, hogy erre 20 perc bőségesen elég, ezért azt várjuk, hogy a dolgozatok kezdési időpontja után 100 perccel a résztvevők többsége már feltölti a dolgozatát és az utolsó 10 percet már csak azok használják ki, akiknek (minden gondos felkészülés ellenére is) valamilyen technikai problémája akad (így elkerülhető lesz a 110 perces határidő letelte előtt a Moodle esetleges túlterhelése is).

A dolgozatok formátumára vonatkozó technikai követelmények:

A megoldásokat lehet kézzel, papírra írni, vagy tetszőleges szövegszerkesztővel, számítógépen is. Érdemes lehet ezt a két megoldást kombinálni is: a folyó szöveget lehet géppel írni és az ábrákról (vagy egyéb, szövegszerkesztővel körülményesebben előállítható részekről, például képletekről) készült fényképeket ebbe importálni.

Bárhogyan is készüljenek azonban a megoldások, azokból egyetlen pdf állományt kell előállítani és ezt beadni. (Nem fogadunk el tehát és nem értékelünk jpg, doc, docx, txt vagy egyéb, pdf-től különböző formátumban beküldött megoldásokat, ezeket a Moodle nem is engedi feltölteni.)

Kérjük, hogy a pdf-ekben a megoldások a feladatok sorszáma szerinti növekvő sorrendben legyenek és minden oldalon maradjon elegendő üres hely a javítók megjegyzéseinek. A pdf első oldalán pedig legyen jól olvashatóan feltüntetve a hallgató neve és Neptun kódja.

A szövegszerkesztőkből természetesen könnyen megoldható a pdf formátumú exportálás. Kézzel írt megoldás esetén szkennerrel lehet a legjobb minőséget elérni. Emellett okostelefonnal is elérhető több szkennelő alkalmazás, például: CamScanner, TurboScan, Smart Doc Scanner. Alternatív, bár általában rosszabb minőséget eredményező megoldás lehet a fényképezés: számos internetes oldal érhető el, ami több fotóból egyetlen PDF állományt készít (például jpg2.pdf.com, smallpdf.com, ilovepdf.com). A jobb olvashatóság érdekében a szkennelésre (esetleg fényképezésre) szánt lapok esetében javasolt egyrészt üres (tehát nem vonalas vagy kockás) papírok használata, valamint a lapok csak egyik oldalának használata.

A pdf-ek generálása kapcsán felmerülő nehézségek elkerülése érdekében kérünk mindenkit, hogy már a dolgozat megírása előtt döntse el, hogy milyen megoldást fog választani és ezt tesztelje is. Eközben ellenőrizze, hogy jól olvasható megoldásokat tud előállítani (így például a betűméret, az irány és a kontraszt megfelelő).

Eredmények, kijavított dolgozatok, megtekintés:

A megoldások és pontozási útmutatók a dolgozatok beadási határideje után legkésőbb egy órával a honlapról lesznek letölthetők.

A kijavított dolgozatok, illetve az eredmények (feladatonkénti bontásban) a Moodle-ból lesznek elérhetők. A javítás mindhárom zárthelyi esetben várhatóan legföljebb egy hétig tart majd, erről pontos információt a tárgy Teams csoportjában teszünk majd közzé.

Akinek a pontszámával, kijavított dolgozatával kapcsolatos kérdése van, az ezt egy, a tárgy Teams csoportjában előre meghirdetett időpontban felteheti a két előadónak a Teams rendszeren keresztül folytatott élő beszélgetés során. Aki ezt a lehetőséget igénybe kívánja venni, annak előre kell regisztrálnia egy, szintén a Teams csoportban közzétett formban. A regisztrált hallgatókat a megtekintés meghirdetett idejében az előadók fogják megkeresni a Teams rendszerben, mégpedig a jelentkezés sorrendjében haladva. Miközben a dolgozattal kapcsolatos konzultáció, a kérdezés joga természetesen minden hallgatót megillet, kérjük, hogy a távolléti zárthelyi speciális körülményeire tekintettel ezzel a lehetőséggel csak az éljen, aki a pontozási útmutató alapos elolvasása után (beleértve annak a pontozással kapcsolatos általános alapelvekre vonatkozó részét is) valóban úgy érzi, hogy a dolgozatának a javítása során hiba történt.

Megengedett segédeszközök, etikai elvek:

A zárthelyi dolgozatok során használható bármilyen írott segédanyag (beleértve a számítógépen vagy más eszközön megnyitható dokumentumokat, így például a tárgyhonlapon közzétett anyagokat is). A megoldásokban azonban továbbra is csak az előadás anyagában szereplő tételekre, állításokra lehet bizonyítás nélkül hivatkozni.

A feladatok megoldása során a hallgatók egymással, illetve külső személlyel semmilyen formában nem kommunikálhatnak.

Ezeknek a szabályoknak a betartásával és a tisztességes munkával kapcsolatban mindenkinek a figyelmét felhívjuk a Hallgatói Képviselet által megfogalmazott irányelvekre.

Az elmúlt két félév távoktatásának a tapasztalatai alapján sajnos elmondhatjuk, hogy a zárthelyiken a csalás, a tisztességtelen viselkedés tömegesen előforduló jelenséggé vált. Mi azonban úgy gondoljuk, hogy a félév során a lehetőségek határain belül mindent megtettünk és megteszünk azért, hogy a tárgyból a számonkéréseket mindenki csalás nélkül is eredményesen teljesíthesse. Ezért elkötelezettek vagyunk abban, hogy a tisztességesen dolgozó hallgatóink érdekeit megvédjük a csalókkal szemben: mindent megteszünk, hogy egyetlen hallgatónknak se kelljen úgy éreznie, hogy hátrányba került csak azért, mert a korrekt munkát választotta. Eközben persze tisztában vagyunk azzal, hogy a csalásokat teljesen kiszűrni lehetetlen - és azzal is, hogy ezt a csalni szándékozók is tudják; ez az egyik oka annak, amiért az ilyen viselkedést mélységesen elítéljük és erkölcstelennek tartjuk. Őszintén bízunk benne, hogy a tárgy hallgatóinak a többsége osztja ezt a véleményünket.
Vizsgák:
A szóbeli vizsgákat (azok számára, akik a megajánlott jegyükön javítani kívánnak, vagy nem szereztek ilyet) a Teams rendszeren keresztül fogjuk lebonyolítani úgy, hogy a vizsgázókat az oktatók a jelentkezés sorrendjében megkeresik. A vizsgatételt (azoknak a kihúzása helyett) az oktatók határozzák meg (véletlen szám generátorral).

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, enélkül a vizsga nem lebonyolítható. 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 í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 megosztja a képernyőjét és egy általa választott eszközt (pl. szövegszerkesztő) használ.

A vizsgával és a megajánlott jeggyel kapcsolatos egyéb információk alább, a tárgykövetelmények között olvashatók.

Előadások, előadók:

Előadó:
 Időpont:
 Helyszín:
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
 Kedd 10.15 - 12.00
 MS Teams
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
 Péntek 12.15 - 14.00
 MS Teams

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.

A távoktatásban az előadások első felét előre rögzítjük és a felvételt közzétesszük az MS Stream-en, a tárgy Teams csoportjában pedig posztoljuk a linket. Az anyaggal kapcsolatos kérdéseket ugyanitt várjuk. Az előadások második felében egy Teams vagy Zoom meeting keretében önálló feladatmegoldás zajlik, a linket szintén a tárgy Teams csoportjában tesszük közzé. A feladatok megoldása közben a megfelelő előadóval is lehet konzultálni, a kitűzött feladatok egy részét pedig az óra végén megbeszéljük. A feladatsorok a tárgy honlapján elérhetők.

Feladatsorok, előadáson használt anyagok:   

Keddi előadások:

Pénteki előadások:

Jegyzet a pénteki 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, ü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.

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

Tárgykövetelmények

Figyelem! Az alábbi információk jelenléti oktatás és számonkérések esetére érvényesek, lásd fentebb.

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. 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). (Távoktatás esetén a feladatsor átvétele a Moodle-ben a dolgozatra való jelentkezésnek felel meg.)

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, 2021. tavaszi félévre vonatkozó) 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.)

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 17-én, 8.00-tól 8.05-ig tartó, külön erre a célra megnyitott vizsgaalkalomra. Azok, akik a 2021. 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 május 25-é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! Május 25-én és június 17-én tehát valódi szóbeli vizsgákat nem tartunk. Külön figyelmet érdemel viszont, hogy május 25-én lesz a pótpótZH is (a Neptunban Díjköteles pótlás néven), így fontos, hogy ezt senki ne keverje össze a fenti, speciális vizsgaalkalommal.

Figyelem: Azok, akik a megajánlott jegyüket a május 25-i pótpótZH-n tervezik megszerezni és ebben a félévben záróvizsgáznak, mindkét május 25-i alkalmat vegyélk fel!

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 28. (szerda) 18.00 - 20.00
Pótzárthelyi: május 11. (kedd) 18.00 - 20.00
Díjköteles pótlás: május 25. (kedd) 8.00 - 10.00

A 2021. április 28-i zárthelyi feladatai és pontozása
A 2021. május 11-i pótzárthelyi feladatai és pontozása

A zárthelyik terembeosztása (jelenléti lebonyolítás esetén) itt lesz olvasható az egyes dolgozatok előtt pár nappal. A zárthelyik eredményeit a kari Moodle rendszerben tesszük közzé.

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.

A zárthelyi (és a pótzárthelyik) anyaga az első 11 oktatási héten az előadásokon elhangzott anyag (beleértve a keddi és a pénteki előadásokat is). Így az utolsó, zárthelyibe tartozó anyagrész az április 23-i, pénteki előadáson hangzik el.

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 - a 2020. tavaszi félév kivételével - 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: