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

2017/2018. második félév

• Előadások, előadók
• A tárgy anyaga
• Információk a tárgy átalakulásáról
• Segédanyagok
• Tárgykövetelmények
• Zárthelyik
• Vizsga
  
• Korábbi évek zárthelyi feladatsorai
• Hasznos linkek
• Fontos információk a BMEVISZM029 kódú, "Kombinatorikus optimalizálás" című tárgy hallgatóinak
  
• Új! Fontos információk a pót- és pótpótzárthelyiről és a megajánlott jegyről
• Új! Vizsgatételsor a szóbeli vizsgára informatikus és matematikus hallgatóknak
• Új! A május 28-i pótpótzárthelyi eredményei Megtekintés: május 31., csütörtök, 12:00, IB136/a
  

---

Előadások:

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

Előadók:

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

---

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

• 1. előadás (2018. február 5.) (A 4. feladat javítva február 6-án)
• 2. előadás (2018. február 6.), Az előadáson bemutatott példa a javító utas algoritmus futására, Az előadáson bemutatott példa az Egerváry-algoritmus futására
• 3. előadás (2018. február 12.), Az előadáson bemutatott diák a Vasorr Kft. feladatának megoldására
• 4. előadás (2018. február 13.)
• 5. előadás (2018. február 19.)
• 6. előadás (2018. február 20.)
• 7. előadás (2018. február 26.)
• 8. előadás (2018. február 27.)
• 9. előadás (2018. március 5.)
• 10. előadás (2018. március 6.)
• 11. előadás (2018. március 12.)
• 12. előadás (2018. március 13.)
• 13. előadás (2018. március 19.)

---

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.

---

Információk a tárgy átalakulásáról:

A Rendszeroptimalizálás (avagy teljes nevén: "Felsőbb matematika informatikusoknak - Rendszeroptimalizálás") tárgy a 2018. tavaszi félévtől jelentősen átalakul. Ez érinti a tárgy anyagát (amely a korábbinál szűkebb) és követelményrendszerét is. A tárgyból korábban szerzett aláírás (a TVSz által biztosított 6 féléven keresztül) természetesen továbbra is érvényes, azonban a tárgykövetelmények (alább részletezett) megváltozása miatt azoknak is érdemes megfontolnia, hogy újból megírják a zárthelyit, akiknek van érvényes aláírása.

Ez az átalakulás nem érinti a matematikus hallgatók BMEVISZM029 kódú, "Kombinatorikus optimalizálás" című tárgyát. Az ezt a tárgyat felvettekre vonatkozó speciális tudnivalók itt olvashatók.

---

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 2010. szeptembere óta 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 részt tartalmazó elektronikus jegyzet letölthető innen.

---

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

• Ha sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor a vizsgajegybe (lásd lentebb) az így kapott eredmény számít bele (akkor is, ha ez rosszabb).

• Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be.

• Ha egy érvényes aláírással rendelkező hallgató az aktuális félévben legalább egy zárthelyin megjelenik, azt úgy tekintjük, hogy az illető kísérletet tett az aláírás feltételeinek újbóli teljesítésére (és rá a fenti feltételek vonatkoznak). Ellenkező esetben a legutolsó olyan félévbeli teljesítményt vesszük figyelembe, amikor a hallgató megkísérelte az aláírás feltételeinek teljesítését.

• Ha egy hallgató egy korábbi félévben legalább 55%-os eredményű zárthelyit írt, de (legalább elégséges) vizsgajegyet mégsem szerzett (mert szóbelire jelentkezett, de azon sikertelen volt vagy nem jelent meg), akkor a megajánlott jegy megszerzését újra megkísérelheti a zárthelyi újbóli megírásával. Ennek hiányában az aláírása természetesen érvényes marad, de a vizsgajegy megszerzéséhez szóbeli vizsgát kell tennie.

A zárthelyit a szorgalmi időszakban írt pótzárthelyin vagy a pótlási héten írt aláíráspótló vizsgán 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: ha azonban 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 (fentiek szerinti) 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 letölthető innen. Figyelem! A 9. tételt június 4-én javítottuk.

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 (május 22-i) pótzárthelyin és a (május 28-i) aláíráspótló vizsgán is lehet, a zárthelyiről írtakkal azonos feltételekkel (lásd fentebb).

