Piles Et Files

Pile : sorties 2, 4, 3, 5 ; contenu final [1].
File : sorties 1, 2, 3, 4 ; contenu final [5].

File de priorite (minimum) : sorties 1, 2, 3, 4 ; contenu final {5}. Ici elle coincide avec la file parce que les valeurs arrivent dans l'ordre croissant ; avec la suite d'insertions 3, 1, 2 les resultats differeraient.

class PileVide(Exception):
    """Levee lors d'une operation sur une pile vide."""

def pile_vide():
    return []

def empiler(p, x):
    p.append(x)

def depiler(p):
    if not p:
        raise PileVide("depiler sur une pile vide")
    return p.pop()

def sommet(p):
    if not p:
        raise PileVide("sommet d'une pile vide")
    return p[-1]

def est_vide(p):
    return len(p) == 0

def taille(p):
    return len(p)

def renverse(t):
    """Nouvelle liste renversee, via une pile. Theta(n) temps et espace."""
    p = pile_vide()
    for x in t:
        empiler(p, x)
    return [depiler(p) for _ in range(taille(p))]

def est_palindrome(mot):
    """Utilise une pile pour comparer la premiere moitie a la seconde."""
    mot = [c for c in mot.lower() if c.isalpha()]
    n = len(mot)
    p = pile_vide()
    for i in range(n // 2):
        empiler(p, mot[i])
    debut = n - n // 2                # on saute le caractere central si n est impair
    for i in range(debut, n):
        if depiler(p) != mot[i]:
            return False
    return True

assert renverse([1, 2, 3]) == [3, 2, 1]
assert est_palindrome("kayak") and est_palindrome("Esope reste ici et se repose")
assert not est_palindrome("python")

4. La pile contient \(n/2\) caracteres : \(\Theta(n)\) en espace. On peut faire mieux avec deux indices se rapprochant, en \(\Theta(1)\) :

def palindrome_deux_indices(mot):
    """Theta(n) temps, Theta(1) espace."""
    t = [c for c in mot.lower() if c.isalpha()]
    g, d = 0, len(t) - 1
    while g < d:
        if t[g] != t[d]:
            return False
        g += 1; d -= 1
    return True

La pile reste toutefois la bonne structure lorsque les donnees arrivent en flux et qu'on ne peut pas revenir en arriere.

PRIORITE = {"+": 1, "-": 1, "*": 2, "/": 2}

def evalue_postfixe(expr):
    """Evalue une expression postfixee. Theta(n)."""
    pile = []
    for jeton in expr.split():
        if jeton in PRIORITE:
            if len(pile) < 2:
                raise ValueError("expression mal formee : operandes manquants")
            b, a = pile.pop(), pile.pop()
            if jeton == "/" and b == 0:
                raise ZeroDivisionError("division par zero")
            pile.append({"+": a+b, "-": a-b, "*": a*b, "/": a/b if b else 0}[jeton])
        else:
            pile.append(float(jeton))
    if len(pile) != 1:
        raise ValueError("expression mal formee")
    return pile[0]

def infixe_vers_postfixe(expr):
    """Algorithme du wagon de triage (Dijkstra). Theta(n)."""
    sortie, operateurs = [], []
    for jeton in expr.split():
        if jeton in PRIORITE:
            # on sort les operateurs de priorite superieure ou egale (associativite gauche)
            while (operateurs and operateurs[-1] != "("
                   and PRIORITE[operateurs[-1]] >= PRIORITE[jeton]):
                sortie.append(operateurs.pop())
            operateurs.append(jeton)
        elif jeton == "(":
            operateurs.append(jeton)
        elif jeton == ")":
            while operateurs and operateurs[-1] != "(":
                sortie.append(operateurs.pop())
            if not operateurs:
                raise ValueError("parenthese fermante orpheline")
            operateurs.pop()                      # retire la "("
        else:
            sortie.append(jeton)
    while operateurs:
        op = operateurs.pop()
        if op == "(":
            raise ValueError("parenthese ouvrante non fermee")
        sortie.append(op)
    return " ".join(sortie)

e = "3 + 4 * 2 - ( 1 + 1 )"
p = infixe_vers_postfixe(e)
print(p)                       # 3 4 2 * + 1 1 + -
assert evalue_postfixe(p) == 9.0
assert evalue_postfixe(infixe_vers_postfixe("( 1 + 2 ) * ( 3 + 4 )")) == 21.0

4. Chaque jeton est empile au plus une fois et depile au plus une fois : le nombre total d'operations de pile est \(\le 2n\), donc la conversion est en \(\Theta(n)\), meme si la boucle while interne peut etre longue a un tour donne. C'est de nouveau un argument d'analyse amortie.

from collections import deque

def simulation_un_guichet(clients):
    """Renvoie la liste des (debut, fin, attente) pour chaque client."""
    horloge, resultats = 0, []
    for arrivee, duree in clients:        # clients supposes tries par arrivee
        debut = max(horloge, arrivee)     # le guichet attend si personne n'est la
        fin = debut + duree
        resultats.append((debut, fin, debut - arrivee))
        horloge = fin
    return resultats

clients = [(0, 5), (1, 3), (2, 4), (10, 2)]
r = simulation_un_guichet(clients)
for i, (d, f, a) in enumerate(r):
    print(f"client {i} : service de {d} a {f}, attente {a}")
attente_moyenne = sum(a for _, _, a in r) / len(r)
print(f"attente moyenne : {attente_moyenne:.2f}")

client 0 : service de 0 a 5, attente 0
client 1 : service de 5 a 8, attente 4
client 2 : service de 8 a 12, attente 6
client 3 : service de 12 a 14, attente 2
attente moyenne : 3.00

import heapq

def simulation_k_guichets(clients, k):
    """k guichets. Le client est servi par le guichet libre le plus tot."""
    guichets = [0] * k                     # instant de liberation de chaque guichet
    heapq.heapify(guichets)
    resultats = []
    for arrivee, duree in clients:
        libre = heapq.heappop(guichets)    # guichet disponible le plus tot
        debut = max(libre, arrivee)
        fin = debut + duree
        resultats.append((debut, fin, debut - arrivee))
        heapq.heappush(guichets, fin)
    return resultats

r2 = simulation_k_guichets(clients, 2)
print(sum(a for _, _, a in r2) / len(r2))     # 0.75

3. Avec \(k\) guichets, il faut a chaque arrivee trouver le guichet qui se libere le plus tot : c'est une extraction de minimum, donc une file de priorite (heapq). Le cout devient \(\Theta(n\log k)\) au lieu de \(\Theta(nk)\) si l'on parcourait tous les guichets. L'attente moyenne chute ici de 3,00 a 0,75.

Noter qu'une file simple ne suffit pas : les guichets ne se liberent pas dans l'ordre ou ils ont ete occupes, puisque les durees de service different.

from collections import deque

def bfs(G, depart):
    """Distances (en nombre d'aretes) de depart a tous les sommets atteignables. Theta(V + E)."""
    dist = {depart: 0}
    file = deque([depart])
    while file:
        s = file.popleft()
        for v in G[s]:
            if v not in dist:                # non encore decouvert
                dist[v] = dist[s] + 1
                file.append(v)
    return dist

def chemin_le_plus_court(G, a, b):
    """Un chemin de a a b de longueur minimale, ou None."""
    if a == b:
        return [a]
    pred = {a: None}
    file = deque([a])
    while file:
        s = file.popleft()
        for v in G[s]:
            if v not in pred:
                pred[v] = s
                if v == b:                   # arret des que la cible est atteinte
                    chemin = [b]
                    while pred[chemin[-1]] is not None:
                        chemin.append(pred[chemin[-1]])
                    return chemin[::-1]
                file.append(v)
    return None

def dfs(G, depart):
    """Parcours en profondeur iteratif, avec pile explicite."""
    vus, ordre, pile = set(), [], [depart]
    while pile:
        s = pile.pop()
        if s in vus:
            continue
        vus.add(s)
        ordre.append(s)
        for v in reversed(G[s]):
            if v not in vus:
                pile.append(v)
    return ordre

G = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"],
     "D": ["B", "C", "E"], "E": ["D"]}

