Cserép Máté honlapja


Gyorslinkek: tartalom, navigáció.


Oktatás » ELTE » Térinformatikai algoritmusok » 2018/2019 ő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 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:

9-10 pont jeles
7-8 pont
5-6 pont +1 jegy a szóbeli vizsgán (amennyiben legalább elégséges)

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
  2. Elemi algoritmusok
  3. Alapvető adatszerkezetek és műveleteik
  4. Shapefile-ok kezelése Pythonban
  5. Rendezések, műveletigény
  6. Gráfok ábrázolási formái és bejárásai
  7. Gráfalgoritmusok I.: minimális költségű utak
  8. Őszi szünet
  9. Gráfalgoritmusok II.: minimális költségű feszítőfák
  10. Indexelés
  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