A tehetséggondozás két fő pillérre támaszkodik. Az egyik a tehetséges diákoknak szóló versenyek, a másik pedig a tehetséges diákok kötelező tananyagon túli oktatása. Ez utóbbi sokszor a versenyekre felkészítést jelenti, de nem kizárólag erről van szó. [NJSZT]
Az informatikai országos versenyek története:
A tehetséggondozás tanítási oldala programozásból az alábbi négy pillérre épül:
Az alábbiakban egy 2+2 éves szakköri tematika következik, melynek első 2 évét regionális (megyei vagy városi, városkörnyéki), utolsó évét pedig országos (legfeljebb 3 helyszínen) szakkörként képzeljük el.
A témák sorrendje ajánlott, több esetben épít az előző témára. Mindezek mellett azonban a tehetségesebb diákok a második évben is bekapcsolódhatnak a képzésbe.
Elképzeléseink szerint az egyes foglalkozások 4-5 tanóra hosszúak lehetnek, a témától, illetve a csoport haladási sebességétől függően.
A résztvevők minden alkalommal egy 8-12 oldalas könyvecskét kapnak az adott foglalkozás témájáról.
Az itt szereplő feladattípusok mindegyikéhez első lépésként 2-4 példát kell elmondani. Ezután meg kell beszélni, hogy mi az, ami közös ezekben a feladatokban. Ezután következik az általános megoldó algoritmus megbeszélése, majd a résztvevők egy konkrét feladatot közösen, majd egy másikat önállóan oldanak meg. Az algoritmusok kódolása minden esetben egyéni feladat.
A feladattípusok: sorozatszámítás, eldöntés, kiválasztás, keresés, megszámolás, maximum-kiválasztás, kiválogatás.
Az óra első része az itt szereplő típusok osztályozásának megbeszélése. Ezt követi a halmaz típus definiálása és a kétféle fő ábrázolási módjának megadása, majd a műveletek megvalósítása. Ezután a résztvevők konkrét halmazokra megírják a feldolgozó programot.
Az itt szereplő feladattípusok mindegyikéhez első lépésként 2-4 példát kell elmondani. Ezután meg kell beszélni, hogy mi az, ami közös ezekben a feladatokban. Ezután következik az általános megoldó algoritmus megbeszélése, majd a résztvevők egy konkrét feladatot közösen, majd egy másikat önállóan oldanak meg. Az algoritmusok kódolása minden esetben egyéni feladat.
A feladattípusok: unió, metszet, összefuttatás, összefésülés, szétválogatás, szétválogatás helyben.
A foglalkozás 3 részből áll. Minden egyes struktúra a megoldandó feladatokkal, problémákkal kezdődik. Ezután következik az adott adattípus műveletei definiálása, ábrázolási módja megbeszélése, majd a műveletek megvalósítása. Végül pedig az adattípust használják valamilyen feladat megoldására.
A foglalkozás a táblázatban keresés elemzésével kezdődik. Ezt követi a megoldási ötlet, a kulcstranszformációs függvény bevezetése, illetve annak megállapítása, hogy ez általában képes különböző elemekhez ugyanazt a címet rendelni. Ezt követi a megoldási stratégiák megbeszélése és ezek alapján valamelyik megvalósítása és kipróbálása.
A foglalkozás a rekurzív specifikációval (azaz feladatok rekurzív megfogalmazásával) kezdődik: faktoriális, Fibonacci számok. Ezt rekurzív algoritmusok követik, mindegyiket az előzőből állítjuk elő (az algoritmus módosítása mellett a kód is mindig módosítandó).
A foglalkozás célja az egyes rendezési módszerek ismertetése, amelyet a résztvevők kódolnak, majd futási időt mérnek a későbbi összehasonlítás céljából (teljesen rendezett, fordítva rendezett, véletlenszerű sorozatra), megvizsgálandó az elemszám kétszerezés, felezés hatása. Ezt követik a speciális rendezések, s legvégül a gyorsrendezés (quicksort).
Sokszor fordul elő az adatok világában, hogy adatok sorrendje megváltozik, egyesek eltűnnek, mások megjelennek és mindehhez az adatstruktúra változtatása körülményes, lassú lenne. Ekkor jön elő az a gondolat, hogy az adatok logikai sorrendjét különböztessük meg a fizikai sorrendtől. Erre való a láncolt ábrázolás. Statikus láncolásról beszélünk, amikor a sorrendet tömbindexekkel adjuk meg, dinamikus láncolásról pedig akkor, amikor mutatókat használunk.
Ez is konkrét feladatok megbeszélésével kezdődik, majd utána meg kell fogalmazni a megoldás elvét (hogyan csinálnánk kézzel?). Ezután jön a visszalépéses keresés algoritmusának megbeszélése és alkalmazása 1-2 konkrét feladatra. A harmadik lépés az összes megoldás és a legjobb megoldás elvének megbeszélése. Utoljára marad a visszalépéses keresés rekurzív változatának megbeszélése, visszautalással a rekurzió témakör utolsó feladatára, aminek megoldása ugyanez volt.
A logikai programozás alapgondolatával kezdődik a foglalkozás, a PROLOG nyelvben szokásos, rokonokkal kapcsolatos feladatkörbeli feladatok megoldásával, valamint kódolásával PROLOG-ban.
A funkcionális programozás alapgondolatával kezdődik a foglalkozás, a Logo függvénykezelő részére alapozva. Áttekintik a szokásos programozási struktúrák rekurzív, funkcionális nyelvi megfelelőit, majd elemi szövegmanipulációs feladatokat oldanak meg.
Sok egyszerű matematikai fogalom (pl. Fibonacci számok) kiszámítására adható egyszerű, hatékony algoritmus, melyek ismerete szükséges feladatok hatékony megvalósításához.
Gráfok fogalmával, alkalmazásával, ábrázolási lehetőségeivel kezdődik a foglalkozás. Ezt követi a két fő bejárási stratégia megbeszélése, majd megvalósítása számítógépen. Sok olyan feladat is előfordul, amikor nehéz kitalálni, hogy a feladat mögött egy gráf-modell húzódik, ráadásul a gráfot magát sokszor nem is ábrázoljuk, hanem csupán az egyes lépésekben a szükséges részét számítjuk ki.
Itt sok gráf-algoritmust kell megbeszélni, amelyek mindegyike a két gráf-bejárás valamelyikére vezethető vissza: Összefüggő-e a gráf, a gráf komponensei, topologikus rendezés, a leghosszabb (kritikus) út, útkeresés két pont között, két pont közötti legrövidebb út, a legrövidebb út súlyozott gráf esetén. Dijkstra algoritmusa.
Ezen a foglalkozáson olyan gráf-algoritmusokat vizsgálunk, amelyek nem gráf-bejáráson alapulnak. Ilyenek a minimális költségű feszítőfa előállítására szolgáló algoritmusok, valamint a Floyd-Warshall algoritmus.
Sok adatstruktúrára jellemző, hogy – rekurzívan – saját magát tartalmazza (egy bináris fa például áll egy gyökérelemből és két bináris fából). A rekurzív adatstruktúrák megvalósítása, hatékony kezelése így fontos programozási feladat.
Több feladattípus esetén van szükségünk arra, hogy a megoldásban a számítógéppel kommunikáljunk. Ilyenek a kétszemélyes játékok (ahol a számítógép az ellenfél), a kitalálós feladatok (amikor a számítógép adja a kérdéseinkre a válaszokat), valamint az online algoritmusok (amikor a feladat megoldása közben szerzünk újabb információkat).
Optimalizálási probléma megoldására szolgáló algoritmus gyakran olyan lépések sorozatából áll, ahol minden lépésben adott halmazból választhatunk. Sok optimalizálási probléma esetén a dinamikus programozási megoldás túl sok esetet vizsgál annak érdekében, hogy az optimális választást meghatározza. Bizonyos esetekben ennél egyszerűbb, hatékonyabb algoritmus is létezik. A mohó stratégia mindig az adott lépésben optimálisnak látszó választást teszi. Vagyis a lokális optimumot választja abban a reményben, hogy ez globális optimumhoz fog majd vezetni.
A matematika sok fogalmat definiál rekurzívan, azaz a fogalom definíciójában használja magát a fogalmat. Ez gyakori a programozási feladatok specifikációjában is. Rekurzív specifikációból könnyű és biztonságos rekurzív algoritmust készíteni, csupán a megvalósítás hatékonyságával kell törődni. Tipikus megoldás erre a rekurzió helyetti táblázatkitöltés, valamint a rekurzió memorizálással.
Egyszerűbb esetben közvetlen rekurzióval van dolgunk (a rekurzív algoritmus saját megát hívja), még más esetekben közvetett rekurzióról van szó (az egyik eljárás hívja a másikat, a másik eljárás pedig az egyiket).
A dinamikus programozás elnevezés egy problémamegoldási módszert jelöl. A módszer lényege, hogy a kiindulási problémát részproblémákra bontjuk és a részproblémák megoldásaival fejezzük ki a megoldást. Bár a megoldást rekurzívan fejezzük ki, azonban a tényleges kiszámítás nem rekurzív módon, hanem táblázatkitöltéssel történik. Ez a módszer hatékony algoritmust eredményez számos fontos probléma megoldására.
Számos olyan gyakorlati számítási probléma van, amely megoldható olyan geometriai modellben, amelyben csak egyszerű objektumok, pontok, egyenesek, szakaszok, szögek, szögtartományok, poligonok szerepelnek.
Sok gyakorlati probléma vezet kombinatorikus feladatok megoldására:
Vizsgálhatjuk, hogy az adott halmazban hány elem van, felsorolhatjuk az összes elemét, megadhatjuk egy adott sorrend szerinti i-edik elemét, adottat követő vagy megelőző elemét.
  |
 |
 |
A tananyag az ELTESCORM keretrendszerrel készült