A (május 22-i) pótzárthelyire jelentkezni nem kell. A (május 28-i) aláíráspótlóra 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 az aláíráspótló vizsgán, 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 megszerzni az aláíráspótlón (é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 olyan hallgatónak engedélyezzük a részvételt, akinek aláírása még nincs és a Neptunban a jelentkezést elmulasztotta.)

Fontos! Azoknak, akik a tárgyból megajánlott jegyet szereztek és ezt érvényesíteni kívánják, a Neptunban jelentkezniük kell az erre a célra külön megnyitott vizsgaalkalomra: ez június 25-én 8:00-tól 8:05-ig van kiírva és a leírásában szerepel, hogy a megajánlott jegy megszerzésére szolgál. Figyelem: ugyanazon a napon 9:00-től 14:00-ig reguláris szóbeli vizsga is van, fontos tehát, hogy a kettőt nem szabad összekeverni! A megajánlott jegyet június 25-én fogjuk a Neptunba beírni - tehát a fentiek szerint azoknak (az informatikus hallgatóknak), akik a következő három feltétel mindegyikének megfelelnek:

• a megajánlott jegyet (bármelyik zárthelyi alkalmon) megszerezték és azt későbbi zárthelyi alkalmon nem veszítették el;
• az erre a célra nyitott (tehát június 25-én, 8:00-tól 8:05-ig tartó) vizsgaalkalomra a Neptunban jelentkeztek;
• egyetlen szóbeli vizsga alkalmával sem fordult elő (beleértve a június 25-i, "valódi" szóbelit is), 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 (tehát június 25-én, 8:00-tól 8:05-ig tartó) vizsgaalkalomra é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 speciális (tehát június 25-én, 8:00-tól 8:05-ig tartó) vizsgaalkalomra mégsem jelentkezik, annak a megajánlott jegyét beírni nem tudjuk!

---

Információk a "Kombinatorikus optimalizálás" című tárgy hallgatóinak

A (BMEVISZM029 kódú, matematikus hallgatóknak szóló) tárgyhoz tartozó vizsgatételsor letölthető innen. Figyelem! A 16. tételt június 4-én javítottuk.

Figyelem! A szóbeli vizsgára nem kell minden tételt megtanulni. Az anyag négy elméleti részből (lineáris programozás, matroidelmélet, közelítő algoritmusok, ütemezési algoritmusok) és három műszaki esettanulmányból (megbízható hálózatok tervezése, hálózatelméleti alkalmazások, statikai alkalmazások) áll.  A vizsgán mind a négy elméleti anyagrészt tudni kell, de a három műszaki esettanulmányból elég egy szabadon választottat megtanulni. A vizsgán mindenki egy tételt fog húzni, ami vagy az elméleti részhez tartozik, vagy az általa (a tétel kihúzása előtt) megjelölt esettanulmány anyagához. (Arra azonban számítani kell, hogy a vizsgáztató néhány fogalom vagy tétel erejéig az elméleti anyagrészbe is bele fog kérdezni akkor is, ha a kihúzott tétel nem ahhoz tartozik.) 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.

Az anyag és a követelmények átalakulásával kapcsolatban fentebb írtak a BMEVISZM029 kódú, "Kombinatorikus optimalizálás" című tárgyra nem vonatkoznak. Ezért ennek a tárgynak a hallgatóságára a következő, speciális információk érvényesek:

