Téma ismertetése
Forums
- Informations concernant l'UE ASDA.
Posez ici vos questions aux enseignant.e.s et aux autres étudiant.e.s.
Organisation et informations administratives
À lire avant de commencer : 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).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.
Le livre a été scanné et fait plus de 40M, son téléchargement est long et il est conseillé de le sauvegarder. Également disponible via https://www.lri.fr/~mcg/PDF/FroidevauxGaudelSoria.pdf
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.
- Révisions sur les structures de données linéaires
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.
- Complexité dans le cas le pire et fonctions usuelles.
Semaine 3
- 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.
Semaine 4
rbres binaires de recherche- Définition
- Recherche d'un élément
- Insertion d'un élément
- Suppression d'un élément
- Complexité
Semaine 5
- 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
- Définition et propriétés algorithmiques
Semaines 6 à 8
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
- Définition et propriétés algorithmiques
Semaines 9 à 10
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.
- Parcours en profondeur et en largeur d'arbres binaires.