Universitatea A. I. Cuza Iaşi

Algoritmica grafurilor

Numele cursuluiAlgoritmica grafurilor CodCS2104
Generaţia Studii de licenţă, 2009 - 2012
Nivel de studii Licenţă An 1 Semestru 1 Statut Obligatoriu
Nr. de ore pe săptămânăNr. total de ore pe semestruNr. de ore de lucru individualCrediteMod de evaluareLimba de predare
CSLPr
2 2 0 0 56 94 5 E ro
Titularul disciplineiTitlu academic şi ştiinţific
Profesor, Dr., Cornelius Croitoru
Discipline absolvite anterior
ObiectiveFamiliarizarea studentilor cu principalele notiuni si rezultate din Teoria Algoritmica a Grafurilor si aplicarea acestora in proiectarea unor algoritmi eficienti pentru diversele probleme de optimizare pe grafuri.
Tematica generalăVocabular al Teoriei Grafurilor, Probleme de drum (parcurgeri, drumuri minime, conexiune), Arbori partiali de cost minim (union-find, complexitate amortizata), Cuplaje, Fluxuri, Reduceri polinomiale pentru probleme de decizie pe grafuri, Abordari ale problemelor NP-hard pe grafuri, Grafuri planare.
Tematica seminariilor / laboratoarelorLa fiecare seminar se discuta 4 probleme (unele cu grad de dificultate ridicat) necesare aprofundarii tematicii prezentate la curs. Enunturile problemelor sunt disponibile de la inceput, oferind posibilitatea studentilor sa se gindeasca in prealabil la solutii si sa caute resurse bibliografice utile pentru obtinerea acestor solutii.
Metode de predareNotele de curs (disponibile de la inceputul cursului) in format pdf,-stilul slide - vor fi prezentate cu ajutorul videoproiectorului.
Bibliografie
  1. CROITORU C., Tehnici de baza in optimizarea combinatorie, Editura Univ. Al. I. Cuza Iasi, Iasi,1992.
  2. CROITORU C., Introducere in proiectarea algoritmilor paraleli, Editura Matrix Rom, Bucuresti, 2002.
  3. TOMESCU I., Probleme de combinatorica si teoria grafurilor, Editura did. si ped., Bucuresti,1981.
  4. DIESTEL R., Graph Theory, Electronic Edition.
  5. CORMEN T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms, MIT Press 2001.
Evaluarecondiţii
criteriiUn student va fi declarat promovat daca punctajul total realizat este macar 40 de puncte.
forme
  • Activitatea de la seminar (prezenta,participare la discutii, solutii originale): 0-18 puncte.
  • Teme pentru acasa (3 teme, in saptaminile 4, 8,12) fiecare cotata cu maxim 14 puncte: 0-42 puncte.
  • Test final scris (in sesiunea de examene): 0-60 puncte.
formula notei finaleSe aplica normele ECTS: studentii care au obtinut minim 40 puncte, sunt sortati descrescator dupa punctajul final si clasificati.
© 2006-2010 FII | despre site | intranet