Que savoir faire ?
I) Introduction à l'algorithmique
-
Vous devez être capable d’analyser le fonctionnement d’un algorithme (faire tourner un algorithme “à la main”).
-
Vous devez être capable de déterminer la complexité en temps dans le pire des cas d’un algorithme (exemples : O(n), O(n2), O(log2(n))...).
II) Tri par insertion
-
Vous devez être capable d’analyser et d’expliquer (faire tourner “à la main”) les algorithmes de tri par insertion sur un exemple donné.
-
Vous devez être capable d’implémenter en Python les algorithmes de tri par insertion.
III) Tri par sélection
-
Vous devez être capable d’analyser et d’expliquer (faire tourner “à la main”) les algorithmes de tri par sélection sur un exemple donné.
-
Vous devez être capable d’implémenter en Python les algorithmes de tri par sélection.
IV) Invariant de boucle
-
Vous devez être capable de trouver un invariant de boucle dans un algorithme.
-
Vous devez être capable de prouver que c’est bien un invariant de boucle.
-
d’utiliser cet invariant de boucle pour démontrer la correction d’un algorithme (notamment les algorithmes de tri par insertion et de tri par sélection).