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:

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:   

 


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 és ütemezéselmélet részeket 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:

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:

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:


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.


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: