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
  • A. Levitin: Introduction to the Design and Analysis of Algorithms

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
    • Adaptív kd-fa: 4.3 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
      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
  13. Klaszterezés, osztályozás, szegmentálás algoritmusai

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

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.zip

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.
Megoldás: SortPerimeter.zip

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().
Megoldás: TreeHeight.zip

4. feladat (4 pont): Adottak Eruópa nagyvárosai közötti repülőjáratok és költségeik a flights.txt adatfájlban, a következő formátum szerint:

  • Az első sor a városok számát tartalmazza: N.
  • A következő N sor a városok neveit adja meg.
  • Az ezt követő sor a repülőjáratok számát definiálja: E.
  • A következő E sor a 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: keressük meg a Budapestről repülővel legfeljebb 1 átszállással elérhető városokat! (2 pont)
2. részfeladat: keressük meg a minimális költségű repülőutat Budapestről Európa többi nagyvárosába, ha az átszállások száma nem számít! (2 pont)

Komplex típus rendezhetővé tételére a 2. feladat megoldása mutat példát (Comparable interfész).
A gráfreprezentáció megvalósítható csúcsmátrixos vagy éllistás implementációval is; vagy felhasználható a Graph segédosztály, amely egy absztrakt interfészt kínál a gráf kezelésére:

  • 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

Példa felhasználás:
Graph graph = new Graph();
// Csúcsok hozzáadása
graph.add("A");
graph.add("B");
graph.add("C");
// Irányított élek hozzáadása súlyokkal
graph.set("A", "B", 10);
graph.set("A", "C", 20);
graph.set("B", "A", 30);

// Van-e él A-ból C-be?
bool x = graph.has("A", "C");
// Az A-ból C-be mutató él költsége?
int y = graph.get("A", "C");
// Az A-ból mely más csúcsok érhetőek el?
Set<String> z = graph.neighbours("A");

Megoldás: Graph.zip