Complexité et structures des
données
Elaboré par Mme Elkamel Hager
FSM de Monastir 2020-2021
1ere année Licence en Sciences de l’Informatique
H. Jamoussi Elkamel , FSM 1
Alg Avancée
Plan du cours
Chapitre 1 : Les enregistrements
Chapitre 2 : la récursivité et le paradigme diviser
pour régner
Chapitre 3 : Les pointeurs
Chapitre 4 : Les Listes chainées
Chapitre 5 : Les Types Abstraits des données
Chapitre 6 : Les piles
Chapitre 7 : Les Files
Chapitre 8 : Les Arbres
Chapitre 9 : Les Arbres binaires de recherche
Chapitre 10 : Analyse et complexité des algorithmes
H. Jamoussi Elkamel , FSM 2
Alg Avancée
1
, Chapitre 2
La récursivité et le paradigme
« diviser pour régner »
Alg Avancée H. Jamoussi Elkamel , FSM
Sommaire
• Introduction
• Objets récursifs
• Méthodes récursives
– définition
– Propriétés d’une méthode récursive
– Exemple : tour de Hanoï
• Type de récursivité
• Pile d’exécution
• Arbre d’exécution
• Le paradigme « diviser pour régner »
– Principe
– Tri fusion
• Conclusion
H. Jamoussi Elkamel , FSM 4
Alg Avancée
2
, Le principe de récursivité
• La récursivité : est l’art d’écrire des algorithmes qui
résolvent des problèmes que l’on ne sait pas résoudre
directement.
• La récursivité permet de définir un concept (un objet ou
une méthode) en fonction de lui-même.
• Certains problèmes se résolvent simplement en résolvant
un sous problème de même nature, mais plus simple…
• On trouve :
– Des objets récursifs : (structures de données ou TAD),
– Des méthodes récursives : (procédures et fonctions).
H. Jamoussi Elkamel , FSM 5
Alg Avancée
Le principe de récursivité
• Tout objet est dit récursif s’il se définit à partir de lui-
même
• Une fonction est dite récursive si elle comporte, dans son
corps, au moins un appel à elle-même
• Une structure est récursive si un de ses attributs en est
une autre instance
H. Jamoussi Elkamel , FSM 6
Alg Avancée
3
données
Elaboré par Mme Elkamel Hager
FSM de Monastir 2020-2021
1ere année Licence en Sciences de l’Informatique
H. Jamoussi Elkamel , FSM 1
Alg Avancée
Plan du cours
Chapitre 1 : Les enregistrements
Chapitre 2 : la récursivité et le paradigme diviser
pour régner
Chapitre 3 : Les pointeurs
Chapitre 4 : Les Listes chainées
Chapitre 5 : Les Types Abstraits des données
Chapitre 6 : Les piles
Chapitre 7 : Les Files
Chapitre 8 : Les Arbres
Chapitre 9 : Les Arbres binaires de recherche
Chapitre 10 : Analyse et complexité des algorithmes
H. Jamoussi Elkamel , FSM 2
Alg Avancée
1
, Chapitre 2
La récursivité et le paradigme
« diviser pour régner »
Alg Avancée H. Jamoussi Elkamel , FSM
Sommaire
• Introduction
• Objets récursifs
• Méthodes récursives
– définition
– Propriétés d’une méthode récursive
– Exemple : tour de Hanoï
• Type de récursivité
• Pile d’exécution
• Arbre d’exécution
• Le paradigme « diviser pour régner »
– Principe
– Tri fusion
• Conclusion
H. Jamoussi Elkamel , FSM 4
Alg Avancée
2
, Le principe de récursivité
• La récursivité : est l’art d’écrire des algorithmes qui
résolvent des problèmes que l’on ne sait pas résoudre
directement.
• La récursivité permet de définir un concept (un objet ou
une méthode) en fonction de lui-même.
• Certains problèmes se résolvent simplement en résolvant
un sous problème de même nature, mais plus simple…
• On trouve :
– Des objets récursifs : (structures de données ou TAD),
– Des méthodes récursives : (procédures et fonctions).
H. Jamoussi Elkamel , FSM 5
Alg Avancée
Le principe de récursivité
• Tout objet est dit récursif s’il se définit à partir de lui-
même
• Une fonction est dite récursive si elle comporte, dans son
corps, au moins un appel à elle-même
• Une structure est récursive si un de ses attributs en est
une autre instance
H. Jamoussi Elkamel , FSM 6
Alg Avancée
3
