VISZMA06 2017 tavasz

Felsőbb matematika villamosmérnököknek - Kombinatorikus optimalizálás


Előadó  Fleiner Tamás (fleiner@cs.bme.hu)

Előadás  kedd    10:15-12:00:  IE220

Gyakorlatok

Kurzuskód
Időpont
Gyakorlatvezető
Terem
11
páros hét csütörtök 14:15-15:45 Fleiner Tamás
IE220


Féléves ütemterv

1.hét
2017. február 7.
1. előadás
Minimális súlyú párosítások, Egerváry magyar módszere.  Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. (helyettesítés)
2.hét 2017. február 14. 2. előadás
Fourier-Motzkin elimináció, Farkas lemma.
2017. február 16. 1. gyakorlat 
3.hét 2017. február 21. 3. előadás
Farkas lemma ekvivalens alakja, LP primál- és duálfeladat, dualitástétel.
4.hét 2017. február 28. 4. előadás
IP feladat, duálisa, optimális megodlás viszonya az LP-hez. IP feladat bonyolultsága, Maximális súlyú párosítás LP alakja és duálisa. LP feladat optimális megoldás szabad paraméterekkel és nxn-es egyenletrendszerrel. TU mátrix definíciója.
2017. március 2. 2. gyakorlat 
5.hét 2017. március 7. 5. előadás
TU mátrixokkal adott ILP optimuma. Irányított gráf incidenciamátrixának TU tulajdonsága. Hálózati folyamok LP alakja, duálisa, pontenciálok. Ford-Fulkerson tétel levezetése a dualitástételből.
2017. március 8. 16-17 IE220 Konzultáció
2017. március 9. 18-20, IB025, I. ZH Megoldások
ZH eredmények
6.hét 2017. március 14. 6. előadás
Intervallumok egyenletes színezése TU mátrixszal adott egyenlőtlenségrendszer megoldhatóságából. Matroidok, mohó algoritmus, függetlenségi axiomák.
2017. március 16. 3. gyakorlat
18-20, tanszék, I. pZH  ZH eredmények
7.hét 2017. március 21. 7. előadás
Körök, bázisok, rangfüggvény. Grafikus és lineáris matroid. Bázis-, rang- és köraxomák,
8.hét 2017. március 28. 8. előadás
Matroidkonstrukciók (törlés, összehúzás), duális matroid, grafikus matroid duálisa, törlés, összehúzás duális művelete, duális rangfüggvény.
2017. március 30. 4. gyakorlat
9.hét 2017. április 3.
12-13:30 IB026 konzultáció
2017. április 4.
9. előadás
Matroidok (direkt) összege, Matroid metszet, matroid unió. Nash-Williams tétele gráf élhalmazának k erdő uniójára történő felbontásáról, Tutte tétele k éldiszjunkt feszítőfa létezéséről.
18-19, IB 025, II. ZH Megoldások
ZH eredmények
10.hét 2017. április 11.
10. előadás
Edmonds matroid metszet algoritmusa, összegmatroid rangfüggvényének levezetése a matroid metszet tételből.
2017. április 13.
5. gyakorlat
18-19, IB025, II. pZH  ZH eredmények
11.hét 2017. április 18.
11. előadás
Gráfok magasabb összefüggősége, annak meghatározása folyamalgoritmussal. Blokkok és 2-komponensek. A maxvissza sorrenden alapuló Nagamochi-Ibaraki algoritmus minimális vágás meghatározására. 
12.hét 2017. április 25.
12. előadás
Fulkerson algoritmusa minimális költségű feszítő fenyő keresésére, gráf 2-(él)összefüggővé tétele minimális számú él behúzásával, 2-összefüggő gráfok fülfelbontása.
2017. április 27.
6. gyakorlat
13.hét 2017. május 2.
13. előadás
2-élösszefüggő gráfok fülfelbontása, Robbins tétele erősen összefüggő irányítás létezéséről, 2k-élösszefüggő gráfok előállítási tétele, gráf vágásfüggvényének szubmoduláris tulajdonsága, Lovász leemelési tétele, Nash-Williams tétele k-élösszefüggő irányítás létezéséről.
 14.hét 2017. május 9.
