cours et exercices de calcul asymptotique
La preuve d'algorithme est une démonstration mathématique qu'un algorithme produit le résultat attendu pour toutes les entrées valides et qu'il se termine effectivement.
L'analyse des fonctions récursives repose sur l'établissement et la résolution de relations de récurrence. Cas de base : condition d'arrêt de la récursion. Relation de récurrence : exprime \(T(n)\) en fonction de \(T\) pour des entrées plus petites.
La méthode de comptage des pas est une technique systématique pour analyser la complexité temporelle d'un algorithme : On identifie les instructions élémentaires et on compte leur nombre d'exécutions.
Lorsqu'on analyse un algorithme, on s'intéresse à deux ressources fondamentales : le temps et l'espace mémoire. Ces deux mesures permettent d'évaluer l'efficacité d'un algorithme et de comparer différentes solutions pour un même problème.
Une variante de boucle (ou fonction de terminaison) est une expression associée à une boucle qui possède les propriétés suivantes : Elle est évaluée à une valeur entière positive ou nulle. Sa valeur décroît strictement à chaque itération de la boucle. Elle fournit une borne inférieure garantissant que la boucle ne peut pas s'exécuter indéfiniment.
Tri rapide Le tri rapide (Quicksort) est un algorithme de tri basé sur le paradigme Diviser pour régner, proposé par C.A.R. Hoare en 1959. C'est l'un des algorithmes de tri les plus utilisés en pratique grâce à ses excellentes performances en moyenne.
Nous voulons souvent raisonner sur le temps d'exécution d'une manière qui ne dépend que de l'algorithme et de son entrée. Ceci peut être réalisé en choisissant une opération élémentaire, que l'algorithme effectue à plusieurs reprises, et en définissant la complexité temporelle \(T(n)\) comme le nombre de ces opérations que l'algorithme effectue étant donné un jeu de données de longueur n.
Un invariant doit satisfaire trois propriétés : initialisation, maintenance et terminaison. Ces trois étapes constituent une preuve par induction que l'algorithme produit le résultat attendu.
pour la boucle for le coût est proportionnel au nombre d'itérations, par contre pour une une boucle while, il faut estimer le nombre d'itérations.
Lorsqu'on analyse un algorithme, on cherche à connaître son comportement pour des entrées de grande taille. Au lieu de mesurer le temps exact d'exécution (qui dépend des machines), on utilise des notations asymptotiques qui permettent de donner une estimation générale de la croissance de la fonction de complexité.
Cette série d'exercices porte sur la récursivité et l'analyse de complexité des algorithmes. Vous serez amené à écrire des fonctions récursives pour résoudre divers problèmes et à estimer leur complexité temporelle.
L'analyse des algorithmes est essentielle pour évaluer leurs performances indépendamment de la machine et du langage d'implémentation. Analyse asymptotique : étude du comportement d'un algorithme quand la taille de l'entrée devient très grande.