UAIC
Departmentul de Informatica

Algoritmica Grafurilor

ro en

Olariu Emanuel Florentin

Toamna/Iarna 2019-2020


Summary

Cursurile acopera tematici de baza in Teoria Algoritmica a Grafurilor. Cunostintele acumulate vor fi aplicate in dezvoltarea de algoritmi eficienti pentru rezolvarea problemelor de optimizare combinatoriala.


Administrativ

Cursuri: saptamanal in C2

Lectori:  Olariu E. Florentin- C212, corpul C, telefon: 0232 20 15 46, olariu at info dot uaic dot ro;  Frasinaru A. Cristian - C212, corpul C, telefon: 0232 20 15 46, acf at info dot uaic dot ro

Consultatii la birou: saptamanale, de preferat intalniri stabilite in prelabil prin e-mail.

Notare:

  • Activitatea de la seminar (prezenta max. 13 puncte, teste max. 12 puncte, participare 10 puncte): 0-35 puncte.
  • Teme pentru acasa: trei seturi de exercitii, max. 15 puncte fiecare, 0-45 puncte. Fecare tema poate fi rezolvata in echipe de 1-2 studenti.
  • Test final in sesiune: 0-70 puncte.
  • Pentru a sustine teza scrisa in sesiune sunt necesare cel putin 35 de puncte din cele maximum 80 puncte din activitatea de seminar si temele pentru acasa.
  • Din maximum 150 puncte limita de promovare este de 70 puncte.

Prerequisites: Cunostinte de baza in proiectarea algoritmilor si structuri de date.


Bibliografie:

  • Cormen T. H., C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009
  • Croitoru C., Tehnici de baza in optimizarea combinatorie, Editura Univ. "Al. I. Cuza", Iasi, 1992.
  • Croitoru C., Introducere in proiectarea algoritmilor paraleli, Editura Matrix Rom, Bucuresti, 2002.
  • Diestel R., Graph Theory, electronic edition.
  • Lovasz L., Combinatorial Problems and Exercises, 2nd edition, North Holland, 1993
  • Tomescu I., Probleme de combinatorica si teoria grafurilor, Editura didactica si pedagogica, Bucuresti, 1981.

Lista tematicilor:

  • Vocabularul Teoriei grafurilor.
  • Probleme de drum: traversarea grafurilor, drumuri de cost minim, conexiune.
  • Arbori partiali de cost minim: union-find, complexitate amortizata.
  • Teoria cuplajelor.
  • Fluxuri in retele.
  • Reduceri polinomiale intre probleme de decizie pe grafuri.
  • Abordarea problemelor NP-dificile.
  • Grafuri planare.
  • Tree decomposition.

 


Situatii la seminar:

Cursuri: