Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu română
Limba de predare: Română

SYLLABUS

I. Date generale
Codul	Disciplina	
MMG0006	Geometrie computaţională	

Semestrul	Ore: C+S+L	Categoria	Statutul	
4	2+1+1	Specialitate	opţională	

II. Cadre didactice cu norma de bază în Universitate
Numele şi	Titlul	Gradul	Catedra	Tipul activităţii	
prenumele	ştiinţific	didactic		C	S	L	
ŢOPAN Liana Manuela	Dr. 	Lect.	Geometrie	*			

Cadre didactice asociate
Numele şi	Titlul	Instituţia	Tipul	Tipul activităţii	
prenumele	ştiinţific		postului	C	S	L	

III. Obiectivele disciplinei
Scopul cursului este sǎ facǎ o introducere în geometria algoritmicǎ şi sǎ prezinte instrumente folosite în matematica aplicatǎ, tehnologia informaţiei şi diferite alte domenii ale stiintei. Seminariile promoveazǎ o mai bunǎ întelegere a noţiunilor teoretice.	

IV. Conţinutul disciplinei
Fundamente algoritmice. Cǎutarea geometricǎ. Învelitori convexe. Probleme de apropiere. Diagrame Voronoi. Arbori. Intersecţii (de poligoane, de segmente, de semiplane). Geometria computaţionalǎ a dreptunghiurilor.	

V. Bibliografie
1. DE BERG, M. - VAN KREFELD, M. - OVERMARS, M. - SCHWARZKOPF, O.:  Computational Geometry,  (2nd edition), Springer, 2000
2. GOODMAN, J. - O'ROURKE, J. (eds.): Handbook of  Discrete and Computational Geometry, CRC Press, 1997
3. OKABE, A. - BOOTS, B. - SUGIHARA, K.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley, 1992
4. O'ROURKE, J.: Art Gallery Theorems and Algorithms, Oxford University Press, 1987
5. O'ROURKE, J.: Computational Geometry in C, Cambridge University Press, 1994	

VI. Tematica activităţilor didactice pe săptămâni
Sǎptǎmâna 1: Fundamente algoritmice. Condiţii geometrice. Modele de calcul.
Sǎptǎmâna 2: Cǎutare geometricǎ. Localizarea punctelor. Cǎutare regionalǎ.
Sǎptǎmâna 3: Învelitori convexe. Construcţia învelitorilor convexe în plan.
Sǎptǎmâna 4: Învelitori convexe în dimensiuni mai mari decât doi.
Sǎptǎmâna 5: Aplicaţii în statisticǎ.
Sǎptǎmâna 6: Probleme de apropiere. Problema celei mai apropiate perechi.
Sǎptǎmâna 7: Diagrama Voronoi.
Sǎptǎmâna 8: Arbori minimali euclidieni. Triangulǎri plane.
Sǎptǎmâna 9: Diagrame Voronoi generalizate. Intervale şi acoperiri.
Sǎptǎmâna 10: Intersecţii plane. Intersecţia poligoanelor convexe. Intersecţia segmentelor de dreaptǎ.
Sǎptǎmâna 11: Intersecţia semiplanelor. Nucleul unui poligon plan.
Sǎptǎmâna 12: Intersecţii spaţiale. Intersecţia poligoanelor convexe. Intersecţia semispaţiilor.
Sǎptǎmâna 13: Geometria dreptunghiurilor. Aria şi perimetrul unei reuniuni de dreptunghiuri.
Sǎptǎmâna 14: Conturul unei reuniuni de dreptunghiuri. Intersecţia dreptunghiurilor.	

VII. Metode didactice folosite
Expunerea, demonstraţia, problematizarea, aloritmizarea, exerciţiul.	

VIII. Evaluare
Vor fi douǎ lucrǎri de control pe parcursul semestrului. Notele acestor lucrǎri de control vor avea, fiecare, o pondere de 20% din nota finalǎ. Studenţilor li se va cere sǎ implementeze unii dintre algoritmi, ceea ce va avea ponderea de 20%. Un examen scris, final, va conta în proporţie de 20%. Activitatea din timpul semestrului are, şi ea, ponderea de 20%.	

IX. Bibliografie suplimentară
1. BOISSONNAT,  J.-D. - YVINEC, M.: Algorithmic Geometry, Cambridge University Press, 1998
2. CORMEN, T.H. - LEISERSON, C.E. - RIVEST, R.L.: Introduction to Algorithms, The MIT Press, Cambridge, Massachusets, 1990
3. EDELSBRUNNER, H.: Algorithms in Combinatorial Geometry, Springer, 1997
4. PREPARATA, F.P. - SHAMOS, M.I.: Computational Geometry, Springer, 1985	

	Data,	
       15.09.2008						         Titular curs,
					                          Lect. Dr. ŢOPAN Liana Manuela

Şef de Catedrǎ
Prof. Univ. Dr. ANDRICA Dorin