Algorithmique des structures de données arborescentes 2017-2018

Emneoversikt

• 

  Forums

  • News Forum

    Informations concernant l'UE ASDA.
  • Questions / réponses Forum

    Posez ici vos questions aux enseignant.e.s et aux autres étudiant.e.s.

• Organisation et informations administratives

    À lire avant de commencer :
  

  1. Cliquer sur le nom d'une section donne accès à son contenu. Par exemple, cliquer sur le lien "Organisation et informations administratives" ci-dessus donne accès au sondage pour le cours optionnel de programmation fonctionnelle.
     
  2. Certains contenus ne sont accessibles qu'après avoir fait une ou plusieurs activités précédentes. Par exemple, pour accéder au sondage, il faut d'abord consulter les modalités d'organisation de ce cours (accessible en cliquant sur le nom de cette section).
     

  Fil: 1Gallup: 1
• Ressources en ligne

  Deux livres fournissent des compléments utiles sur le cours. Les thèmes des chapitres suivants seront abordés dans le cours :

  •  Livre Éléments d'algorithmique :
  • Chapitre 1, sections 1.1, 1.2.1 (et 1.3 pour un complément).
  • Chapitre 2, sections 2.1.1, et 2.2 partiellement.
  • Chapitre 3 : listes, piles, arbres, sections 3.1, 3.2, 3.3.
  • Chapitre 4 : section 5.1.3.
  • Chapitre 6 : sections 6.1 à 6.4

  
  

  •  Livre Types de données et algorithmes :
    • Chapitres 1 (notion d'algorithme) et 2 (complexité), ainsi que 3 pour un exemple.
    • Le chapitre 4 est utile pour comprendre la notion de type abstrait.
    • Chapitre 5 : structures linéaires.
    • Chapitre 7 : structures arborescentes.
    • Chapitre 10 : ABR.
    • Chapitre 11 : arbres équilibrés.

  Filer: 2
• Semaine 1

    Contenu:

  • Révisions sur les structures de données linéaires
    
  • Complexité dans le cas le pire et fonctions usuelles.
    
  • Rédiger une preuve par récurrence.
    
  • Vocabulaire sur les arbres binaires.
    
  • Premières propriétés des arbres binaires.

  Mappe: 1Filer: 3Quizer: 2
• Semaine 2

   Retour sur les points suivants :

  • Complexité dans le cas le pire et fonctions usuelles.
    
  • Rédiger une preuve par récurrence.
  • Premières propriétés des arbres binaires.

  Filer: 3
• Semaine 3

   Contenu

  • Reprise des notions de semaine 2
  • Complexité dans le cas le pire et fonctions usuelles.
  • Rédiger une preuve par récurrence.
  • Premières propriétés des arbres binaires.
  • Algorithmes génériques sur les arbres.

  Filer: 2
• Semaine 4

    Contenu : Arbres binaires de recherche

  • Définition
  • Recherche d'un élément
  • Insertion d'un élément
  • Suppression d'un élément
  • Complexité

  Filer: 3
• Outils de développement

   Cette partie fournit :

  • Une bibliothèque appelée ASDA, pour générer et afficher des arbres.
  • Une configuration Emacs qui ajoute des fonctionnalités (comme la vérification à la volée du code, la complétion automatique, les abréviations, ...).
  • 3 mini-tutoriels ci-dessous pour l'installation et l'utilisation de la bibliothèque et d'Emacs.

  Note. L'utilisation d'emacs n'est pas obligatoire (éditeurs alternatifs : Atom ou SublimeText).

  Filer: 3
• Semaine 5

    Contenu : Arbres binaires de recherche (ABR) et arbres équilibrés 

  • CI et TM : suite des exercices sur les ABR.
  • Cours en amphi : arbres équilibrés
    • Définition et propriétés algorithmiques
      
    • Outil générique : les rotations
      
    • Arbres AVL
    • Arbres rouges et noirs

  Fil: 1
• Semaine 6

    Contenu : Arbres équilibrés

  • Définition et propriétés algorithmiques
    
  • Outil générique : les rotations
  • Arbres rouge-noir
  • Définition et propriété d'équilibre
  • Insertion et suppression
  • Arbres AVL
    
  • Définition et propriété d'équilibre
  • Insertion et suppression

    Changements sous Moodle :
  

  1. Lancer les tests se fait maintenant en téléchargeant le fichier student.ml (l'éditeur est désactivé).
  2. La ligne

     open Type

     du fichier student.ml à télécharger peut être remplacée (ou non) par

     open Asda

     ce qui permet de développer sous l'environnement habituel et de télécharger le fichier sans changement.  
  3. La bibliothèque Asda a été mise à jour pour que les types définis dans Asda soient les mêmes que ceux des feuilles d'exercices. Par exemple, EmptyRB devient Leaf pour les arbres rouges et noirs. D'autres modifications seront envisageables (par exemple, pouvoir préciser le nom du fichier dans lequel générer une image). 
  4. La mise  à jour s'exécute très rapidement (relancer le terminal et Emacs 25 après) :

  5. bash <(curl -s 'http://www.labri.fr/perso/zeitoun/asda_upgrade')
     

  Filer: 2
• Semaines 8 et 9

    Contenu : Retour sur les parcours. Arbres planaires. Énumération.

  • Parcours en profondeur et en largeur d'arbres binaires.
    
  • Arbres planaires : définition.
  • Énumération
  • Mots et chemins de Dyck.
  • Bijections classiques entre arbres planaires, binaires, et mots de Dyck.
  • Énumération du nombre de chemins de Dyck de longueur donnée.

  Filer: 2
• Semaine 10

   Algorithme de Huffman

  Filer: 2
• Annales

  Filer: 2