• A Kombinatorikus optimalizálás tárgy anyagának továbbra is része a matroidelmélet, ami a Rendszeroptimalizálás tárgy anyagában 2018. tavaszától kezdve már nem szerepel, így az előadásokon erről a témáról nem lesz szó. Ennek az anyagrésznek az elsajátításához (nem kötelező) konzultációkat biztosítunk, ezeket Recski András tartja. Természetesen önállóan is fel lehet készülni ebből az anyagrészből (például a tárgyhoz tartozó jegyzet segítségével). A konzultációk a következő hétfőkön, 16.15-től 18.00-ig lesznek az IE216.1-es teremben: február 19., március 5., március 19., április 9., április 23., május 7. vagy május 14. Figyelem: amennyiben valamelyik felsorolt napon 16.30-ig egyetlen hallgató sem jelenik meg, akkor az aznapi konzultáció elmarad.
• A Kombinatorikus optimalizálás tárgykövetelményei annyiban térnek el a fentiektől, hogy vizsgajegyet nem lehet megajánlott jegyként szerezni, csak szóbeli vizsgával.
• A zárthelyi közös lesz a két tárgy hallgatósága számára, így abban csak az előadásokon szereplő anyaghoz tartozó feladatok lesznek. A szóbeli vizsga tételsorában viszont szerepelni fog a matroidelmélet is (így a vizsgatételsor már különböző lesz a két tárgy esetében).

Ezek a speciális feltételek csak a 2018. tavaszi félévre vonatkoznak és a tárgy átalakulásából fakadó ideiglenes helyzetet tükröznek.

---

Zárthelyik:

Zárthelyi:	május 8. (kedd)	18.00 - 20.00
Pótzárthelyi:	május 22. (kedd)	10.00 - 12.00

A május 22-i pótzárthelyi helyszíne az IB028-as terem. (A pótzárthelyire jelentkezni nem kell.)
A május 22-i pótzárthelyi eredményei

A május 8-i zárthelyi feladatai és a feladatok megoldásai
A május 8-i zárthelyi eredményei

A dolgozatok eredménye (legkésőbb) május 14-én, hétfőn reggel kerül fel a honlapra. A dolgozatok megtekintésére május 14-én 12.15-től lesz lehetőség az IB136/a teremben. A feladatok megoldása már a dolgozat utáni napon felkerül a honlapra.

Fontos! A zárthelyik és pótzárthelyik technikai lebonyolításával kapcsolatban az alábbiakra hívjuk fel a figyelmet.

• A zárthelyiken semmilyen segédeszköz nem használható.
• Mindegyik zárthelyi alkalmon egy 5 feladatból álló dolgozatot kell megírni. Mindegyik feladat 12 pontot ér, az aláíráshoz szükséges minimális pontszám 24. A munkaidő 90 perc.
• Kérjük, hogy a zárthelyik írásakor mindenki megfelelő mennyiségű üres lappal érkezzen. Minden lapra fell kell írni (jól olvashatóan, lehetőleg a jobb felső sarokban) a dolgozatíró nevét és Neptun kódját, valamint az azon a lapon megoldott feladat sorszámát. Ezeket az adatokat szabad (sőt érdemes) már a zárthelyi megkezdése előtt felírni (vagy akár rányomtatni) a lapokra, de ettől eltekintve minden lapnak üresnek kell lenni.
• Kérjük, hogy minden feladat külön lapra kerüljön. A zárthelyi beadásakor kérjük szépen a lapokat a feladatok sorszáma szerint növekvőleg sorbarendezni, majd a zárthelyit hosszában kettéhajtani oly módon, hogy a név és a Neptun-kód kívül olvasható legyen. Kérjük, hogy a dolgozatot senki ne tűzze össze.
• Kérjük, hogy a dolgozat írása közben a (feladatlaptól különböző) papírjait mindenki egy stószban tartsa maga előtt, az éppen nem használt papírokat tegye alulra.
  
