fişa disciplinei

1. Date despre program
1.1 Instituţia de învăţământ superior	Universitatea Babeş-Bolyai Cluj-Napoca	
1.2 Facultatea	Facultatea de Matematică şi Informatică	
1.3 Departamentul	Departamentul de informatică	
1.4 Domeniul de studii	Informatică	
1.5 Ciclul de studii	Master	
1.6 Programul de studiu / Calificarea	Informatică didactică - ȋn limba romȃnă 	

2. Date despre disciplină
2.1 Denumirea disciplinei	Algoritmi din teoria grafurilor (pentru perfecţionarea profesorilor)	
2.2 Titularul activităţilor de curs	Lect.dr. Mihaiela Lupea	
2.3 Titularul activităţilor de seminar	Lect.dr. Mihaiela Lupea	
2.4 Anul de studiu	1	2.5 Semestrul	2	2.6. Tipul de evaluare	E	2.7 Regimul disciplinei	Obligatorie	

3. Timpul total estimat (ore pe semestru al activităţilor didactice)
3.1 Număr de ore pe săptămână	3	Din care: 3.2 curs	2	3.3 seminar/laborator	1 	
3.4 Total ore din planul de învăţământ	42	Din care: 3.5 curs	28	3.6 seminar/laborator	14	
Distribuţia fondului de timp:	ore	
Studiul după manual, suport de curs, bibliografie şi notiţe	38	
Documentare suplimentară în bibliotecă, pe platformele electronice de specialitate şi pe teren	20	
Pregătire seminarii/laboratoare,teme, referate, portofolii şi eseuri	55	
Tutoriat	10	
Examinări 	20	
Alte activităţi: proiect individual	15	
3.7 Total ore studiu individual	158	
3.8 Total ore pe semestru	200	
3.9 Numărul de credite	8	

4. Precondiţii (acolo unde este cazul)
4.1 de curriculum	Algoritmică şi programare (pentru perfectionarea profesorilor)
Structuri de date și complexitatea algoritmilor (pentru perfecţionarea profesorilor)	
4.2 de competenţe	Abilităţi medii de programare	

5. Condiţii (acolo unde este cazul)
5.1 De desfăşurare a cursului	Sală de curs cu videoproiector	
5.2  De desfăşurare a seminarului/laboratorului	Sală de laborator cu calculatoare dotate cu limbajele de programare Pascal, C, C++, Java.	

6. Competenţele specifice acumulate

Competenţe profesionale	
•	Dobândirea de către studenţi a noţiunilor teoretice de bază din domeniul teoriei grafurilor.
•	Insuşirea şi programarea unor algoritmi din teoria grafurilor. 
•	Utilizarea tehnicilor de programare: backtracking, greedy şi programarea dinamică în implementarea algoritmilor specifici grafurilor.  
•	Modelarea  problemelor din diferite domenii folosind grafuri.
	
Competenţe transversale	•	Abilitatea de a modela probleme din lumea reală folosind grafuri.
•	Executarea responsabilă a lucrărilor de laborator.
•	Aplicarea regulilor de muncă riguroasă și eficientă.
•	Manifestarea unor atitudini responsabile faţă de domeniul știinţific și didactic.
•	Respectarea principiilor și a normelor de etică profesională.	

7. Obiectivele disciplinei (reieşind din grila competenţelor acumulate)

7.1 Obiectivul general al disciplinei	
Prezentarea la nivel teoretic a conceptelor specifice din teoria grafurilor, introducerea algoritmilor de prelucrare a grafurilor si modelarea problemelor din diferite domenii folosind grafuri. 
	
7.2 Obiectivele specifice

	•	Cunoaşterea la nivel teoretic a conceptelor de bază şi a algoritmilor din teoria grafurilor. 
•	Implementarea de algoritmi specifici grafurilor folosind tehnicile: backtracking, greedy şi programarea dinamică.  
•	Modelarea  problemelor din diferite domenii folosind grafuri.

8. Conţinuturi
8.1 Curs	Metode de predare	Observaţii	
1.	Grafuri neorientate şi grafuri orientate – noţiuni de bază

2.	Algoritmi de bază în prelucrarea grafurilor
-	parcurgerile în lăţime şi în adâncime
-	determinarea componentelor conexe (respectiv, tare conexe)
-	sortarea topologică
-	determinarea punctelor de articulare ale unui graf conex

3- 4. Drumuri în grafuri şi optimizari în mulţimea drumurilor
-	algoritmul lui Moore-Dijkstra, algoritmul lui Bellman-Kalaba, algoritmul lui Ford, 
-	algoritmi matriceali (Floyd-Hu, Dantzig, Floyd-Hu-Warshall) 

5.    Arbori parţiali de cost minim: algoritmii lui Kruskal şi Prim

6-7. Arbori multicăi : B-arbori, arbori ‘roşu şi negru’, arbori ‘splay’

8.    Algoritmul euristic A* cu aplicaţii la planificarea căilor robotilor 

9.    Algoritmi greedy euristici în grafuri: colorarea grafurilor şi 
       problema comis-voiajorului

10.  Grafuri şi jocuri, grafuri AND/OR. 

11.  Fluxuri în reţele de transport: algoritmul lui Ford-Fulkerson,
       fluxuri de cost minim. 

12. Cuplaje în grafuri: definitii, algoritm pentru determinarea cuplajului maxim, algoritm pentru determinarea cuplajului de pondere maxima. 

13. Modelarea prin grafuri a proceselor economice.

14. Aplicaţii ale grafurilor în diferite domenii (chimie, sociologie)
	•	Expunerea interactivă
•	Explicaţia
•	Conversaţia
•	Demonstraţia didactică		
Bibliografie
1. BERGE C., Graphes et hypergraphes, Dunod, Paris 1970. 
2. B. ANDRÁSFAI: Introductory graph theory, Akadémiai Kiadó - North Holland, 1987. 
3. BERGE C., Teoria grafurilor si aplicatiile ei, Ed. Tehnica, 1972 
4. T. TOADERE: Grafe. Teorie, algoritmi si aplicatii , Ed. Albastra, Cluj-N.(ed.I, II si III), 2002 si 2009 
5. KÁSA ZOLTÁN: Combinatorica cu aplicatii, Presa Universitara Clujeana, 2003. 
6. CORMEN, LEISERSON, RIVEST: Introducere in algoritmi, Editura Computer Libris Agora, 2000 
7. ROSU A.: Teoria grafelor, algoritmi, aplicatii. Ed. Milit.1974 
8.CIUREA E., CIUPALA L., Algoritmi – algoritmii fluxurilor in retele, Ed. Matrix Rom, 2006 
11. HARRIS J. M., HIRST  J. L., MOSSINGHO M.J.: Combinatorics and Graph Theory, Second Edition. Springer 2008.Chapter 1: Graph Theory. Sections §1.1, §1.2 and §1.4.
 	
8.2 Seminar/Laborator	Metode de predare	Observaţii		
1.	Produs soft: 
-	alegerea modului de reprezentare a grafurilor 
-	 implementarea operaţiilor de citire, scriere şi  parcurgeri graf. 
2.	Crearea unei liste de enunţuri de probleme din lumea reală care se modelează folosind grafuri şi algoritmii prezentaţi în cursurile 1-4.
3.	Prelucrarea arborilor multicăi – exerciţii. 
4.	Prezentarea de către studenţi a referatelor  teoretice. 
5.	Analiza şi implementarea algoritmilor aleşi pentru produsul soft.
6.	Algoritmi euristici în grafuri – exerciţii. 
7.	Prezentarea şi evaluarea produselor soft realizate de către studenţi 	Explicaţii, dialog, studiu de caz	La fiecare două saptămâni se desfăşoară o şedinţă de câte 2 ore de seminar/laborator.

Fiecare student  are de  elaborat un  referat  teoretic, bazat pe lucrări ştiinţifice din domeniul teoriei grafurilor.

Studenţii vor realiza individual un  produs soft bazat pe algoritmi din domeniul teoriei grafurilor.	
Bibliografie
1.	KÁSA Z., TARTIA C., TAMBULEA L.: Culegere de probleme de teoria grafelor, Lito. Univ.  Cluj-Napoca 1979. 
2.	CATARANCIUC S., IACOB M.E., TOADERE T., Probleme de teoria grafelor, Lito. Univ. 
      Cluj-Napoca, 1994.
3.  TOMESCU I., Probleme de combinatorica si teoria grafurilor. Ed. Did. si Pedag. Bucuresti 1981

	

9. Coroborarea conţinuturilor disciplinei cu aşteptările reprezentanţilor comunităţii epistemice, asociaţiilor profesionale şi angajatori reprezentativi din domeniul aferent programului
•	Cursul respecta recomandările IEEE şi ACM legate de Curiculla pentru specializarea Informatică. 
•	Conţinutul disciplinei este în concordanţă cu conţinuturile disciplinelor similare ale altor centre universitare din tară și din străinătate.
•	Conţinutul disciplinei asigură cunoştintele din domeniul teoriei grafurilor prevăzute în programa şcolară de liceu, clasa a XI-a, specializarea Matematică-informatică intensiv informatică.

10. Evaluare
Tip activitate	10.1 Criterii de evaluare	10.2 Metode de evaluare	10.3 Pondere din nota finală(%)	
10.4 Curs	Cunoasterea principalelor notiuni si algoritmi pentru rezolvarea unor probleme teoretice sau practice. 
	       Examen scris în sesiune	40%	
10.5 Seminar/ activități laborator	1. Capacitatea de a sintetiza, compara şi extinde rezultate ştiinţifice specifice domeniului teoriei grafurilor.

2.Capacitatea de a realiza un produs soft bazat pe algoritmi din domeniul teoriei grafurilor.

3.Listă de probleme şi rezolvări de exerciţii 	1.	Prezentare referat teoretic bazat pe lucrări ştiinţifice din domeniul teoriei grafurilor.

2.	Implementarea unor algoritmi prezentaţi la curs.

3.	Activitate seminar
	25%

25%

10%	
10.6 Standard minim de performanţă	

Studentul trebuie să obţină cel puţin nota 5 la toate probele de evaluare. 

Data completării		Semnătura titularului de curs		Semnătura titularului de seminar
01.10.2014		             Lect.dr. Mihaiela Lupea           	Lect.dr. Mihaiela Lupea	

Data avizării în departament			           Semnătura directorului de departament	
							Prof. dr. Bazil Pârv