Informatika tanárszak             2002.

Szigorlati tematika
'Programozási módszertan' tárgyból

 1. Programozási tételek:_sorozathoz érték rendelése. Az egyes tételek elemzése, variációk összehason­lítása (formális specifikáció). Másolás, kiválogatás tétele. Programozási tételek összeépítése.

 2. Programozási tételek:_rendezések, sorozatokhoz sorozat rendelése, ill. sorozathoz sorozatok rende­lése. Az egyes tételek elemzése, variációk összehasonlítása (elemibbekre való visszavezetés).

 3. Programozási tételek:_logaritmikus keresés, backtrack. A visszalépéses keresés elve, és az ez alap­ján "levezetett" egyéb programozási tételek megfogalmazása (illusztrálásuk konkrét példákkal).

 4. Adatleírás:_adatok jellemzői (azonosító, érték, hatáskör, kezdőérték, hozzáférési jog, típus stb.) Elemi adattípusok és ábrázolásuk. Összetett típusok (direktszorzat, unió, sokaság: tömb, file, halmaz) és ábrázolásuk. Online algoritmusok.

 5. Adatleírás:_sorozattípusok (lehetséges műveletek), nevezetes sorozattípusok és ábrázolásaik (vermek, sorok, listák, absztrakt sorozatok; folytonos, láncolt és blokkolt ábrázolás). Nevezetes sorozattípusok algebrai specif­kációja. Dinamikus programozás feljegyzéses módszerrel

 6. Adatleírás: tömbök, címfüggvények, speciális mátrixok; táblázat-típuskonstrukció; keresési módsze­rek táblázatokban (lineáris, bináris, gyakoriságszerinti, kulcstranszformáció [hash-elés]). Tömbök és táblázatok algebrai specifikációja.

 7. A program hatékonysága:_a hatékonyság "dimenziói" (hely, idő, bonyolultság), szintjei (globális, lokális); a végrehajtási idő csökkentése (példákon keresztül). A mohó algoritmus és alklamazásai.

 8. A program hatékonysága:_helyfoglalás csökkentése (példákon keresztül); lokális hatékonyság (kód­hatékonyság); a hatékonyság mérése. Dinamikus programozás és alkalmazásai.

 9. File-ok:_file-típuskonstrukciók (input, output szekvenciális file, direkt, és asszociatív file; file-mo­dulok) A file típusok algebrai specifikációja.

10. Adatfeldolgozás:_adatszerkezet és programszerkezet megfeleltetése; elemenkénti feldolgozhatóság; struktúra szerinti feldolgozás; struktúramegfeleltetés, konfliktusok. Szekvenciális file-ok feldolgozá­sának specialitásai (előreolvasás, file-vége, pufferelés).

11. Szövegfeldolgozás:_szövegtípusok (karakter, szöveg és szövegfile; valamint reprezentációjuk, imp­lemetációjuk); elemi szövegfeladatok; "sűrű" ábrázolás; szövegformázás; keresés szövegben.

12. Rekurzió:_rekurzív specifikáció (példák), rekurzív algoritmusok (példák), és implementációs prob­lémák; rekurzió és iteráció kapcsolata, programozási tételek rekurzívan.

13. Hierarchikus adatszerkezetek:_nevezetes rekurzív konkrét típusok fák, bináris fák és ábrázo­lásaik, szokásos műveleteik; rendezés fával, keresőfák. A fák algebrai specifikációja.

14. Hierarchikus adatszerkezetek: szekvenciális ábrázolás: piramisrendezés; kiegyensúlyozott fák; nem bináris fák, B-fák.

15. Gráfok:_a gráftípus és ábrázolási lehetőségek, műveletek, szélességi bejárás és alkalmazásai: útkeresés, legrövidebb út, leghosszabb út, összefüggőség.

16. Gráfok:_a gráftípus és ábrázolási lehetőségek, műveletek, mélységi bejárás és alkalmazásai: útkeresés, legrövidebb út, leghosszabb út, összefüggőség.

17. Gráfok:_ feszítő fák, Euler út és Euler kör, hálózati folyamok, páros gráfok, Floyd-Warshall algoritmus.

18. A program helyessége:_a helyes programkészítési stílus (felülről lefelé és alulról felfelé építkezés, elvek - indokok, programozási tételek); tesztelési és hibakeresési módszerek (statikus, dinamikus; fe­kete-, ill. fehér-doboz módszerek), hibakeresést támogató eszközök (gyakorlati tapasztalatai alapján); helyességbizonyítás.

19. Programozási filozófiák: Nemdeterminisztikus algoritmusok, párhuzamosság (szemaforok, monito­rok, üzenetátadásos modellek), online algoritmusok.