C17 : Compétences

Algorithmes de recherche

Écrire un algorithme de recherche dans une liste non triée :

- recherche séquentielle d'un élément

- recherche séquentielle d'un maximum ou d'un minimum

Écrire un algorithme de recherche dans une liste triée :

- recherche dichotomique

Coût d'un algorithme

Estimer le coût de quelques algorithmes classiques :

- coût linéaire pour le parcours séquentiel d'une boucle

- coût quadratique pour les algorithmes de tri par insertion et par sélection

Correction d'un algorithme

Donner l'invariant pour les algorithme de tri par sélection et par insertion

Terminaison d'un algorithme

Montre la terminaison de l'algorithme de recherche dichotomique à l'aide d'un variant de boucle