Analyse et conception d'algorithmes

3 crédits · Deuxième année

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