Rendszeroptimalizálás
|
Kombinatorikus optimalizálás
|
BMEVISZMA10
|
BMEVISZM029
|
(informatikus MSc
hallgatóknak)
|
(matematikus MSc vagy
alkalmazott matematikus MSc hallgatóknak)
|
Előadó: |
Időpont: |
Helyszín: |
Kaszanitzky Viktória (email:
kaszanitzky_KUKAC_cs.bme.hu) |
Hétfő 8:15 - 10:00 |
E1B |
Csütörtök 8:15 - 10:00 |
E1B |
1. hét |
02.10.h |
Bonyolultságelméleti alapfogalmak |
02.13.cs |
NP-nehéz problémák polinom időben megoldható
spec. esetei: maximális független ponthalmaz, pont-, illetve
élszínezés |
|
2. hét | 02.17.h |
Additív hibával közelítő algoritmusok:
egyszerű gráfok élszínezése, síkgráfok színezése, a
leghosszabb kör nem közelíthető additív hibával |
02.20.cs |
Multiplikatív hibával közelítő algoritmusok,
minimális lefogó ponthalmaz keresése és maximális élszámú
páros részgráf keresése |
|
3. hét | 02.24.h |
Approximációs algoritmus a halmazfedési
feladatra |
02.27.cs |
Steiner-fa |
|
4. hét | 03.03.h |
Az utazóügynök probléma |
03.06.cs |
A metrikus utazóügynök probléma,
Christofides algoritmusa |
|
5. hét | 03.10.h |
Polinomiális és teljesen polinomiális
approximációs sémák |
03.13.cs |
Teljesen polinomiális approximációs séma a
részösszeg problémára |
|
6. hét | 03.17.h |
Az optimális hozzárendelés problémája |
03.20.cs |
Egerváry algoritmusa |
|
7. hét | 03.24.h |
Kétváltozós lineáris programozási feladatok
grafikus megoldása |
03.27.cs |
Farkas-lemma |
|
8. hét | 03.31.h |
A lineáris program célfüggvényének felülről
korlátosságának feltételei |
04.03.cs |
A lineáris programozás dualitástétele |
|
9. hét | 04.07.h |
Egészértékű programozás |
04.10.cs |
Totálisan unimoduláris mátrixok |
|
10. hét | 04.14.h |
A lineáris és egészértékű programozás
alkalmazásai 1. |
04.17.cs |
Tavaszi szünet, nincs
előadás. |
|
04.21.h |
Tavaszi szünet, nincs előadás. | |
04.24.cs |
Tavaszi szünet, nincs előadás. | |
11. hét | 04.28.h |
Konzultáció |
04.28.h 18-20 | ZH (az anyag az ápr. 14-i
előadás anyagát még tartalmazza) |
|
05.01.cs |
Nemzeti ünnep, nincs előadás. | |
12. hét | 05.05.h |
A lineáris és egészértékű programozás alkalmazásai 2. |
05.08.cs |
A lineáris és egészértékű programozás alkalmazásai 3. | |
13. hét | 05.12.h |
Tartalék |
05.12.h 18-20 | PZH |
|
05.15.cs |
Tartalék |
|
14. hét | 05.19.h |
Ütemezési feladatok 1. |
05.22.cs |
Ütemezési feladatok 2. |
|
1. vizsgahét |
06.02.h |
PPZH |
Zárthelyi: | április 28. |
18-20 |
Pótzárthelyi: | május 12. |
18-20 |
Díjköteles pótlás: | június 2. |
??? |