VISZA028 2019 tavasz

Gráfok és algoritmusok

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

Előadás kedd 8:15-10:00: H406

Gyakorlatok

Kurzuskód	Időpont	Gyakorlatvezető	Terem
T1	péntek 10:15-11:45	Tóthmérész Lilla	H406

Féléves ütemterv

1.hét	2019. február 5.	1. előadás Néhány tipikus algoritmikus bizonyítás: mohó technika.
1.hét	2019. február 8.	1. gyakorlat
2.hét	2019. február 12.	2. előadás Néhány tipikus algoritmikus bizonyítás: javító utak. Stabil párosítások, Gale-Shapley algoritmus.
2.hét	2019. február 15.	2. gyakorlat
3.hét	2019. február 19.	3. előadás Stabil párosítások hálóstruktúrája, stabil párosítások alkalmazásai: Pym linking tétele, Galvin tételének általánosítása.
3.hét	2019. február 22.	3. gyakorlat
4.hét	2019. február 26.	4. előadás Stabil párosítások nem páros gráfokon, Irving algoritmusa, stabil félpárosítások.
4.hét	2019. március 1.	4. gyakorlat
5.hét	2019. március 5.	5. előadás Minimális vágások keresése, a Nagamochi--Ibaraki-algoritmus (maxvissza sorrend), Karger algoritmusa.
5.hét	2019. március 8.	5. gyakorlat
6.hét	2019. március 12.	6. előadás Merevkörű gráfok, szimpliciális csúcs, merevkörű gráfok listaszínezése.
6.hét	2019. március 15.	Nemzeti ünnep, a gyakorlat elmarad
Tavaszi szünet
7.hét	2019. március 26.	7. előadás Merevkörű gráfok és a maxvissza sorrend.
7.hét	2019. március 29.	6. gyakorlat
8.hét	2019. április 2.	8. előadás Lamináris halmazrendszerek reprezentációja és a Gomory-Hu fa.
8.hét	2019. április 5.	7. gyakorlat
9.hét	2019. április 9.	9. előadás Minimális vágások kaktuszreprezentációja.
9.hét	2019. április 12.	8. gyakorlat
10.hét	2019. április 16.	10. előadás Edmonds algoritmusa, Tutte tétele, Tutte--Berge-formula, Edmonds--Gallai-struktúratétel, faktorkritikus gráfok. Tudnivalók
11.hét	2019. április 23.	11. előadás Lovász leemelési tétele, 2k-élösszefüggő gráfok előállítása, Nash-Williams irányítási tétele.
11.hét	2019. április 26.	9. gyakorlat
12.hét	2019. április 30.	12. előadás Áramok és folyamok, Hoffmann-tétel, algoritmus minimális költségű folyam keresésére .
12.hét	2019. május 3.	10. gyakorlat
13.hét	2019. május 6.	8-10 QBF13 ZH Megoldások
	2019. május 7.	13. előadás Minimális költségű folyamalgoritmus befejezése. Folyamok kerekítése, és annak alkalmazásai: páros gráfok élszínezése, és egyenletes k-élszínezése.
	2019. május 10.	11. gyakorlat
14.hét	2019. május 14.	14. előadás Baranyai tétele (Ez pedig egy másik, részletesebb leírás)
14.hét	2019. május 17.	10-12 pZH H406 (gyakorlat helyett) Megoldások
pótlási hét	2019. május ??.	aláíráspótlás Betekintés:

Jegyzet

Frank András: Diszkrét optimalizálás

Frank András: Gráfelmélet

Az egyes előadásokhoz tartozó anyagok ill. a gyakorlatok feladatsorai is tartalmaznak a felkészülést segítő anyagokat.

Értékelés, tárgykövetelmények, vizsga

Zárthelyik, pótzárthelyik, aláírás:

A félév során egy öt feladatból álló, 90 perces zárthelyi lesz. Az aláírás feltétele, hogy ez a zárthelyi sikeres legyen (azaz az elérhető 50 pont 40%-át, konkrétan legalább 20 pontot érjen). A zárthelyi esetében biztosítjuk pótlás lehetőségét, amikoris a meg nem írt zárthelyi pótolható vagy 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ás után sincs aláírása, az a ppZH alkalmával megírhatja ugyanezt a 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.

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 vonhat maga után.

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 jelezzék az előadónak írt e-mailben.

Az zárthelyikre osztályzatot nem adunk, hanem az azon szerzett pontszám beszámít a vizsgajegybe.

Vizsga:

Vizsgázni csak az jöhet, aki a neptunban jelentkezett az adott vizsgaalkalomra, továbbá a vizsgára jelentkezéshez érvényes aláírással rendelkezik. Felhívjuk a figyelmet arra, hogy a neptun csak a vizsgára jelentkezett hallgatók eredményeinek a felvitelét engedélyezi, így nincs lehetőségünk olyan hallgatót vizsgáztatni, aki bármilyen okból nincs a neptun által generált vizsgalapon. A jelentkezések és lemondások a vizsgát megelőző napon 12 órakor lezárulnak. Elővizsgát nem tartunk.

