Formation algorithme, tutoriel & guide de travaux pratiques en pdf.

Analyse d’algorithmes

• Algorithme : – « recette », séquence d’actions définies de façon non ambigüe, qui peut être appliquée pour résoudre un problème en un temps fini.
• Analyse d’un algorithme : – Approprié à la tâche à laquelle il est destiné ?
– Meilleur qu’un autre ? – Possibilités d’amélioration ?
– Ressources utilisées en temps et en mémoire ?
– Performances indépendamment de l’implémentation ?
Outil d’analyse : Comportement asymptotique de fonctions
• Questions :
– Peut-on extrapoler le temps requis pour résoudre un problème sur base de jeux de données de test (plus petits…) ? – Comment comparer deux algorithmes indépendamment des machines sur lesquelles ils seront implémentés ?
– Comment s’assurer qu’un algorithme s’adaptera bien à une augmentation de la taille du problème à résoudre ?
• Etudier le temps requis par un algorithme en fonction de la taille du problème.
→ Comment comparer le taux de croissance de différentes fonctions ?
• Hypothèses simplificatrices :
– Soient 2 algorithmes A1 et A2 avec :
• A1 systématiquement plus rapide que A2 pour de « petits » jeux de données.
• A2 systématiquement plus rapide que A1 pour de « grands » jeux de données. A2 sera préféré à A1 car « presque toujours » meilleur.
– On ne tient pas compte des paramètres de performances propres aux ordinateurs sur lesquel l’algorithme est implémenté.
Comparaison asymptotique de fonctions
• Fonctions étudiées :
– Temps de calcul en fonction de la taille des données (input).
– Domaine : nombre naturels.
– Image : nombres réels positifs.
[ ): 0,F → ∞ℕ