Apprendre à raisonner sur les structures algorithmiques de bases, à les utiliser et à les programmer : tableaux, structures séquentielles (listes, mots, files), arbres et graphes.
-
Outils d'analyse des algorithmes (20%) : analyse d'algorithmes et complexité asymptotique, preuve de terminaison, preuve de correction, invariants, préconditions et postconditions
-
Vecteurs et matrices (15%) : recherche dichotomique, produits scalaire et matriciel, tableaux
-
Listes et séquences finies (25%) : monoïde libre, sous-séquences, facteurs, concaténation, listes chainées, doublement chainées, implémentation par tableau, structures abstraites de listes, files, piles
-
Arbres (25%) : induction, dépendances entre arité, nombre de nœuds et hauteur, parcours d'arbres
-
Graphes (15%) : lemme des poignées de mains, théorème de caractérisation des arbres, représentation matricielle, fermeture transitive
