fişa disciplinei
1. Date despre program
1.1 Instituţia de învăţământ superior	Universitatea Babes-Bolyai Cluj-Napoca	
1.2 Facultatea	Facultatea de Matematica si Informatica	
1.3 Departamentul	Departamentul de Informatica	
1.4 Domeniul de studii	Informatica	
1.5 Ciclul de studii	Licenta	
1.6 Programul de studiu / Calificarea	Informatica	

2. Date despre disciplină
2.1 Denumirea disciplinei	Algoritmica grafelor	
2.2 Titularul activităţilor de curs	Conf.Dr. Teodor Toadere	
2.3 Titularul activităţilor de seminar	Conf.Dr.Teodor Toadere	
2.4 Anul de studiu	3	2.5 Semestrul	5	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ă	4	Din care: 3.2 curs	2	3.3 seminar/laborator	2	
3.4 Total ore din planul de învăţământ	14	Din care: 3.5 curs	28	3.6 seminar/laborator	28	
Distribuţia fondului de timp:	Ore	
Studiul după manual, suport de curs, bibliografie şi notiţe	50	
Documentare suplimentară în bibliotecă, pe platformele electronice de specialitate şi pe teren	20	
Pregătire seminarii/laboratoare, teme, referate, portofolii şi eseuri	30	
Tutoriat	10	
Examinări 	20	
Alte activităţi: ..................	0	
3.7 Total ore studiu individual	100	
3.8 Total ore pe semestru	75	
3.9 Numărul de credite	6	

4. Precondiţii (acolo unde este cazul)
4.1 de curriculum	•		
4.2 de competenţe	•		

5. Condiţii (acolo unde este cazul)
5.1 De desfăşurare a cursului	•		
5.2  De desfăşurare a seminarului/laboratorului	•		

6. Competenţele specifice acumulate
Competenţe profesionale	- Prezentarea notiunilor de teoria grafelor
- Dobandirea de catre studenti a unui instrument de modelare a problemelor din diferite domenii.
- Insusirea si programarea unor algorimi din teoria grafelor.	•	Cunoasterea, intelegerea si folosirea conceptelor de baza din Informatica teoretica.	
Competenţe transversale	•		•	Cunoasterea momentelor mai importante din istoria calculatoarelor si istoria Informaticii si cunoasterea celor mai importanti oameni din Informatica
•	Capacitatea de a vedea Informatica ca pe un tot unitar si, prin prisma aceasta, capacitatea de a vedea interconexiuni intre diferitele domenii de studiu ale Informaticii; Capacitatea de a tine cursuri despre evolutia in timp a Informaticii  	

7. Obiectivele disciplinei (reieşind din grila competenţelor acumulate)
7.1 Obiectivul general al disciplinei	•	Obtinerea unei imagini de ansamblu a Algorimicii Grafelor cunoasterea si intelegerea notiunilor, modelelor generale de probleme si algoritmilor de rezolvare a acestora	
7.2 Obiectivele specifice

	•	Realizarea unor produse informatice de rezolvare pe diferite problelme specifice	

8. Conţinuturi
8.1 Curs	Metode de predare	Observaţii	
1. Notiuni de baza: multigraf orientat, neorientat, graf, subgraf, graf partial, drum, circuit, lant, ciclu (simplu, elementar, eulerian, hamiltonian), reprezentari ale grafelor (geometric, matricial, cu dictionare), grafe tare conexe, conexe (alg. pentru determinarea componentelor conexe).
2. Drumuri in grafe: lungimea unui drum (matricea distantelor, centru, raza, diametru), valoarea unui drum, optimizari in multimea drumurilor, algoritmul lui Moore-Dijkstra, algoritmul lui Bellman-Kalaba, algoritmul lui Ford, algoritmi matriceali (Floyd-Hu, Dantzig, Floyd-Hu-Warshall), drum critic, drumuri Euleriene, drumuri Hamiltoniene.
3. Numere fundamentale in teoria grafelor: numar de stabilitate interna, algoritm pentru determinarea multimilor interior stabile, numar de stabilitate externa, algoritm pentru determinarea multimilor exterior stabile, numar cromatic, numar ciclomatic.
4. Arbori si paduri: notiuni generale, algoritmii lui Kruskal si Prim. 
5. Grafe planare
6. Fluxuri in retele de transport: definitii de baza, algoritmul lui Ford-Fulkerson, extensii ale algoritmului lui Ford-Fulkerson, fluxuri de cost minim.
7. Cuplaje in grafe: definitii, algoritm pentru determinarea cuplajului maxim, algoritm pentru determinarea cuplajului de pondere maxima.
8. Probleme extremale (teoremele lui Ramsey si Turán)
9. Probleme de numarare si enumerare.	Expunere, descriere, explicatii, exemple	Un curs dureaza 2 ore si exista un curs in fiecare saptamana	
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: Combinatiroca 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
9. http://www.wikipedia.org

Culegeri de probleme:
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.
	
8.2 Seminar / laborator	Metode de predare	Observaţii	
La fiecare seminar, unul la doua saptamani, probleme (teoreme) pe care le rezolva studentii folosind notiunile predate.
La fiecare laborator, unul la doua saptamani, fiecare student primeste cate o tema pe care sa o rezove, sa elaboreze o documentatie si sa o predea la laboratorul urmator. 	

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ă
•	Cursul ofera o imagine de ansamblu asupra modelarii cu ajutorul grafelor, ofera studentului o expertiza generala asupra rezolvarii de probleme cu modele din Teoria Grafelor.

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	70%	
10.5 Seminar/laborator	Realizarea unor produse informatice (aplicatii) documentatiile corespunzatoare	Evaluare lucrarilor realizate	20%	
				
10.6 Standard minim de performanţă	
•	Studentul trebuie sa obtina minim nota 4 prin insumarea noteler de la examenul scris si de la laborator. 

Data completării		Semnătura titularului de curs		Semnătura titularului de seminar
..........................		Conf.Dr.Teodor Toadere		Conf.Dr.Teodor Toadere

Data avizării în departament			           Semnătura directorului de departament	
...........................................					Prof. Dr. Bazil Parv