Programme de colles¶

Semaines du 27/01, du 03/02 et du 10/02¶

Terminaison d'un algorithme, variant.
Correction d'un algorithme, invariant.
Complexité d'un algorithme, notation \(\mathcal{O}\). Complexité amortie.
Types et opérateurs de base en C, boucles et structures de contrôle en C.
Aspects fonctionnels et impératifs de Ocaml.
Exemples d'études et d'implémentations d'algorithmes dans ces deux langages (exponentiation rapide, tri, crible, algorithme d'Euclide, \dots)

Tableaux associatifs et hachage
Fonction de hachage, résolution des collisions par chaînage. Applications
Bases de données
Langage sql requêtes sur une ou plusieurs tables.
Arbres binaires
Définition, hauteur, taille, relation entre hauteur et taille (preuve). Implémentation en C et en OCaml. Parcours préfixe, infixe, suffixe et en largeur. Arbres binaires de recherche, caractérisation par le parcours infixe (preuve). File de priorité, tas binaire, ajout et de suppression d’un élément dans un tas, tri par tas.
Stratégie algorithmiques : force brute, retour sur trace, algo glouton

Terminaison de programmes
Relation d'ordre, ordre lexicographique et ordre produit sur un produit cartésien. Ensemble bien ordonnée définition par il n'existe pas de suite strictement décroissante, équivalence avec l'existence d'un élément minimal pour toute partie non vide. Application à la preuve de terminaison d'un programme. Exemples : fonction d'Ackermann , tri par épuisement des inversion.
Ensembles inductifs
Définition inductive d'un ensemble, exemples. Preuve par induction structurelle.
Décomposition en sous problèmes
Méthode diviser pour régner, résolution d'équation de complexité de la méthode diviser pour régner. Programmation dynamique : découpe maximale d'une barre, somme maximale d'un chemin dans une pyramide, rendu de monnaie, longueur de la plus longue sous séquence commune.