Gráfok és algoritmusok
A VIK Wikiből
A tantárgy néhány olyan, a gráfelmélethez szorosan kapcsolódó területet igyekszik bemutatni, amelyekre egy bevezető kurzuson rendszerint nem jut idő. Az vizsgált problémák megoldásában az algoritmikus megközelítés kiemelt szerepet kap.
Követelmények
Előtanulmányi rend
- Ajánlott: Bevezetés a számításelméletbe 2. vagy A számítástudomány alapjai.
A szorgalmi időszakban
- Az aláírás feltételei:
- A gyakorlatokon való részvétel.
- ZH-k teljesítéséhez elérhető 50 pont 40%-át, tehát legalább 20 pontot kell elérni. 5 feladatból áll a ZH, és 90 perces.
- Pótlási lehetőségek:
- Mindkét ZH pótolható egyszer a félév közben, egyszer meg pótlási héten (pótpótzárthelyi), viszont a pótpótZH már különeljárási díj fejében írható meg. A pZH-t a ZH-val azonos anyagrészből van, és 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 vizsgadőszakban
- Vizsga: szóbeli előre kiadott tételekből.
Félévvégi jegy
- A ZH-ról hozott pontok 40%-ban, a vizsga 60%-ban számít bele az évvégi jegybe.
- Ponthatárok:
Pont Jegy 0 - 39 1 40 - 54 2 55 - 69 3 70 - 84 4 85 - 100 5
Segédanyagok
- Az előadások videói/diasorai megtalálhatóak itt bejelentkezést követően.
Előadás (2022)
- 1. Előadás
- 2. Előadás
- 3. Előadás
- 4. Előadás
- 5. Előadás
- 6. Előadás
- 7. Előadás
- 8. Előadás
- 9. Előadás
- 10. Előadás
- 11. Előadás
- 12. Előadás
- 13. Előadás
Gyakorlat (2022)
- 1. Gyakorlat
- 2. Gyakorlat
- 3. Gyakorlat
- 4. Gyakorlat
- 5. Gyakorlat
- 6. Gyakorlat
- 7. Gyakorlat
- 8. Gyakorlat
- 9. Gyakorlat
- 10. Gyakorlat
- 11. Gyakorlat
Összefoglaló
Ajánlott könyvek
- Frank András - Diszkrét optimalizálás
- Frank András - Gráfelmélet
- Frank András - Kombinatorikus algoritmusok II.
Zárthelyi
- 2021
Vizsga
- 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.
- 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ó.
