Cserép Máté honlapja

Célkitűzés

A kurzus egyik célja azoknak az adatstruktúráknak és algoritmusoknak a megismertetésére a hallgatókkal, amelyek informatikában széles körben - így a térinformatikában egyaránt - alapvetőnek számítanak. A szemeszter második fele kitekintést nyújt a speciálisan a térinformatika területén alkalmazott eljárásokra és adatszerkezetekre.

Számonkérés és értékelés

A hallgatók a tárgyból megajánlott jegyet vagy vizsgajegyet szerezhetnek.
Megajánlott jegy a szorgalmi időszak során kiírt beadandó programozási feladatok teljesítésével szerezhető. Megajánlott jegy hiányában - vagy annak elutasítása esetén - a kurzus szóbeli vizsgával teljesíthető.
A beadandó feladatokra összesen 10 pont szerezhető, az elérhető pontszám alapján a következő érdemjegy kerül megajánlásra:

Beadandó feladatok

A feladatkiírások a Beadandó Kezelő Rendszerben érthetőek el, a megoldásokat is ott szükséges feltölteni.

Irodalomjegyzék

• Fekete István et al.: Algoritmusok és adatszerkezetek
• Rónyai L., Ivanyos G., Szabó R.: Algoritmusok
• Elek István: Adatbázisok, térképek, információs rendszerek
• Orgován Krisztina: Konvex- és mozgó objektumok indexelése
• Elek István: Topologikus térbeli adatstruktúrák

• ---

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Új algoritmusok
• P. Rigaux, M. O. Scholl, A. Voisard: Spatial Databases: With Application to GIS
• H. Samet: The Design and Analysis of Spatial Data Structures
• M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry
• A. Levitin: Introduction to the Design and Analysis of Algorithms

Python tananyagok

• Mark Summerfield: Python 3 programozás, Kiskapu Kiadó, 2009
• Eric Matthes: Python Crash Course, No Starch Press, 2015

Tematika

1. Bevezetés, Python alapismeretek
   • telepítési útmutató, gyakorlati példakód
2. Elemi algoritmusok
   • elméleti segédanyag, gyakorlati példakód
3. Alapvető adatszerkezetek és műveleteik
   • tömb, láncolt listák, verem, sor
   • gyakorlati példakód, megye.zip
4. Shapefile-ok kezelése Pythonban
   • kerület számítás, megjelenítés, megye.zip
   • PyShp dokumentáció
5. Rendezések, műveletigény
   • buborék-, beszúró- és maximum kiválasztó rendezés
   • gyorsrendezés, gyakorlati példakód
   • összefésülő rendezés
   • algoritmusok műveletigénye
   • néptáncos vizuális szemléltetés
6. Gráfok ábrázolási formái és bejárásai
   • gráfok ábrázolásai, szélességi bejárás, mélységi bejárás
   • szélességi bejárás példa, flights.csv
   • NetworkX tutorial és dokumentáció
7. Gráfalgoritmusok I.: minimális költségű utak
   • elsőbbségi sor, kupac
   • Dijkstra algoritmus, gyakorlati példakód, flights.csv
   • Bellman-Ford algoritmus
8. Őszi szünet
9. Gráfalgoritmusok II.: minimális költségű feszítőfák
   • minimális költségű feszítőfák
   • Prim algoritmus szemléltetése
   • Kruskal algoritmus szemléltetése
   • gyakorlati példakód, telepulesek.zip
10. Indexelés
    • bináris fa, bináris keresőfák
    • önkiegyensúlyozó fák: AVL fák, 2-3 fák
    • térbeli indexelési eljárások
      • Grid indexek: 4.1 fejezet
      • kd-fa: 4.2 fejezet
      • Adaptív kd-fa: 4.3 fejezet
      • Negyedelő-fa: 4.7 fejezet
      • R-fa: 5.1 fejezet
    • gyakorlati példakód
11. Topológia, algoritmusok és adatszerkezetek
12. Geometriai eredetű algoritmusok
    • Jarvis's march algoritmus
      Introduction to Algorithms / Új algoritmusok, 33.3 fejezet (ld. irodalomjegyzékben)
    • Graham's scan algoritmus
      Introduction to Algorithms / Új algoritmusok, 33.3 fejezet (ld. irodalomjegyzékben)
    • Quickhull algoritmus
      Introduction to the Design and Analysis of Algorithms, 5.5 fejezet (ld. irodalomjegyzékben)
    • Chan algoritmusa
    • gyakorlati példakód
13. Klaszterezés, osztályozás, szegmentálás algoritmusai
    • elméleti segédanyag (6.1 fejezet)
    • példák, gyakorlati példakód

Vizsgatematika