-
Cours :
- Arbres binaires de recherche
- cours 1
transparents : pdf, html - planche de TD/TP 1 (pdf)
- cours 1
- Tas
- cours 2
transparents : pdf, html - planche de TD/TP 2 (pdf)
- cours 2
- Parcours de graphe
- cours 3
transparents : pdf, html - planche de TD/TP 3 (pdf)
- cours 3
- Plus courts chemins et coloration de graphe
- cours 4
transparents : pdf, html - planche de TD/TP 4 (pdf)
- cours 4
- Programmation dynamique 1
- cours 5
transparents : pdf, html - planche de TD/TP 5 (pdf)
- cours 5
- Programmation dynamique 2
- Recherche textuelle
- cours 7
transparents : pdf, html - planche de TD/TP 7 (pdf)
- cours 7
- Algorithmes randomisés
- cours 8
transparents : pdf, html - planche de TD/TP 8 (pdf)
- cours 8
- Calculabilité
- transparents : pdf
- planche de TD/TP 9 (pdf)
- Complexité
- transparents : pdf
- planche de TD/TP 10 (pdf)
Tas
Structure de données abstraite : file de priorité (minimum)
- Test du vide de la file de priorité
- Insertion d’un nouvel élément avec une priorité donnée
- Recherche de l’élément de priorité minimum
- Extraction de l’élément de priorité minimum
Interface :
heap.isempty() # true or false
heap.insert(element, priority) # modifies heap
heap.minimum() # returns element
heap.extract_minimum() # remove minimum priority
Utilisation de tas binaires
Arbre binaire parfait étiqueté par les priorités tel que pour tout nœud p d’étiquette x:
- toutes les étiquettes des enfants de p sont supérieures à x
Parfait signifie que tous les niveaux sont complets, sauf le dernier rempli de gauche à droite
Hauteur d’un tas binaire
La hauteur d’un tas binaire à n nœuds est égale à ⌈log2(n) + 1⌉.
Test du vide de la file de priorité
- Test du vide de l’arbre binaire…
Complexité : O(1)
Insertion d’une nouvelle priorité
Insertion d’une nouvelle priorité
Insertion d’une nouvelle priorité
Insertion d’une nouvelle priorité
Insertion d’une nouvelle priorité
- Insérer à la prochaine place libre dans l’arbre qui doit rester parfait,
- puis faire remonter le long de la branche jusqu’à satisfaire la contrainte sur les priorités
Complexité : O(log n)
Recherche de l’élément de priorité minimum
- La priorité minimum est à la racine de l’arbre
Complexité : O(1)
Extraction de l’élément de priorité minimum
Extraction de l’élément de priorité minimum
Extraction de l’élément de priorité minimum
Extraction de l’élément de priorité minimum
Extraction de l’élément de priorité minimum
- Remplacer la racine de l’arbre par le dernier élément du niveau le plus bas (pour que l’arbre reste parfait)
- Faire descendre la priorité le long de la branche qui mène à l’élément de priorité minimum, jusqu’à satisfaire la contrainte sur les priorités
Complexité : O(log n)