INF1008 - Analyse et conception d'algorithmes

L'étudiant développera son habileté à produire des algorithmes corrects et efficaces. Il pourra analyser la complexité spatiale et temporelle d'un algorithme. Il entrera en contact avec différentes classes d'algorithmes et s'habituera à choisir le type d'algorithme qui convient le mieux à un problème donné.

Définition d'un algorithme et de sa complexité. Notations asymptotiques. Résolution de récurrence. Étude d'efficacité et de complexité d'algorithmes de tri. Stratégies de conception d'algorithmes : algorithmes voraces, diviser-pour-régner, programmation dynamique, algorithmes probabilistes, exploration de graphes. Études de cas.

Préalable 1 :

ALG1001	Logiques et Ensembles
ou
PIF1005	Mathématiques pour informaticiens I

Préalable 2 :

INF1004

Structures de données et algorithmes