Aller au contenu

Interface (Bac 🎯)⚓︎

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 Synthèse de ce qu'il faut retenir pour le bac

Interface du type abstrait File⚓︎

Point de cours 1

Une file est un ensemble ordonné d'éléments qui se manipule comme une file d'attente :

  • on peut insérer un élément à la fin de la file, c'est l'opération enfiler
  • on peut tester si la file est vide, c'est l'opération file_vide
  • si la file n'est pas vide, on peut retirer l'élément en début de file, c'est l'opération défiler

alt

L'interface du type abstrait File peut se réduire à quatre opérations :

Opération Signature Description
creer_file creer_file() Renvoie une file vide
file_vide file_vide(file) Renvoi un booléen indiquant si la file est vide
enfiler enfiler(file, elt) Ajoute elt à la fin de la file
defiler defiler(file) Retire l'élément au début de la file et le renvoie

Quelques propriétés à retenir :

  • Le premier élément qu'on peut retirer d'une file est forcément le premier à y être entré, c'est une structure First In First Out (FIFO).
Acronyme anglais Signification Structure
LIFO Dernier entré premier sorti Pile
FIFO Premier entré premier sorti File
  • En particulier si on défile tous les élément, l'ordre dans lequel on les retire de la file est le même que leur ordre d'insertion.
  • La séquence d'éléments dans la file peut être représentée par une liste mais contrairement à une pile on a besoin d'accéder à deux éléments qui sont aux extrémités de la liste.
  • Le type File nécessite un accès aux deux extrémités d'une liste donc une implémentation par une liste chaîné immuable avec des tuples n'est pas possible comme pour le type Pile. On proposera des implémentations de file mutable mais on verra une implémentation du type File avec deux piles, qui peut se décliner en file immuable si on utilise des piles immuables implémentées avec des tuples.

⏱️ Complexité

L'accès à deux extrémités peut se traduire par des complexités différentes si on a besoin de parcourir toute la structure pour atteindre l'une des extrémités. Selon l'implémentation on aura :

  • une complexité constante en \(O(1)\) et une linéaire en \(O(n)\) pour les opérations defiler et enfiler.
  • une complexité constante en \(O(1)\) pour les deux opérations, ce qui peut être réalisé sans trop d'efforts.

Exemple 1 : applications des files

La structure de File se retrouve dans de nombreuses situations où on doit gérer un ensemble d'éléments :

  • la file d'attente à un guichet de gare, à une caisse de supermarché, pour accéder à une formation sélective sur Parcoursup ...
  • le stockage des yaourts dans un rayon de supermarché : le client défile le yaourt qui se trouve devant, le cariste enfile les nouveaux produits derrière.

On retrouve aussi la structure de File dans de nombreuses situations en informatique :

  • les programmes en cours d'exécution ou processus accédent à tour de rôle à la ressource processeur qui n'exécute qu'un seul programme à la fois, ils sont placés dans une file de priorité : le modèle du tourniquet équivaut à celui d'une file d'attente : le processus qui achève son temps d'accès processeur vient se placer en fin de file et le processus en début de file accède à son tour au processeur.
  • les travaux d'impressions lancés sur une imprimante en réseau sont placés dans une file d'impression
  • lors du parcours d'un graphe en largeur, on maintient une file d'attente des prochains sommets à visiter.

Exercice 1

💻 Saisir ses réponses sur Capytale

Question 1

Faire un tableau d'évolution des variables queue et queue2 au cours de l'exécution du code ci-dessous. On considère qu'il s'agit de files mutables.

🐍 Script Python
1
2
3
4
5
6
7
queue = creer_file()
enfiler(queue 8)
enfiler(queue, 4)
enfiler(queue, 3)
queue2 = creer_file()
while not file_vide(queue):
    enfiler(queue2, defiler(queue))

On représente une file par debut : 8 - 4 - 3 : fin et une file vide par debut : : fin.

Ligne queue queue2
1 debut : : fin rien
2 debut : 8 : fin rien
3 debut : 8 - 4 : fin rien
4 debut : 8 - 4 - 3 : fin rien
5 debut : 8 - 4 - 3 : fin debut : : fin
6 debut : 8 - 4 - 3 : fin debut : : fin
7 debut : 4 - 3 : fin debut : 8 : fin
6 debut : 4 - 3 : fin debut : 8 : fin
7 debut : 3 : fin debut : 8 - 4 : fin
6 debut : 3 : fin debut : 8 - 4 : fin
7 debut : : fin debut : 8 - 4 - 3 : fin
6 debut : : fin debut : 8 - 4 - 3 : fin

Question 2

En vous inspirant de la question précédente, écrire une fonction copie(file) qui renvoie une copie de la file passée en paramètre en garadant intacte la file initiale après exécution. On pourra utiliser deux files auxiliaires, le code ressemble à celui de l'exercice 2 question 3 du chapitre Piles.

🐍 Script Python
def enfiler(file):
    copie = creer_file()
    autre = creer_file()
    while not file_vide(file):
        elt = defiler(file)
        enfiler(copie, elt)
        enfiler(autre, elt)
    # on reconstitue la file initiale
    while not file_vide(autre):
        enfiler(file, defiler(autre))
    return copie

Exercice 2

💻 Saisir ses réponses sur Capytale

On suppose qu'on a étendu l'interface du type abstrait File avec une fonction lire_debut(file) qui lit l'élément en début de file sans le défiler.

Écrire une fonction fusion(file1, file2) permettant de réaliser la fusion triée de deux files file1 et file2 supposées triées avec le maximum en fin de file. On ne demande pas de maintenir les files file1 etfile2`.

🐍 Script Python
def fusion(file1, file2):
    file3 = creer_file()
    while (not file_vide(file1)) and (not file_vide(file2)):
        e1 = lire_debut(file1)
        e2 = lire_debut(file2)
        if e1 <= e2:
            enfiler(file3, defiler(file1))
        else:
            enfiler(file3, defiler(file2))
    while (not file_vide(file1)):
        enfiler(file3, defiler(file1))
    while (not file_vide(file2)):
        enfiler(file3, defiler(file2))
    return file3