Récapitulatif donnees

• Donner l'organisation générale d'une FILE

• Savoir ce que veut dire FIFO

• Définir l'arrière et l'avant d'une FILE

• Connaître l'interface d'une FILE

• Savoir utiliser une interface en version mutable

• Savoir utiliser une interface en version non-mutable

• Savoir ce que réalise la méthode append() sur le type list natif de Python

• Savoir ce que réalise la méthode pop(0) sur le type list natif de Python

• Savoir qu'on peut implémenter une FILE de plusieurs façons dont un tableau contenant deux PILES.

• Être capable d'expliquer le fonctionnement de la FILE contenant deux piles

• Connaître le coût attendu d'une implémentation de la File en lecture, insertion, suppression

  • Coût linéaire au défilement pour l'implémentation sous forme d'un simple tableau ne contenant que les données (peu efficace)
  • Coût parfois linéaire, parfois constant pour l'implémentation deux piles au défilement
  • Coûts CONSTANTS à l'enfilement et défilement pour l'implémentation liste chaînée
  • Coûts CONSTANTS à l'enfilement et défilement pour l'implémentation deux tableaux
  • Coûts CONSTANTS à l'enfilement et défilement pour l'implémentation dictionnaire et un tableau
  • Coûts CONSTANTS à l'enfilement et défilement pour l'implémentation avec un tableau (infos + données)

A faire !

A faire !

A faire !

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