• Kérjük, hogy a zárthelyi írásának megkezdése előtt mindenki a teremben felügyelő oktatók által kihirdetett, illetve a táblára felírt ültetési rend pontos figyelembevételével foglaljon helyet. Ennek a figyelmen kívül hagyása, vagy nem pontos betartása előidézhet olyan helyzetet, amikor két, azonos dolgozatot író hallgató egymáshoz túl közel kerül; ha ez az ültetési rend figyelmen kívül hagyásából fakad, akkor az azt megsértő hallgató dolgozata automatikusan érvénytelen.
• Kérjük, hogy a zárthelyi írásakor a teremben mindenki úgy foglaljon helyet, hogy van nála írószerszám, a dolgozat írásához használandó üres lapok és valamilyen, azonosításra alkalmas fényképes igazolvány. Ezen kívül mindenkinél lehet enni- és innivaló, de semmi más. Minden egyéb személyes holmit (így a táskákat, kabátokat, mappákat, írott vagy nyomtatott jegyzeteket, elektronikus eszközöket, stb.) a terem szélén, a fogasokon, vagy (különösen jelentősebb értékű tárgyak esetén) a tanári asztalon vagy amellett kell elhelyezni. Nyomatékosan kérjük tehát, hogy mind a dolgozatot írók közti üres székek, mind pedig az üresen maradt padsorokban található ülések maradjanak tökéletesen szabadok a dolgozat írásának teljes ideje alatt. (Ha az épületben van őrzött ruhatár, érdemes ott elhelyezni a dolgozat írásához nem szükséges személyes tárgyakat.)
• A dolgozat írása közben szigorúan tilos bármilyen (akár szóbeli, akár írásbeli) kommunikáció a dolgozatot író hallgatók között. Bármilyen problémát vagy igényt (legyen szó akár a legegyszerűbbekről, mint például egy tollra vagy zsebkendőre vonatkozó kérésről) a teremben felügyelő oktatóknak kell jelezni. Ennek a megsértése a kommunikáció tartalmától függetlenül az azt kezdeményező hallgató dolgozatának az érvénytelenségét vonhatja maga után.
• A zárthelyi írása közben senkinél nem lehet sem bekapcsolt mobiltelefon (még elnémítva sem), sem bármely más elektronikus eszköz; kérjük, aki ezt igényli, gondoskodjon karóráról a dolgozat írásának idejére.
• A dolgozat írásának megkezdése után az első 30 percben a termet elhagyni nem lehet, ennek az időnek a letelte után pedig a késve érkező hallgatók már nem kezdhetik el a zárthelyi írását.
• Amint a teremben felügyelő oktatók bejelentik a munkaidő leteltét, a továbbiakban semmit nem szabad írni a dolgozatra. (Ez alatt tehát az értendő, hogy akár az éppen írt szót vagy mondatot is félbe kell hagyni.) Ha valaki ezt megszegi, azt kockáztatja, hogy a dolgozata minden további mérlegelés nélkül érvénytelen lesz. 
• Kérjük, hogy a munkaidő letelte után mindenki a lehető leghamarabb juttassa el a dolgozatát a teremben felügyelő valamelyik oktatóhoz - mégpedig az oktatók által kért beadási rend maximális betartásával. Ha a dolgozatát valaki nem közvetlenül egy felügyelő oktató kezébe adja, akkor a szemével kövesse nyomon a dolgozat útját valamelyik oktatóig. A késve érkező dolgozatok automatikusan érvénytelenek - függetlenül attól, hogy a késedelem közvetlenül a dolgozatot író hallgató hibájából származik-e vagy sem.

---

Korábbi évek zárthelyi feladatsorai:

A tárgy anyagának átalakulása miatt a 2018. tavaszi félévtől a korábbi zárthelyik 1-es, 2-es, 5-ös és 6-os feladati használhatók a zárthelyire való készüléshez. 

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

2017. tavaszi félév: zárthelyi, pótzárthelyi
2016. tavaszi félév: zárthelyi, pótzárthelyi
2015. tavaszi félév: zárthelyi, pótzárthelyi
2014. tavaszi félév: zárthelyi, pótzárthelyi
2013. tavaszi félév: zárthelyi, pótzárthelyi
2012. tavaszi félév: zárthelyi, pótzárthelyi
2011. tavaszi félév: zárthelyi, pótzárthelyi
2010. tavaszi félév: zárthelyi, pótzárthelyi
2009. őszi félév: zárthelyi, pótzárthelyi
2009. tavaszi félév: zárthelyi, pótzárthelyi
2008. őszi félév: zárthelyi, pótzárthelyi
2007. őszi félév: zárthelyi, pótzárthelyi
2006. őszi félév: zárthelyi, pótzárthelyi
2005. őszi félév: zárthelyi, pótzárthelyi
2004. őszi félév: zárthelyi, pótzárthelyi
2003. őszi félév: zárthelyi, pótzárthelyi
2002. őszi félév: zárthelyi, pótzárthelyi

---

Hasznos linkek:

• Egy ingyenesen letölthető lineáris és egészértékű program megoldó szoftver: LpSolve