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
2019

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. 
2020. 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.
Előrehozott tavaszi szünet
6.hét 2020. március 24. 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
2020. március 27. 3. gyakorlat   megoldások
7.hét 2020. március 31. 7. előadás (konzultáció)
2020. március 31.
18-20, I. ZH Megoldások

8.hét 2020. április 7. 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.
9.hét 2020. április 14.
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.
2020. április 17. 4. gyakorlat  megoldások
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 helyett konzultáció
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.
11-12. előadás  
Ütemezési problémák, közelítő algoritmusok
2020. május 8.
Konzultáció
13.hét 2020. május 12.
6. gyakorlat  megoldádok  
2020. május 14.
18-20: ZH előtti konzultáció
2020. május 15.
8-10, II. ZH Megoldások

 14.hét 2020. május 19.
14. előadás Tartalék
2020. május 22.
8-10, I. pZH  Megoldások  
pótlási hét
2020. május 26.
8-10, II. pZH
1. vizsgahét
2020. június 4.
aláíráspótlás:




Jegyzet, segédanyag
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ő.


A távoktatással megtartott előadások anyaga (prezentáció és narráció) szintén letölthető.

Korábbi ZH feladatok
2019-ből.


É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
51-62 pont
közepes
63-75 pont

76-100 pont
jeles