Cod : I317
Titular curs : Conf. dr. M. Cosulschi
Forma de invatamant : Informatica (3 ani)
Ciclul : 1 Anul : 2
Semestrul : 1, Curs : 2h, Laborator : 2h
Nr. credite : 6
Profil : Informatica
Specializare : Informatica
Tip disciplina : obligatorie
Categoria formativa : fundamentala

Obiective:

• cunoasterea si utilizarea adecvata a notiunilor specifice limbajului utilizat in teoria grafurilor;
• explicarea si interpretarea unor idei, proiecte, procese, precum si a continuturilor teoretice si practice ale teoriei grafurilor;
• proiectarea, implementarea si evaluarea unor aplicatii ale grafurilor in diverse domenii;
• deprinderea metodelor directe si indirecte, specifice rezolvarii problemelor matematice;

Continutul cursului:

• Algoritmi si complexitatea calculului
  1. Complexitatea calculului;
  2. Complexitate asimptotica;
  3. Aplicatii ale notatiilor asimptotice;
• Grafuri finite neorientate
  1. Definitii. Operatii pe grafuri;
  2. Metode de reprezentare;
  3. Parcurgeri de grafuri;
  4. Grafuri conexe. Muchie critica;
• Cicluri hamiltoniene si euleriene intr-un graf neorientat;
• Arbori binari
  1. Metode de reprezentare;
  2. Metode de parcurgere;
  3. Arbori binari de cautare. Arbori binari de cautare optimali;
• Arbori oarecare
  1. Metode de reprezentare;
  2. Metode de parcurgere;
  3. Arbori de acoperire de cost minim: algoritmul lui Boruvka, algoritmul lui Prim, algoritmul lui Kruskal;
  4. Structuri de date pentru multimi disjuncte;
• Grafuri orientate
  1. Metode de reprezentare si parcurgere;
  2. Sortare topologica;
  3. Componente tare conexe: algoritmul lui Kosaraju, algoritmul lui Tarjan, algoritmul lui Gabow;
• Distante in grafuri
  1. Drumul minim de la un varf la celelalte varfuri: algoritmul lui Moore, algoritmul lui Dijkstra;
  2. Drumuri minime intre toate perechile de varfuri: algoritmul lui Roy-Floyd-Warshall;
• Fluxuri in retele de transport
  1. Retea de transport. Flux. Taietura;
  2. Graf rezidual. Drum de ameliorare. Flux maxim–taietura minima
  3. Algoritmul Ford-Fulkerson.

1. M. Cosulschi, Algoritmica grafurilor si aplicatii, Editura Universitaria, Craiova, 2014.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introducere in Algoritmi,Computer Libris Agora, Cluj-Napoca, 1999.
3. L. Livovschi, H. Georgescu, Analiza si sinteza algoritmilor, Ed. Stiintifica si Enciclopedica, Bucuresti, 1986.
4. I. Tomescu, Combinatorica si teoria grafurilor, Tipografia Universitatii din Bucuresti, 1978.
5. C. Croitoru, Tehnici de baza in optimizarea combinatorie, Editura Univ. Al. I. Cuza Iasi, Iasi, 1992.
6. J.-C. Fournier, Graph Theory and Applications, Wiley-Blackwell, 2009.
7. D. Jungnickel, Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics, 3rd Edition, Springer, 2008.

Material didactic:

1. Algorithmic Graph Theory and Sage

Pachete software:

1. Leda;
2. The Boost Graph Library;
3. AllegroGraph - o baza de date scalabila pentru date RDF;

Alte cursuri:

1. Teoria Grafurilor si Combinatorica
2. Algoritmica grafurilor
3. Graph Algorithms, University of California at Irvine
4. Graph Algorithms, Slovak University of Technology in Bratislava