Chapitre 1 (en construction)
Structure de Données: Piles et Files
Dans ce chapitre, on va parler de structures de données et en particulier des piles et des files.
​
0 - Mise en situation:
​
Situation 1: Le Large Hadron Collider (LHC) est un collisionneur de particules qui se trouve au Centre Européen pour la Recherche Nucléaire (CERN) à la frontière franco-suisse. Il utilise le tunnel du Large Electron Positron (LEP) pour produire des collisions proton-proton avec une énergie de 14 TeV (à comparer avec l'énergie du premier niveau atomique dans l'atome de Bohr!) dans le centre de masse (chaque faisceau de protons a une énergie de 7 TeV). Les croisements de paquets se produisent toutes les 25 ns (ce qui correspond à une fréquence de 40 MHz) en quatre points où sont installées les expériences (ATLAS, CMS, LHCb et ALICE) qui observent les particules issues de collisions.
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
La figure de gauche montre le détecteur de l'expérience de la physique de particules LHCb. Celle de droite montre les trajectoires de différentes particules crées pendant une seule collision proton-proton.
​
Sachons q'un détecteur en physique de particules est un instrument compliqué constitué de différents modules assurant de nombreuses fonctions électroniques: d’amplification, de filtrage, de comptage, de conversion analogique-numérique (CAN voir sujet mines IPT 2015), d'échantillonnage, du traitement d'informations et d'enregistrement permanent (sur des disques durs ou des bandes magnétiques).
​
Résumons alors la procédure:
​
Interactions rayonnement-matière => Signal physique => Photomultiplicateur => Signal électrique faible => Amplification => Signal électrique puissant => Conversion analogique numérique (CAN) => Enregistrement.
​
Toutes ces opérations prennent un temps d'attente supérieur à 25 ns donc on obtient un problème de recouvrement des signaux physiques.
​
Afin d'éviter ce problème on utilise une mémoire tampon (en anglais Buffer: utilisée pour enregistrer temporairement des données, notamment entre deux processus ne travaillant pas au même fréquence) qui permet de stocker les informations par ordre de leur arrivée (First In First Out ou FIFO).
​
La structure de données utilisée dans une mémoire tampon est appelée une file (en anglais Queue).
​
Les files servent à traiter les données dans l'ordre dans lequel elles arrivent (très utilisées dans les mécanismes d'attente).
​
Les files sont utilisées dans les systèmes d'impression pour traiter les requêtes dans l'ordre dans lequel elles arrivent.
​
Les files sont utilisées par le système d'exploitation dans les mécanismes d'ordonnancement afin de gérer l'ordre d'exécution des processus.
​
Les files sont utilisées aussi dans les algorithmes de parcours en largeur.
​
Situation 2: Pendant la rédaction de son rapport de TIPE avec le logiciel Word sur Windows, Ali a fait une faute de frappe. Afin de corriger l'erreur, il appuie sur les deux boutons ctrl + z en même temps.
​
En effet, la fonction "annuler la frappe dans un traitement de texte" ou le fameux "ctrl + z" utilise une pile afin de mémoriser l'historique de modifications.
​
La pile est la structure de données la plus fondamentale en informatique.
​
Les processus dans un ordinateur gère un système de piles.
​
Une pile est utilisée pour visiter les pages visitées dans un navigateur web (Firefox, InternetExplorer, Chrome...). Chaque page visitée est empilée, le bouton précédent va simplement dépiler afin d'obtenir la page précédemment visitée.
​
On utilise une pile afin d'évaluer les expressions mathématiques sans parenthèses en notation polonaise inverse par exemple a 12 + b * +3 -
​
Les algorithmes de recherche en profondeur et les algorithmes récursifs utilisent aussi des piles.
​
1 - Les structures de données linéaires (les piles et les files)
Définition: Une structure de données est une organisation des données permettant de simplifier ou d'accélérer leur traitement. Elle relie entre elles les données.
​
Type abstrait de donnée:
Dans ce chapitre, on commencera à s'intéresser à un type abstrait de données (on parle aussi de la représentation logique définissant le comportement et qu'on différencie de la réalisation concrète et physique avec utilisation de la mémoire).
​
Implémentation:
Ensuite, on étudiera la question de l'implémentation de ces concepts avec Python.
​
​
On distingue différents types de structures de données ou plutôt comme on vient d'évoquer de type abstrait de données: les structures linéaires et les structures non linéaires.
- Les structures linéaires par exemple permettent de relier des données en séquences, c'est à dire qu'on peut numéroter les éléments. Chaque élément a un rang c'est le cas des listes mais aussi des piles et des files qui sont simplement des cas particuliers de listes, ce sont (les piles et les files) des listes mais avec des opérations restreintes.
​
= Les structures de données non linéaires qui permettent de relier un seul élément à plusieurs autres éléments c'est le cas des arbres, des graphe. (Hors programme IPT uniquement pour les classes MPI)
​
Mais avant de commencer le cours. Demandons-nous: Qu'est ce qu'une liste? Qu'est ce qu'une pile? Qu'est ce qu'une file? A quoi sert une file? ...
​
Une liste est la forme la plus simple et la plus courante d'organisation des données c'est simplement une suite d'éléments du même type. On l'utilise pour stocker en mémoire des données qui doivent être traitées dans un certain ordre. Dans une liste on peut ajouter ou enlever un ou plusieurs éléments ou bien simplement consulter en élément.
​
Une pile est une liste où on ne peut pas ajouter ou enlever des éléments qu'aux extrémités d'un côté ou d'un autre de la liste.
Exemple :
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
En informatique, une pile est une structure dans laquelle le dernier élément ajouté sera le premier à être récupéré. On alors dit qu'une pile suit la règle LIFO en anglais last-in first-out ce qui signifie derniers arrivés les premiers sortis.
​
On peut illustrer ce fonctionnement en prenant l'exemple d'une pile d'assiettes; on ajoute des assiettes sur la pile et on les récupère en commençant par la dernière ajoutée.
​
Maintenant, je vais vous donner la vraie définition d'une pile (en anglais appelée "stack"):
​
Soit P du type pile est une structure de données abstraite, munie des opérations suivantes :
​
- empiler(P,x) : ajoute l’élément x à la pile P si la pile n’est pas pleine, sinon, renvoie une erreur.
- depiler(P) : enlève l’élément au sommet de la pile P et le renvoie. Si la pile est vide, renvoie une erreur.
- est_pleine(P) : suivant la réalisation de la pile, renvoie un booléen suivant si la pile P est pleine ou non. Si
elle est pleine, on ne peut plus ajouter d’éléments.
- sommet(P) : renvoie le sommet de la pile P si celle-ci est non vide.
- est_vide(P) : renvoie un booléen suivant si la pile P est vide ou non.
- creer_pile(n) : construire une pile vide, de capacité n : la pile peut contenir n éléments.
​
2 - Implémentation en Python des opérations:
​
def estVide(P):
return P[0] == 0
​
​
def creerPile(n):
P= [None] * (n+1)
P[0] = 0
return P
​
def estPlein(P):
return P[0] = len(P) - 1
​
def empiler(P,x):
if P[0] == n+1:
return print("Arrêter le programme, débordement!")
else:
i = P[0]
P[i] = x
P[0] = i + 1
return P
​
ou bien
​
def empiler(P,x):
assert not estPleine(P), "la pile est pleine"
P[0] = P[0] + 1
P[P[0]] = x
​
​
def depiler(P):
if P[0] == 1:
print("Attention! il y a un débordement négatif")
return None
else:
P[0] = P[0] - 1
i = P[0]
return P
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
Une file: (en anglais appelée Queue) est une structure de données dans laquelle les éléments sont récupérées dans l'ordre dans lequel ils ont été ajoutés. Les premiers éléments ajoutés seront donc les premiers à être récupérés.
On dit qu'une file suit la règle FIFO en anglais first in first out ce qui signifie premier entré premier sorti.
Pour mieux comprendre on peut prendre l'image d'une file d'attente où les premières personnes sortant de la file sont les premières personnes arrivant.
Sur la figure on montre une file vide, on peut accéder aux deux côtés. Au contraire de la pile, les éléments seront insérés de haut et retiré par le bas:
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
- Ajoutons le nombre A, on dit qu'on enfile un élément.
- On peut ensuite ajouter le nombre B toujours par le haut.
- Maintenant retirons un élément, on retire par le bas. Le nombre A est sorti de la file. On appelle cette opération défiler un élément.
- On peut également consulter la valeur de l'élément A qu'on retire.
- Retirons le nombre B
- Comme pour la pile, il existe aussi une opération pour tester si la file est vide.
​
Mais à quoi sert une file?
​
Les files servent à traiter des données dans l'ordre dans lequel elles arrivent. Elles sont très utilisées dans les mécanismes d'attentes. Une file est utilisée dans les systèmes d'impression pour traiter les requêtes dans l'ordre dans lequel elles arrivent les fils sont utilisés par les systèmes d'exploitation dans les mécanismes d'ordonnancement afin de gérer l'ordre d'exécution des processus. On utilise aussi des files pour gérer une mémoire tampon en anglais buffer les algorithmes de parcours en largeur utilise aussi une file.
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
TD sur les PILES et Les FILES
Exercice 1: (Implémentation d'une pile par un tableau avec Python)
On veut définir une pile d'entiers à l'aide d'un tableau T[0...n]. On utilise donc Python: un tel tableau est défini comme une liste de n+1 entiers, initialisé avec des 0 partout.
1 - Ecrire un programme python qui génére une liste T = [0,...,0] (on pourrait prendre n = 5)
2 - Ecrire deux fonctions EMPILER(P,x) et DEPILER(P) en Python avec les instructions suivantes:
une instruction raise(IndexError) qui met immédiatement fin au programme en générant une erreur de type IndexError (il existe différents type d'erreurs, comme NameError, TypeError, SyntaxError, AssertionError...)
​
3 - Ecrire une fonction PileVide(P) qui retourne True si la pile est vide et False sinon.
​
​
​
Exercice 2: Implémentation d’une file d’attente:
​
Le type abstrait de données “files d’attente” est une structure linéaire de stockage de données munie des fonctions suivantes :
• estFileVide(f) : renvoie True si la file f est vide, False sinon ;
• fileVide() : renvoie la file vide ;
• ajouter(x,f) : ajoute le client x à la fin de la file ;
• suivant(f) : renvoie le client en tête de la file non vide f et le supprime de f.
​
a) Proposer une implémentation en Python où la file est stockée dans une simple liste. Évaluer la complexité des fonctions ajouter et suivant.
​
b) Pour obtenir une complexité en temps constant (ou temps constant amorti) des deux fonctions ajouter et suivant, on se propose de stocker une file à l’aide de deux piles :
∗ la première contient le début de la file, le premier client à servir se trouvant au sommet ;
∗ la deuxième contient la fin de la file, le dernier client entré se trouvant au sommet.
​
Mettre en œuvre ce principe en Python ; concrètement, la file f pourra être définie comme une liste de deux piles [p0,p1]; expliquer son intérêt du point de vue de la complexité. Outre les primitives ci-dessus, on programmera l’affichage d’une file.
​
Exercice 3 : Concours Mines Informatique Pour Tous (IPT) 2017 (lien)
​
​
​
​
​
​
​