CSI 3505 - Conception et analyse des algorithmes
(Automne 2009)

Analyse des cas moyens et du pire cas. Analyse de la complexité. Notations asymptotiques et classes de complexité de base. Techniques de conception d'algorithmes: exhaustive, diviser pour régner, programmation dynamique glouton, retour arrière. Complexité computationelle de problèmes : arguments de borne inférieure. Classes P, NP, et NP complet; traitement des problèmes NP complet. Préalables: CSI2510/CSI2610, CSI2501 ou; (pour les étudiants en spécialisation mathématiques seulement: CSI2510/CSI2610 et MAT2541 ou MAT2543).

Professeur

Dr. Paola Flocchini
Bureau: SITE 5064
Téléphone: (613) 562-5800 ext. 6582
Courriel: flocchin@site.uottawa.ca
Heures de consultation: Jeudi 10:45- 12:45

Syllabus du cours (pdf)

Annonces

Devoirs

Matériel de cours

Manuel: (Obligatoire)
"Foundations of Algorithms Using C++ Pseudocode" (Troisième ou Deuxième Edition), R. Neapolitan, K. Naimipour, Jones and Bartlett Publishers. (disponible à la Librairie AGORA)

• Introduction
  Introduction - 1 per page
• logn!=O(nlogn)
• Diviser pour regner
  Diviser pour regner - 1 per page
• Programmation dynamique (nouvelle version)
  Programmation dynamique - 1 per page (nouvelle version)
• Rappel: Les graphes
• Representation d'ensembles
  Representation d'ensembles - 1 per page
• Algorithmes voraces
  Algorithmes voraces - 1 per page
• Traversee des graphes
  Traversee des graphes - 1 per page
• Complexité du calcul (Nouvelle version )
  Complexité du calcul - 1 per page (Nouvelle verison)
• Autres algorithmes
  Autres algorithmes - 1 per page

Exercices.
• Les exercices vus en classe le Jeudi 1 Octobre.
• Les solutions des exrcices vus en classe le Jeudi 1 Octobre.
• Autres exercices ...

Schemas d'évaluation

D = moyenne des devoirs
M = note du test (mi-session),
X = note de l'examen final

T = ( 2X + M )/ 3

Si (T >= D) ou (T >= 70)
Note finale = .75*T + .25*D

Sinon
Note finale = (1-R)*T + R*D
oú R = .25*(max(0,T-50))/20.