assert bfs(G, "A") == {"A": 0, "B": 1, "C": 1, "D": 2, "E": 3}
c = chemin_le_plus_court(G, "A", "E")
assert len(c) == 4                            # A - B - D - E (ou A - C - D - E)
print(dfs(G, "A"))                            # ['A', 'B', 'D', 'C', 'E']

4. Pourquoi BFS donne le plus court chemin. Invariant : la file contient, a tout instant, des sommets dont les distances prennent au plus deux valeurs consecutives \(d\) et \(d+1\), dans cet ordre. Les sommets sont donc decouverts par distance croissante, et la premiere fois qu'un sommet est atteint, c'est par un chemin de longueur minimale.

DFS, lui, plonge le plus loin possible avant de revenir : sur le graphe ci-dessus, il atteint \(E\) par \(A \to B \to D \to E\) (longueur 3, ici optimale), mais sur un graphe ou une longue branche mene a la cible avant un raccourci, il donnerait un chemin arbitrairement plus long. DFS repond a « existe-t-il un chemin ? », BFS a « quel est le plus court ? ».

1. Une variable unique est detruite par le depilement : si le minimum est depile, il faut retrouver le minimum des elements restants, ce qui coute \(\Theta(n)\). Il faut donc memoriser l'historique des minimums.

