• Conseils pour bien utiliser les activités disponibles dans ce cours

    1. Pré-requis, Objectifs, Plan du cours
    2. Comment bien utiliser les ressources de ce cours ?
    3. Contexte académique

    • THEME 0
      Appréhender le pseudo-code
      THEME 1
      Analyse d'algorithmes : complexité, preuves (invariants, ...)
      THEME 2
      Récursivité
      THEMES 3 & 4
      Liste chainée (& variantes)
      THEMES 5 & 6
      Pile, file, arbre
      THEME 7
      Tris classiques

    • 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