A vizsga ebből a tárgyból szóbeli. A vizsga megkezdésekor a vizsgázónak kisorsolunk egy tételt a tárgyhoz tartozó, a vizsgatételsorból. Ennek a kidolgozására (vagyis a szóbeli felelethez egy vázlat vagy bő jegyzet elkészítésére) legalább 45 percet biztosítunk. Negyvenöt perc felkészülési idő letelte után a vizsgáztató abban az esetben is elkezdheti a vizsgáztatást, ha a hallgató még nem jelezte, hogy elkészült. A felelet abból áll, hogy a vizsgázó egyrészt a jegyzeteire támaszkodva részletesen beszámol a húzott tételben található tananyagról, másrészt a vizsgáztató néhány szúrópróbaszerű, a tananyag további részével kapcsolatos kérdésére válaszol. (A vizsga sikerességéhez tehát nem elég a kihúzott tétel ismertetése, az fent említett további kérdésekre is kell tudni válaszolni.) Az elégséges megszerzésének feltétele, hogy a vizsgázó az anyagban szereplő minden lényeges (a tételsorban félkövéren szedett) definíciót és tételt pontosan ki tudjon mondani, illetve tudjon értelmezni. Ugyancsak szükséges, hogy a nem vastagon szedett részek esetében is legfeljebb egy-két hiányossága legyen a vizsgázónak. Ennél több viszont nem is kell a ketteshez, azaz a tételsorban szereplő tételek bizonyításainak ismerete csak a közepes vagy jobb jegy megszerzéséhez szükséges. Ha valaki az egyszerűbb bizonyításokat is tudja, akkor jók az esélyei a hármas szóbeli feleletre. A négyes vagy ötös felelethez (esetleg kisebb-nagyobb segítséggel) már a nehéz bizonyításokat is el kell tudni mondani (és persze érteni is kell azokat). A vizsgán számítani kell arra is, hogy a zárthelyik által le nem fedett anyagrészből bizonyosan kap kérdést a vizsgázó.

A vizsgajegy a zárthelyi eredményének ill. a vizsgán nyújtott szóbeli teljesítménynek a súlyozott átlaga, amiben a zárthelyiedmény súlya 2, a szóbeli vizsgáé pedig 3. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyi eredményétől). Ez a gyakorlatban azt jelenti, hogy a zárthelyi eredményei alapján egy 16 és 40 közötti "hozott pontszámot" számítunk ki, ami a két ZH pontszámának 40%-a, és ehhez adódik a szóbeli vizsgán szerezhető, legfeljebb 60 pont. Ha a szóbeli részen szerzett pontszám 24-nél kevesebb, akkor a vizsgajegy elégtelen, egyébként pedig a hozott pontszám és a vizsgán szerzett pontok összegéből az alábbiak szerint számítjuk a vizsgajegyet: 40 és 54 pont között elégséges, 55 és 69 pont között közepes, 70 és 84 pont között jó, végül 85 és 100 pont között jeles.

Aki elégtelenre vizsgázik, az egy ízben ismétlő vizsgát tehet amennyiben a vizsgaidőszak hátralévő részében még van meghirdetett vizsgaalkalom és arra tud jelentkezni. Sikeres vizsga esetén is tehető javító vizsga. Ismétlő ill. javító vizsga esetén a zárthelyikből származó eredmények változatlan módon érvényesek. A férőhelyek függvényében további ismétlő/javító vizsgára is van lehetőség, azonban ugyanabban félévben csupán két vizsga díjmentes: a harmadik alkalomtól ez díjköteles, amit a neptun kiszámláz. Érdemes bölcsen élni ezzel a lehetőséggel, tudva, hogy aki ugyanazon tárgyból hat vizsgán is elégtelen eredményt ér el, azt az egyetem tanulmányi okból elbocsátja. Igény esetén a későbbiekben indítunk vizsgakurzust azok számára, akik aláírással rendelkeznek, és az adott vizsgaidőszakban vizsgát szeretnének tenni.

A vizsgákat megelőző konzultáción a vizsgára való készülés közben felmerült kérdéseket lehet feltenni. A konzultáción bárki részt vehet, nem csak az, aki az éppen soron következő vizsgára jelentkezett. Idén ebből a tárgyból nincs előre meghirdetett konzultáció, a konzultáció igényét e-mailben érdemes egyeztetni az előadóval.

A vizsgán (ebből a tárgyból) nem szükséges alkalmi viseletben megjelenni. A hallgató (egyébként civilizált) öltözködése a szóbeli vizsga eredményét semmilyen tekintetben sem befolyásolja.