2. On maintient une seconde pile mins ou mins[-1] est toujours le minimum de la pile principale. A l'empilement de \(x\), on empile \(\min(x, \text{mins}[-1])\) ; au depilement, on depile les deux. Les deux piles ont exactement la meme hauteur, donc mins[-1] correspond toujours a l'etat courant.

class PileMin:
    """Pile avec acces au minimum en Theta(1). Espace Theta(n)."""

    def __init__(self):
        self.elements = []
        self.mins = []

    def empiler(self, x):
        self.elements.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

    def depiler(self):
        if not self.elements:
            raise IndexError("pile vide")
        self.mins.pop()
        return self.elements.pop()

    def minimum(self):
        if not self.mins:
            raise IndexError("pile vide")
        return self.mins[-1]

    def __len__(self):
        return len(self.elements)

p = PileMin()
for x in [5, 3, 8, 3, 9]:
    p.empiler(x)
assert p.minimum() == 3
p.depiler(); p.depiler()          # retire 9 puis 3
assert p.minimum() == 3           # il reste un 3
p.depiler()                       # retire 8
assert p.minimum() == 3
p.depiler()                       # retire 3
assert p.minimum() == 5
print("pile min validee")

Les trois operations sont en \(\Theta(1)\) : elles ne font qu'un nombre constant de append/pop et une comparaison. Le cout est un doublement de l'espace, soit \(\Theta(n)\).

4. Oui, mais c'est plus delicat : la valeur minimale peut sortir par la tete, alors que les nouvelles arrivent par la queue. Deux solutions :

• simuler la file par deux piles min (technique de la section 1) : le minimum de la file est le minimum des minimums des deux piles, donc \(\Theta(1)\), et le cout amorti des operations reste \(\Theta(1)\) ;
• maintenir une deque monotone contenant les indices des candidats au minimum en ordre croissant de valeur : c'est la technique du « minimum glissant », en \(\Theta(1)\) amorti.

from collections import deque

def trouve(laby, c):
    """Coordonnees (i, j) du premier caractere c, ou None."""
    for i, ligne in enumerate(laby):
        j = ligne.find(c)
        if j >= 0:
            return (i, j)
    return None

def resout(laby):
    """Chemin le plus court de D a A, sous forme de liste de coordonnees."""
    depart, arrivee = trouve(laby, "D"), trouve(laby, "A")
    if depart is None or arrivee is None:
        return None
    n, p = len(laby), len(laby[0])
    pred = {depart: None}
    file = deque([depart])
    while file:
        i, j = file.popleft()
        if (i, j) == arrivee:
            chemin = [(i, j)]
            while pred[chemin[-1]] is not None:
                chemin.append(pred[chemin[-1]])
            return chemin[::-1]
        for di, dj in ((-1,0), (1,0), (0,-1), (0,1)):
            i2, j2 = i + di, j + dj
            if (0 <= i2 < n and 0 <= j2 < p
                    and laby[i2][j2] != "#" and (i2, j2) not in pred):
                pred[(i2, j2)] = (i, j)
                file.append((i2, j2))
    return None

