Tehnici De Optimizare Combinatoriala
QUICK INFO: CU 2h / SE 1h EXAMEN SCRIS / 7.5 CREDITE
ATENȚIE: Cursul s-a încheiat. Lista de subiecte de la d. prof. D. R. Popescu este aici.
PROGRAMA ANALITICA
- Reprezentarea retelelor, drumuri, cicluri si arbori partiali în grafuri. Probleme de fluxuri.
- Reprezentarea si analiza algoritmilor.
- Drumuri minime: algoritmi pentru definirea etichetelor, arborele drumurilor minime, distante minime în retele aciclice, algoritmul lui Dijkstra si implementarea lui Dial.
- Drumuri minime: algoritmi pentru corectarea etichetelor. Conditii de optimalitate, algoritmul generic de corectare a etichetelor, detectarea ircuitelor negative, algoritmul lui Floyd.
- Fluxuri maxime: Fluxuri si taieturi, algoritmul de etichetare, teorema flux maxim - taietura minima, fluxuri cu margini inferioare.
- Implicatii combinatoriale ale fluxurilor în retele: teorema lui Konig privind cuplajele maxime în grafurile bipartite, teoremele lui Menger privind conexitatea grafurilor.
- Fluxuri maxime: algoritmi polinomiali. Algoritmul de crestere a fluxului pe drumurile cele mai scurte, etichete de distante si retele stratificate, algoritmul preflow-push generic.
- Algoritmi de flux de cost maxim. Conditii de optimalitate, dualitate, algoritmul drumurilor minime succesive, algoritmul primal-dual, algoritmul out-of-kilter.
- Aplicatii la scalarea datelor, managementul proiectelor, fluxuri dinamice, probleme de rutare pe arce, planificarea productiei.
- Arbori partiali de cost minim: conditii de optimalitate, algoritmii lui Kruskal si Prim.
- Introducere în teoria matroizilor: sisteme de axiome, exemple de matroizi, matroizi si grafuri, teoria transversalelor si matroizi, arbori partiali de cost minim si matroizi. Caracterizarea algoritmica a matroizilor.
BIBLIOGRAFIE
- Network Flows: Theory, Algorithms and Applications - Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin [see Files]
EVALUARE
Nu se va tine cont de seminar, doar ca la examen veti avea subiecte asemanatoare cu cele tratate la seminar.