Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
Domeniul: Matematica
Programul de studii: Matematică Computaţională (în limba maghiară)
Limba de predare: Maghiară

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MMG1007	Geometrie algoritmică	

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

II. Foállásban az  Egyetem  oktatói
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
VARGA Csaba Gyorgy	Dr. 	Prof.	Geometrie	*			

Társult oktatók
Név	Tudományos	Intézmény	Állás	Tevékenység 	
	fokozat		típusa	E	Sz	L	

III. A tantárgy célkituzései
Az előadás megismeterteti a a hallgatokkal az algoritmikus geometria alapfogalmait és eszközeit amelyeket alkalmazhatnak az alkalmazott matematika, informatika és különböző tudományterületeken. A szemináriumokon olyan feladatokat oldunk meg, amelyek elősegítik a tananyag jobb megértését és az alafogalmak tisztázását és ezek alaklmazható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 gáfok, monoton sokszögekről, Voronoi diagramokról, Delaunay háromszögelésről, ezek magasabb dimenzióju általánosiţásaikról valamint ezen fogalmak alkalmazásaikról fizikában, csillagászatban, biologiában és más tudományterületeken. Az előadás informális, intuitív stílusú (kerülve a túlzott absztraktizálást),  a hangsúlyt elsősorban a különféle alkalmazásokra helyezve.	

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íkgráfok és Euler tétele
             3.3.  Síkgrá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ásara
             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 haromszö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
13.4.	
14. Előadás

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

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

    5. Szeminárium:
           -   nem euklidészi metrikák
           - a  Poincare  modell            
 
    6. Szeminárium:
           -  affin diagramok
           - súlyozott diagramok

    7. Szeminárium:
           - a vágások széleinek a megszekesztése

    8. Szeminárium:
            - félsíkok metszetei
            - a legkisebb területű háromszög
    
     9. Szeminárium: 
           - a proteinek szerkezete
  10. Szeminárium:
         - a folyadékok dinamikája

   11. Szeminárium:
        - galaxisok eloszlása
  
   12. Szeminárium:
        -  az oxigén atomok szerkezete
  
   13. Szeminárium:
       -  egyéni dolgozat bemutatása (I)
   
   14. Szeminárium:
     - -  egyéni dolgozat bemutatása (II)	

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

VIII. Értékelés
                      -  szemináriumi tevekenység 30 %
                      - egyéni dolgozat bemutatása 30%
                      - szobeli vizsga                       40%	

IX. Kiegészíto 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,						     Eloadás felelose,
          2009.II.10					     Prof. Dr. VARGA Csaba Gyorgy

                                              Tanszékveztő

                                    Prof. Dr. Andrica Dorin