Cserép Máté honlapja


Gyorslinkek: tartalom, navigáció.


Oktatás » ELTE » Térinformatikai algoritmusok » 2017/2018 ő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 vizsgajegyet szereznek.
A vizsgáztatás vegyes rendszerben történik: a rendes vizsgák írásbeliek, az utóvizsga szóbeli számonkéréssel kerül megvalósí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

Java tananyagok

  • J. Nyékyné Gaizler: Java 2 útikalauz programozóknak 5.0
  • B. Bates, K. Sierra: Head First Java / Agyhullám Java

Tematika

  1. Elemi algoritmusok
  2. Tanítási szünet (UNESCO Egyetemi Sport Nemzetközi Napja)
  3. Alapvető adatszerkezetek és műveleteik
  4. Rendezések, műveletigény
  5. Fa adatstruktúrák
  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. Térbeli indexelési eljárások
    • Grid indexek: 4.1 fejezet
    • kd-fa: 4.2 fejezet
    • Negyedelő-fa: 4.7 fejezet
    • R-fa: 5.1 fejezet
  11. Topológia, algoritmusok és adatszerkezetek
  12. Geometriai eredetű algoritmusok
    • Jarvis's march algoritmus
      Új algoritmusok, 33.3 fejezet (ld. irodalomjegyzékben)
    • Graham's scan algoritmus
      Új algoritmusok, 33.3 fejezet (ld. irodalomjegyzékben)
    • Quickhull algoritmus
  13. Klaszterezés, osztályozás, szegmentálás algoritmusai

Programozási feladatok

A kitűzött házi feladatok megoldása opcionális, de minden helyes megoldás 1-2 ponttal növeli az írásbeli vizsgán elért pontszámot. A feladatokat tetszőleges programozási nyelven meg lehet oldani.
A megoldásokat a NEPTUN tanulmányi rendszerben kell feltölteni a kiírt határidőig.

1. feladat (2 pont): Határozzuk meg melyik a legkisebb kerületű magyar megye! A megyék adatai a hun_megye.txt segédfájlban adottak. A fájl formátuma a következő:

  • Az első sor a megyék számát tartalmazza (N), a fájlnak további 2*N sora van.
  • Minden megyét további 2 sor ír le:
    • Az első sor a megye nevét és a koordináták számát (K) tartalmazza.
    • A második az adott megyét leíró poligon (x;y) koordinátapárjai (összesen 2*K lebegőpontos szám).
  • A sorok elemeit szóközök választják el.

A fájlkezelési alapokra példa a FileInput.zip állományban található.
Megoldás: MinPerimeter.java

2. feladat (1 pont): Határozzuk meg az N legnagyobb kerületű magyar megyét! A megyék adatai az előző feladatból már ismert hun_megye.txt segédfájlban adottak. Az N értékét a standard (konzol) inputról kell beolvasni. A feladatot tetszőlegesen választott rendezéssel meg lehet oldani.

3. feladat (1 pont): Határozzuk meg egy bináris (kereső)fa magasságát. A bináris fához kiindulási példa implementáció a 4. előadás példakódjában található, ebben az esetben az elkészítendő művelet szignatúrája: public int BinarySearchTree::height().