Előadó Fleiner Tamás (fleiner@cs.bme.hu)
Előadás kedd 10:15-12:00 Teams
Gyakorlatok
| Kurzuskód |
Időpont |
Gyakorlatvezető |
Terem |
| 11 |
minden második hét péntek 8:30-10:00 | Fleiner Tamás |
Teams |
| konzultáció |
minden "első" hét péntek 8:30-10:00 | Fleiner Tamás | Teams |
| 1.hét |
2021 .
február 9. |
1. előadás Alapozás, ismétlés: hálózati folyamok, javító utas algoritmus, |
| 2.hét | 2021 . február 16. |
2. előadás Maximális súlyú párosítások, Egerváry magyar módszere. |
| 2021 . február 19. | 1. gyakorlat | |
| 3.hét | 2021 . február 23. | 3. előadás Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma. |
| 4.hét | 2021 .
március 2. |
4. előadás Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel. |
| 2021 . máricus 5. | 2. gyakorlat | |
| 5.hét | 2021 . március 9. | 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. |
| 6.hét | 2021 . március 16. | 6.
előadás 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 |
| 2021 . március 19. | 3.
gyakorlat |
|
| 7.hét | 2021 . március 23. |
7. előadás (konzultáció) |
| 2021 . március 23. |
18-20, I. ZH Megoldások |
|
| 8.hét | 2021 . március 30. |
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. |
| Tavaszi
szünet |
||
| 9.hét | 2021 . április 13. |
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. |
| 2021 . április 16. | 4.
gyakorlat |
|
| 10.hét | 2021 .
április 20. |
10.
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. |
| 11.hét | 2021 . április 27. |
11. 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. |
| 2021 . április 30. | 5. gyakorlat | |
| 12.hét | 2021 .
május 4. |
12.
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. |
| 2021 . május 7. |
6. (előrehozott) gyakorlat | |
| 13.hét | 2021 .
május 11. |
13. előadás Konzultáció |
| 2021 . május 13. |
18-20, II. ZH Megoldások | |
| pótlási hét |
2021 . május 20. |
8-10, pZH Megoldások |
| 1. vizsgahét | 2021 . május 26. |
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.
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é.
| 0-39 pont |
elégtelen |
| 40-54 pont |
elégséges |
| 55-69 pont |
közepes |
| 70-84 pont |
jó |
| 85-100 pont |
jeles |