Cserép Máté honlapja

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.

Vizsgaeredmények

Tematika

1. Elemi algoritmusok
   • Elméleti segédanyag
   • Gyakorlati példakód
2. Alapvető adatszerkezetek és műveleteik
   • E-learning tananyag: 3-9. fejezet
   • Gyakorlati példakódok
3. Rendezések, műveletigény
   • E-learning tananyag: 15., 17., 19., 2. fejezet
   • Gyorsrendezés
   • Gyakorlati példakódok
4. Fa adatstruktúrák
   • E-learning tananyag: 8., 12. fejezet
   • AVL fák, 2-3 fák
   • Gyakorlati példakód
5. Gráfok ábrázolási formái és bejárásai
   • E-learning tananyag: 23-24., 29. fejezet
6. Gráfalgoritmusok I.: minimális költségű utak
   • E-learning tananyag: 25-26. fejezet
7. -
8. Őszi szünet
9. Gráfalgoritmusok II.: minimális költségű feszítőfák
   • E-learning tananyag: 28. fejezet
10. Térbeli indexelési eljárások
    • Digitális jegyzet: 4.1, 4.7, 5.1 fejezet
11. Topológia, algoritmusok és adatszerkezetek
    • Előadás diasor
12. -
13. Geometriai eredetű algoritmusok
    • Konvex burok:
      Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 33.3 fejezet
      Berg, Cheong, Kreveld, Overmars: Computational Geometry, 11. fejezet
    • 3D-s domborzat modellezés: digitális jegyzet, 5.1 fejezet
14. Klaszterezés, osztályozás, szegmentálás algoritmusai
    • Digitális jegyzet: 6.1 fejezet
    • Példák

Vizsgatematika
Vizsga 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 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 hétfő éjfélig lehet feltölteni a NEPTUN tanulmányi rendszerbe (Neptun Meet Street -> Feladatok).

7. beadandó feladat: Egy szerverfarm üzemeltető vállalkozás több európai nagyvárosban is rendelkezik központtal, amelyek összefüggő hálózatba vannak kapcsolva. Határozzunk meg egy körmentes topológiát a hálózatra, amely a teljes rendszer összköltségét is minimalizálja egyben (minimális feszítőfa)! A bemeneti adatokat a network.txt állomány tartalmazza. A fájl formátuma a következő:

• Az első sor a szerverközpontok számát tartalmazza: N.
• A következő N sor a szerverek telephelyeinek neveit adja meg.
• Az ezt követő sor a kapcsolatok számát definiálja: E.
• A következő E sor a kapcsolatok két végpontját és távolságukat adja meg. Az útvonalak irányítatlanok.

6. beadandó feladat: Implementáld Dijkstra minimális útkereső algoritmusát! Az eljárás szignatúrája lehet például az alábbi, ahol a costs a bementi csúcsmátrix a költségekkel (sorfolytonos reprezentáció), d és p tömbök az algoritmus kimenete:
public void dijkstra(double[] costs, double[] d, int[] p)
Az eljárás ettől eltérő szignatúrával és éllistás reprezentációval is implementálható.

5. beadandó feladat: 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

4. beadandó feladat: 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

3. beadandó feladat: Soroljuk fel a magyar megyéket kerületük szerint rendezetten! A megyék adatai az előző feladatokból már ismert hun_megye.txt segédfájlban adottak. A feladatot gyorsrendezéssel kell megvalósítani.
Megoldás: SortPerimeter.java

2. beadandó feladat: Határozzuk meg az N legnagyobb kerületű magyar megyét növekvő sorrendben! 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 a hatékonyság érdekében a tanult adatszerkezetekkel, és nem a maximum keresés algoritmusának N-szeri ismétlésével kell megvalósítani.
Példa bemenet: 3
Példa kimenet:
3. Pest
2. Bács-Kiskun
1. Borsod-Abaúj-Zemplén
Megoldás: MultipleMaxPerimeter.java

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

• Minden sor 1 megye adatát tartalmazza.
• A sorok első eleme a megye neve.
• A sorok további elemei az adott megyét leíró poligon (x;y) koordinátapárjai, szóközzel elválasztva.
• A poligon vonalláncok zártak.
• 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: MaxPerimeter.java

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
• 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