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

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

Aktuális: Vizsgatételsor (a 2017. tavaszi félévre)

Aláíráspótló eredmények Megtekintés: e-mailben egyeztetett időpontban. 1-2. feladatok: cscsgy kukac cs pont bme pont hu,
3-4. feladatok: recski kukac cs pont bme pont hu, 5-6. feladatok: wiener kukac cs pont bme pont hu.

Zh és pótzh eredmények

zh: feladatok és megoldások

• Előadások, előadók
• A tárgy anyaga
• Segédanyagok
• Tárgykövetelmények
• Zárthelyik
• Vizsga
  
• Korábbi évek zárthelyi feladatsorai
• Hasznos linkek

---

Előadások:

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

Előadók:

Csehi Csongor György	(email: cscsgy_KUKAC_cs.bme.hu)
Recski András	(email: recski_KUKAC_cs.bme.hu)
Wiener Gábor	(email:  wiener_KUKAC_cs.bme.hu)

---

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 műszaki alkalmazásaiba is betekintést nyújtson. 

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 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 kari mérnökinformatikus mesterképzés 2015. tavaszától átalakult, megújult formában indul. Ez a Rendszeroptimalizálás (illetve új, teljes nevén: "Felsőbb matematika informatikusoknak - Rendszeroptimalizálás") tárgyat is érinti. Azonban az anyag változása a korábbiakhoz képest nem jelentős, az 5%-ot nem haladja meg, így a korábbi segédanyagok, zárthelyi dolgozatok a tárgyból való felkészüléshez továbbra is jól használhatók.

Felhívjuk azok figyelmét, akik a tárgyat a 2014. tavaszi, vagy annál korábbi félévben már felvették a kari honlapon olvasható, az MSc tantervek átmenetének szabályozásáról szóló dokumentumra. Ebből többek között kiderül, hogy a BMEVISZM117-es kódú, korábbi tárgyból aláírást szerzett hallgatók az ugyanezen a kódon kiírt vizsgakurzust, míg az aláírással nem rendelkező hallgatók az új, BMEVISZMA02 kódú tárgyat kell, hogy felvegyék.

Mindez a matematikus vagy alkalmazott matematikus MSc képzésre járó hallgatókat nem érinti, ők továbbra is a BMEVISZM029-es kódú, Kombinatorikus optimalizálás című tárgyat vehetik fel.

---

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 ennek a legalább elégséges szintű megírása. A tárgy szóbeli vizsgával zárul.

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.

A tárgyhoz tartozó (az aktuális félévre vonatkozó) vizsgatételsor letölthető innen.
(A fenti linken elérhető tételsor vonatkozik mindazokra, akik a BMEVISZMA02 kódú "Felsőbb matematika informatikusoknak - Rendszeroptimalizálás" című, vagy a BMEVISZM029 kódú "Kombinatorikus optimalizálás" című tárgyat vették fel (reguláris kurzusként).

---

Zárthelyik:

Zárthelyi:	április 11. (kedd)	18.00 - 20.00
Pótzárthelyi:	április 20. (csütörtök)	18.00 - 20.00

A zárthelyi és a pótzárhelyi helyszíne egyaránt a K.F.51-es terem.

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 6 feladatból álló dolgozatot kell megírni (lásd a korábbi évek feladatsorait). Mindegyik feladat 10 pontot ér, az elégséges ponthatára 24 pont (ennyi már elégséges), 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(ok) 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.
• Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen három részre: az 1-es/2-es, a 3-as/4-es és az 5-ös/6-os feladatpárokra. (Így tehát például ne legyen olyan lap, amelynek az egyik oldalán a 2-es, a másikon a 3-as feladat megoldása szerepel.) 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 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.

A tárgyból (a TVSz-nek megfelelően) a pótlási héten lesz aláíráspótló vizsga is (ennek a pontos ideje egyelőre nem ismert).
Az aláíráspótló vizsgára a Neptunban jelentkezni kell! (Aki ezt elmulasztja, annak az ezen az alkalmon megszerzett aláírását nem tudjuk beírni a Neptun rendszerbe. Így nincs lehetőségünk arra, hogy olyan hallgatónak engedélyezzük a részvételt, aki a Neptunban a jelentkezést elmulasztotta.)

---

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

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
• Az előadáson bemutatott példa az Egerváry-algoritmus futására