La File présentée ici est facile à réaliser mais a des performances assez faibles.
On ne l'utilise que lorsqu'on veut réaliser rapidement un prototype et qu'on se moque des performances pour le moment.
(Rappel) 1.1 Primitives d'une File
A (RAPPEL) Fonctions d'interface
Fonctions d'interface d'un module : en informatique, les fonctions d'interface caractérisent les fonctions qui sont utilisables par l'utilisateur d'un module.
B (RAPPEL) Primitives
Les primitives font partie des fonctions de base disponibles pour ce type abstrait de données.
En utilisant les primitives, on doit pouvoir construire toutes les autres fonctionnalités voulues.
Les futures implémentations des primitives devront donc avoir le coût le plus faible possible (puisqu'elles sont utilisées par les autres fonctionnalités).
C - Les primitives d'une File
nouvelleFile() -> File VIDE : on crée une nouvelle file vide.
newQueue() en anglais.
estFileVide(f:File) -> bool : prédicat qui renvoie True si la File p transmise est une File vide.
isEmptyQueue() en anglais.
enfiler(f:File, elt:Element) -> File NON VIDE : on renvoie une file en rajoutant l'élément elt à l'ARRIERE dans f.
enqueue() en anglais.
defiler(f:File NON VIDE) -> File : on supprime l'élément à l'AVANT et renvoie la nouvelle File f.
dequeue() en anglais.
La fonction n'est pas définie si la file est vide.
lireAvant(f:File NON VIDE) -> Element : on renvoie l'élément à l'avant (sans le supprimer).
front() en anglais.
La fonction n'est pas définie si la file est vide.
Contrairement à la Liste, il n'y a pas de primitives liées au type intermédiaire Place : pas de fonctions acces(), successeur() ou contenu() nécessaires puisque l'utilisateur n'a le droit que d'accéder au sommet. On lui simplifie le travail en ne lui fournissant que les outils nécessaires à la gestion de ce type de structure.
01° Quel est le coût espéré des primitives enfiler(), defiler() et lire_avant() ?
...CORRECTION...
On voudrait qu'elles soient à coût CONSTANT si possible.
02° On se propose d'utiliser directement le type list de Python pour tenter de faire notre File. Quel est le coût des méthodes suivantes sur un tableau t ?
t.append(elt)
t.pop()
t.pop(0)
t.insert(0, elt)
...CORRECTION...
Nous avons vu que :
t.append(elt) est à coût amorti CONSTANT
t.pop() est à coût CONSTANT
t.pop(0) est à coût LINEAIRE car il faut déplacer tous les éléments d'une case vers la gauche.
t.insert(0, elt) est à coût LINEAIRE car il faut déplacer tous les éléments d'une case vers la droite. Si le tableau dynamique a déjà atteint sa taille maximum, il faudra même recréer un tableau plus grand.
03° Expliquons maintenant pourquoi on ne peut pas obtenir une bonne implémentation de File en utilisant directement le type list de Python :
Possibilité 1 :
l'Arrière est positionné sur l'indice 0 du tableau dynamique et
l'Avant est positionné sur le dernier indice du tableau dynamique.
En image, cela donne ceci :
graph LR
I(("Arrière"))-. enfilement .-> D("[0]") --> C["[1]"] --> B["[2]"] --> A("[3]") -. défilement .-> S(("Avant"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
Questions : avec ce choix d'implémentation
Que veut dire insérer à l'arrière ? Quel est le coût de cette action ?
Que veut dire supprimer à l'avant ? Quel est le coût de cette action ?
Pourquoi ne peut-on pas choisir ceci pour obtenir une bonne implémentation de File ?
...CORRECTION...
Choix 1 : l'arrière est l'indice 0 et l'avant le dernier indice du tableau dynamique.
Insérer à l'arrière veut donc signifier insérer sur l'indice 0.
C'est donc à coût LINEAIRE puisqu'on va devoir utiliser t.insert(0, elt) qui est à coût LINEAIRE.
Supprimer l'avant veut donc signifier supprimer la dernière case du tableau.
C'est donc à coût CONSTANT puisqu'on va devoir utiliser t.pop() qui est à coût CONSTANT.
Cela n'est pas optimum car l'une des deux opérations est à coût LINEAIRE.
04° Passons à l'autre possibilité.
Possibilité 2 :
l'Avant est positionné sur l'indice 0 du tableau dynamique et
l'Arrière est positionné sur le dernier indice du tableau dynamique.
graph RL
I(("Arrière"))-. enfilement .-> D("[3]") --> C["[2]"] --> B["[1]"] --> A("[0]") -. défilement .-> S(("Avant"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
Questions : avec ce choix d'implémentation
Que veut dire insérer à l'arrière ? Quel est le coût de cette action ?
Que veut dire supprimer à l'avant ? Quel est le coût de cette action ?
Pourquoi ne peut-on pas choisir ceci pour obtenir une bonne implémentation de File ?
...CORRECTION...
Choix 2 : l'arrière est l'indice final et l'avant l'indice 0 du tableau.
Insérer à l'arrière va donc signifier l'insertion en fin de tableau dynamique.
C'est donc à coût CONSTANT puisqu'on va devoir utiliser t.append(elt) qui est à coût CONSTANT.
Supprimer à l'avant va donc signifier de supprimer le contenu de la case d'indice 0.
Cela va se faire à coût LINEAIRE puisqu'on va devoir utiliser t.pop(0) qui est à coût LINEAIRE (on va décaler le contenu des cases une à une).
Cela n'est pas optimum car l'une des deux opérations est à coût LINEAIRE.
Voyons maintenant deux autres implémentations de meilleur qualité car elles réagissent à coût constant pour enfiler() et defiler()
.
2 - Bonne implémentation : File avec un modèle liste chaînée Tête Fin
05° On se propose d'implémenter notre File en utilisant comme modèle une liste chaînée de tuples.
Une liste chaînée vide est composée du tuple vide ()
Une liste chaînée non vide pointe vers un tuple (valeur de tête, successeur)
Quels étaient les coûts des fonctions suivantes en utilisant la structure tuples-cellules proposée ci-dessus ?
inserer_tete()
supprimer_tete()
inserer_fin()
supprimer_fin()
...CORRECTION...
Nous avons vu que :
inserer_tete() est à coût CONSTANT.
supprimer_tete() est à coût constant
inserer_fin() est à coût LINEAIRE car il faut supprimer et stocker les têtes pour atteindre la fin et ensuite les remettre en place.
supprimer_fin() est à coût LINEAIRE car il faut supprimer et stocker les têtes pour atteindre la fin et ensuite les remettre en place.
06° Pourquoi n'est-il pas utile de continuer sur cette voie d'implémentation ?
...CORRECTION...
Nous avons besoin de savoir insérer à coût CONSTANT d'un côté et de supprimer à coût CONSTANT de l'autre.
Puisqu'on agit toujours à coût LINEAIRE sur la Fin, on ne parviendra pas à agir de façon constante sur ce côté.
07° On se propose d'implémenter notre File en utilisant comme modèle une liste chaînée d'objets Cellule.
Une liste chaînée vide est composée un objet dont l'attribut tete contient None.
Une liste chaînée non vide est un objet dont l'attribut tete pointe vers une Cellule (qui est la cellule de tête).
Quels étaient les coûts des fonctions suivantes en utilisant la structure proposée ci-dessus (sur laquelle on ne connaît que la référence de la Tête) ?
inserer_tete()
supprimer_tete()
inserer_fin()
supprimer_fin()
...CORRECTION...
Nous avons vu que :
insererTete() est à coût CONSTANT puisqu'on sait localiser facilement la tête.
supprimerTete() est à coût CONSTANT puisqu'on sait localiser facilement la tête
insererFin() est à coût LINEAIRE car on d'abord localiser la cellule de Fin en partant de la la cellule de Tête.
supprimerFin() est à coût LINEAIRE car on doit d'abord localiser le prédécesseur de la cellule de Fin en partant de la Tête.
08° Pourquoi n'est-il pas utile de continuer sur cette voie d'implémentation ?
...CORRECTION...
Nous avons besoin de savoir insérer à coût CONSTANT d'un côté et de supprimer à coût CONSTANT de l'autre.
Puisqu'on agit toujours à coût LINEAIRE sur la Fin, on ne parviendra pas à agir de façon constante sur ce côté.
09° Comment améliorer notre liste chaînée pour parvenir à nous permettre d'implémenter correctement une File ?
...CORRECTION...
Il faudrait parvenir à insérer à coût CONSTANT en Fin de liste.
Nous avions vu dans l'activité Implémentation de Liste 3 que c'était possible si on stockait la référence de la Cellule de Fin dans la liste, en plus de la Cellule de Tête.
Voici donc ce que vous allez faire dans cette partie : réaliser une File à partir d'une Liste pointant sa Tête et sa Fin déjà implémentée (dans l'activité Implémenter une Liste 3).
10° Voici un extrait de la documentation de ce module : on y détaille notamment les coûts des différentes fonctions d'insertion et de suppression.
Question : Où placer l'Avant pour obtenir une suppression à coût CONSTANT ? où placer l'Arrière pour insérer à coût CONSTANT ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Primitives d'interface cachant l'aspect objet---------------------------------------------+ CST : nouvelle_liste() -> Liste+ CST : est_liste_vide(lst:'Liste') -> bool+ CST : inserer_tete(lst:'Liste', elt:'Element') -> None+ CST : inserer_fin(lst:'Liste', elt:'Element') -> None+ LIN : inserer(lst:'Liste', elt:'Element', i:'int VALIDE') -> None+ CST : supprimer_tete(lst:'Liste NON VIDE') -> 'Element'+ LIN : supprimer_fin(lst:'Liste NON VIDE') -> 'Element'+ LIN : supprimer(lst:'Liste', i:'int VALIDE') -> 'Element'+ LIN : longueur(lst:'Liste') -> int+ CST : premier(lst:'Liste NON VIDE') -> 'Element'+ CST : dernier(lst:'Liste NON VIDE') -> 'Element'+ LIN : ieme(lst:'Liste NON VIDE', i:'int VALIDE') -> 'Element'
...CORRECTION...
Un seul choix possible pour la suppression à coût constant : on ne sait que supprimer la Tête. Cela veut donc dire qu'il faudra placer l'AVANT au niveau de la TETE.
On placera donc l'ARRIERE au niveau de la FIN et ça tombe bien : on sait insérer à coût constant au niveau de la FIN.
11° Téléchargez le module, et enregistrez le dans un répertoire implementation_file de votre espace de travail. Il faudra impérativement enregistrer le module sous le nom liste_chainee_objet_tete_fin.py.
12° Créer dans le même répertoire un programme file_basee_liste_tete_fin.py dont le contenu est fourni ci-dessous. Attention, les assertions vont provoquer l'arrêt brutal car les fonctions ne sont pas complétées pour le moment :
"""Module proposant une implémentation d'une File MUABLE en utilisant une liste chaînée tete-fin sous forme objetSur notre exemple :* L'AVANT de la File est la TETE de la liste chaînée (pour la suppression à coût CST)* L'ARRIERE de la File est la FIN de la liste chaînée (pour l'insertion à coût CST)Fonctions primitives--------------------CST : nouvelle_file() -> 'File'CST : est_file_vide(f:'File') -> boolCST : enfiler(f:'File', elt:'Element') -> NoneCST : defiler(f:'File NON VIDE') -> 'Element'CST : lire_avant(f:'File NON VIDE') -> 'Element'"""# Importationfromliste_chainee_objet_tete_finimportnouvelle_listefromliste_chainee_objet_tete_finimportest_liste_videfromliste_chainee_objet_tete_finimportinserer_finfromliste_chainee_objet_tete_finimportsupprimer_tetefromliste_chainee_objet_tete_finimportpremier# Fonctions primitives de la Filedefnouvelle_file()->'File':"""Renvoie une nouvelle File vide"""passdefest_file_vide(f:'File')->bool:"""Prédicat qui renvoie True si la File est vide"""passdefenfiler(f:'File',elt:'Element')->None:"""Enfile elt dans la File"""passdefdefiler(f:'File NON VIDE')->'Element':"""Défile la file f"""passdeflire_avant(f:'File')->'Element':pass# Programme de testif__name__=='__main__':a=nouvelle_file()enfiler(a,0)enfiler(a,5)enfiler(a,10)enfiler(a,15)s=lire_avant(a)asserts==0defiler(a)s=lire_avant(a)asserts==5
Utiliser une Liste Tete Fin pour implémenter une File
Choix de la place de l'Avant
On place l'Avant de la File du côté la Tête de la Liste puisque la suppression est à coût CONSTANT uniquement sur la Tête.
On place donc l'Arrière du côté de la Fin. ATTENTION : pour obtenir une insertion en Fin à coût CONSTANT, il faut impérativement une Liste mémorisant Tête et Fin.
Les données du point de vue de la File
graph RL
I(("Arrière"))-. enfilement .-> D("Fin de Liste") o--o C["..."] o--o B["..."] o--o A("Tête de Liste") -. défilement .-> S(("Avant"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
13° Finaliser le module File en réalisant les 5 primitives de la File en utilisant en interne le module Liste qui utilise lui-même en interne une implémentation objet.
graph TB
A("file_basee_liste_tete_fin.py") -- importe --> C["liste_chainee_objet_tete_fin"] -- "utilisant un modèle" --> B["liste chaînée Tête Fin"]
Il faudra bien entendu comprendre comment utiliser les fonctions importées sur les lignes 20 à 24 depuis le module liste_chainee_objet_tete_fin.
La fonction native help() est votre amie !
>>> help(inserer_fin)
Help on function inserer_fin in module liste_chainee_objet_tete_fin: inserer_fin(lst: 'Liste', elt: 'Element') -> None Rajoute elt en Fin de liste>>> help(...)
Correction du Module File dont le modèle est une liste chaînée Tête Fin
"""Module proposant une implémentation d'une File MUABLE en utilisant une liste chaînée tete-fin sous forme objetSur notre exemple :* L'AVANT de la File est la Tete de la liste chaînée (pour la suppression à coût CST)* L'ARRIERE de la File est la Fin de la liste chaînée (pour l'insertion à coût CST)Fonctions primitives--------------------CST : nouvelle_file() -> 'File'CST : est_file_vide(f:'File') -> boolCST : enfiler(f:'File', elt:'Element') -> NoneCST : defiler(f:'File NON VIDE') -> 'Element'CST : lire_avant(f:'File NON VIDE') -> 'Element'"""# Importationfromliste_chainee_objet_tete_finimportnouvelle_listefromliste_chainee_objet_tete_finimportest_liste_videfromliste_chainee_objet_tete_finimportinserer_finfromliste_chainee_objet_tete_finimportsupprimer_tetefromliste_chainee_objet_tete_finimportpremier# Fonctions primitives de la Filedefnouvelle_file()->'File':"""Renvoie une nouvelle File vide"""returnnouvelle_liste()defest_file_vide(f:'File')->bool:"""Prédicat qui renvoie True si la File est vide"""returnest_liste_vide(f)defenfiler(f:'File',elt:'Element')->None:"""Enfile elt dans la File"""inserer_fin(f,elt)# L'insertion en fin d'une Liste Tête-Fin est à coût constantdefdefiler(f:'File NON VIDE')->'Element':"""Défile la file f"""returnsupprimer_tete(f)deflire_avant(f:'File')->'Element':returnpremier(f)# Programme de testif__name__=='__main__':a=nouvelle_file()enfiler(a,0)enfiler(a,5)enfiler(a,10)enfiler(a,15)s=lire_avant(a)asserts==0defiler(a)s=lire_avant(a)asserts==5
3 - Bonne implémentation d'une File MUTABLE : modèle à deux Piles
On utilise une Pile pour gérer l'Arrière et une autre Piles pour gérer l'Avant :
Lorsqu'on veut enfiler un élément, on l'empile dans une PilepileEntree.
Lorsqu'on veut defiler, on dépile en réalité le sommet d'une PilepileSortie.
Pour comprendre réellement le mécanisme, rien de mieux qu'un exemple.
Sur l'image ci-dessous, on a inséré les horaires d'arrivée des clients dans un magasin.
Le premier est arrivé à 13h,
le suivant à 13h20...
La dernière heure au Sommet de pileEntree correspondant donc à l'arrivée du dernier client.
Pour défiler ces données, on voit bien qu'on ne peut pas juste dépiler cette Pile : on obtiendrait le client qui vient d'entrer, celui de 14h30 !
Comment faire ?
14° En considérant qu'on ne peut agir que sur les deux Piles, auriez-vous une solution pour récupérer le client entré à 13h ?
Comme souvent, la solution est évidente ... une fois qu'on l'a trouvé.
Comment faire alors ?
Nous avons déjà vu plusieurs fois que vider une Pile dans une Pile (ou une Liste dans une Liste en n'agissant que sur la Tête) revient à inverser les éléments.
L'idée est donc de déverser la Pile d'entrée dans la Pile de sortie.
Le Sommet d'entrée le plus récent (en rose) se retrouve en dernière position dans la Pile de sortie.
Et l'élément au Somment de la pile de Sortie se trouve être le plus ancien élément de l'entrée.
La subtilité est qu'il ne faut faire ce déversement que SI (la Pile de sortie est vide ET qu'on veut défiler).
La File avec un modèle deux Piles
On utilise une Pile pour gérer l'Arrière et une autre Pile pour gérer l'Avant :
Lorsqu'on veut enfiler un élément, on l'enfile dans une Pile d'entrée qu'on nommera pileEntree.
Lorsqu'on veut défiler les données de la File, deux cas se présentent :
SI pileSortie est vide :
On déverse d'abord pileEntree dans pileSortie en dépilant les éléments un par un dans l'autre pile : cela va permettre d'inverser les positions respectives du premier arrivé et du dernier arrivé.
Après cette opération, pileEntree est vide : il suffit de dépiler la Pile d'entrée pour défiler.
SI la pileSortie n'est pas vide :
Pour défiler, il suffit de dépiler pileSortie.
Il ne faut surtout pas déverser car l'élément le plus ancien non traité est bien le sommet de pileSortie. Si on rajoute les éléments de la pile d'entrée, on va mettre des éléments plus récents au dessus du plus ancien
Les étapes de l'inversion en images
pileEntree a déjà reçu ceci :
On veut défiler mais pileSortie est vide. Il faut donc déverser pileEntree dans pileSortie. Comment ? Tant que pileEntree n'est pas vide, on la dépile en mémorisant l'ancien sommet qu'on empile dans pileSortie.
Etape 1 : On dépile pileEntree en mémorisant l'ancien sommet (14h30) et on l'empile dans pileSortie
On continue. On dépile pileEntree en mémorisant l'ancien sommet (14h20) et on l'empile dans pileSortie
On continue. On dépile pileEntree en mémorisant l'ancien sommet (14h00) et on l'empile dans pileSortie
Au final, à la fin du déversement, pileEntree sera vide et pileSortie aura de nouveaux éléments et son sommet sera bien le plus ancien élément reçu par la File !
Maintenant que pileSortie n'est pas vide, on peut la défiler et obtenir l'élément "13h".
Et on peut continuer à enfiler de nouveaux éléments : ils iront dans pileEntree. D'ailleurs, tant que pileSortie n'est pas vide, ces éléments resteront stocker dans pileEntree.
Nous allons maintenant réaliser cette implémentation de File MUABLE basée sur deux Piles IMMUABLES par exemple.
L'utilisateur écrira donc des instructions de ce type pour manipuler sa File MUABLE :
enfiler(file, 5) pour enfiler 5 dans sa File.
Par contre, comme nos Piles sont immuables, on écrira des choses comme ceci à l'intérieur des primitives puisqu'on manipulera des Piles IMMUABLES pour implémenter les données de notre Pile MUABLE :
Pour enfiler : pileEntree = empiler(pileEntree, 5).
Pour défiler : pileSortie = defiler(pileSortie).
graph LR
I(("Arrière"))-- enfilement --> D("Pile d'entrée") -- "déversement si sortie vide" --> A("Pile de sortie") -- défilement --> S(("Avant"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
15-A° ENFILEMENT : nous allons stocker les références de nos deux piles dans un tableau que nous nommerons f puisque cette variable permettra de gérer la file.
f = [pileEntree, pileSortie].
Pour accéder à la pileEntree, il suffit donc d'accéder à f[0].
Pour accéder à la pileSortie, il suffit donc d'accéder à f[1].
Voici donc un exemple d'utilisation de la file : on y enfile des éléments qui viennent s'empiler dans la pile d'entrée.
>>> f = nouvelleFile()
>>> f
[(), ()]>>> enfiler(f, 5)
>>> f
[(5, ()), ()]>>> enfiler(f, 10)
>>> enfiler(f, 20)
>>> f
[(20, (10, (5, ()))), ()]
Question : quelle instruction doit-on trouver dans la fonction enfiler() pour parvenir à rajouter un nouvel élément dans la pileEntree IMMUABLE ? A ou B ?
f[0] = empiler(f[0], 5)
empiler(f[0], 5)
...CORRECTION...
Pour obtenir la référence de pileEntree, il faut utiliser effectivement f[0] puisque la pile d'entrée est stockée dans l'indice 0 du tableau f.
Les piles sont IMMUABLES dans cette implémentation : les fonctions "modifiant" les piles renvoient donc une "copie modifiée" de la pile fournie en entrée.
La réponse est donc A :
f[0] = empiler(f[0], 5)
De façon abstraite, cela revient à demander ceci :
pileEntree = empiler(pileEntree, 5)
15-B° LECTURE DE L'AVANT : on désire maintenant lire l'Avant de notre File (le 5 puisque c'est le premier élément qu'on avait inséré), il faudra d'abord regarder si la pile de sortie f[1] est vide, ou pas.
Comme c'est le cas ici, il faudra déverser la pile d'entrée f[0] dans la pile de sortie f[1].
>>> f
[(20, (10, (5, ()))), ()]>>> lire_avant(f)
5>>> f
[(), (5, (10, (20, ())))]>>> enfiler(f, 50)
>>> f
[(50, ()), (5, (10, (20, ())))]>>> lire_avant(f)
5>>> f
[(50, ()), (5, (10, (20, ())))]
Deux question :
sur l'exemple ci-dessus, que voyez-vous de notable sur la position du plus ancien élément (5) stockée avant et après la premier lecture ?
pourquoi le 5 est-il toujours au sommet de la pile de sortie même après avoir enfiler un 50 et demander une deuxième lecture de l'Avant ?
...CORRECTION...
On remarque que le contenu de la pile est inversée. Le 5 est maintenant au sommet de la pile de sortie. Or, ce 5 était le premier arrivé lors du remplissage de la pile d'entrée.
15-C° DEFILEMENT : on veut maintenant défiler notre file, implémentée avec deux piles. Pour cela, il suffit de dépiler la pile de sortie.
f = [pileEntree, pileSortie].
>>> f
[(), (5, (10, (20, ())))]>>> defiler(f)
5>>> f
[(), (10, (20, ()))]
Question quelle instruction doit-on trouver dans la fonction defiler() pour parvenir à supprimer le sommet de la pile de sortie IMMUABLE stockée à l'intérieur de la variable f ?
f[1] = depiler(f[1])
depiler(f[1])
...CORRECTION...
Pour atteindre la pile de sortie, il faut utiliser f[1] puisque la pile de sortie est stockée dans l'indice 1 du tableau f.
L'énoncé dit que nos piles sont IMMUABLES. Si on veut modifier notre File, il faut donc remplacer par affectation l'ancienne Pile de sortie par la nouvelle.
La réponse est donc A : f[1] = depiler(f[1])
Passons à l'écriture de l'implémentation File avec deux Piles.
Vous disposez plus bas d'un module incorporant une implémentation d'une Pile IMMUABLE (déjà réalisée) et l'ébauche de l'implémentation d'une File MUABLE basée sur l'utilisation de deux Piles.
Vous trouverez plus bas la correction du module complet en cas de problèmes lors de la réalisation du module.
16° Deux questions.
Regarder l'implémentation ci-dessous. Comment se nomment les fonctions permettant de vérifier si une pile ou une file est vide ?
Regarder la fonction nouvelle_file(). Quelle est la structure qui stocke les données de la file ? Que contient cette structure ?
"""Module implémentant un File MUABLE en utilisant un tableau de deux PilesLes Piles sont implémentées sous forme de tuples (sommet, reste de la pile)Les Files sont implémentées sous forme de tableaux [pileEntree, pileSortie]Fonctions primitives de la File--------------------------------... : nouvelle_file() -> 'File'... : est_file_vide(f:'File') -> bool... : enfiler(f:'File', elt:'Element') -> None... : defiler(f:'File NON VIDE') -> 'Element'... : lire_avant(f:'File NON VIDE') -> 'Element'"""# Primitives de la File (fait partie de l'interface utilisateur)defnouvelle_file()->'File':"""Renvoie la référence d'une File sous forme d'un tableau [pileEntree, pileSortie]"""pile_entree=nouvelle_pile()# inputStack en anglaispile_sortie=nouvelle_pile()# outputStack en anglaisreturn[pile_entree,pile_sortie]defest_file_vide(f:'File')->bool:"""Prédicat qui renvoie True si la File est entièrement vide, False sinon"""returnest_pile_vide(f[0])andest_pile_vide(f[1])defenfiler(f:'File',elt:'Element')->None:"""Enfile l'élement elt dans la file f"""passdefdefiler(f:'File NON VIDE')->'Element':"""Défile la file NON VIDE f et renvoie l'élément supprimé"""passdeflire_avant(f:'File NON VIDE')->'Element':"""Renvoie l'avant de la file NON VIDE f sans la modifier"""pass# Fonctions primitives des PILES (Hors interface utilisateur)defnouvelle_pile()->'Pile':"""Renvoie une Pile vide"""return()defest_pile_vide(p:'Pile')->bool:"""Prédicat qui renvoie True si la pile est vide"""returnp==()defempiler(p:'Pile',elt:'Element')->'Pile':"""Renvoie une nouvelle pile où elt est le sommet et pile la suite de notre nouvelle pile."""return(elt,p)defdepiler(p:'Pile NON VIDE')->'Pile':"""Renvoie une nouvelle pile où on a supprimé l'ancien sommet d'une pile NON VIDE"""returnp[1]deflire_sommet(p:'Pile NON VIDE')->'Element':"""Renvoie la valeur stockée au sommet d'une pile NON VIDE"""returnp[0]# Autres fonctions hors interfacedefdeverser_entree_vers_sortie(f:'File')->None:"""Déverse entièrement la pile d'entrée dans la pile de sortie"""whilenotest_pile_vide(f[0]):elt=lire_sommet(f[0])f[0]=depiler(f[0])f[1]=empiler(f[1], elt)# Programme de testif__name__=='__main__':a=nouvelle_file()enfiler(a,0)enfiler(a,5)enfiler(a,10)enfiler(a,15)s=lire_avant(a)asserts==0defiler(a)s=lire_avant(a)asserts==5
...CORRECTION...
On constate que les fonctions se nomment est_pile_vide() et est_file_vide().
La FILE est implémentée sous la forme d'un tableau de deux éléments : l'indice 0 correspond à la pile d'entrée et l'indice 1 correspond à la pile de sortie.
f = [pileEntree, pileSortie].
17-A° Créer la fonction enfiler() après avoir étudié le prototype pour savoir ce qu'elle doit recevoir et renvoyer. Pensez à aller revoir les QCM précédents si vous n'arrivez pas à trouver ce qu'il faut y faire.
Prototype
enfiler(f:'File',elt:'Element')->None
17-B° Expliquer comment la fonction deverser_entree_vers_sortie() réalise le déversement de la pile d'entrée vers la pile de sortie.
1
2
3
4
5
6
defdeverser_entree_vers_sortie(f:'File')->None:"""Déverse entièrement la pile d'entrée dans la pile de sortie"""whilenotest_pile_vide(f[0]):elt=lire_sommet(f[0])f[0]=depiler(f[0])f[1]=empiler(f[1], elt)
Notez bien que cette fonction ne fait pas partie de l'interface : l'utilisateur n'est pas censé faire cela lui-même : ce sont les fonctions d'interface defiler() et lire_avant() qui en font l'appel au besoin. L'utilisateur n'est pas autorisé à l'utiliser puisqu'elle ne figure pas dans la liste des fonctions d'interface utilisables.
17-C° Créer la fonction lire_avant(). Attention, pensez à vérifiez d'abord si la pile de sortie est vide. Dans ce cas, il faudra utiliser la fonction deverser_entree_vers_sortie() pour remplir la file de sortie.
On pourra ensuite lire le sommet de la pile de sortie.
Prototype
lire_avant(f:'File NON VIDE')->'Element'
17-D° Créer la fonction defiler() qui devra également d'abord utiliser deverser_entree_vers_sortie() si la pile de sortie est vide. Attention, notez bien que cette fonction travaille sur une File MUABLE et qu'on en profite pour renvoyer l'élément qu'on vient de supprimer.
Prototype
defiler(f:'File NON VIDE')->'Element'
Le code final corrigé est en fin de section.
18° Utiliser des instructions dans la console pour enfiler 5, 10, 20. Défiler (vous devriez obtenir 5). Enfiler ensuite un 40. Défiler jusqu'à bout. Vous devriez obtenir le 10, le 20 puis le 40.
...CORRECTION...
>>> f = nouvelle_file()
>>> enfiler(f, 5)
>>> f
[(5, ()), ()]>>> enfiler(f, 10)
>>> f
[(10, (5, ())), ()]>>> enfiler(f, 20)
>>> file
[(20, (10, (5, ()))), ()]>>> defiler(f)
5>>> f
[(), (10, (20, ()))]>>> enfiler(f, 40)
>>> f
[(40, ()), (10, (20, ()))]>>> defiler(f)
10>>> f
[(40, ()), (20, ())]>>> defiler(f)
20>>> f
[(40, ()), ()]>>> defiler(f)
40>>> f
[(), ()]
19° Quel est le coût de la fonction enfiler() ?
Constant 𝞗(1)
Linéaire en 𝞗(n)
Linéaire en 𝞞(n)
Quadratique en 𝞗(n2)
...CORRECTION...
La fonction enfiler() consiste à :
Accéder à une case d'un tableau statique dont on connait l'indice : coût constant
Utiliser la fonction d'interface des piles empiler() : coût constant avec l'implémentation (sommet, reste de la pile)
La fonction enfiler() est donc à coût constant.
20° Quel est le coût de la fonction lire_avant() dans le meilleur des cas ? dans le pire des cas ?
Constant 𝞗(1) dans le meilleur des cas et dans le pire des cas.
Constant 𝞗(1) dans le meilleur des cas et linéaire en 𝞗(n) dans le pire des cas.
Constant 𝞗(1) dans le meilleur des cas et linéaire en 𝞞(n) dans le pire des cas.
Linéaire en 𝞗(n) dans le meilleur des cas et dans le pire des cas.
Linéaire en 𝞞(n) dans le meilleur des cas et dans le pire des cas.
...CORRECTION...
Dans le meilleur des cas, la fonction lire_avant() consiste à :
Accéder à une case d'un tableau statique dont on connait l'indice : coût constant
Utiliser la fonction d'interface des piles lire_sommet() : coût constant avec l'implémentation (sommet, reste de la pile)
La fonction lire_avant() est donc à coût constant dans le meilleur des cas.
Dans le pire des cas, il va falloir déverser les données (intégralement stockées dans la pile d'entrée) dans la pile de sortie avant toute lecture. Comme on doit déplacer les données une par une de la pile d'entrée vers la pile de sortie, on retrouve un coût linéaire. Et comme on doit vraiment gérer toute les données, la complexité est bien en 𝞗(n).
Il s'agit donc de la réponse B.
21° Quel est le coût de la fonction defiler() dans le meilleur des cas ? dans le pire des cas ?
Constant 𝞗(1) dans le meilleur des cas et dans le pire des cas.
Constant 𝞗(1) dans le meilleur des cas et linéaire en 𝞗(n) dans le pire des cas.
Constant 𝞗(1) dans le meilleur des cas et linéaire en 𝞞(n) dans le pire des cas.
Linéaire en 𝞗(n) dans le meilleur des cas et dans le pire des cas.
Linéaire en 𝞞(n) dans le meilleur des cas et dans le pire des cas.
...CORRECTION...
C'est exactement comme la lecture de l'avant. La réponse est donc la réponse B.
Implémentation n° 1 d'une File MUABLE basée à l'interne sur l'utilisation de deux Piles IMMUABLES
graph LR
I(("Arrière"))-. enfilement .-> D("Pile d'entrée") -- "déversement si sortie vide" --> A("Pile de sortie") -. défilement .-> S(("Avant"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
Principe général
Enfiler dans la File revient à empiler dans la Pile d’entréef[0].
Défiler la File revient à dépiler la Pile de sortie NON VIDEf[1].
Astuce (à connaître) : Si la Pile de sortie est VIDE lorsqu’on veut défiler, il faut d’abord déverser la Pile d’entrée dans la Pile de sortie.
Coût du défilement
On notera que le coût du défilement dépend de la pile de sortie.
Si elle contient encore des données, le coût est CONSTANT.
Si elle est vide, il faut d'abord déverser une fois à coût LINEAIRE les données situées dans la pile d'entrée.
Comme avec le tableau dynamique, on retrouve alors la notion de coût CONSTANT amorti : le coût est globalement constant puisqu'on va réaliser ce déversement assez peu souvent. Sans faire de théorie, on voit que le coût va être souvent constant et uniquement parfois linéaire. C'est pour cela qu'on considère que le coût amorti est constant.
Module 1
AVANTAGE : le module est indépendant de tout autre module.
DESAVANTAGE : on a dû créer un type Pile local pour créer notre File, alors qu'on a déjà créer une Pile plusieurs fois auparavant...
"""Module implémentant un File MUABLE en utilisant un tableau de deux PilesLes Piles sont implémentées sous forme de tuples (sommet, reste de la pile)Les Files sont implémentées sous forme de tableaux [pileEntree, pileSortie]Fonctions primitives de la File--------------------------------CST : nouvelle_file() -> 'File'CST : est_file_vide(f:'File') -> boolCST : enfiler(f:'File', elt:'Element') -> NoneCST* : defiler(f:'File NON VIDE') -> 'Element'CST : lire_avant(f:'File NON VIDE') -> 'Element'"""# Fonctions primitives de la File (interface utilisateur)defnouvelle_file()->'File':"""Renvoie la référence d'une File sous forme d'un tableau [pileEntree, pileSortie]"""pile_entree=nouvelle_pile()# inputStack en anglaispile_sortie=nouvelle_pile()# outputStack en anglaisreturn[pile_entree,pile_sortie]defest_file_vide(f:'File')->bool:"""Prédicat qui renvoie True si la File est entièrement vide, False sinon"""returnest_pile_vide(f[0])andest_pile_vide(f[1])defenfiler(f:'File',elt:'Element')->None:"""Enfile l'élement elt dans la file f"""f[0]=empiler(f[0],elt)defdefiler(f:'File NON VIDE')->'Element':"""Défile la file NON VIDE f et renvoie l'élément supprimé"""ifest_pile_vide(f[1]):deverser_entree_vers_sortie(f)valeur=lire_sommet(f[1])f[1]=depiler(f[1])returnvaleurdeflire_avant(f:'File NON VIDE')->'Element':"""Renvoie l'avant de la file NON VIDE f sans la modifier"""ifest_pile_vide(f[1]):deverser_entree_vers_sortie(f)returnlire_sommet(f[1])# Fonctions primitives des PILES (hors interface)defnouvelle_pile()->'Pile':"""Renvoie une Pile vide"""return()defest_pile_vide(p:'Pile')->bool:"""Prédicat qui renvoie True si la pile est vide"""returnp==()defempiler(p:'Pile',elt:'Element')->'Pile':"""Renvoie une nouvelle pile où elt est le sommet et pile la suite de notre nouvelle pile."""return(elt,p)defdepiler(p:'Pile NON VIDE')->'Pile':"""Renvoie une nouvelle pile où on a supprimé l'ancien sommet d'une pile NON VIDE"""returnp[1]deflire_sommet(p:'Pile NON VIDE')->'Element':"""Renvoie la valeur stockée au sommet d'une pile NON VIDE"""returnp[0]# Autres fonctions hors interfacedefdeverser_entree_vers_sortie(f:'File')->None:"""Déverse entièrement la pile d'entrée dans la pile de sortie"""whilenotest_pile_vide(f[0]):elt=lire_sommet(f[0])f[0]=depiler(f[0])f[1]=empiler(f[1], elt)# Programme de testif__name__=='__main__':a=nouvelle_file()enfiler(a,0)enfiler(a,5)enfiler(a,10)enfiler(a,15)s=lire_avant(a)asserts==0defiler(a)s=lire_avant(a)asserts==5
Implémentation n° 2 d'une File MUABLE basée à l'interne sur l'utilisation de deux Piles IMMUABLES
Le problème de l'implémentation précédente ?
On utilise le type Pile mais on crée intégralement le type dans le module plutôt que d'utiliser une Pile IMMUABLE déjà implémentée ailleurs.
Module 2 dépendant du module pile_immuable
Avantage : le module File lui-même est plus court et on peut changer facilement de support pour gérer les Piles.
Désavantage : le module File possède une dépendance par rapport au module Pile.
"""Module implémentant un File MUABLE en utilisant un tableau de deux PilesLes Files sont implémentées sous forme de tableaux [pileEntree, pileSortie]Fonctions primitives de la File--------------------------------CST : nouvelle_file() -> 'File'CST : est_file_vide(f:'File') -> boolCST : enfiler(f:'File', elt:'Element') -> NoneCST* : defiler(f:'File NON VIDE') -> 'Element'CST : lire_avant(f:'File NON VIDE') -> 'Element'"""# Importationfrompile_immuableimportnouvelle_pilefrompile_immuableimportest_pile_videfrompile_immuableimportempilerfrompile_immuableimportdepilerfrompile_immuableimportlire_sommet# Fonctions primitives et d'interface de la Filedefnouvelle_file()->'File':"""Renvoie la référence d'une File sous forme d'un tableau [pileEntree, pileSortie]"""pile_entree=nouvelle_pile()# inputStack en anglaispile_sortie=nouvelle_pile()# outputStack en anglaisreturn[pile_entree,pile_sortie]defest_file_vide(f:'File')->bool:"""Prédicat qui renvoie True si la File est entièrement vide, False sinon"""returnest_pile_vide(f[0])andest_pile_vide(f[1])defenfiler(f:'File',elt:'Element')->None:"""Enfile l'élement elt dans la file f"""f[0]=empiler(f[0],elt)defdefiler(f:'File NON VIDE')->'Element':"""Défile la file NON VIDE f et renvoie l'élément supprimé"""ifest_pile_vide(f[1]):deverser_entree_vers_sortie(f)valeur=lire_sommet(f[1])f[1]=depiler(f[1])returnvaleurdeflire_avant(f:'File NON VIDE')->'Element':"""Renvoie l'avant de la file NON VIDE f sans la modifier"""ifest_pile_vide(f[1]):deverser_entree_vers_sortie(f)returnlire_sommet(f[1])# Fonctions hors interfacedefdeverser_entree_vers_sortie(f:'File')->None:"""Déverse entièrement la pile d'entrée dans la pile de sortie"""whilenotest_pile_vide(f[0]):elt=lire_sommet(f[0])f[0]=depiler(f[0])f[1]=empiler(f[1], elt)# Programme de testif__name__=='__main__':a=nouvelle_file()enfiler(a,0)enfiler(a,5)enfiler(a,10)enfiler(a,15)s=lire_avant(a)asserts==0defiler(a)s=lire_avant(a)asserts==5
22-A (mini-projet individuel)° Réaliser le squelette du module implémentant ce type de file : ne fournissez que les prototypes des primitives : types attendus, la phrase de description de l'action provoquée.
22-B (mini-projet individuel)° Réaliser un module proposant une interface liée à ce type d'implémentation.
22-C (mini-projet individuel)° Proposer un jeu de tests complet pour votre code.
Activité publiée le 14 10 2020
Dernière modification : 27 11 2022
Auteur : ows. h.
