Informatika 11. o. - Intenzív
a 2006-os tantervnek megfelelő tankönyv
Tartalomjegyzék
GRÁFOK
Irányított és nem irányított gráfok
Meghatározások
Sajátos gráfok
Gráfok ábrázolási módjai
Illeszkedési mátrix (pont-él mátrix, incidencia mátrix)
Éllista
Boole-mátrix vagy csúcsmátrix (szomszédszági mátrix, adjacenciamátrix)
Adjacencialista (szomszédsági lista)
A gráfok tulajdonságai
teljes tartalomjegyzék...
A gráfok bejárása
Szélességi bejárás (Breadth First)
Mélységi bejárás (Depth First)
Útmátrix
Összefüggőség
Erősen összefüggő komponensek
Első módszer
Második módszer
Harmadik módszer
Legrövidebb utak meghatározása
A legrövidebb utak problémája
Adott csúcsból induló legrövidebb utak – Dijkstra algoritmusa
Legrövidebb utak minden csúcspárra – a Roy-Floyd algoritmus
Feszítőfák meghatározása
Minimális feszítőfa meghatározása, Kruskal és Prim algoritmusai
Megoldott feladatok
Kitűzött feladatok
DINAMIKUS ADATSZERKEZETEK
Mutatók
Típus nélküli mutatók
Tipizált mutatók
Megoldott feladatok
Gyakorlatok
Dinamikus változók
Láncolt listák
Egyszeresen láncolt listák
Kétszeresen láncolt listák
Megoldott feladatok
Kitűzött feladatok
FAGRÁFOK
A fák típusai
Nyílt fák
Gyökeres fák és rendezett fák
Bináris fák és bővített fák
Gyökeres fák ábrázolása és bejárása
Bináris és keresőfák
A kupac adatszerkezete
Megoldott feladatok
Kitűzött feladatok
A MOHÓ PROGRAMOZÁSI MÓDSZER
Megoldott feladatok
A hátizsákprobléma
Ütemezés
Háromszög
Kitűzött feladatok
A VISSZALÉPÉSES KERESÉS PROGRAMOZÁSI MÓDSZERE
A módszer általános ismertetése
Megoldott feladatok
Nyolc királynő a sakktáblán
Permutációk
Variációk
Kombinációk
Delegációk
Adott halmaz összes lehetséges részhalmaza
A Descartes-szorzat
Szürjektív függvények
Minimális összeg
Teve
Pénzérmék
Térképszínezés
Számfelbontás
Halmazpartíció
Kannibálok és misszionáriusok
Részgráf
A Hamilton-út (-kör)
Euler-vonal (-kör)
Rekurzívan implementált backtracking algoritmusok
Permutáció
Zárójelek
Részhalmaz
Számfelbontás
Lábak
Labirintus
Lóugrás
Tank
Kitűzött feladatok
AZ OSZD MEG ÉS URALKODJ PROGRAMOZÁSI MÓDSZER
A módszer általános leírása
Megoldott feladatok
Maximum keresése
Minimum és maximum keresése
Hatványozás
Bináris keresés
Gyorsrendezés (Quick Sort)
Összefésüléses rendezés (Merge Sort)
A keresési és rendezési algoritmusok hatékonyságának tárgyalása
Hanoi tornyai
Tábla lefedése
Tábla
Kitűzött feladatok
Fraktálok
Egy kis történelem
Koch-görbe egyenlő oldalú háromszögre
Koch-görbe négyszögre
A Peano-görbe
Fára emlékeztető görbe
A Perron-görbe
A sárkánygörbe
Zárt vonalú fraktálok
Kitűzött feladatok
A DINAMIKUS PROGRAMOZÁSI MÓDSZER
Megoldott feladatok
Kitűzött feladatok
PROGRAMOZÁSI MÓDSZEREK ÖSSZEHASONLÍTÁSA EGY FELADAT ALAPJÁN
Mohó módszer (Greedy)
Visszalépéses keresés (Backtracking)
Oszd meg és uralkodj (Divide et impera)
Dinamikus programozás
A módszer bonyolultsága – θ(n2)
IRODALOMJEGYZÉK
Kapcsolódó könyvek
