VISZMA06 2019 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:  E306cd

Gyakorlatok

Kurzuskód
Időpont
Gyakorlatvezető
Terem
11
minden második hét péntek 8:15-9:45 Fleiner Tamás
QBF10


Féléves ütemterv

1.hét
2019. február 5.
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
2019. február 8. 1. gyakorlat 
2.hét 2019. február 12. 2. előadás
Maximális súlyú párosítások, Egerváry magyar módszere. 
3.hét 2019. február 19. 3. előadás
Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma.
2019. február 22. 2. gyakorlat 
4.hét 2019. február 26. 4. előadás
Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel.
5.hét 2019. március 5. 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. 
2019. március 8. 3. gyakorlat
6.hét 2019. március 12. 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.
2019. március 14. 14-16, IB134, konzultáció
Tavaszi szünet
7.hét 2019. március 26. 7. előadás
Ford-Fulkerson tétel levezetése, intervallummátrix TU tulajdonsága, intervallumrendszer egyenletes színezése
2019. március 26. 18-20, I. ZH Megoldások
Terembeosztás (vezetéknév kezdőbetűje szerint):
A-R
S-Z
QBF08
QBF10
2019. március 29. 4. gyakorlat
8.hét 2019. április 2. 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. 
9.hét 2019. április 9.
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.
2019. április 12.
5. gyakorlat
10.hét 2019. április 16.
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 2019. április 23.
11. előadás

2019. április 26.
6. gyakorlat
12.hét 2019. április 30.
12. előadás
Fulkerson algoritmusa minimális költségű feszítő fenyő keresésére
13.hét 2019. május 7.
13. előadás

2019. május 9.
18-20, II. ZH Megoldások
 14.hét 2019. május 14.
14. előadás
2019. május 17.
pZH  Megoldások   Betekintés:
pótlási hét
2019. május 21.
ppZH  Betekintés:
1. vizsgahét
2019. május 27.
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 is 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 vagy lekési, az nem vehet rész ezen a számonkérésen, így jegyet sem szerezhet, hiszen az ekkor megszerzett eredményt nem tudjuk 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.) A dolgozatok eredményei (legkésőbb a következő napon) a tárgy honlapjára is felkerülnek. 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 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-54 pont
elégséges
55-69 pont
közepes
70-84 pont

85-100 pont
jeles