VISZMA06 2022  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  QBF08

Gyakorlatok

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



Féléves ütemterv

1.hét
február 15.
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 február 22. 2. előadás
Maximális súlyú párosítások, Egerváry magyar módszere. 
február 25. 1. gyakorlat 
3.hét március 1. 3. előadás
Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma.
4.hét március 8.
4. előadás
Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel.
máricus 11. 2. gyakorlat 
5.hét március 15. Nemzeti ünnep: az előadás elmarad
6.hét március 22. 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.
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.
március 25. 3. gyakorlat (konzultáció) megoldások
7.hét március 28. 18-20, IE007, I. ZH Megoldások
március 29.
6. 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.
8.hét április 5. 7. 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.
április 8. 4. gyakorlat és a hozzá tartozó megoldásvázlatok
9.hét április 12.
8. 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.
10.hét április 19.
Tavaszi szünet: az előadás elmarad
április 22.
5. gyakorlat és a hozzá tartozó megoldásvázlatok
11.hét április 26.
9. 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 május 3.
10. 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.  
május 6.
6. gyakorlat és a hozzá tartozó megoldásvázlatok
13.hét május 10.
11. előadás

14.hét május 17.
12. előadás
Konzultáció
május 19.
18-20, IE007, II. ZH Megoldások
május 20. 7. gyakorlat
pótlási hét május 26.
8-10, pZH  Megoldások  
1. vizsgahét június 1.
aláíráspótlás




Jegyzet, segédanyag


Jordán Tibor, Recski András, Szeszlér Dávid:
Rendszeroptimalizálás, Typotex Kiadó, 2004.

Ez 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ő,  de már a teams csoportba feltöltött anyagok között is megtalálható.
 
Ezen kívül még a
korábbi ZH feladatok és a megoldásaik is segítik a felkészülést.



É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.

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 azzal a további megkötéssel, hogy az elégtelennél jobb osztályzathoz mindkét ZH-nak sikeresnek kell lennie. (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