Récapitulatif donnees

Type Abstrait

• Savoir définir l'idée générale du type abstrait Dictionnaire

• Savoir utiliser les fonctions d'interface (qui seront données) d'un Dictionnaire pour réaliser une tâche donnée. Par exemple :

  • nouveauDictionnaire() -> Dictionnaire
  • ajouter(cle:Cle, valeur:Valeur, d:Dictionnaire) -> None
  • modifier(cle:Cle, valeur:Valeur, d:Dictionnaire) -> None
  • rechercher(cle:Cle, d:Dictionnaire) -> Valeur
  • supprimer(cle:Cle, d:Dictionnaire) -> None

Implémentation Python

• Savoir créer un dictionnaire en Python
• Savoir rajouter un couple clé-valeur
• Savoir modifier une valeur associée à une clé
• Savoir supprimer un couple clé-valeur

Avantages / désavantages du dictionnaire en tant que structure de données

• Donner le coût supposé pour de bonnes implémentations des trois types TABLEAU, LISTE CHAINEE, DICTIONNAIRE.

  • Lecture d'une valeur
  • Modification d'une valeur
  • Insertion d'une valeur
  • Suppression d'une valeur
  • Concaténation de deux séries de valeurs
  • Recherche d'une valeur

Les 3 méthodes Python à connaitre sur le type natif Dict

• Que renvoie la méthode keys() ?
• Que renvoie la méthode values() ?
• Que renvoie la méthode items() ?
• Savoir utiliser la méthode keys()
• Savoir utiliser la méthode values()
• Savoir utiliser la méthode items()
• Savoir réaliser une fonction Python permettant de rechercher une valeur dans un dictionnaire

Arbre représentant une structure hierarchique

• Savoir ce qu'est une Arborescence c'est à dire un Arbre possédant une ???
• Un Arbre peut-il posséder des boucles ou des cycles ?
• Savoir ce qu'est un Noeud
• Savoir ce qui caractérise une Racine
• Savoir ce qui caractérise une Feuille

• Pouvoir tracer l'arbre représentant une situation (plateau de jeu, page HTML, maison...)

• Définir un Arbre comme

  • soit un Arbre Vide
  • soit l'ensemble d'un Noeud et des sous-arbres auxquelles il mène

• Identifier les sous-arbres d'un Arbre dont on vous donne la Racine

Arbre Binaire

• Définir un Arbre Binaire comme

  • soit un Arbre Vide
  • soit l'ensemble d'un Noeud et de ses DEUX sous-arbres

• Savoir que la position du fils Gauche et du fils Droit ne code pas la même information dans le cas d'un Arbre Binaire.

• Donner l'idée générale d'organisation d'un Arbre Binaire

• Savoir utiliser les fonctions d'interface d'un Arbre Binaire (et des Noeuds)

  • nouveauNoeud(x:Elt) -> Noeud
  • contenu(noeud:Noeud) -> Elt
  • nAV() -> Arbre
  • nouvelArbre(noeud:Noeud, g:Arbre, d:Arbre) -> Arbre
  • racine(arbre:Arbre) -> Noeud
  • gauche(arbre:Arbre) -> Arbre
  • droite(arbre:Arbre) -> Arbre

• Savoir trouver la Taille d'un Arbre Binaire connaissant sa géométrie

• Savoir qu'il existe deux choix pour la profondeur d'une Racine
• Savoir trouver la Profondeur d'un Noeud
• Savoir trouver la Hauteur d'un Arbre
• Définir Arbre Binaire Complet
• Comprendre que pour un Arbre Binaire Complet : hauteur = log2(taille+1) si on prend une profondeur de Racine à 1
• Définir Arbre Binaire Filiforme
• Comprendre que pour un Arbre Binaire Filiforme : hauteur = taille si la profondeur de la Racine est de 1

• Estimer la hauteur d'un Arbre Binaire quelconque :

  • Profondeur 1 pour la racine : ⌈log2(taille+1)⌉ ≤ hauteur ≤ taille
  • Profondeur 0 pour la racine : ⌊log2(taille)⌋ ≤ hauteur ≤ taille - 1

• Que vaut log2(2) ?

• Que vaut log2(4) ?
• Que vaut log2(8) ?
• Que vaut log2(16) ?

A faire !

A faire !

A faire !