Felsőbb matematika informatikusoknak - Rendszeroptimalizálás

A tantárgy angol neve: Advanced Mathematics for Informatics - System Optimisation

Adatlap utolsó módosítása: 2019. december 10.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Mérnökinformatikus szak, MSc képzés

Felsőbb matematika

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZMA02 1 4/0/0/v 4  
3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid,
A tantárgy tanszéki weboldala http://cs.bme.hu/rendszeropt
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Csehi Csongor Györgyegyetemi tanársegéd
 Számítástudományi és Információelméleti Tanszék

Dr. Recski András

egyetemi tanár

Számítástudományi és Információelméleti Tanszék

Dr. Szeszlér Dávid

egyetemi docens

Számítástudományi és Információelméleti Tanszék

Dr. Wiener Gábor

egyetemi docens

Számítástudományi  és Információelméleti Tanszék

5. A tantárgy az alábbi témakörök ismeretére épít

lineáris algebra, gráfelmélet és algoritmuselmélet alapjai

6. Előtanulmányi rend
Kötelező:
NEM ( TárgyEredmény( "BMEVISZM117" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZM117", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZMA10" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA10", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

7. A tantárgy célkitűzése

A tantárgy az operációkutatás és a kombinatorikus optimalizálás néhány területére nyújt bevezetést. A téma legfontosabb algoritmusainak, módszereinek és azok korlátainak ismertetése mellett célul tűzi ki, hogy ezek gyakorlati életbeli alkalmazási lehetőségeit is bemutassa. A tantárgy által érintett főbb 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.

8. A tantárgy részletes tematikája

1)      Lineáris és egészértékű programozás: A páros gráfban maximális méretű párosítás keresésére szolgálú javító utas algoritmus ismétlése. Egerváry algoritmusa maximális összsúlyú párosítás és teljes párosítás keresésére páros gráfban.

2)      Lineáris és egészértékű programozás: A lineáris programozás alapfeladata, a megoldhatóság és korlátosság kérdései. Kétváltozós lineáris programozási feladatok grafikus megoldása. A lineáris programozás bonyolultsága. Gyakorlati életben felmerülő problémák formalizálása lineáris programozási feladatként.

3)      Lineáris és egészértékű programozás: Az egészértékű programozás alapfeladata, annak bonyolultsága. Korlátozás és szétválasztás (Branch and Bound) módszer egészértékű programok megoldására. Gyakorlati életben felmerülő problémák formalizálása egészértékű programozási feladatokként.

4)      Lineáris és egészértékű programozás: A lineáris programozás alapfeladatának mátrixos alakja. Szükséges és elégséges feltételek lineáris egyenletrendszerek nemnegatív változókkal való, illetve lineáris egyenlőtlenségrendszerek megoldhatóságára: a Farkas-lemma.

5)      Lineáris és egészértékű programozás: Szükséges és elégséges feltételek a lineáris program célfüggvényének korlátosságára. A lineáris programozás dualitástétele.

6)      Lineáris és egészértékű programozás: Hálózati folyamfeladatok formalizálása lineáris programozási feladatként: a maximális folyam, a minimális költségű folyam, illetve a többtermékes folyamprobléma.

7)      Lineáris és egészértékű programozás: Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazások páros gráfok párosításaival, hálózati folyamokkal és intervallumrendszerek színezésével kapcsolatos problémákra.

8)      Közelítő algoritmusok: NP-nehéz problémák kezelése. NP-nehéz problémák polinomiális időben megoldható speciális esetei: erőforrások ütemezése, maximális független ponthalmaz keresése, élszínezés.

9)      Közelítő algoritmusok: Additív hibával közelítő algoritmus fogalma. Additív hibával közelítő algoritmusok színezési problémákra, a leghosszabb kör keresésének feladata. Multiplikatív hibával közelítő algoritmus fogalma, a maximális páros részgráf probléma.

10)  Közelítő algoritmusok: A minimális lefogó ponthalmaz probléma. A súlyozott halmazfedési feladat: NP-nehézsége, approximációs algoritmus.

11)  Közelítő algoritmusok: Steiner-fák: approximációs algoritmus a metrikus és az általános esetre. Az utazóügynök probléma, 2-approximációs algoritmus az utazóügynök probléma metrikus esetére.

12)  Közelítő algoritmusok: Christofides algoritmusa az utazóügynök probléma metrikus esetére. Teljesen polinomiális approximációs séma fogalma, a részösszeg probléma.

13)  Ütemezési algoritmusok: Ütemezési feladatok típusai. Egygépes ütemezések, listás ütemező algoritmus párhuzamos gépek esetén. Listás ütemezés LPT, illetve leghosszabb út szerinti sorrendben megelőzési feltételekkel és azok nélkül, Hu algoritmusa.

14)  Megbízható hálózatok tervezése: Lokális élösszefüggőség és élösszefüggőségi szám fogalma és meghatározása algoritmikusan. Nagamochi és Ibaraki algoritmusa. Minimális méretű 2-élösszefüggő, illetve 2-összefüggő részgráfok keresése: Khuller-Vishkin és Cheriyan-Thurimella algoritmus. Gráfok 2-élösszefüggővé növelése: Plesnik algoritmusa.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

Heti 4 óra előadás

10. Követelmények A félév folyamán egyetlen zárthelyit íratunk. A félévvégi aláírás megszerzésének feltétele a zárthelyin legalább 40%-os teljesítmény elérése. A zárthelyin elért, ennél jobb eredménnyel a tárgy vizsgajegye is megszerezhető: legalább 55%-os eredményért elégséges, legalább 70%-os eredményért közepes, legalább 85%-os eredményért pedig jó vizsgajegyet ajánlunk meg.

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.

A vizsgaidőszakban:

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, akkor a zárthelyi eredménye alapján megajánlott jegyét a továbbiakban nem tekintjük érvényesnek. Ilyenkor a vizsgajegyben a zárthelyi eredményét 40%-os súllyal vesszük figyelembe.

Elővizsga: nincs

11. Pótlási lehetőségek 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ét vesszük figyelembe. 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.

12. Konzultációs lehetőségek

Előzetes egyeztetés szerint.


13. Jegyzet, tankönyv, felhasználható irodalom

Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004, 2011.

 


14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra56
Félévközi készülés órákra12
Felkészülés zárthelyire12
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés40
Összesen120
15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Dr. Szeszlér Dávid

egyetemi docens

Számítástudományi  Információelméleti Tanszék