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 4.
9. előadás
Matroidok direkt összege, összefüggősége, grafikus matroid linearitása. Matroid metszet, matroid unió.
18-19, IB 025, II. ZH Megoldások
ZH eredmények
10.hét 2017. április 11.
10. 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. 
2017. április 13.
5. gyakorlat
18-19, IB025, II. pZH Megoldások
ZH eredmények
11.hét 2017. április 18.
11. előadás
2-ö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. Fulkerson algoritmusa minimális költségű feszítő fenyő keresésére.
12.hét 2017. április 25.
12. előadás
2017. április 27.
6. gyakorlat
13.hét 2017. május 2.
13. előadás
 14.hét 2017. május 9.
14. előadás
18-19, IB026, III. ZH (IB027) Megoldások
ZH eredmények
2017. május 11.
7. gyakorlat
pótlási hét
2017. május 17.
10-11, IB026, III. pZH Megoldások
ZH eredmények
1. vizsgahét
2017. május ??.
ppZH
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