VISZMA06 2020 tavasz

Felsőbb matematika villamosmérnököknek - Kombinatorikus optimalizálás


Előadó  Fleiner Tamás (fleiner@cs.bme.hu)

Előadás  kedd    10:15-12:00:  IE007

Gyakorlatok

Kurzuskód
Időpont
Gyakorlatvezető
Terem
11,12
minden második hét péntek 8:30-10:00 Fleiner Tamás
IE007
konzultáció
minden "első" hét péntek 8:30-10:00 Fleiner Tamás IE007


Féléves ütemterv

1.hét
2020. február 11.
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 2020. február 18. 2. előadás
Maximális súlyú párosítások, Egerváry magyar módszere. 
2019. február 21. 1. gyakorlat 
3.hét 2020. február 25. 3. előadás
Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma.
4.hét 2020. március 3.
4. előadás
Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel.
2020. máricus 6. 2. gyakorlat 
5.hét 2020. március 10. 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 2020. március 17. 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.
2020. március 20. 3. gyakorlat
7.hét 2020. március 24. 7. előadás
Ford-Fulkerson tétel levezetése, intervallummátrix TU tulajdonsága, intervallumrendszer egyenletes színezése
2020. március 24.
18-20, I. ZH Megoldások
Terembeosztás (vezetéknév kezdőbetűje szerint):




8.hét 2020. március 31. 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. 
2020. április 3. 4. gyakorlat
9.hét 2020. április 7.
9. előadás
Gráf 2-(él)összefüggővé tétele minimális számú új él hozzáadásával, 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.
Tavaszi szünet
10.hét 2020. április 21.
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.
2020. április 24.
5. gyakorlat
11.hét 2020. április 28.
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.
12.hét 2020. május 5.
12. előadás
Ütemezési problémák, közelítő algoritmusok
2020. május 8.
6. gyakorlat
13.hét 2020. május 12.
13. előadás
Konzultáció
2020. május 14.
18-20, II. ZH Megoldások
Terembeosztás (vezetéknév kezdőbetűje szerint):





 14.hét 2020. május 19.
14. előadás ZH betekintés
2020. május 22.
pZH ?? (gyakorlat helyett) Megoldások  
pótlási hét
2020. május 26.
pZH:
1. vizsgahét
2020. június 4.
aláíráspótlás:




Jegyzet
Jordán Tibor, Recski András, Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, 2004.
A jegyzet amellett, hogy az előadáson tárgyalt anyagnál jóval bővebb, elektronikus formában olcsón és könnyen beszerezhető.



É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 10 pontos feladatból áll. Az félévközi jegy feltétele, hogy mindkét zárthelyi sikeres legyen (azaz az elérhető 40 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.

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 időpontja (körülbelül a szorgalmi időszak közepétől) a neptunból deríthető ki. Az itt írt 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.

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 félévközi jeggyé az alábbiak szerint. (Aki egyetlen ZH-t sem ír meg, az "nem teljesítette" bejegyzést kap erre a kurzusra.)

0-39 pont
elégtelen
40-50 pont
elégséges
50-62 pont
közepes
63-75 pont

76-100 pont
jeles