Babeş-Bolyai Tudományegyetem, Kolozsvár
Matematika és Informatika Kar
Képzési szint: licensz
Doménium: informatika
Szak: Informatika 
Előadás nyelve: magyar

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MMG0006	Számítógépes geometria	

Félév	Órák: C+S+L	Kategória	Típus	
4	2+0+1		opcionális	

II. Főállásban az Egyetem oktatói
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
Oláh-Gál Róbert	dr. 	egyetemi adjunktus	Informatikai rendszerek	*		*	

III. A tantárgy célkitűzései
Az előadás megismerteti a hallgatókkal az algoritmikus geometria alapfogalmait és eszközeit, amelyeket alkalmazhatnak az alkalmazott matematika, informatika és különböző tudományterületeken. A laborokon olyan feladatokat oldunk meg, amelyek elősegítik a tananyag jobb megértését és az alapfogalmak tisztázását és ezek alkalmazhatóságát a különböző tudományterületeken.	

IV. A tantárgy tartalma
Az előadáson szó lesz többek között gráfok, monoton sokszögekről, Voronoi-diagramokról, Delaunay-féle háromszögelésről, ezek magasabb dimenziójú általánosításairól, valamint alkalmazásukról fizikában, csillagászatban, biológiában és más tudományterületeken. Az előadás informális, intuitív stílusú,  a hangsúlyt elsősorban a különféle alkalmazásokra helyezzük.	

V. Könyvészet
1. DE BERG, M. - VAN KREFELD, M. - OVERMARS, M. - SCHWARZKOPF, O.:  Computational Geometry,  (2nd edition), Springer, 2000
2. BOISSONNAT,  J.-D. - YVINEC, M.: Algorithmic Geometry, Cambridge University Press, 1998
3. CORMEN, T.H. - LEISERSON, C.E. - RIVEST, R.L.: Introduction to Algorithms, The MIT Press, Cambridge, Massachusets, 1990
4. EDELSBRUNNER, H.: Algorithms in Combinatorial Geometry, Springer, 1997
5. GOODMAN, J. - O'ROURKE, J. (eds.): Handbook of  Discrete and Computational Geometry, CRC Press, 1997
6. OKABE, A. - BOOTS, B. - SUGIHARA, K.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley, 1992
7. O'ROURKE, J.: Art Gallery Theorems and Algorithms, Oxford University Press, 1987
8. O'ROURKE, J.: Computational Geometry in C, Cambridge University Press, 1994
9. PREPARATA, F.P. - SHAMOS, M.I.: Computational Geometry, Springer, 1985

VI. Az oktatói tevékenység heti tematikája
1. Előadás
1.1.	Az algoritmika alapjai
1.2.	Algoritmusok komplexitása
1.3.	Adatszerkezetek
1.4.	Vermek és sorok

2. Előadás
             2.1. Bináris fák  
             2.2. Piros és fekete fák
             2.3. B-fák

3. Előadás
              3.1. Gráfelméleti alapok
             3.2. Síkbeli gráfok és Euler tétele
             3.3.  Síkbeli gráfok ábrázolása

4. Előadás
              4.1. Szakaszok metszéspontjainak a meghatározása
              4.2. Egy algoritmus a szakaszok metszéspontjának a meghatározására
              4.3. Az algoritmus komplexitása

5. Előadás
              5.1. A sík két felosztásának fedése
              5.2. Két konvex sokszög fedésének a meghatározása

 6. Előadás
             6.1. Sokszögek háromszögesítése  
             6.2. A művészeti galéria tétele
             
7. Előadás
            7.1. Egy sokszög felbontása monoton részekre
            7.2. Egy monoton sokszög háromszögesítése

8. Előadás
           8.1. Konvex sokszögek
           8.2. Egy ponthalmaz konvex burkolója 
           8.3. A konvex burkoló meghatározása (Jarvis, Graham algoritmusok)

9. Előadás
            9.1.  Voronoi diagramok
            9.2.  Voronoi diagramok szerkesztése az „oszd meg és uralkodj” módszerrel

10. Előadás
            10.1. Egy véges halmaz háromszögesítése
            10.2. Delaunay háromszögesítés
            10.3. A Delaunay háromszögesítés meghatározása

11. Előadás
             11.1. Láthatosági gráfok
             11.2. A legrövidebb út 
             11.3. A láthatosági gráf  meghatározása

12. Előadás
             12.1. Geometriai felosztások
             12.2. Szelési feladatok
             12.3. Geometria objektumok szeléseinek meghatározása

13.  Előadás
13.1.	A geometria transzformációk módszere
13.2.	Félsíkok metszése
13.3.	A legkisebb területű háromszög meghatározása

14. Előadás
14.1.	Dinamikus és kinematikus Voronoi diagramok
14.2.	Dinamikus  Delaunay háromszögesítés

Laborok
  
    1.  Labor 
            – algoritmusok komplexitása
             – adatszerkezetek
             – vermek és sorok
   
   2.  Labor
             – bináris kereső fák 
             – piros-fekete fák
             – B-fák
  
    3. Labor
             – sokszögek háromszögesítése   
  
    4.  Labor
           – sima geometriai objektumok Voronoi diagramja
           – a felületek formák szerkesztése

    5. Labor
           – nem euklideszi metrikák
           – a  Poincaré modell            
 
    6. Labor
          – affin diagramok
           – súlyozott diagramok

    7. Labor
           – a vágások széleinek a megszerkesztése
    
    8. Labor
            – félsíkok metszetei
            – a legkisebb területű háromszög
    
     9. Labor 
           – a proteinek szerkezete

  10. Labor
         – a folyadékok dinamikája

   11. Labor
        – galaxisok eloszlása
  
   12. Labor
        – az oxigén atomok szerkezete
  
   13. Labor
       – egyéni projektek bemutatása (I)
   
   14. Labor
     – egyéni projektek bemutatása (II)	

VII. Alkalmazott didaktikai módszerek
Előadás, párbeszéd, problémafelvetés, feladatmegoldások, egyéni és csoportos projektek.	

VIII. Értékelés
– gyakorlati tevékenység: 60 %
– írásbeli vizsga : 40%	

IX. Kiegészítő könyvészet
1. OKABE, A. - BOOTS, B. - SUGIHARA, K.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley, 1992
2. O'ROURKE, J.: Art Gallery Theorems and Algorithms, Oxford University Press, 1987
3. O'ROURKE, J.: Computational Geometry in C, Cambridge University Press, 1994
4. PREPARATA, F.P. - SHAMOS, M.I.: Computational Geometry, Springer, 1985

	Dátum: 2009.11.26.				Előadás felelőse
							Dr. Oláh-Gál Róbert, egyetemi adjunktus

Tanszékvezető				Dékán
Dr. Boian Mircea, egyetemi tanár	Dr. Leon Ţâmbulea, egyetemi tanár