| Héger Tamás (email: heger_KUKAC_cs.bme.hu) | Kedd 10.15 - 11.45 |
| Héger Tamás (email: heger_KUKAC_cs.bme.hu) | Csütörtök 08.30 - 10.00 | ||
| Fleiner Tamás (email: fleiner_KUKAC_cs.bme.hu) | Csütörtök 08.30 - 10.00 |
Zárthelyi, pótzárthelyi dolgozatok:
| Április 15. (szerda), 18:00-19:30 | ||
| Április 29. (szerda), 18:00-19:30 | ||
| Május 14. (csütörtök), 18:00-19:30 | ||
| Június 1. (hétfő), 10:00-12:00 | ||
| Június 5. (péntek), 10:00-12:00 |
|
1. hét |
február 17. |
1. előadás: Gráfok kromatikus száma, független csúcshalmazok, alsó és felső korlátok a kromatikus számra, mohó színezés. Páros (kétosztályú) gráfok, jellemzés körökkel. Fleiner Tamás diái (élszínezés az előadáson már nem volt). |
| február 19. | 1. gyakorlat, néhány feladat megoldásával. | |
|
2. hét |
február 24. |
2. előadás: A BME Formula Racing Team bemutatkozása (tagfelvétel március 1-ig). Élkromatikus szám, triviális becslés, Vizing és Shannon tételei (nem biz). Kőnig élszínezési tétele páros gráfokra (nem biz). Maximális párosítások, lefogó ponthalmazok, kapcsolat a megfelelő gráfparaméterek között. Párosítás növelése javító úttal tetszőleges gráfban; ha a párosítás nem maximális, akkor van javító út. Javító utas algoritmus páros gráfok maximális méretű párosításának keresésére. Fleiner Tamás diái: élszínezések (a vége felé), folyamok, párosítások (még csak egy kis részét fedtük le az előadáson). |
| február 26. | 2. gyakorlat, néhány feladat megoldásával. | |
|
3. hét |
március 3. |
3. előadás: Páros gráfok mátrixreprezentációja, maximális párosítás keresése javító úttal a mátrixreprezentációban. Ha már nincs javító út: Hall tétele, Kőnig tétele páros gráfok maximális párosításainak és minimális lefogó ponthalmazainak méretéről. Maximális súlyú párosítások, súlyozott lefogások, kapcsolatuk. Fleiner Tamás diái: folyamok, párosítások (ennek a végén van az előadáson vetített példa a javító utas algoritmus futtatására mátrixreprezentációban), max súlyú párosítások (ennek kb az első fele volt eddig az előadáson). |
| március 5. | 3. gyakorlat, néhány feladat megoldásával. | |
|
4. hét |
március 10. |
4. előadás: Egerváry tétele, a magyar módszer. Hálózati folyamok, vágások, maximális folyam, minimális vágás, optimalitási kritérium, MFMC- (Ford--Fulkerson-) tétel. Folyam növelése javító úttal. Fleiner Tamás diái: magyar módszer (órán kivetített példa a vége felé), folyamok. |
| március 12. | 4. gyakorlat, néhány feladat megoldásával. | |
|
5. hét |
március 17. |
5. előadás: Hálózati folyamok: javítóutas algoritmus, egészértékűségi lemma, néhány általánosabb feladat visszavezetése az alapfeladatra. Lineáris egyenlőtlenségrendszerek, lineáris programozási (LP) feladat. Az LP feladat geometriai interpretálása és megoldása két változó esetén. Lineáris egyenlőtlenségrendszerek megoldása a Fourier--Motzkin-elimináció segísével (egyelőre az eljárás helyességét nem igazoltuk). Fleiner Tamás diái (lineráis egyenlőtlenségek, FM-elimináció). A folyamokhoz kapcsolódó tananyag az előző diasoron szerepel, az előadáson veített példa itt. |
| március 19. | 5. gyakorlat, nehány feladat megoldásával. | |
|
6. hét |
március 24. |
Nincs előadás (dékáni szünet a Simonyi Konferencia miatt). |
| március 26. |
6. előadás (VÁLTOZÁS!) FM elimináció helyessége, megoldhatóság esetén megoldás konstruálása fordított sorrendű értékadással, példa ezen a diasoron (középtájt). Ha az FM-elimináció során tilos sort kapunk, akkor a tilos sor előáll a kibővített együtthatómátrix sorainak nemnegatív együtthatós lineáris kombinációjaként. Lineáris egyenlőtlenségrendszerek mátrixos alakja. Farkas-lemma. Kanonikus alakú lineáris programozási (LP) feladat megoldhatóságának és a célfüggvény korlátosságának vizsgálatára, alternatív egyenlőtlenségrendszerek felírása a Farkas-lemma alapján. Duális LP rendszer felírása, az optimális célfüggvényértékek egybeesése. Fleiner Tamás diái (lineáris programozás, dualitás). |
|
|
7. hét |
március 31. |
6. gyakorlat, nehány feladat megoldásával. |
| április 2. | Nincs gyakorlat (tavaszi szünet) | |
|
8. hét |
április 7. |
Nincs előadás (tavaszi szünet). |
| április 9. | Nincs gyakorlat (tavaszi szünet). | |
|
9. hét |
április 14. |
Nincs előadás EA helyett konzultáció lesz az 1. ZH-ra való minél eredményesebb felkészülés érdekében. |
| április 15. |
Első ZH. Tananyag: az első 6 gyakorlat anyaga. Időpont, helyszín: 18:00-19:30, Q-I (Q épület, I-es (nagy) előadó). Feladatsor, pontozási útmutató (mintamegoldásokkal). |
|
| április 16. | 7. gyakorlat, néhány feladat megoldásával. | |
|
10. hét |
április 21. |
7. előadás Lineáris programozás dualitástétele, sztenderd alakú LP duálisának felírása. Egészértékű programozási (IP) feladat, TU mátrixok, TU mátrixszal és egész jobboldalakkal felírt LP-nek ha van megoldása, illetve optimális megoldása, akkor van egészértékű megoldása, illetve optimális megoldása is. (Irányított) gráfok illeszkedési mátrixa. Fleiner Tamás diái: dualitás, egészértékű programozás. |
| április 22. | 8. gyakorlat, néhány feladat megoldásával. | |
|
11. hét |
április 28. |
8. előadás Irányított gráfok és páros gráfok illeszkedési mátrixa TU. Max súlyú párosítás keresése IP feladatként TU együtthatómátrixszal. Gráfok többszörös összefüggősége: lokálisan (két csúcs viszonylatában )és globálisan (az egész gráfra vonatkozóan) értelmezett k-szoros összefüggőség és élösszefüggőség. Vágások, éldiszjunkt, illetve belsejükben pontdiszjunkt utak, Menger tételei. |
| április 29. | Első pótZH (18:00, E1B). Feladatsor, pontozási útmutató. | |
| április 30. | 9. gyakorlat, néhány feladat megoldásával. | |
|
12. hét |
május 5. |
9. előadás Gráfok él- és pontösszefüggésének meghatározása folyamokkal. Max-vissza sorrend, élösszefüggőség meghatározása a Nagamochi-Ibaraki algoritmussal. Elvágó élek, 2-komponensek. Egy gráf kétszeresen élösszfüggővé tételéhez szükséges behúzandó élek minimális száma. Fleiner Tamás diái. |
| május 7. | 10. gyakorlat, néhány feladat megoldásával. | |
|
13. hét |
május 12. |
10. előadás Egy gráf kétszeresen összefüggővé tételéhez szükséges élek minimális száma. Kétszeresen összefüggő gráfok ekvivalens jellemzései. Fülfelbontás. Kétszeres (él)összefüggőség és fülfelbontás kapcsolata. |
| május 14. | 11. gyakorlat: készülés a 2. ZH-ra (konzultáció), új feladatsor nincs. | |
| május 14. | 2. ZH: 18-20, Q-I. Tananyag a 10. gyakorlatig. Feladatsor, pontozási útmutató (javított változat). | |
|
14. hét |
május 19. |
11. előadás Robbinst tétele egy gráf erősen összefüggővé irányíthatóságáról. Közelító algoritmusok, abszolút és relatív hiba, példák. A halmazfedési feladat, mohó algoritmus. |
| május 21. | 12. gyakorlat: feladatsor. | |
|
15. hét |
május 26. |
Az előadás elmarad. |
| május 28. | A gyakorlat elmarad. | |
|
15. hét |
június 1 (hétfő) |
Második pótzh: feladatsor, pontozási útmutató. |
| június 5 (péntek). | Pót-pót ZH (díjköteles pótlás, Neptunban kell rá regisztrálni). 10:00-12:00, QBF13. |
A félév során kettő darab, 90 perces, négy vagy öt 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 egy-egy alkalommal biztosítunk pótlási lehetőséget. 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.
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 a tényt legalább egy héttel a dolgozatírás előtt e-mailben jelezzék az előadó felé.
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 megajánlott jeggyé az alábbiak szerint, azzal a további megkötéssel, hogy az elégtelennél jobb osztályzathoz mindkét ZH-nak sikeresnek kell lennie. (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 |
jó |
| 85-100 pont |
jeles |
A megajánlott jegyet elfogadni úgy lehet, hogy jelentkezni kell az e célból létrehozott szóbeli vizsgaalkalomra. Mindenki, aki erre a vizsgaalkalomra jelentkezik, automatikusan a megajánlott jegyét kapja.
Aki nem fogadja el a megajánlott jegyét (azaz nem jelentkezik erre a speciális vizsgára), az szóbeli vizsgát tehet, amin legfeljebb egy osztályzatot tud javítani a megajánlott jegyén (rontani viszont korlátlanul tud). A szóbeli vizsgához vizsgatételsor tartozik, ami a félév végére alakul ki, és majd itt érhető el, ebben részletesebb tájékoztató is található a vizsgáról. A szóbeli vizsgán egy tételt sorsolunk a vizsgázónak, melynek kidolgozására 30 percet biztosítunk. A vizsga során ellenőrző kérdések erejéig a többi tételbe is belekérdezhetünk, a ZH által le nem fedett anyagrészből biztosan kap kérdést a vizsgázó.