Structure de pile et file

Cours/Algorithmie/Structure de pile et file

TBD : todo-lists TBD pile et file. Intérêt : implémenter une todo list. Application à la recursion terminale et non terminale.

TBD liste facole ajouter et supprimer à la fin : pile ok mais file ? Supprimer au début liste chaînée supprimer au milieu ?

Dérivés

listes chaînées très utilisé en système et en algo lorsque l'on a besoin uniquement d'accéder au suivant TBD : pile/files : structure invention de la pile : https://www.youtube.com/watch?v=2vBVvQTTdXg Hamblin's stack utilisation de deux piles une opération et une nombre. Samelson et bauer

TBD : bornées : faire avec des listes + démo amortie TBD : decques circulaires TBD : faire gain/perte TBD : exo pile/file simple (jouer avec la structure) et usage dans des algos. Montrer aussi que la pile peut être utilisée pour stocker des variables : faire fibo et enfin dire que c'est comme ça en mémoire : heap et stack. Donner exemple de l'appel de fonction et de la recursion.

Usage

Structure

Application : Rendre itératif des algorithmes récursifs

TBD grace à une todo list (aka une pile) https://www.youtube.com/watch?v=HXNhEYqFo0o

TBD :

cours ici https://www.cs.odu.edu/~zeil/cs361/latest/Public/recursionConversion/index.html#converting-recursive-algorithms-to-iteration On a vu recursion terminale et parfois ça marche pas ex. fibonnacci. on reprend et on regarde comment on ferait en stockant les infos à fire.

https://www.lirmm.fr/~dony/notesCours/c4.s.pdf

https://www.enseignement.polytechnique.fr/informatique/INF321/Amphis12/amphi5.pdf

https://web4.ensiie.fr/~dubois/recursivite.pdf fact est récursive primitive.L'écrire de façon itérative.

avec un tant que utiliser https://www.cs.odu.edu/~zeil/cs361/latest/Public/recursionConversion/index.html#converting-recursive-algorithms-to-iteration

Ackermann, le retour

Essayons de voir comment écrire l'algorithme d'Ackermann sans toutes ces récurrences, comme on l'a fait avec la fonction 91.

Pour calculer $\text{Ack}(m, n)$ :

soit $m=0$ alors $A = n+1$
soit $m>0$ et $n=0$ et alors $A = \text{Ack}(m-1, 1)$
soit $m>0$ et $n>0$ et alors :
1. $A = \text{Ack}(m, n-1)$
2. $A = \text{Ack}(m-1, A)$

On voit que ce n'est pas une formulation récursive terminale à cause du troisième cas. En 3.2 :

on utilise la valeur de $A$ calculée en 3.1
on utilise la valeur que valait $m$ avant 3.1

Il faut donc se rappeler de $m$ pour le calcul de 3.2 tout en utilisant la valeur de $A$ calculée précédemment. Pour ce genre de récursion, on peut utiliser une TODO list qui nous permet de nous rappeler toutes les tâches à effectuer et des variables à sauvegarder :

on commence avec une TODO liste vide
positionner les variables $m$ et $n$ à leurs valeurs et $A$ à 0
on ajoute à la liste le triplet (1, m, n)
tant que la TODO liste n'est pas vide :
1. prendre le dernier item de la list (en le supprimant de la liste)
  1. si le premier élément de l'item vaut 1 alors on affecte :
    1. $m$ au second élément du triplet
    2. $n$ au troisième élément du triplet
  2. si le premier élément vaut 2 alors on affecte :
    1. $m$ au second élément du triplet
    2. $A$ à $n$
2. On fait le calcul :
  1. si $m=0$ alors $A=n+1$
  2. si $m>0$ et $n=0$ alors on ajoute $(1, m-1, 1)$ à la TODO list
  3. si $m>0$ et $n>0$ alors :
    - on ajoute $(2, m-1)$ à la TODO list
    - on ajoute $(1, m, n-1)$ à la TODO list
rendre $A$

TBD faire $A(2, 3)$

On peut même se passer de $A$ complètement :

on commence avec une TODO liste vide
positionner les variables $m$ et $n$ à leurs valeurs
on ajoute à la liste l'entier $m$
tant que la TODO liste n'est pas vide :
1. prendre le dernier item de la list (en le supprimant de la liste) et en l'affectant à $m$
2. On a un choix selon les valeurs de $m$ et $n$ :
  - si $m=0$ alors $n=n+1$
  - si $m>0$ et $n=0$ alors (récursion terminale):
    - $n = 1$
    - ajoute l'entier $m-1$ à la TODO List
  - $m>0$ et $n>0$ alors :
    - ajoute l'entier $m-1$ à la TODO List
    - ajoute l'entier $m$ à la TODO List
    - $n=n-1$
rendre $A$

Implémentation en python en utilisant une liste comme TODO-list :

def Ack(m, n):
    s = [m]
    while (s):
        m = s.pop()
        if m == 0:
            n += 1
        elif n == 0:
            s.append(m - 1)
            n = 1
        else:
            s.append(m - 1)
            s.append(m)
            n -= 1
        return n

pas récursivité terminale = il faut faire des trucs en plus de la récursion. Il faut se rappeler de que l'on veut faire. Avec une TODO list (faire exemple avec ack petit) = pile en informatique faire un item de la todo list = dépile.

truc à faire = empile https://www.cs.odu.edu/~zeil/cs361/latest/Public/recursionConversion/index.html#conversion-using-stacks

curryfication puis decurryfication A(m, n) = A(0, n') A'(s, n) = A'(s[:-1], A(s[-1], n)) A'([m], n) = A(m, n) par récurrence sur m+n = k

TBD faire la preuve que c'est ok (voir https://stackoverflow.com/a/54356919)

Notez que tout algorithme récursif peut s'écrire de façon itérative avec une TODO-list (une pile).