INF5000 Conception et analyse d’algorithmes (2 crédits)

Analyse de l'efficacité des algorithmes: analyse asymptotique, analyse en pire cas et en moyenne. Notation asymptotique, résolutions de récurrences. Stratégies de conception d'algorithmes: algorithmes voraces, «diviser pour régner», «diminuer pour régner». Algorithmes probabilistes. Complexité de calcul. Problèmes combinatoires difficiles rencontrés dans le domaine du génie informatique : nature et caractérisation. Approches de résolution : approche de construction, approche de réparation. Techniques de résolution: heuristique vorace, recuit simulé, recherche avec tabou, recherche locale itérée, algorithme génétique, colonies de fourmis.