Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
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.
Mérnökinformatikus szak, MSc képzés
Felsőbb matematika
Név:
Beosztás:
Tanszék, Int.:
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
Dr. Wiener Gábor
lineáris algebra, gráfelmélet és algoritmuselmélet alapjai
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ó.
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.
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.
Heti 4 óra előadás
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
Előzetes egyeztetés szerint.
Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004, 2011.
Számítástudományi Információelméleti Tanszék