Problémamegoldó szeminárium
(Informatikatanár szak)
Ismeretanyag:
- Rekurzióval, dinamikus programozással, mohó stratégiával megoldható feladatok, elméleti áttekintés, ismétlés:
- Rekurzió fogalma, alkalmazása, példák (n faktorizális, Fibonacci sorozat, Hanui tornyai, partícióprobléma stb.)
- Rekurzív algoritmusok futási ideje, tárhelye, helyességük bizonyítása
- Dinamikus programozás stratégiája, lépései, alkalmazása, példák (LKR, mátrixszorzás, hátizsák feladat stb.)
- Dinamikus programozási stratégia futási ideje, tárhely igénye, helyessége
- Absztrakt adattípusok, adatszerkezetek használata: verem, sor, prioritási sor, halmaz, tömb, lánc, fa, kupac
- Mohó stratégia, alkalmazása, kapcsolata a dinamikus programozási stratégiával, példák (esemény-kiválasztási probléma, hátizsák feladat, Huffman kódolás stb.)
- Mohó stratégia futási ideje, tárhely igénye, helyessége
- Rekurzióval, dinamikus programozással, mohó stratégiával megoldható feladatok, gyakorlati alkalmazások, ismeretek elmélyítése
- Absztrakt adattípusok, adatszerkezetek megvalósítása egy tetszőleges programozási nyelven (C/C++, JAVA, LOGO, esetleg Pascal)
- Önálló probléma feldolgozás, feladatok megoldása a különböző közoktatási versenyfelületek archívumából:
- Logo OSzTV, Nemes Tihamér OITV, Informatika OKTV, Közép Európai Informatikai Diákolimpia, Nemzetközi Informatikai Diákolimpia
- Gráf algoritmusok és összetett adatszerkezetek, elméleti áttekintés, ismétlés
- Gráfok, típusai (súlyozott-súlyozatlan, irányított-irányítatlan), jelölések, ábrázolások, definíciók
- Szélességi keresés alkalmazása, példa
- Szélességi keresés futási ideje, tárhely igénye, helyessége
- Mélységi keresés alkalmazása, példa
- Mélységi keresés futási ideje, tárhely igénye, helyessége
- Élek osztályozása, topologikus rendezés, erősen összefüggő komponensek
- Dijskstra algoritmus alkalmazása, példa
- Dijskstra algoritmus futási ideje, tárhely igénye, helyessége
- Összetett adatszerkezetek
- Gráf algoritmusok és összetett adatszerkezetek alkalmazása feladatok megoldásában
- Gráfok, mint absztrakt adattípus megvalósítása egy tetszőleges programozási nyelven (C/C++, JAVA, esetleg Pascal)
- Önálló probléma feldolgozás, feladatok megoldása a különböző közoktatási versenyfelületek archívumából:
- Nemes Tihamér OITV, Informatika OKTV, Közép Európai Informatikai Diákolimpia, Nemzetközi Informatikai Diákolimpia
- LEGO Robot verseny feladatainak vizsgálata, konkrét megvalósításuk
- A problémamegoldási stratégiák csoportosítása, ütemezése.
Kötelező irodalom:
- logo.inf.elte.hu/ (opens new window)
- nemes.inf.elte.hu (opens new window)
- NemesTihamér versenyfeladatok (opens new window)
- Mester (opens new window)
- SPOJ (opens new window)
- HackerRank (opens new window)]
- ACM (opens new window)
- www.cs.bme.hu/acm/ (opens new window)
- www.ioinformatics.org (opens new window)
- T. H. Cormen, C. E. Leiserson, R.L. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003.