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.25 - 09.55 | ||
Fleiner Tamás (email: fleiner_KUKAC_cs.bme.hu) | Csütörtök 08.30 - 10.00 |
Zárthelyi, pótzárthelyi dolgozatok:
Április 2. (szerda), 18-20 | ||
Április 16. (szerda), 18-20 | ||
Május 8. (csütörtök), 18-20 | ||
Május 19. (hétfő), 18-20 | ||
Május 26. (hétfő), 10-12 |
1. hét |
február 11. |
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. A BME Formula Racing Team bemutatkozása (tagfelvétel feb. 23-ig). Fleiner Tamás diái (1-7. dia / 1-94. oldal (léptetés)) |
február 13. | 1. gyakorlat, néhány feladat megoldásával. | |
2. hét |
február 18. |
2. előadás: Páros (kétosztályú) gráfok, jellemzés körökkel. Élkromatikus szám, triviális becslés, Vizing és Shannon tételei (nem biz). Kőnig élszínezési tétele. 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 (még nem biz). Fleiner Tamás diái: előző diasor (8-9.dia / 95-119. oldal) |
február 20. | 2. gyakorlat, néhány feladat megoldásával és tippekkel. | |
3. hét |
február 25. |
3. előadás: Párosítások növelése javító úttal, ha egy párosítás nem a legnagyobb, akkor van javító út. Részletesebben páros gráfokban: alternáló és javító utak keresése élek irányításával / mátrixreprezentációban (vetített példa (68-81. oldal (10. dia))); mi következik abból, ha egy páros gráfban már nincs javító út (Kőnig tétele páros gráfok maximális párosításainak és minimális lefogó ponthalmazainak méretéről, deficites Hall-tétel, Hall-tétel), konstruktív bizonyítékok egy párosítás maximalitására. Maximális súlyú párosítások, súlyozott lefogások. Fleiner Tamás diái: párosítások (53. oldaltól), súlyozott párosítások (4. diáig / 20. oldal, de előadáson még nem minden szerepelt). |
február 27. | 3. gyakorlat és néhány feladat megoldása. | |
4. hét |
március 4. |
4. előadás: Egerváry tétele, a magyar módszer (az EA-n vetített példa (26-33. oldal (6. dia))). Hálózati folyamok, vágások, folyam nagysága, vágás kapacitása, kapcsolatuk. Fleiner Tamás diái a magyar módszerről és a folyamokról (1-19. oldal (1-4. dia)). |
március 6. | 4. gyakorlat, és néhány feladat megoldása. | |
5. hét |
március 11. |
5. előadás: Hálózati folyamok: maximális folyam, minimális vágás, folyam növelése és minimális vágás keresése javító utakkal (segédgráfos eljárás), MFMC- (Ford--Fulkerson-) tétel. Egészértékűségi lemma, alkalmazás páros gráfok maximális párosításaira. Néhány általánosabb feladat visszavezetése az alapfeladatra. Fleiner Tamás diái. |
március 13. | 5. gyakorlat, néhány feladat megoldásával. | |
6. hét |
március 18. |
6. előadás: Lineáris egyenlőtlenségrendszerek, Fourier--Motzkin-elimináció. Tilos sor előállítása az eredeti egyenlőtlenségekből. Fleiner Tamás diái: Fourier--Motzkin-elimináció, Farkas-lemma. |
március 20. | 6. gyakorlat, néhány feladat megoldásával. | |
7. hét |
március 25. |
7. előadás Lineáris egyenlőtlenségrendszerek mátrixos alakja. Farkas-lemma. Lineáris programozási (LP) feladat (feltételek, célfüggvény), geometriai interpretáció két ismeretlen esetén, optimális megoldás keresése. Lineáris programozási feladat sztenderd alakja. Lineáris feltételeket kielégítő megoldás létezésének és a célfüggvény korlátosságának vizsgálata, alternatív egyenlőtlenségrendszerek felírása a Farkas-lemma alapján. Duális lineáris program (DLP), kapcsolat a célfüggvények optimális értékei között. Fleiner Tamás diái: lineáris programozás, dualitás. |
március 27. | 7. gyakorlat, néhány feladat megoldásával. | |
8. hét |
április 1. |
EA helyett konzultáció lesz az 1. ZH-ra való minél eredményesebb felkészülés érdekében. |
április 2. |
1. ZH: 18-20, Q-I. Tananyag: az eddigi 7 gyakorlat anyaga. Feladatsor, pontozási útmutató. | |
április 3. | 8. gyakorlat (IP modellek felírása), néhány feladat megoldásával. | |
9. hét |
április 8. |
8. előadás Ha az LP és a DLP is megoldható, akkor az optimális célfüggvényértékek megegyeznek. LP feladatok általánosított sztenderd alakja, azok duálisa. Egészértékű és vegyes programozási feladatok (IP / MIP), LP relaxált, kapcsolat a IP és az LP relaxált megoldáshalmazai között, továbbá az IP és az LP relaxált célfüggvényének optimuma, valamint a duális LP és annak IP megszorításának optimális célfüggvényértékei között. Az LP és az IP feladatok bonyolultsága. Fleiner Tamás diái: dualitás, egészértékű programozás. |
április 10. | 9. gyakorlat, néhány megoldással. | |
10. hét |
április 15. |
9. előadás Gráfok kromatikus száma IP feladatként, gyakorlati implementáció, GLPK és Gurobi szoftvercsomagok működésének bemutatása. TU mátrixok, TU mátrixszal és egész jobboldallal adott LP egész megoldásai. Műveletek TU mátrixokkal, melyek megőrzik a TU tulajdonságot. Irányított gráfok, páros gráfok illeszkedési mátrixa TU. Fleiner Tamás diái: egészértékű programozás. |
április 16. |
1. PótZH: 18-20, Q-I. Tananyag: ugyanaz, mint az 1. ZH anyaga. Feladatsor és pontozási útmutató. | |
április 17. | Nincs gyakorlat (tavaszi szünet). | |
11. hét |
április 22. |
Nincs előadás (tavaszi szünet). |
április 24. | Nincs gyakorlat (tavaszi szünet).. | |
12. hét |
április 29. |
10. előadás Hálózatok megbízhatósága: többszörös élösszefüggőség és összefüggőség lokálisan / globálisan (két csúcs viszonylatában / a gráf egészén) értelmezve. Menger tétele. Gráfok élösszefüggőségi, összefüggőségi száma. Lokális élösszefüggőség meghatározása folyamokkal. Maxvissza sorrend, gráf (globális) élösszefüggőségének meghatározása (Nagamochi-Ibaraki-algoritmus). Fleiner Tamás diái: többszörös összefüggőség. |
május 1. | Nincs gyakorlat (állami szünet). Gyakorló feladatsor: gyakorló feladatsor, néhány megoldással. | |
13. hét |
május 6. |
11. előadás Az előző két előadás témájához kapcsolódó gyakorló feladatok megoldásának prezentálása (a közelgő ZH-ra való tekintettel). |
május 8. | 10. gyakorlat: konzultáció (készülés a 2. ZH-ra), új feladatsor nincs. | |
május 8. |
2. ZH: 18-20, E1B |
|
14. hét |
május 13. |
12. előadás Elvágó élek, 2-komponensek, izolált, levél és belső komponensek, a 2-komponensek és elvágó élek erdője. Elvágó pontok, blokkok, maxblokkok, izolált és levél blokkok, a T_2(G) gráf. Gráfok kétszeresen (él)összefüggővé tételéhez szükséges minimális élek száma. Kétszeresen (él)összefüggő gráfok szerkezete, fülfelbontásuk. Egy gráf pontosan akkor kétszeresen (él)összefüggő, ha van megfelelő fülfelbontása. Fleiner Tamás diái: többszörös összefüggőség, fülfelbontás |
május 15. | 11. gyakorlat: feladatsor, néhány megoldással. | |
15. hét |
május 19. |
2. PZH: 18-20, Q-II. Tananyag: a 2. ZH tananyaga |
május 20. |
13. előadás Approximációs algoritmusok: abszolút (additív) és relatív (multiplikatív) hiba, példák közelíthetőségre és közelíthetetlenségre (ha P/=NP). Halmazfedési feladat nehézsége, (1+log(n))-es közelítés. Ütemezési feladatok, optimalizálandó célfüggvények, átfutási idő minimalizálása egy gépre (triviális), SPT sorrend optimalitása az átlagos befejezési időre egy gépen. Fleiner Tamás diái: approximációs algoritmusok, ütemezési feladatok. |
|
május 22. | 12. gyakorlat. | |
16., póthét |
május 26. |
PPZH: 10-12, QBF10. Mindenkinek egyetlen, a rosszabbul sikerült ZH pótlására van lehetősége. A számonkérhető tananyag ugyanaz, mint a megfelelő eredeti ZH-ban. |
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 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ó.