Algorithmique

Le cours consiste en deux parties : structures de données et techniques algorithmiques.
1. Structures de données :
• Méthodologie : définition des objectifs (type abstrait de données) ; réalisation concrète (structure
de données) ; analyse de complexité
• Exemples traités :
o types linéaires (pile, file, file à priorité) : tableaux dynamiques et tas ;
o type dictionnaire : arbres binaires de recherche et tables de hachage.

2. Techniques algorithmiques :
• Méthodes de conception d'algorithmes et leur analyse (correction et
complexité) :

o Diviser pour régner
o Programma-on dynamique
o Recherche exhaustive et énuméra-on
o Algorithmes probabilistes
o Algorithmes d'approximation (dont glouton)

• Exemples tirés de divers domaines : tableaux, nombres, texte, géométrie, graphes, logique,
ordonnancement.
• Algorithmes classiques : tri fusion, tri rapide, algorithme de Karatsuba, etc.

• Structures de données de base : tableaux, liste chaînée, arbre binaire ; et leurs algorithmes de parcours
• Structures algorithmiques de base : boucles, branchement conditionnel, récursivité
• Notions d'analyse d'algorithme : preuve de correction, analyse de complexité élémentaire (notations de
Landau)