7. gyakorlat (konzultáció)
18-19, IB026, III. ZH (IB027) Megoldások
ZH eredmények
2017. május 11.
14. előadás, ZH megbeszélés
pótlási hét
2017. május 17.
10-11, QBF12, III. pZH  Megoldások  ZH eredmények Betekintés: május 18. 10h IB 137/B
1. vizsgahét
2017. május 22.
10-12, Tanszék (IB134), aláíráspótlás
ZH eredmények




Jegyzet
Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004.
A jegyzet amellett, hogy az előadáson tárgyalt anyagnál jóval bővebb, elektronikus formában is beszerezhető.



Értékelés, tárgykövetelmények, vizsga

A tantárgyi adatlap tartalmazza a tárgyról szóló tudnivalókat, többek között a követelményeket.

Zárthelyik, pótzárthelyik, aláírás:

A félév során három zárthelyi lesz. Ezek közül két zárthelyi három, egy pedig négy 10 pontos feladatból áll, időtartamuk 60 ill. 80 perc a feladatok számától függően. Az félévközi jegy feltétele, hogy mindhárom zárthelyi sikeres legyen (azaz az elérhető 40 pont 40%-át, konkrétan legalább 12 ill. 16 pontot érjen), és legalább egy zárthelyinek már az első számonkéréskor (tehát nem a pótlási alkalmak valamelyikén) sikeresnek kell lennie. Minden zárthelyihez biztosítunk pótlási lehetőséget. Ezen alkalmakkor az adott témakörben meg nem írt zárthelyi pótolható ill. a már megírt zárthelyi javítható. A pZH-t a ZH-val azonos anyagrészből íratjuk, és szándékunk szerint a ZH-val azonos nehézségű. A pZH-n  elért eredmény felülírja az adott számonkérés korábbi eredményét, kivéve egy sikeresen megírt ZH sikertelen javításának esetét: ilyenkor az adott ZH pontszáma a sikeres számonkérés minimális pontszáma, azaz 12 vagy 16 lesz.

Akinek a fenti pótlások után pontosan egy zh-ja nem sikeres, az a ppZH alkalmával megírhatja a hiányzó számonkérést, és annak az eredménye végleges lesz. Erre a neptunban kell jelentkezni, aholis aláíráspótló vizsga néven fut ez a számonkérés. Figyelem! Aki a neptunbeli jelentkezést elmulasztja vagy lekési, az nem vehet rész ezen a számonkérésen, így jegyet sem szerezhet, hiszen az ekkor megszerzett eredményt nem tudjuk a neptunban adminisztrálni. Az ppZH-n való részvételért a neptun utólag különeljárási díjat számláz ki. (A szorgalmi időszakban tartott pótzárthelyire nem szükséges jelentkezni a neptunban, azon mindenki a saját döntése szerint részt vehet.)

A ppZH időpontja (körülbelül a szorgalmi időszak közepétől) a neptunból deríthető ki. Az itt írt dolgozatokat még aznap kijavítjuk és biztosítjuk abba a betekintést. (Ennek a pontos időpontját a dolgozatírás közben hirdetjük ki.) A dolgozatok eredményei (legkésőbb a következő napon) a tárgy honlapjára is felkerülnek. Aki a megtekintésen nem tud megjelenni, az a dolgozatát kérésre később is megnézheti, de ekkor már a dolgozat pontozásán nem tudunk változtatni.

A kijavított zárthelyi és pótzárthelyi dolgozatokba betekintést biztosítunk.

A számonkérések megírásakor az alábbi szabályok betartását követeljük meg.

Kérjük, hogy mindazon hallgatók, akikre a dolgozatíráskor speciális szabályokat kell alkalmazni, ezt legalább egy héttel a dolgozatírás előtt jelezzék az előadónak.

Az egyes zárthelyikre osztályzatot nem adunk, hanem a legalább egy számonkérésen megjelenő hallgatók összpontszámát konvertáljuk félévközi jeggyé az alábbiak szerint. (Aki egyetlen ZH-t sem ír meg, az "nem teljesítette" bejegyzést kap erre a kurzusra.)

0-39 pont
elégtelen
40-54 pont
elégséges
55-69 pont
közepes
70-84 pont

85-100 pont
jeles