Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
FISA DISCIPLINEI
| MMG1007 | Geometrie algoritmică |
| Titularii de disciplina |
Prof. Dr. VARGA Csaba Gyorgy, csvarga cs.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 |