Előadó Fleiner Tamás (fleiner@cs.bme.hu)
Előadás kedd 10:15-12:00 QBF08
Gyakorlatok
Kurzuskód |
Időpont |
Gyakorlatvezető |
Terem |
11 |
minden második hét péntek 8:30-10:00 | Fleiner Tamás |
QBF08 |
konzultáció |
minden "első" hét péntek 8:30-10:00 | Fleiner Tamás | IB134 |
1.hét |
február
15. |
1.
előadás Alapozás, ismétlés: hálózati folyamok, javító utas algoritmus, EgÉr lemma, páros gráf párosításai, alternáló utas algoritmus |
2.hét | február 22. |
2. előadás Maximális súlyú párosítások, Egerváry magyar módszere. |
február 25. | 1. gyakorlat | |
3.hét | március 1. | 3.
előadás Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma. |
4.hét | március
8. |
4.
előadás Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel. |
máricus 11. | 2. gyakorlat | |
5.hét | március 15. | Nemzeti ünnep: az előadás
elmarad |
6.hét | március 22. | 5.
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. |
március 25. | 3. gyakorlat (konzultáció) megoldások | |
7.hét | március 28. | 18-20, IE007, I. ZH Megoldások |
március 29. |
6.
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. |
|
8.hét | április 5. |
7.
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. |
április 8. | 4. gyakorlat és a hozzá tartozó megoldásvázlatok | |
9.hét | április 12. |
8.
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. |
10.hét | április
19. |
Tavaszi szünet: az előadás elmarad |
április 22. |
5. gyakorlat és a hozzá tartozó megoldásvázlatok | |
11.hét | április 26. |
9.
előadás Közelítő algoritmusok. Élkromatikus szám, síkgráf kromatikus szám közelítése additív hibával, leghosszabb kör additív hibával való közelíthetetlensége. 2-közelítés a lefogó ponthalmaz méretére, logaritmikus közelítés a halmazfedési problémára. |
12.hét | május 3. |
10.
előadás Ütemezési problémák. Alapfogalmak, jelölésrendszer, hasznos módszerek: SPT sorrend és listás ütemezés. FD és FFD heurisztikák a ládapakolási problémára. |
május 6. |
6. gyakorlat és a hozzá tartozó megoldásvázlatok | |
13.hét | május
10. |
11. előadás |
14.hét | május 17. |
12. előadás Konzultáció |
május 19. |
18-20, IE007, II. ZH Megoldások | |
május 20. | 7. gyakorlat | |
pótlási hét | május 26. |
8-10, QBF10, pZH
Megoldások
(a fenti, neptunban is szereplő időpont a helyes) |
1. vizsgahét | június 1. |
14-16, IB134,aláíráspótlás |
É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 zárthelyi lesz,
mindegyik öt, egyenként 10 pontos feladatból áll. 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 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 20 lesz.
A
kijavított zárthelyi és pótzárthelyi dolgozatokba betekintést
biztosítunk.
Akinek a fenti, alanyi jogon jár 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 (pl úgy, hogy lekési), az
nem vehet rész ezen a számonkérésen, így jegyet sem szerezhet,
ugyanis az ekkor megszerzett eredményt nem tudnánk 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 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.) 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.
0-39 pont |
elégtelen |
40-54 pont |
elégséges |
55-69 pont |
közepes |
70-84 pont |
jó |
85-100 pont |
jeles |