Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
Domeniul: Matematica
Programul de studii: Matematică Didactică - î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	specialitate	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 célja, hogy a diákokkal ismertessük az Algoritmikus geometria fogalmait és módszereit, amelyeknek jelentős alkalmazásaik vannak több tudományetrületen, mint:alkalmazott matematika, fizika, biologia, informatika. Itt megemlítjük a Voronoi diagramok alkalmazását az asztronomiában, molekuláris fizikában, bilogiában és más tudományterületeken.
 A diákok az elsajátított ismereteket és módszereket felahasználhatják az oktatásban és a kutatásban	

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. CHEN JIANER, Computational Geometry: Methods and Applications, Texas A & M University, 1996. 
2. BOISSONAT, J.-D.- YVINEC, M, Algorithmic Geometry, Cambridge, 1998. 
3. T.H. COrmen, CH. E. LEISERSON, R.R. RIVEST, Introducere în algoritmi,  Ediţia în limba română Computer Libris Agora, 2000.
       4. V. N. Serezhkin, V. A. Blatov, and A. P. Shevchenko. Voronoi-dirichlet     
     polyhedra for uranium(vi) atoms in oxygencontaining compounds. In In the Russian   
    Journal of Coordination Chemistry, volume 21, pages 155–161, 1995.
       5.  M. Serrano1, G. D. Fabritiis2, P. Espaol1, E. G. Flekky3, and P. V. Coveney.     
     Mesoscopic dynamics of voronoi fluid particles. In In the Journal of Physics A:   
     Mathematics and General, volume 35, pages 1605–1625, 2002.
       6. V. N. Serezhkin, V. A. Blatov, and A. P. Shevchenko. Voronoi-dirichlet     
         polyhedra for uranium(vi) atoms in oxygencontaining compounds. In In the Russian   
          Journal of Coordination Chemistry, volume 21, pages 155–161, 1995.
       7.  M. Serrano1, G. D. Fabritiis2, P. Espaol1, E. G. Flekky3, and P. V. Coveney.     
       Mesoscopic dynamics of voronoi fluid particles. In In the Journal of Physics A:   
       Mathematics and General, volume 35, pages 1605–1625, 2002.
      8. D. Stora, P.O. Agliati, M.P. Cani, F. Neyret, and J.D. Gascuel. Animating lava    
      flows. In Graphics Interface, 1999.
      9. L. Zaninetti. The galaxies distribution as given from the voronoi diagrams. In In     
    the Journal of Astronomy and Astrophysics, Italy.
     10. F. M. Richards. The interpretation of protein structures: total volume, group     
          volume distributions, and packing density. In In the Journal of Molecular Biology,   
           volume 82, pages 1–14, 1974.
     11. W. L. Roque and H. Choset. The green island formation in forest fire modeling 
           with voronoi diagrams. In In the 3rd  Center for Geometric Computing Workshop    
           on Compuational Geometry, 1998.	

VI. Az oktatói tevékenység heti tematikája
  
 Előadások

  1. Előadás: Gráfok
     -  a gráfelmélet elemei
     -  síkgráfok,  Euler tétele

  2. Előadás: Egyenesek metszése
             - szakaszok metszése
             - algoritmusok a szakaszok  metszéspontjainak meghatározására
             - algoritmusok komplexitása

  3. Előadás:A sík felosztása             
         - a sík két egymást fedő felosztásának meghatározása
          - két egymást fedő sokszög meghatározása

  4. Előadás: Sokszögek háromszögesítése  
         - a művészeti galleria tétele
         - egy sokszög felbontása monoton részekre

  5. Előadás: Felbontások          
          - egy monoton sokszög háromszögesítése
          -egy sokszög háromszögesítése

  6. Előadás:  Konvex halmazok
           - egy ponthalmaz konvex burkolójának a meghatarozása
           -konvex burkoló meghatározása(Jarvis,  Graham algoritmusai)

  7. Előadás: Voronoi diagramok
         - Voronoi diagramok és azok alapvető  tulajdonságai
         - Voronoi diagramok szerkesztése a  “divide et impera” algoritmussal

  8. Előadás: Háromszögesítések
           - egy véges ponthalmaz háromszögesítése 
           - a Delaunay háromszögesítés
           - a Delaunay háromszögesítés meghatározása

  9. Előadás: Geometriai felbontások
           - vágások peremének a megatározása
           - vágások peremének a megszerkesztése

  10. Előadás: Dinamikus és kinematikus Voronoi diagramok 
            - dinamikus és kinematikus Voronoi  diagramok
            - dinamikus Delaunay háromszegesítés és   alkalmazásai

  11. Előadás:  Nagyobb dimenziók
            - Voronoi diagramok nagyobb  dimenziókban               
            - Delaunay felbontások
            - egy alkalmazás a csillagászatban     

  12. Előadás:  Egy alklamazás a biologiában             
         -  növényfajták ábrázolása Voronoi diagramok segítségével
         - egy alkalmazás a növények növekedésében           

  13. Előadás: Egy alkalmazás a proteinek szerkezetének leírásában     
           -  a Voronoi diagramok alkalmazása a  proteinek szerkezetének leírásában          
           -  a proteinek térfogatának kiszámítása

 14.  Előadás: Egy fizikai alkalmazás
          - az oxigén atomok szekezete
          - egy alkalmazás a folydékok mehanikájában

     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. F.P. PREPARATA-M.I. SHAMOS ,Computational Geometry, Springer, 1985. 
 2. J. O'ROURKE , Computational, Geometry in C, Cambridge, 1993. 
 3. M. DE BERG , Computational Geometry, Springer, 1997. 
 4. EDELSBRUNNER H., Algorthims in Combinatorial Geometry, Springer-Verlag, Berlin, 1987.
 5. T.H. Cormen, CH. E. LEISERSON, R.R. RIVEST, Introducere în algoritmi,
  Ediţia în limba română Computer Libris Agora, 2000.	

	Dátum,						Eloadás felelose,
	
        2007.04.24                          			Prof. Dr. VARGA Csaba Gyorgy