Előadó Fleiner Tamás (fleiner@cs.bme.hu)
Előadás kedd 10:30-12:00 IB025 (Márc 21: STFKis)
Gyakorlatok
Kurzuskód |
Időpont |
Gyakorlatvezető |
Terem |
11 |
csütörtök 8:25-9:55 | Fleiner Tamás |
R505 |
12 |
csütörtök 8:25-9:55 | Héger Tamás | R504 |
1.hét |
február
28. |
1.
előadás Gráfok kromatikus száma, alsó és felső korlátok, mohó színezés. Páros gráfok, élkromatikus szám, Kőnig tétele páros gráfok élszínezéséről. |
március 2. | 1. gyakorlat | |
2.hét | március 7. |
2. előadás Hálózati folyamok, javító utas algoritmus, Ford-Fulkerson-tétel, EgÉr-lemma, páros gráfok maximális párosításai. Az alternáló utas algoritmus futtatása a páros gráf mátrixreprezentációján. |
március 9. |
2. gyakorlat | |
3.hét | március 14. | 3.
előadás Maximális súlyú párosítások, Egerváry magyar módszere. |
március 16. | 3. gyakorlat | |
4.hét | március
21. |
4.
előadás
Helyszín: STFKis Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma. |
máricus 23. | 4. gyakorlat | |
5.hét | március 28. | 5.
előadás Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel. |
március 30. | 5. gyakorlat | |
6.hét | április
4. |
6.
előadás IP feladat, duálisa, optimális megoldás viszonya az LP-hez. TU mátrix definíciója, TU tulajdonságot megőrző operációk. TU mátrixokkal adott IP optimuma. Irányított gráf incidenciamátrixának TU tulajdonsága. Maximális súlyú párosítás LP alakja, ennek duálisa és közgazdaságtani interpretációja, piaci egyensúly. LP és IP feladat megoldásának bonyolultsága, hálózati folyamok LP alakja, duálisa, pontenciálok. Ford-Fulkerson tétel levezetése a dualitástételből. Idén elmarad: intervallummátrix TU tulajdonsága, intervallumrendszer egyenletes színezése. Az I. ZH anyaga eddig tart. |
április 6. | Tavaszi szünet, nincs
gyakorlat |
|
7.hét | április 11. | Tavaszi szünet, nincs
előadás |
április 13. | 6. gyakorlat | |
8.hét | április 18. |
7. előadás ZH előtti konzultáció Néhány eddigi gyakorlat megoldása |
április 19. | 18-20, IB025, I. ZH megoldások |
|
április 20. | 7. gyakorlat ZH megbeszélés |
|
9.hét | április 25. |
8.
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. Gráf 2-(él)összefüggővé tétele minimális számú új él hozzáadásával. |
április 27. | 8. gyakorlat | |
10.hét | május 2. |
9.
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. |
május 3. |
18-20, IB025, I. pZH | |
május 4. |
9. gyakorlat | |
11.hét | május 9. |
10.
előadás Közelítő algoritmusok. Élkromatikus szám, síkgráf kromatikus szám közelítése additív hibával. 2-közelítés a lefogó ponthalmaz méretére, logaritmikus közelítés a halmazfedési problémára. Ütemezési problémák. Alapfogalmak, jelölésrendszer, hasznos módszerek: SPT sorrend és listás ütemezés. FF és FFD heurisztikák a ládapakolási problémára. |
május
11. |
10. gyakorlat | |
12.hét | május 16. |
11. előadás Megoldásvázlatok ZH előtti konzultáció |
május
18. |
ZH előtti konzultáció | |
május 18. | 18-20, IB025, II.
ZH megoldások |
|
13.hét | május
23. |
12.
előadás 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. |
május 25. |
11. gyakorlat | |
14.hét | május 30. |
13.
előadás |
június 1. |
||
pótlási hét | június 5. |
8-10, II. pZH IB134
|
Értékelés,
tárgykövetelmények,
vizsga
Zárthelyik, pótzárthelyik, aláírás:
A félév során két 90 perces, négy feladatból álló zárthelyi lesz,
mindegyiken 50 pont szerezhető. A legalább elégséges félévközi
jegy feltétele, hogy mindkét zárthelyi sikeres legyen (azaz az
elérhető 50 pont 40%-át, konkrétan legalább 20 pontot érjen).
Mindkét zárthelyi esetében biztosítjuk pótlás lehetőségét.
Ilyenkor 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 ha egy sikeresen megírt
ZH javítása 20 pontnál kevesebbet ér: ekkor az adott ZH végső
pontszáma a sikeres számonkérés minimális pontszáma, azaz 20
lesz.
A
kijavított zárthelyi és pótzárthelyi dolgozatokba betekintést
biztosítunk.
0-39 pont |
elégtelen |
40-54 pont |
elégséges |
55-69 pont |
közepes |
70-84 pont |
jó |
85-100 pont |
jeles |