Algorithmique intermédiaire : analyse d'algorithmes, structures de données

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

Comment bien utiliser les ressources de ce cours ?

Pour chaque chapitre, le cours est présenté sous la forme de slides commentées à l'oral, formant une vidéo. Les slides sont disponibles par ailleurs en PDF.
Quant-aux exercices, certains sont à correction automatique, d'autres sont sous forme d'une fiche de TD classique. Attention, à l'exception du quizz sur les invariants, les exercices à correction automatique sont plus faciles que les exercices plus classiques, disponibles dans les fiches de TD.

Il est donc conseillé de : regarder les vidéos du chapitre, puis mettre en application par les quizz à correction automatique, puis faire des exercices des fiches de TD en PDF et comparer avec les corrigés, qui sont également disponibles en PDF.

En particulier : les exercices de type glisser-déposer pour créer un algorithme permettent de prendre certaines formes d'automatismes, car la structure globale est déjà fournie, mais ne remplacent aucunement l'élaboration d'un algorithme à partir d'une page blanche. Le fait de déterminer vous-mêmes la structure de votre algorithme est une compétence indispensable à acquérir.

Pour combler cela, une piste d'amélioration envisagée à moyen terme consiste en l'ajout d'exercices d'implémentation, en C ou en Python, des algorithmes demandés, avec évaluation automatique. Cela permettra d'évaluer la capacité des étudiants à écrire un algorithme à partir d'une "page blanche".

Contexte académique

Ce cours est dispensé aux étudiants de Licence 1 à l'Université Clermont Auvergne, dans le portail scientifique Maths-Informatique.

Il s'agit de la dernière matière d'informatique de l'année (mars-mai), qui est précédée de :

1. Représentations en binaire : représentations binaires des nombres et des caractères, logique booléenne (voir le cours ouvert Caseine correspondant ici)
   
   
2. Algorithmique et programmation en Python : découvrir les notions de bases d'algorithmiques (variables, types, Si, boucles, fonctions, listes au sens de Python, dictionnaire) implémentées en en Python (voir le cours ouvert Caseine correspondant ici)
   
   
3. Introduction à la programmation en C : implémentation en C des notions vues au premier semestre (variables, types, Si, boucles, fonctions), ainsi que : tableaux 1D/2D, chaînes de caractères, structures struc, pointeurs, allocation dynamique