def affiche_solution(laby, chemin):
    grille = [list(l) for l in laby]
    for (i, j) in chemin:
        if grille[i][j] == ".":
            grille[i][j] = "*"
    for l in grille:
        print("".join(l))

laby = ["#########",
        "#D..#...#",
        "#.#.#.#.#",
        "#.#...#.#",
        "#.#####.#",
        "#......A#",
        "#########"]
chemin = resout(laby)
print(f"longueur : {len(chemin) - 1} pas")
affiche_solution(laby, chemin)

longueur : 9 pas
#########
#D..#...#
#*#.#.#.#
#*#...#.#
#*#####.#
#******A#
#########

4. Chaque case est enfilee au plus une fois (le test not in pred le garantit) et l'on examine 4 voisins par case : la complexite est \(\Theta(np)\) en temps et en espace, ou \(np\) est le nombre de cases. C'est optimal.

Avec une pile (donc un DFS), l'algorithme trouverait toujours un chemin s'il en existe, mais pas necessairement le plus court : il plongerait dans le premier couloir rencontre jusqu'a un cul-de-sac avant de revenir. En revanche, DFS consomme souvent moins de memoire sur les labyrinthes tres longs et etroits.

1. Recalculer le minimum de chaque fenetre : \(\Theta(nk)\).

2. Avec un tas contenant les couples \((valeur, indice)\), on extrait le minimum en ignorant les indices sortis de la fenetre : \(\Theta(n\log n)\).

3. Invariant. On maintient une deque \(D\) d'indices telle que, apres traitement de l'indice \(i\) :

• tous les indices de \(D\) sont dans la fenetre courante \([i-k+1,\; i]\) ;
• les valeurs \(t[j]\) pour \(j \in D\) sont strictement croissantes de la tete vers la queue.

Sous cet invariant, la tete de \(D\) est l'indice du minimum de la fenetre.

from collections import deque

def minimum_glissant(t, k):
    """Minimum de chaque fenetre de k elements consecutifs. Theta(n)."""
    if k <= 0 or k > len(t):
        return []
    D, res = deque(), []
    for i, x in enumerate(t):
        # 1. retirer en tete les indices sortis de la fenetre
        if D and D[0] <= i - k:
            D.popleft()
        # 2. retirer en queue les candidats devenus inutiles
        while D and t[D[-1]] >= x:
            D.pop()
        D.append(i)
        # 3. des que la fenetre est complete, lire le minimum en tete
        if i >= k - 1:
            res.append(t[D[0]])
    return res

t = [1, 3, -1, -3, 5, 3, 6, 7]
assert minimum_glissant(t, 3) == [-1, -3, -3, -3, 3, 3]

import random
for _ in range(400):
    n = random.randint(1, 25)
    u = [random.randint(-9, 9) for _ in range(n)]
    k = random.randint(1, n)
    naif = [min(u[i:i+k]) for i in range(n - k + 1)]
    assert minimum_glissant(u, k) == naif
print("minimum glissant valide")

4. Correction. Montrons que l'invariant est preserve.

• L'etape 1 elimine exactement l'indice qui vient de quitter la fenetre (il ne peut y en avoir qu'un a chaque pas, et s'il est present il est en tete puisque \(D\) est croissante en indices).
• L'etape 2 elimine tout indice \(j\) tel que \(t[j] \ge x = t[i]\). Un tel \(j\) ne peut plus jamais etre minimum d'une fenetre future : toute fenetre contenant \(j\) (avec \(j < i\)) contient aussi \(i\), dont la valeur est inferieure ou egale et qui sortira plus tard. Sa suppression ne fait donc perdre aucune reponse.
• Apres l'ajout de \(i\) en queue, les valeurs restent strictement croissantes puisque tous les elements \(\ge x\) ont ete retires.

La tete de \(D\) est donc l'indice de valeur minimale parmi les candidats encore valides, c'est-a-dire le minimum de la fenetre.

Complexite. Chaque indice est ajoute a \(D\) exactement une fois et en est retire au plus une fois. Le nombre total d'operations sur la deque est donc \(\le 2n\), et le cout global est \(\Theta(n)\), bien que la boucle while interne puisse effectuer \(\Theta(n)\) retraits a une iteration donnee. L'espace est \(\Theta(k)\).