Cserép Máté honlapja

Gyorslinkek: tartalom, navigáció.

Oktatás » ELTE » Algoritmusok a geoinformatikában » 2022/2023 ősz

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 a félév során három beadandó feladatot készítenek el, amelyek értékelése ötfokozatú skálán (1-5) történik. Az aláírás feltétele mindhárom beadandó feladat legalább elégséges szintre (2) történő teljesítése. A gyakorlati jegy az így szerzett 3 érdemjegy számtani közepe.
A megoldásokat a NEPTUN tanulmányi rendszerben kell feltölteni a kiírt határidőig.

Az előadás kollokviummal zárul, amely szóbeli vizsga formájában kerül lebonyolításra.

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

Előadás tematika

  1. Alapvető adatszerkezetek és műveleteik
  2. Elemi algoritmusok
    • Összegzés, számlálás, maximum kiválasztás, lineáris keresés, bináris keresés
    • Feltételes változatok
    • Elméleti segédanyag
  3. Rendezések, műveletigény
  4. Fa adatstruktúrák
  5. Gráfok ábrázolási formái és bejárásai
  6. Gráfalgoritmusok I.: minimális költségű utak
  7. Gráfalgoritmusok II.: minimális költségű feszítőfák
  8. Térbeli indexelés
  9. 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
  10. Klaszterezés, osztályozás, szegmentálás algoritmusai

Vizsga

Vizsgatematika

Gyakorlati tematika

  1. Python alapismeretek
  2. Elemi műveletek, elágazások, hibakezelés
  3. Iteráció, kollekciók
  4. Függvények
  5. Elemi algoritmusok
  6. Rendező algoritmusok
  7. Komplex adatszerkezetek
  8. Táblázatos adatok kezelése
  9. Skaláris adatok vizualizációja
  10. Vektoros téradatok olvasása és feldolgozása
  11. Raszteres téradatok olvasása és feldolgozása
  12. Gráfalgoritmusok
  13. Térbeli indexelés
  14. Konvex-burok algoritmusok
  15. Klaszterező algoritmusok

Gyakorlati segédanyagok