Cserép Máté honlapja

Gyorslinkek: tartalom, navigáció.

Oktatás » ELTE » Térinformatikai algoritmusok » 2016/2017 ő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. -
  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

Vizsgatematika
Korábbi feladatsorok: 2015. december 21. , 2016. január 11.

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 minden héten szerda 8 óráig lehet feltölteni a NEPTUN tanulmányi rendszerben.

1. feladat (1 pont): Határozzuk meg melyik a legnagyobb népsűrűségű magyar megye! A megyék adatai a megyek.txt segédfájlban adottak. A fájl formátuma a következő:

  • Minden sor 1 megye adatát tartalmazza.
  • Minden sor rendre az adott megye következő információiból áll:
    • név,
    • régió,
    • székhely,
    • terület (km2),
    • népesség (10.000 fő),
    • településeinek száma.
  • A sorok elemeit szóközök választják el.

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

2. feladat (1 pont): Soroljuk fel a magyar megyéket népsűrűségük szerint rendezetten! A megyék adatai az előző feladatokból már ismert megyek.txt segédfájlban adottak. A feladatot tetszőlegesen választott rendezéssel meg lehet oldani.
Megoldás: SortDensity.java

3. feladat (2 pont): Határozzuk meg egy bináris (kereső)fa leveleinek számát. A bináris fához kiindulási példa implementáció az 5. előadás példakódjában található, ebben az esetben az elkészítendő művelet szignatúrája: public int BinarySearchTree::leafCount().
Az algoritmus leírása megtalálható a digitális jegyzetben.
Megoldás: LeafCount.zip

4. feladat (2 pont): Keressük meg a Budapestről repülővel legfeljebb 1 átszállással elérhető városokat! A városok és az útvonalak adatai a flights.txt adatfájlban adottak. A fájl formátuma a következő:

  • Az első sor a települések számát tartalmazza: N.
  • A következő N sor a városok neveit adja meg.
  • Az ezt követő sor az útvonalak számát definiálja: E.
  • A következő E sor az repülőjáratok két végpontját adja meg. Az útvonalak irányítatlanok.

Megoldás: BreadthFirstSearch.zip

5. feladat (3 pont): Keressük meg a minimális költségű repülőutat (az átszállások száma nem számít) Budapestről Európa többi nagyvárosába! A városok és a járatok adatai a flights2.txt adatfájlban adottak. A fájl formátuma a következő:

  • Az első sor a települések számát tartalmazza: N.
  • A következő N sor a városok neveit adja meg.
  • Az ezt követő sor az útvonalak számát definiálja: E.
  • A következő E sor a repülőjáratok két végpontját és költségét adja meg. Az útvonalak irányítatlanok, mindkét irányba ugyanolyan áron közlekednek a repülők.

1. részfeladat: adjuk meg a minimális költséget városonként (2 pont).
2. részfeladat: adjuk meg a minimális költséghez tartozó útvonalat is városonként (1 pont).

Komplex típus rendezhetővé tételére a 2. feladat megoldása mutat példát (Comparable interfész).
A bedandóhoz további segédletként szolgál a Graph reprezentációs osztály a következő interfésszel:

  • void add(String vertex): csúcs hozzáadása
  • void set(String source, String target, Integer cost): irányított él hozzáadása / módosítása
  • Boolean has(String vertex): csúcs létezésének lekérdezése
  • Boolean has(String source, String target): él létezésének lekérdezése
  • Integer get(String source, String target): élköltség lekérdezése
  • void remove(String vertex): csúcs eltávolítása
  • void remove(String source, String target): él eltávolítása
  • Set<String> neighbours(String vertex): csúcs szomszédainak lekérdezése

Megoldás: Dijkstra.zip

6. feladat (2 pont): Határozzunk meg egy körmentes topológiát az alábbi repülőút hálózatra, amely a teljes rendszer összköltségét is minimalizálja egyben (minimális feszítőfa)! A városok és a járatok adatai a flights2.txt adatfájlban adottak, a fájl formátuma az 5. feladatnál definiált.

Megoldás: Prim.zip