VISZMA09 2023 tavasz

Kombinatorikus optimalizálás

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

Előadás kedd 10:30-12:00 IB025 (Márc 21: STFKis)

Gyakorlatok

Kurzuskód	Időpont	Gyakorlatvezető	Terem
11	csütörtök 8:25-9:55	Fleiner Tamás	R505
12	csütörtök 8:25-9:55	Héger Tamás	R504

Féléves ütemterv

1.hét	február 28.	1. előadás Gráfok kromatikus száma, alsó és felső korlátok, mohó színezés. Páros gráfok, élkromatikus szám, Kőnig tétele páros gráfok élszínezéséről.
1.hét	március 2.	1. gyakorlat
2.hét	március 7.	2. előadás Hálózati folyamok, javító utas algoritmus, Ford-Fulkerson-tétel, EgÉr-lemma, páros gráfok maximális párosításai. Az alternáló utas algoritmus futtatása a páros gráf mátrixreprezentációján.
2.hét	március 9.	2. gyakorlat
3.hét	március 14.	3. előadás Maximális súlyú párosítások, Egerváry magyar módszere.
3.hét	március 16.	3. gyakorlat
4.hét	március 21.	4. előadás Helyszín: STFKis Lineáris egyenlőtlenségrendszerek, a lineáris programozás alapfeladata. Fourier-Motzkin elimináció, Farkas lemma.
4.hét	máricus 23.	4. gyakorlat
5.hét	március 28.	5. előadás Farkas lemma ekvivalens alakjai, LP primál- és duálfeladat, dualitástétel.
5.hét	március 30.	5. gyakorlat
6.hét	április 4.	6. 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. Az I. ZH anyaga eddig tart.
6.hét	április 6.	Tavaszi szünet, nincs gyakorlat
7.hét	április 11.	Tavaszi szünet, nincs előadás
7.hét	április 13.	6. gyakorlat
8.hét	április 18.	7. előadás ZH előtti konzultáció Néhány eddigi gyakorlat megoldása
	április 19.	18-20, IB025, I. ZH megoldások
	április 20.	7. gyakorlat ZH megbeszélés
9.hét	április 25.	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	április 27.	8. gyakorlat
10.hét	május 2.	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.
	május 3.	18-20, IB025, I. pZH
	május 4.	9. gyakorlat
11.hét	május 9.	10. előadás Közelítő algoritmusok. Élkromatikus szám, síkgráf kromatikus szám közelítése additív hibával. 2-közelítés a lefogó ponthalmaz méretére, logaritmikus közelítés a halmazfedési problémára. Ütemezési problémák. Alapfogalmak, jelölésrendszer, hasznos módszerek: SPT sorrend és listás ütemezés. FF és FFD heurisztikák a ládapakolási problémára.
11.hét	május 11.	10. gyakorlat
12.hét	május 16.	11. előadás Megoldásvázlatok ZH előtti konzultáció
	május 18.	ZH előtti konzultáció
	május 18.	18-20, IB025, II. ZH megoldások
13.hét	május 23.	12. 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.
13.hét	május 25.	11. gyakorlat
14.hét	május 30.	13. előadás
14.hét	június 1.
pótlási hét	június 5.	8-10, II. pZH IB134

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

Ezen kívül még a korábbi ZH feladatok és a megoldásaik is segítik a felkészülést. (A VISZMA06 kurzus nem teljesen azonos a jelenleg futó VISZMA09-cel, ezért a korábbi ZH-k feladatai az idén számonkért tananyagnak csak egy részét fedi le.)

É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, négy feladatból álló zárthelyi lesz, mindegyiken 50 pont szerezhető. 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 ha egy sikeresen megírt ZH javítása 20 pontnál kevesebbet ér: ekkor az adott ZH végső 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.

A számonkérések megírásakor az alábbi szabályok betartását követeljük meg.

Csak a honlapon meghirdetett beosztásnak megfelelő teremben írható meg a zárthelyi dolgozat: ha valaki nem a számára előírt teremben jelenik meg, nem írhatja meg ott a számonkérést. A termekben az ülésrendet a dolgozatírást felügyelő kollégák jelölik ki, ez kötelezően érvényes minden részvevőre.
A hallgatónál legyen okmánynak minősülő, fényképes igazolvány (személyi, jogosítvány, útlevél vagy új típusú diákigazolvány), amellyel kérésre igazolja magát, valamint jól láthatóan és megbízhatóan író, nem piros színű toll.
Minden hallgatónak gondoskodnia kell arról, hogy legyenek nála a dolgozatíráshoz A4-es méretű lapok. Minden lap jobb felső sarkában fel kell tüntetni a hallgató nevét és neptun-kódját. A kiosztott feladatlapot a hallgatók megtarthatják, de arra nem dolgozhatnak, azt a dolgozattal beadni nem lehet.
A dolgozatírást a hallgató akkor kezdheti meg, ha megjelenik a számára kijelölt teremben legkésőbb 20 perccel a hivatalos kezdési időpont után. A dolgozatírást megkezdő hallgató nem távozhat a teremből a dolgozatírás első 20 percében.
A dolgozatírás megkezdésétől a dolgozatírás végéig a dolgozatot író hallgató a dolgozatírást felügyelő személyeken kívül senki mással nem kommunikálhat.
A dolgozatírás alatt a hallgató által elérhető helyen nem lehet sem elektronikus eszköz (telefon, laptop, számológép, okosóra, stb), sem írott vagy nyomtatott tankönyv, jegyzet, segédanyag, sem pedig táska vagy kabát.
Aki a fenti szabályok valamelyikét megszegi, annak a dolgozata érvénytelen, ill. a vétség (súlyától függően) további eljárást von maga után.

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 megajánlott 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	jó
85-100 pont	jeles

A megajánlott jegyet elfogadni úgy lehet, hogy jelentkezni kell az e célból létrehozott szóbeli vizsgaalkalomra. Mindenki, aki erre a vizsgaalkalomra jelentkezik, automatikusan a megajánlott jegyét kapja. Aki nem fogadja el a megajánlott jegyét (azaz nem jelentkezik erre a speciális vizsgára), az szóbeli vizsgát tehet, amin legfeljebb egy osztályzatot tud javítani a megajánlott jegyén (rontani viszont korlátlanul tud). A szóbeli vizsgához vizsgatételsor tartozik, ami a félév végére alakul ki. A szóbeli vizsgán egy tételt sorsolunk a vizsgázónak, aminek a kidolgozására 30 percet biztosítunk. A vizsga során ellenőrző kérdések erejéig a többi tételbe is belekérdezhetünk, a ZH által le nem fedett anyagrészből biztosan kap kérdést a vizsgázó.