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 6 beadandó programozási feladat teljesítésével szerezhető.
A beadandó feladatokra egyenként 5, összesen 30 pont szerezhető, az elérhető pontszám alapján a következő érdemjegy kerül megajánlásra:
| 26-30 pont | jeles |
| 21-25 pont | jó |
| 16-20 pont | közepes |
Megajánlott jegy hiányában - vagy annak elutasítása esetén - a kurzus írásbeli/szóbeli vizsgával teljesíthető.
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
- Bevezetés, Python alapismeretek
- Alapvető adatszerkezetek és műveleteik
- Elemi algoritmusok
- Shapefile-ok kezelése Pythonban
- Rendezések, műveletigény
- Gráfok ábrázolási formái és bejárásai
- Őszi szünet
- Gráfalgoritmusok I.: minimális költségű utak
- Gráfalgoritmusok II.: minimális költségű feszítőfák
- Térbeli 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
- Jupyter munkafüzet, telepulesek.zip
- Topológia, algoritmusok és adatszerkezetek
- -
- Geometriai eredetű algoritmusok; Klaszterezés, osztályozás, szegmentálás algoritmusai
- 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
- Elek István: Adatbázisok, térképek, információs rendszerek (6.1 fejezet)
- Jupyter munkafüzet
- Jarvis's march algoritmus