Algoritmizálás
(Informatikatanár szak)
- Pédaprogramok
- Régi honlap példaprogramokkal és előadás-anyagokkal (opens new window)
- Régi algoritmusok és adatszerkezetek II. előadások anyagai (opens new window)
Alapfogalmak, algoritmusok elemei
- Változó fogalma, adattípusok.
- Statikus és dinamikus memóriakezelés
- Elemi utasítások, a gépi kód működése. Szekvencia, ugrás, feltételes ugrás, szubrutin hívása.
- Algoritmusok elemei magas szintű programozási nyelvekben:
- szekvencia,
- szelekció,
- iteráció,
- rekurzió.
- A tömb fogalma és kezelése.
- Algoritmusok jellemzői, a futási idő és tárigény fogalma. Elemi kereső és rendező algoritmusok:
- beszúró- és buborék rendezés, lineáris- és logaritmikus keresés
- külső és helyben rendezések
- függvények növekedési üteme, jelölések
- rendezések futási idejének elemzése, rendezések típusai.
- A függvény fogalma, függvényhívás formái, bemeneti paraméterek, visszatérési érték és funkciói.
Alapvető adatszerkezetek, algortimusok tulajdonságai
- A verem és sor adatszerkezet és működése, a verem jelentősége a függvényhívások folyamán.
- Rekurzió működése az informatikában, rekurzióval megoldható feladatok.
- Kupacrendezés, gyorsrendezés, vödrös és radix rendezés, időigény elemzése.
- Rendező algoritmusok futási idejének elemzése.
- Struktúra és Osztály típus. Láncolt listák és megvalósításuk.
- Elemi és absztrakt adatszerkezetek, az interfész funkciója:
- verem, sor
- bináris kupac, prioritási sor, binomiális kupac és alkalmazásai
- halmaz és függvény absztrakt adatszerkezet (Map, Set)
- bináris keresőfák, önszervező keresőfák (Splay, AVL, 2-3, B, Piros-fekete)
- hasítótáblák, ugrólisták
- Amortizációs költségelemzés.
- Kettős adatszerkezetek.
6.3 Nevezetes informatikai problémák és algoritmusok
- Mintaillesztés: automatával, Knuth-Morris-Pratt algoritmus.
- Hátizsák feladat, tükörszó probléma.
- Eseménytér fogalma, dinamikus programozás, mohó stratégia.
- Optimális pénzváltás, hátizsák probléma, töredékes hátizsák probléma
- Csoportkép optimális időpontjainak meghatározása feladat.
- Hemming-távolság, Damerau–Levenshtein-távolság, Wagner–Fischer algoritmus.
- Számelméleti algoritmusok, nyilvános kulcsú tikosítás, RSA algoritmus.
- Gráf absztrakt adattípus, gráf tárolási módok, számított gráf fogalma és példák.
- Gráf-algoritmusok (gráf bejárások és keresések, Floyd-Warshall, PageRank algoritmus).
- Dijkstra- és A* algoritmus.
- Speciális gráfok, páros gráfok és párosítási problémák. Magyar módszer.
- Kruskal-algoritmus, halmazerdő adatszerkezet. Prím-algoritmus.
- Ajánlórendszerek. Számítási bonyolultság fogalma, Turing-gép, bonyolultsági osztályok.
- Gráfok tulajdonságai, gráf alapú adatbányászati módszerek. Adattudomány.
- A mesterséges intelligencia alapfogalmai.
- Visszalépéses keresés, alfa-béta vágás, gráfjátékok.
- Approximációs algoritmusok, utazóügynök probléma és időbonyolultsága, approximációs megoldások.
- Tanuló algoritmusok, genetikus algoritmusok.
- Neurális hálózatok, gépi tanulás. Tensorflow.
- Véletlenített algoritmusok.
- Online problémák és online algoritmusok:
- átlagos eset elemzés, versenyképességi elemzés
- online algoritmusok empírikus vizsgálata
- online klaszterezezési és ütemezési feladatok
- online nyugtázás, ládapakolás, k-szerver probléma
- véletlenített online algoritmusok
- online tanuló algoritmusok