Résumé
I) Introduction à l'algorithmique
-
Un algorithme est la spécification d'un schéma de calcul sous forme d'une suite finie d'opérations élémentaires obéissant à un enchaînement déterminé.
-
Quand on écrit un algorithme, on utilise un langage dit "langage naturel" ("tant que", "si"...), ce langage naturel permet de passer facilement à un langage de programmation (Python, Java...), on dit alors que l'on implémente l'algorithme.
-
La notion de complexité d'un algorithme va rendre compte de l'efficacité de cet algorithme. Il existe 2 types de complexité : une complexité en temps et une complexité en mémoire. Nous nous intéresserons ici uniquement à la complexité en temps. La complexité en temps est directement liée au nombre d'opérations élémentaires qui doivent être exécutées afin de résoudre un problème donné.
-
Nous nous intéresserons uniquement à la complexité en temps “dans le pire cas”.
-
Pour comparer des algorithmes, nous allons uniquement nous intéresser à ce que l'on appelle "l'ordre de grandeur asymptotique" (notation O).
II) Tri par insertion
-
Connaître l’algorithme du tri par insertion.
-
Connaître l’algorithme du tri par sélection.
-
Savoir que l’algorithme du tri par insertion a une complexité en temps dans le pire des cas en (quadratique).
III) Tri par sélection
-
Connaître l’algorithme du tri par sélection.
-
Savoir que l’algorithme du tri par sélection a une complexité en temps dans le pire des cas en (quadratique).
IV) Invariant de boucle
-
On appelle “invariant de boucle” une propriété qui est vraie avant et après chaque itération (boucle).
-
Un invariant de boucle peut permettre de prouver la correction d’un algorithme.
-
Il est nécessaire de démontrer que l’on a bien un invariant de boucle, cette démonstration doit se faire en 3 étapes :
-
INITIALISATION : on doit montrer que l'invariant de boucle est vrai avant la première itération de la boucle.
-
CONSERVATION : on doit montrer que si l'invariant de boucle est vrai avant une itération de la boucle, il le reste avant l'itération suivante.
-
TERMINAISON : une fois la boucle terminée, l'invariant fournit une propriété utile qui aide à montrer la correction de l'algorithme.
-