Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Ingineria Informatiei - 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.	Algebra, Analiza si 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. Laboratoarele 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. Algorithms and Applications, (3rd edition), Springer, 2008
2. CHEN, J. - Computational geometry. Methods and applications, Texas AM, 1996
3. MOUNT, D., Lectures in Computational Geometry, 1997
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
Week 1: Invelitori convexe in plan. Cazuri degenerate si robustete. [1 (sectiunile 1.1, 1.2), 2 (3.1)]
Week 2: Invelitori convexe. Constructia invelitorii convexe a unei multimi de puncte din plan. [1 
         cap.1), 2(4.2, 5.1), 
         3(lectia 2, 3)]
    Lab 1: Algoritmul lui Graham. Implementare [5 (cap 3)]
Week 3: Intersectii de segmente.. [1(2.1, 2.2), 3 (lectia 4), 2(3.3, 4.1)] 
Week 4: Determinarea suprapunerii a doua diviziuni ale planului. [1 (2.3), 3(lectia 5)] 
    Lab 2: Cautare si intersectii[5(cap 1, 7)]
Week 5: Problema galeriei de arta. Triangulari. [1 (3.1), 3(lectia 6)]
Week 6: Partitionarea unui poligon in parti monotone. Triangularea unui polygon monoton. [1 (3.2,   
         3.3), 2(4.4), 3(lectia 7)]

    Lab 3: Triangulari. Implementare [5(cap 1)]
Week 7: Intersectii de semiplane. [1 (4.1, 4.2, 4.3, 4.4), 3(lectia 8)]
Week 8: Localizarea unui punct. Aplicatia trapezoidala. [1 (6.1), 3(lectia 14)]

    Lab 4: Triangularea in timp liniar. Implementare [5(cap 2)]

Week 9: Un algoritm incremental pentru determinarea pozitiei.Cazuri degenerate. [1(6.2, 6.3), 
         3(lectia 15)]

Week 10: Problema oficiului postal.Diagrama Voronoi. [1 (7.1, 7.2), 2(5.2, 5.3), 3(lectia 18)]
    Lab 5: Implementarea algoritmului incremental [5(chap 5)]
Week 11: Diagrame Voronoi pentru segmente. [1 (7.3, 7.4), 2(4.3)]
Week 12: Triangularea Delaunay. [1 (9.1, 9.2, 9.3), 3(lectia 20)] 
    Lab 6: Algoritmi pentru triangularea Delaunay [5(cap 5)]
Week 13: Invelitori convexe in 3-dim. [1 (11.1, 11.2), 2(10.2)]

Week 14: Invelitori convexe si intersectii de semispatii. [1 (11.4), 2(10.3)]

    Lab 7: Implementarea algoritmului incremental [5(cap 5)].	

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 40%. Un examen scris, final, va conta în proporţie 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	

       Decan,							Sef de Catedra
	Prof. dr. Leon Tambulea				Conf. Dr.  BREAZ Simion Sorin

	Data,							Responsabil de curs,
	30.09.2009						Lect. TOPAN Liana Manuela