Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat

FISA DISCIPLINEI

Codul
Denumirea disciplinei
MMG1007 Geometrie algoritmică
Specializarea
Semestrul
Ore: C+S+L
Categoria
Statutul
Matematică Computatională - în limba maghiară
1
2+2+0
obligatorie
Matematică Computaţională - în limba maghiară
1
2+2+0
specialitate
obligatorie
Matematică Didactică - în limba maghiară
1
2+2+0
specialitate
obligatorie
Modelare Interdisciplinară - în limba maghiară
1
2+2+0
specialitate
obligatorie
Titularii de disciplina
Prof. Dr. VARGA Csaba Gyorgy,  csvargacs.ubbcluj.ro
Obiective
Scopul cursului este de a familiariza studentii cu notiunile si metodele geometriei algebrice, care se pot aplica in numeroase domenii de stiinta, cum ar fi matematica aplicata, fizica, biologia, informatica. Aici mentionam si aplicatiile diagramei lui Voronoi in astronomie, fizica moleculara, biologia, si altele. Studentii pot folosi cele invatate in cercetare si in predare. La curs punem accentul in principal la diferite aplicatii.
Continutul
Cursuri

Curs 1. Grafe
- elemente din teoria grafelor
- grafe planare, Teorema lui Euler
Curs 2. Intersectia segmentelor
- algoritm pentru determinare intersectiei segmentelor
- complexitatea algoritmilor
Curs 3. Divizia planului
- suprapunerea a doua diviziuni de plan
- suprapunerea poligoanelor
Curs 4. Triunghiularea poligoanelor generale
- teorema galeriei de arta
- descompunerara unui poligon in parti monotone
Curs 5. Triangularea poligoanelor monotone
Curs 6. Multimi convexe
- determinarea invelitoarei convexe a unei multimi (algoritmul lui Jarvis si algoritmul lui Graham)
Curs 7. Diagrame Voronoi
- Diagrame Voronoi si proprietati importante
- Constructia diagramei Voronoi folosind metoda “divide et impera”
Curs 8. Triangularea unei multimi finite de puncte
- determinarea triunghiularii Delaunay
Curs 9. Diviziuni geometrice
- determinarea si constructia taieturilor
Curs 10. Diagrame dinamice si kinematice Voronoi
Curs 11. Dimensiuni mai mari
- Diagrame Voronoi in dimensiuni mai mari
- triangulare Delauney
- aplicatie in astronomie
Curs 12. O aplicatie in biologie
- cresterea plantelor cu ajutorul diagramei lui Voronoi
Curs 13. O aplicatie a diagramei Voronoi in descrierea structurii proteinului
- calcularea volumului proteinului
Curs 14. O aplicatie in fizica
- structura atomului de oxigen
- o aplicatie in mecanica fluidelor

Seminarii

Seminar 1. complexitatea algoritmilor,structure de date
Seminar 2. arbori de cautare, B-arbori
Seminar 3. triangularea poligoanelor
Seminar 4. Constructia lantului sigma la diagrame Voronoi
Seminar 5. metrici neeuclidiene, modelul lui Poincare
Seminar 6. diagrame afine, diagrame ponderate
Seminar 7. triunghiul cu aria cea mai mica
Seminar 8. intersectia semiplanelor
Seminar 9. structura proteinelor
Seminar 10. dinamica fluidelor
Seminar 11. descrierea galaxiilor
Seminar 12. structura atomului de oxigen
Seminar 13. prezentare referat (I)
Seminar 14. prezentare referat (II)
Bibliografie
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 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 the Russian Journal of Coordination Chemistry, volume 21, pages 155–161, 1995.
7. 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 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 the 3rd Center for Geometric Computing Workshop on Compuational Geometry, 1998.
Evaluare
-activitate la seminarii 30%
-prezentare referat 30%
-examen oral 40%
Legaturi: Syllabus-urile tuturor disciplinelor
Versiunea in limba engleza a acestei discipline
Versiunea in format rtf a acestei discipline