UAIC
Departamentul de Informatica

Algoritmica Grafurilor

ro en

Olariu Emanuel Florentin

Toamna/Iarna 2024-2025

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, mail: fe.olariu@gmail.com;  Frasinaru A. Cristian - C212, corpul C, telefon: 0232 20 15 46

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

Notare:

  • Activitatea de la seminar (teste max. 22 puncte, participare la rezolvarea problemelor max. aproximativ 20 puncte): 0-42 puncte.
  • Teme pentru acasa: trei seturi de exercitii, max. 16 puncte fiecare, 0-48 puncte. Fecare tema poate fi rezolvata in echipe de cel mult 4 studenti; fiecare student va fi lider/responsabil pentru cel putin o problema din setul aferent temei.
  • Test final in sesiune (obligatoriu): 0-70 puncte.
  • Pentru a sustine teza scrisa in sesiune sunt necesare cel putin 30 de puncte din cele maximum 90 puncte din activitatea de seminar si temele pentru acasa.
  • Din maximum 160 puncte limita de promovare este de 80 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.

 

Fisa cursului.

Situatiile la seminar. Bonusul pentru temele scrise in LaTeX a fost adaugat la punctajul problemei 1.

Rezultatele examenului din 20 februarie 2025:

Repartitia pe sali la examenul din 20 februarie 2025 (8:00 - 9:30):

  • grupele A1 - A5 in C2;
  • grupele B1 - B4 in C112;
  • grupele E1 - E3 si X in C309.

Cursuri: