VISZMA06 2021  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  Teams

Gyakorlatok

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



Féléves ütemterv

1.hét
2021 . február 9.
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 2021 . február 16. 2. előadás
Maximális súlyú párosítások, Egerváry magyar módszere. 
2021 . február 19. 1. gyakorlat 
3.hét 2021 . február 23. 3. előadás
Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma.
4.hét 2021 . március 2.
4. előadás
Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel.
2021 . máricus 5. 2. gyakorlat 
5.hét 2021 . március 9. 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 2021 . március 16. 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
2021 . március 19. 3. gyakorlat
7.hét 2021 . március 23. 7. előadás (konzultáció)
2021 . március 23.
18-20, I. ZH Megoldások

8.hét 2021 . március 30. 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.
Tavaszi szünet
9.hét 2021 . április 13.
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.
2021 . április 16. 4. gyakorlat
10.hét 2021 . április 20.
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 2021 . április 27.
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.
2021 . április 30. 5. gyakorlat
12.hét 2021 . május 4.
12. 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.
2021 . május 7.
6. (előrehozott) gyakorlat 
13.hét 2021 . május 11.
13. előadás
Konzultáció  
2021 . május 13.
18-20, II. ZH Megoldások
pótlási hét
2021 . május 20.
8-10, pZH  Megoldások  
1. vizsgahét 2021 . május 26.
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.

Előadásvideók, diasorok


É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éseken alkalmazott szabályokat később hirdetjük meg annak függvényében, hogy online vagy jelenléti oktatás lesz az adott időpontban.

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