Pré-requis :
- Bases de l'algorithmique : variables & types, instruction conditionnelle (Si), boucle (Pour et Tant que), tableaux (ou listes au sens Python)
- (recommandé mais pas strictement nécessaire) implémentation en C ou en Python des bases de l'algorithmiques mentionnées ci-dessus
Objectifs :
- Savoir analyser un algorithme : complexité temporelle, preuve de correction, preuve de terminaison
- Maîtriser plusieurs structures de données : avantages et inconvénients de chacun, savoir les manipuler
- Maîtriser les algorithmes classiques de parcours et de tri
Contenu/Plan du cours :
- Rappels des notations de pseudo-code
- Complexité temporelle
- (Introduction aux) Preuves d'algorithme : correction, terminaison
- Récursivité
- Structure de données liste chaînée :
- Variantes : simplement chaînée, doublement chaînée, doublement chaînée circulaire
- Comparaison de complexité avec les tableaux pour les opérations usuelles.
- Structures de données pile et file
- Arbre binaire (enraciné).
- Vocabulaire, opérations simples
- Parcours (en largeur, en profondeur, préfixe, infixe, suffixe)
- Introduction aux Arbres Binaire de Recherche : recherche et insertion simple (sans rotation)
- Algorithmes classiques de tri : par insertion, par sélection, rapide, fusion
- Contact: Aurelie Lagoutte