Comme pour les arbres, il existe différentes façons de parcourir un graphe. On peut le parcourir en largeur ou en profondeur. Le parcours d’un graphe consiste à visiter tous ses nœuds.

Parcours en largeur

Nous allons utiliser des nœuds avec un attribut « visite » à « Faux » par défaut et qui sera mis à « Vrai » lorsqu’il aura été visité. Des nœuds sont dit adjacents ou voisins s’ils sont réliés par une arrête. Voici donc un algorithme du parcours en largeur :

VARIABLES
f : file
nœud : nœud de départ (origine)
x : nœud actuellement visité
y : nœud

DEBUT
nœud.visite = Vrai
f.enfile(nœud)
tant que f est non vide:
    x = f.defile()
    afficher x
    pour chaque y adjacent à x:
        si y.visite est Faux:
            y.visite = Vrai
            f.enfile(y)
FIN

1) Appliquez cet algorithme au graphe ci-dessous en partant de A. On notera sur une même ligne le nœud actuellement visité et le contenu de la file f. Dans le cas de plusieurs voisins, on les ajoutera dans l’ordre alphabétique.

2) Faire un tableau des distances entre A et les autres nœuds.

3) Qui a-t-il de remarquable entre ce tableau et le parcours en largeur ?

4) Appliquez à nouveau cet algorithme au graphe ci-dessous en prenant A comme nœud initial.

Parcours en profondeur

Voici maintenant un algorithme qui propose un parcours en profondeur :

VARIABLES
nœud : nœud de départ (origine)

DEBUT
profondeur(nœud):
    nœud.visite = True
    afficher nœud
    pour chaque y adjacent à nœud:
        si y.visite est Faux:
            profondeur(y)

FIN

5) Quelle est la particularité de ce programme par rapport au parcours en largeur ?

6) Appliquez cet algorithme au graphe ci-dessous en partant de A.

7) Appliquez à nouveau cet algorithme au graphe ci-dessous en prenant A comme nœud initial.

Chemin

Il est souvent nécessaire de trouver un chemin entre deux nœuds d’un graphe. Voici un algorithme qui permet de faire cette recherche :

VARIABLES
graphe : le graphe
start : nœud de départ (origine)
end : nœud d'arrivée
chaine : chemin initialement vide

DEBUT
trouve-chaine(graphe, start, end, chaine)
    ajouter start à chaine
    si start = end:
        retourner chaine
    pour chaque y adjacent à start:
        si y n'appartient pas à chaine:
            chemin = trouve-chaine(graphe, y, end, chaine)
            si chemin est non-vide
                retourner chemin
    retourner None
FIN

8) Appliquez rigoureusement cet algorithme au graphe ci-dessous entre A et C.

9) Appliquez à nouveau cet algorithme au graphe ci-dessous entre A et C.

Cycle

Un cycle est une suite d’arrêtes (donc une chaine) dont les deux extrémités sont identiques.

Il est parfois intéressant de savoir si un graphe contient un cycle. Par exemple un graphe qui contient un cycle ne peut pas être un arbre.

Voici donc un algorithme qui permet de détecter s’il y a au moins un cycle dans un graphe :

VARIABLES
graphe : le graphe
d : le nœud de départ
p : pile

DEBUT
trouve-cycle(graphe, d)
    p.empile(d)
    tant que p n'est pas vide:
        x = p.depile()
        pour chaque y adjacent à x:
            si y.visite est Faux:
                p.empile(y)
        si x.visite est Vrai:
            retourner Vrai
        sinon:
            x.visite = Vrai
    retourner Faux
FIN

10) Appliquez cet algorithme au graphe en haut de page en prenant A comme nœud initial.

11) Appliquez à nouveau cet algorithme au graphe ci-dessous en prenant A comme nœud initial.

implémentations : programmes de référence

Programme 1 —Parcours en profondeur

def parcours(g, vus, s):
     """parcours en profondeur depuis le sommet s"""
     if s not in vus:
          vus.add(s)
          for v in g.voisins(s):
               parcours(g, vus, v)

def existe_chemin(g, u, v):
     """existe-t-il un chemin de u à v ?"""
     vus = set()
     parcours(g, vus, u)
     return v in vus

Programme 2 — Parcours en profondeur avec une pile

def parcours(g, vus, s):
     """parcours en profondeur depuis le sommet s"""
     pile = Pile()
     pile.empiler(s)
     while not pile.est_vide():
          s = pile.depiler()
          if s in vus:
               continue
          vus.add(s)
          for v in g.voisins(s):
               pile.empiler(v)

Programme 3 — Détecter la présence d’un cycle dans un graphe

BLANC, GRIS, NOIR = 1, 2, 3
def parcours_cy(g, couleur, s):
     """parcours en profondeur depuis le sommet s"""
     if couleur[s] == GRIS:
          return True
     if couleur[s] == NOIR:
          return False
     couleur[s] = GRIS
     for v in g.voisins(s):
          if parcours_cy(g, couleur, v):
               return True
          couleur[s] = NOIR
     return False

def cycle(g):
     couleur = {}
     for s in g.sommets():
          couleur[s] = BLANC
     for s in g.sommets():
          if parcours_cy(g, couleur, s):
               return True
     return False

Programme 4 — Parcours en largeur

def parcours_largeur(g, source):
     """parcours en largeur depuis le sommet source"""
     dist = {source: 0}
     courant = {source}
     suivant = set()
     while len(courant) > 0:
          s = courant.pop()
          for v in g.voisins(s):
               if v not in dist:
                    suivant.add(v)
                    dist[v] = dist[s] + 1
          if len(courant) == 0:
               courant, suivant = suivant, set()
     return dist

def distance(g, u, v):
     """distance de u à v (et None si pas de chemin)"""
     dist = parcours_largeur(g, u)
     return dist[v] if v in dist else None

Exercices

Exercice 1

Dérouler à la main le parcours en profondeur sur le graphe suivant

pour différentes valeurs du sommet de départ. Donner à chaque fois la valeur finale de l’ensemble vus, c’est-à-dire l’ensemble des sommets atteints par le
parcours.

Exercice 2

Dérouler à la main le parcours en largeur sur le graphe suivant

pour différentes valeurs du sommet de départ. Donner à chaque fois la valeur finale du dictionnaire dist, c’est-à-dire la distance à la source de chaque
sommet atteint par le parcours.

Exercice 3

On peut se servir d’un parcours en profondeur pour déterminer si un graphe non orienté est connexe, c’est-à-dire si tous ses sommets
sont reliés entre eux par des chemins. Pour cela, il suffit de faire un parcours en profondeur à partir d’un sommet quelconque, puis de vérifier
que tous les sommets ont été atteints par ce parcours. Écrire une fonction est_connexe() qui réalise cet algorithme. On pourra se servir de la méthode
sommets() de la classe Graphe et de la fonction parcours du programme de référence 1 voir plus haut .

Exercice 4

Dans cet exercice, on se propose d’utiliser le parcours en profondeur pour construire un chemin entre deux sommets, lorsque c’est possible.
On le fait avec deux fonctions, comme dans le programme de référence 1 voir plus haut.

def parcours_ch(g, vus, org, s):
    """parcours depuis le sommet s, en venant de org"""
    …
def chemin(g, u, v):
    """un chemin de u à v, le cas échéant, None sinon"""
    …

L’idée est que l’attribut vus n’est plus un ensemble mais un dictionnaire, qui associe à chaque sommet visité le sommet qui a permis de l’atteindre
pendant le parcours en profondeur. La fonction parcours_ch prend un argument supplémentaire, org (pour origine), qui est justement le sommet qui
a permis d’atteindre s, en empruntant l’arc org → s. Écrire le code de la fonction parcours_ch ; il est très semblable à celui de la fonction parcours
du programme de référence n°1 . Écrire ensuite le code de la fonction chemin qui renvoie un chemin entre les sommets u et v, le cas échéant, et None s’il n’existe pas de chemin entre ces deux sommets. Pour cela, lancer un parcours en profondeur à partir du sommet u, en donnant à org la valeur None, puis, si le sommet v a été atteint, construire le chemin dans un tableau en« remontant » le dictionnaire vus de v jusqu’à u.

Exercice 5

Dans cet exercice, on se propose d’utiliser le parcours en largeur pour construire un chemin de longueur minimale entre deux sommets.
On le fait avec deux fonctions, comme dans le programme de référence n°4.

def parcours_largeur_ch(g, source):
    """parcours depuis le sommet source"""
    …

def chemin(g, u, v):
    """un chemin de u à v, le cas échéant, None sinon"""
    …

L’idée est qu’un dictionnaire vus remplace le dictionnaire dist. Ce dictionnaire vus associe à chaque sommet visité le sommet qui a permis
de l’atteindre pendant le parcours en largeur. Écrire le code de la fonction parcours_largeur_ch ; il est très semblable à celui de la fonction
parcours_largeur du programme de référence 4. Pour le sommet source, on lui associe la valeur None dans le dictionnaire vus. Écrire ensuite le code de la fonction chemin qui renvoie un chemin réalisant la distance entre les sommets u et v, le cas échéant, et None s’il n’existe pas de chemin entre ces deux
sommets. Pour cela, lancer un parcours en largeur à partir du sommet u puis, si le sommet v a été atteint, construire le chemin dans un tableau
en« remontant » le dictionnaire vus de v jusqu’à u.

Exercice 6

Les nœuds d’un arbre binaire peuvent être vus comme les sommets d’un graphe non orienté. En particulier, on peut donc parcourir les nœuds d’un arbre avec un parcours en profondeur ou en largeur. Pour le parcours en profondeur, il s’agit d’un parcours que nous avons déjà présenté, à savoir le parcours préfixe . Dans cet exercice, on se propose de parcourir les nœuds d’un arbre binaire avec un parcours en largeur.
Écrire une fonction largeur(a) qui reçoit un arbre binaire a en argument et imprime les valeurs de ses différents nœuds dans un ordre donné par un
parcours en largeur, c’est-à-dire la valeur contenue dans la racine, puis les valeurs contenues dans les nœuds immédiatement en-dessous (profondeur 1),
puis celles contenues dans les nœuds encore en-dessous (profondeur 2), etc.
Adapter pour cela le code du programme de référence 4.

Corrections

Exercice 1

Exercice 2

Exercice 3

On suit l’algorithme proposé, en faisant uniquement attention au cas pathologique d’un graphe qui ne contiendrait aucun
sommet.

def est_connexe(g):
    """le graphe est-il connexe ?
    (uniquement pour un graphe non orienté)"""
    ts = g.sommets()
    if len(ts) == 0:
        return True
    s = ts.pop()
    vus = set()
    parcours(g, vus, s)
    for s in ts:
        if s not in vus:
            return False
    return True

Exercice 4

Pour parcours_ch, l’ajout dans un ensemble devient un ajout dans un dictionnaire.

def parcours_ch(g, vus, org, s):
    """parcours depuis le sommet s, en venant de org"""
    if s not in vus:
        vus[s] = org
        for v in g.voisins(s):
            parcours_ch(g, vus, s, v)

Pour chemin, on prend soin de tester si v a été atteint par le parcours. Dans le cas contraire, on renvoie None. Sinon, on construit le chemin avec une
boucle while.

def chemin(g, u, v):
    """un chemin de u à v, le cas échéant, None sinon"""
    vus = {}
    parcours_ch(g, vus, None, u)
    if v not in vus:
        return None
    ch = []
    s = v
    while s is not None:
        ch.append(s)
        s = vus[s]
    ch.reverse()
    return ch

De fait, le chemin est construit à l’envers. On prend soin de le renverser avec la méthode reverse avant de le renvoyer.

Exercice 5

On garde la structure du programme 4, le dictionnaire vus prenant la place du dictionnaire dist.

def parcours_largeur_ch(g, source):
    """parcours depuis le sommet source"""
    vus = {source: None}
    courant = {source}
    suivant = set()
    while len(courant) > 0:
        s = courant.pop()
        for v in g.voisins(s):
            if v not in vus:
                suivant.add(v)
                vus[v] = s
        if len(courant) == 0:
            courant, suivant = suivant, set()
    return vus

La seconde partie, à savoir la reconstruction du chemin, n’est pas différente de celle effectuée dans l’exercice précédent pour un parcours en profondeur.

def chemin(g, u, v):
    """un chemin de u à v, le cas échéant, None sinon"""
    vus = parcours_largeur_ch(g, u)
    if v not in vus:
        return None
    ch = []
    s = v
    while s is not None:
        ch.append(s)
        s = vus[s]
    ch.reverse()
    return ch

Exercice 6

La subtilité consiste ici à correctement traiter les arbres vides. On a le choix de le faire avant ou après l’insertion dans les ensembles.
On choisit ici de le faire après, ce qui évite de faire un cas particulier pour un arbre qui serait intégralement vide.

def largeur(a):
    courant = []
    suivant = []
    courant.append(a)
    while len(courant) > 0:
        n = courant.pop()
        if n is None:
            continue
        print(n.valeur)
        suivant.append(n.gauche)
        suivant.append(n.droit)
        if len(courant) == 0:
            courant, suivant = suivant, []

Activité : « Qui suit qui ? »

1. La mise en situation

Dessiner sur votre feuille 5 prénoms (Alice, Bob, Charles, Driss, Elsa) éparpillés de manière aléatoire. Voici leurs relations sur Instagram :

Alice suit Bob et Elsa.

Bob suit Alice.

Charles suit Alice et Driss.

Driss ne suit personne.

Elsa suit Bob et Charles.

Consigne : Représenter ces relations par des flèches sur leur cahier.

2. Pourquoi pas une liste ?

Nous avons vu les listes chaînées où chaque nœud a un seul suivant. Pourquoi est-ce que notre classe Cellule habituelle ne suffit pas pour modéliser cette situation ? »

3. Formalisation

Introduisez le vocabulaire de base en utilisant le dessin de correction :

Les personnes sont des ……………………………………….

Les flèches sont des ……………………………………………

L’ensemble s’appelle …………………………………………..

4. Comment coder ça ?

Si on devait créer une classe Sommet, à quoi ressemblerait son constructeur pour qu’on puisse retrouver ses abonnés ? »

class Sommet:
    def __init__(self, nom):
        ………………………………………….
        ………………………………………….

# Exemple de création
a = Sommet("Alice")
b = Sommet("Bob")
a.voisins.append(b) # Alice suit Bob

Exercice de clôture : Le Réseau des Développeurs

On considère le mini-graphe suivant représentant trois serveurs informatiques connectés :

Le serveur A est connecté au serveur B.

Le serveur B est connecté au serveur C.

Le serveur C est connecté au serveur A (c’est une boucle).

1. En utilisant la classe Sommet définie précédemment, écrivez les instructions Python permettant de créer ces trois serveurs et d’établir leurs connexions.

Si on exécute l’instruction print(a.voisins[0].voisins[0].nom), qu’est-ce qui va s’afficher à l’écran ?

Définition

Un graphe est un objet mathématique très simple avec lequel on peut faire des choses extrêmement compliquées. Il est constitué de sommets (ou nœuds) reliés par des arêtes (ou liens). Si les arêtes sont fléchées, on parle de graphe orienté sinon on parle de graphe non-orienté. Dans un graphe orienté, on appelle parents d’un nœud, les nœuds qui pointent vers lui. On appelle fils d’un nœud, les nœuds vers lesquels il pointe.

Un graphe peut représenter un réseau social, des liens d’amitié, un réseau routier.

1) Pour le graphe ci-dessous, dire s’il est orienté ou non, donner le nombre de sommets et le nombre d’arêtes.

C’est un graphe orienté (il y a des flèches). Il a 6 sommets et 8 arêtes.

2) Pour le graphe ci-dessous, dire s’il est orienté ou non, donner le nombre de sommets et le nombre d’arêtes.

C’est un graphe non-orienté (il n’y a pas de flèches). Il a 5 sommets et 6 arêtes.

On utilisera parfois des graphes pondérés pour représenter par exemple des distances sur une carte. Dans un tel graphe, les arêtes sont associées à un poids :

Propriétés

Les propriété les plus communes pour parler d’un graphe sont les suivantes :

• une chaîne (ou chemin) est une suite d’arêtes consécutives ;
• la longueur d’une chaîne est le nombre d’arêtes qui la compose ;
• la distance entre deux sommets est la longueur de la chaîne la plus courte entre ces deux sommets ;
• un cycle est une chaîne fermée composée d’arêtes distinctes. C’est à dire qui commence et termine par le même sommet et qui n’empreinte pas deux fois la même arête.

3) Pour le graphe ci-dessous, trouvez deux cycles. Donnez également la distance entre A et D.

Voici les trois cycles possibles : DCBD, DCEBD et CEBC. La distance entre A et B est 2.

Représentation

Nous avons utilisé intuituvement une représentation visuelle d’un graphe. Mais nous aurions pû utiliser une description textuelle d’un graphe. Par exemple pour celui de la question 2 :

• A est relié à E ;
• B est relié à C, D et E ;
• C est relié à B, D et E ;
• D est relié à C et B ;
• E est relié à A, B et C.

4) Dessinez le graphe correspondant à la description ci-dessous :KevinMattéoTomEmmaClaireDavid

• Tom est ami avec Emma, Claire et Mattéo ;
• Claire est amie avec Tom, Emma et David ;
• Mattéo est ami avec Tom et Kevin ;
• Emma est amie avec Tom et Claire ;
• David est ami avec Claire ;
• Kevin est ami avec Mattéo.

5) Dessinez le graphe correspondant à la description ci-dessous :

• A est à 12 km de B ;
• B est à 12 km de A, 9 km de C et 25 km de D ;
• C est à 9 km de B ;
• D est à 25 km de B et 6 km de E ;
• E est à 6 km de D.

Implémentations 1

On parle d’implémentation lorsqu’il s’agit de « représenter » un graphe dans un système informatique. Même si nous ne verrons pas directement comment on implémente un graphe en Python nous allons parler des deux principales implémentations d’un graphe.

Matrice d’adjacence

Une matrice n’est qu’un tableau à double entrée :

Nous avons ci-dessus une matrice à 3 lignes et 4 colonnes. En mathématiques on utilise les matrices pour effectuer des calculs, nous les utiliserons ici simplement comme des tableaux à deux dimensions.

Une matrice d’adjacence est une matrice carrée (même nombre de lignes que de colonnes) où chaque ligne et chaque colonne représentent un sommet. Pour un graphe non-orienté on mettra un « 1 » sur la case [i][j] s’il y a une arête entre le sommet i et le sommet j, et un « 0 » sinon. Pour un graphe orienté on mettra un « 1 » sur la case [i][j] s’il y a une arête du sommet i vers le sommet j, et un « 0 » sinon. Pour un graphe pondéré on mettra sur la case [i][j] le poids du lien entre le sommet i et le sommet j.

6) Donnez la matrice d’adjacence du graphe ci-dessous.

7) Donnez la matrice d’adjacence du graphe ci-dessous.

8) Donnez la matrice d’adjacence du graphe ci-dessous.

Listes d’adjacence

Pour un graphe non orienté, une liste d’adjacence associe à chaque sommet la liste de ses voisins. Par exemple, pour le graphe ci-dessous

La liste d’adjacence serait :

• A → [B, C, E] ;
• B → [A] ;
• C → [A, D] ;
• D → [C, E] ;
• E → [A, D].

Pour un graphe orienté, une liste d’adjacence associe à chaque sommet la liste de ses successeurs. C’est à dire les sommets vers lesquels il pointe. Il est également possible de faire une liste d’adjacence des prédécesseurs, ou même les deux pour des raisons de symétrie.

9) Donnez la liste d’adjacence du graphe ci-dessous.

10) Donnez la liste d’adjacence des successeurs du graphe ci-dessous.

Choix d’implémentation

On utilisera une matrice d’adjacence dans le cas d’un graphe avec beaucoup de liens (on parle de graphe dense) et une liste d’adjacence dans le cas contraire. Cela permettra de gagner de la mémoire. Le choix peut aussi dépendre de l’utilité du graphe. En fonction de l’algorithme utilisé, on pourra préférer une implémentation à l’autre.

Implémentations 2

Nous avons vu dans ci-dessus, deux façons de représenter un graphe : par matrice d’adjacence ou par liste d’adjacence. Nous allons utiliser ces deux implémentations ici.

Matrice d’adjacence

Nous utiliserons le même graphe que le précédent :

1) Créez en Python la matrice d’adjacence de ce graphe.

2) (Dificile) Proposez une fonction matrice_largeur permettant de parcourir en largeur ce graphe. On utilisera une liste pour enregistrer les nœuds visités.

3) (Plus dificile) Proposez une fonction matrice_profondeur permettant de parcourir en profondeur ce graphe.

Liste d’adjacence

Nous utiliserons ici le même graphe que précédement.

4) Créez en Python les listes d’adjacence de ce graphe. (On utilisera un tableau à deux dimensions)

5) (Dificile) Proposez une fonction listes_largeur permettant de parcourir en largeur ce graphe. On utilisera une liste pour enregistrer les nœuds visités.

6) (Plus difficile) Proposez une fonction listes_profondeur permettant de parcourir en profondeur ce graphe.

programmes de référence

programme 1 : Graphe représenté par une matrice d’adjacence

class Graphe:
    """un graphe représenté par une matrice d’adjacence,
    où les sommets sont les entiers 0,1,...,n-1"""

    def __init__(self, n):
        self.n = n
        self.adj = [[False] * n for _ in range(n)]

    def ajouter_arc(self, s1, s2):
        self.adj[s1][s2] = True

    def arc(self, s1, s2):
        return self.adj[s1][s2]

    def voisins(self, s):
        v = []
        for i in range(self.n):
            if self.adj[s][i]:
                v.append(i)
        return v

programme 2 : Graphe représenté par un dictionnaire d’adjacence

class Graphe:
    """un graphe comme un dictionnaire d’adjacence"""

    def __init__(self):
        self.adj = {}

    def ajouter_sommet(self, s):
        if s not in self.adj:
            self.adj[s] = set()

    def ajouter_arc(self, s1, s2):
        self.ajouter_sommet(s1)
        self.ajouter_sommet(s2)
        self.adj[s1].add(s2)

    def arc(self, s1, s2):
        return s2 in self.adj[s1]

    def sommets(self):
        return list(self.adj)

    def voisins(self, s):
        return self.adj[s]

programme 3 : Coloriage glouton d’un graphe

def mex(voisins, couleur):
    """la plus petite couleur non utilisée par les voisins"""
    n = len(voisins)
    dispo = [True] * (n + 1)
    for v in voisins:
        if v in couleur and couleur[v] <= n:
            dispo[couleur[v]] = False
    for c in range(n + 1):
        if dispo[c]:
            return c

assert False # on n’arrivera jamais ici

def coloriage(g):
    """colorie graphe g avec un algorithme glouton"""
    couleur = {}
    n = 0
    for s in g.sommets():
        c = mex(g.voisins(s), couleur)
        couleur[s] = c
        n = max(n, c + 1)
    return couleur, n

Exercices

Exercice 1

Dessiner tous les graphes non orientés ayant exactement trois sommets.

Exercice 2

Combien y a-t-il de graphes orientés ayant exactement trois sommets ? On ne demande pas de les dessiner tous, mais seulement de les dénombrer.

Exercice 3

Ajouter à la classe Graphe du programme 1 (matrice d’adjacence) une méthode afficher pour afficher le graphe sous la forme suivante
0 -> 1 3
1 -> 2 3
2 -> 3
3 -> 1
c’est-à-dire une ligne par sommet, avec pour chacun la liste de ses voisins.

Exercice 4

Ajouter à la classe Graphe du programme 2 (dictionnaire d’adjacence) une méthode afficher pour afficher le graphe sous la forme suivante
0 {1, 3}
1 {2, 3}
3 {1}
2 {3}
c’est-à-dire une ligne par sommet, avec pour chacun l’ensemble de ses voisins.
L’ordre des sommets n’est pas important. L’ensemble des voisins peut être affiché directement avec print.

Exercice 5

Ajouter à la classe Graphe du programme 2 une méthode
nb_sommets() qui donne le nombre de sommets du graphe.

Exercice 6

Ajouter à la classe Graphe du programme 1 une méthode degre(s) qui donne le nombre d’arcs issus du sommet s. On appelle cela le degré du sommet s.

Exercice 7

En utilisant l’exercice précédent, ajouter à la classe Graphe du programme 36 une méthode nb_arcs() qui donne le nombre total d’arcs du graphe.

Exercice 8

Ajouter à la classe Graphe du programme 2 une méthode degre(s) qui donne le nombre d’arcs issus du sommet s. On appelle cela le degré du sommet s.

Exercice 9

En utilisant l’exercice précédent, ajouter à la classe Graphe du programme 2 une méthode nb_arcs() qui donne le nombre total d’arcs du graphe.

Exercice 10

Ajouter aux classes Graphe des programmes 1 et 2 une méthode supprimer_arc(s1, s2) pour supprimer l’arc entre les sommets s1 et s2. S’il n’y a pas d’arc entre ces sommets, la méthode n’a aucun effet. On supprime un élément d’un ensemble avec sa méthode remove.

Exercice 11

Donner une coloration du graphe des régions ci-dessous qui n’utilise que quatre couleurs.

Corrections

Exercice 1

Il y en a 8 au total

Exercice 2

Il y a six arcs possibles (0 → 1, 1 → 0, 1 → 2, 2 → 1, 2 → 0, 0 → 2), chacun pouvant être présent ou absent, soit 26 = 64
possibilités au total.

Exercice 3

def afficher(self):
     for s in range(self.n):
     print(s, "->", end="")
     for v in range(self.n):
          if self.adj[s][v]:
               print("", v, end="")
     print()

Exercice 4

On fait un cas particulier pour l’ensemble vide, histoire qu’il ne soit pas affiché comme set() mais comme {}.

def afficher(self):
     for s in self.adj:
          if len(self.adj[s]) == 0:
               print(s, "{}")
          else:
               print(s, self.adj[s])

Exercice 5

Le nombre de sommets est égal au nombre d’entrées dans le dictionnaire :

def nb_sommets(self):
     return len(self.adj)

Exercice 6

Le code est très semblable à celui de la méthode voisins :

def degre(self, s):
     d = 0
     for i in range(self.n):
          if self.adj[s][i]:
               d += 1
     return d

Exercice 7

Il suffit de faire la somme de tous les degrés.

def nb_arcs(self):
     n = 0
     for s in range(self.n):
          n += self.degre(s)
     return n

Exercice 8

C’est exactement le cardinal de l’ensemble adj[s] :

def degre(self, s):
     return len(self.adj[s])

Exercice 9

Comme dans l’exercice 7, on fait la somme de tous les degrés.

def nb_arcs(self):
     n = 0
     for s in self.adj:
          n += self.degre(s)
     return n

Exercice 10

Pour la matrice d’adjacence, on affecte le booléen False dans la matrice :

def supprimer_arc(self, s1, s2):
     self.adj[s1][s2] = False

Pour le dictionnaire d’adjacence, on supprime s2 de l’ensemble des voisins de s1, si l’arc existe :

def supprimer_arc(self, s1, s2):
     if self.arc(s1, s2):
          self.adj[s1].remove(s2)

Exercice 11

Auvergne-Rhône-Alpes 0
Bourgogne-Franche-Comté 1
Bretagne 1
Centre-Val de Loire 2
Corse 0
Grand Est 0
Hauts-de-France 1
Île-de-France 3
Normandie 0
Nouvelle-Aquitaine 1
Occitanie 2
Pays de la Loire 3
Provence-Alpes-Côte dAzur 1
Guadeloupe 0
Martinique 0
Guyane 0
La Réunion 0
Mayotte 0

Algorithme de parcours

Un parcours de graphe est un algorithme consistant à explorer tous les sommets d’un graphe de proche en proche à partir d’un sommet initial donné. Cela généralise les parcours des arbres binaires que vous avez déjà vus.

Ces parcours sont notamment utilisés pour rechercher un plus court chemin (routage sur Internet, applications de navigation dans un réseau de métros ou de trains) ou pour trouver la sortie d’un labyrinthe.

1. Parcours de graphes, en version intuitive⚓︎

Parcours en largeur

Dans un parcours en largeur, on progresse par « cercles concentriques » à partir du sommet de départ. On visite d’abord tous les sommets à une distance de 1 unité du point départ, puis tous les sommets à une distance de 2 unités, etc. (en considérant que la distance est le nombre d’arêtes).

Par exemple, avec le graphe suivant,

le parcours en largeur au départ de A donne la liste suivante des sommets :

A ; B ; D ; C ; E ; F ; G ; H

(avec la convention que, quand il y a plusieurs sommets à la même distance, on les écrit dans l’ordre alphabétique).

Exercice 1

Effectuer le parcours en largeur du graphe représenté ci-dessous, en partant du sommet A.

Solution

Le résultat du parcours en largeur est : A ; B ; C ; E ; D ; G ; F.

Exercice 2

Effectuer le parcours en largeur du graphe représenté ci-dessous, en partant du sommet D.

Solution

Le résultat du parcours en largeur est : D ; F ; A ; B ; C ; K ; E ; H ; G.

Parcours en profondeur

Dans un parcours en profondeur, l’idée est de suivre un chemin le plus loin possible. Si on arrive au bout d’un chemin, on revient à la bifurcation précédente pour explorer un nouveau chemin.

Par exemple, avec le graphe suivant :

un parcours en profondeur au départ du sommet A donne :

A ; B ; E ; F ; C ; K ; H ; G ; D ; Q ; M.

Exercice

Le mécanisme d’un parcours en profondeur est encore plus explicite dans le cas des graphes orientés.

Effectuer le parcours en profondeur du graphe représenté ci-dessous, en partant du sommet A.

Solution

Le résultat du parcours en profondeur est : A ; E ; G ; F ; C ; B ; D.

2. Parcours de graphes, en version rigoureuse⚓︎

Algorithme de parcours

Les deux types de parcours (en largeur et en profondeur) reposent sur le même principe de base :

• Le sommet de départ dep étant donné, on crée une structure V qui contiendra au départ uniquement ce sommet dep .
• Tant que V n’est pas vide :
  • on choisit un sommet s existant dans V ;
  • on visite s, c’est-à-dire qu’on l’affiche ;
  • on ajoute à V tous les voisins de s pas encore découverts.

La structure V sert donc à mémoriser les sommets qui ont été découverts mais pas encore visités.

• Si on choisit une file (FIFO), on visitera les sommets dans l’ordre d’arrivée, donc les plus proches du sommet précédent. On obtient donc un parcours en largeur (  Breadth First Search, ou BFS).
• Si on choisit une pile (LIFO), on visitera d’abord les derniers sommets arrivés, donc on parcourt le graphe en visitant à chaque étape un voisin du précédent. On obtient donc un parcours en profondeur (  Depth First Search, ou DFS).

2.1. Le parcours en largeur⚓︎

Exemple de parcours en largeur

Voici une illustration du parcours en largeur d’un graphe avec B comme sommet de départ :

Codes couleur :

• vert : les sommets non encore traités.
• rouge : le sommet en cours de traitement.
• orange : la file d’attente des sommets qui seront bientôt traités. On y rajoute à chaque fois les voisins du sommet en cours de traitement, uniquement si ils n’ont pas encore été découverts.
• noir : les sommets traités.

Le résultat du parcours en largeur du graphe est donc : B ; A ; D ; E ; C ; F ; G ; H

Remarque : quand on ajoute plusieurs voisins d’un seul coup dans la file, on fait ici le choix de les ajouter dans l’ordre alphabétique.

Un outil en ligne

Un outil en ligne, permet de visualiser le résultat du parcours en profondeur (DFS : depth first search) d’un graphe.

Un graphe est donné en exemple, mais vous pouvez le modifier ou construire le vôtre :

Dans les menus déroulants, bien choisir Algorithm : BFS et Example graph : directedGraph

2.2. Codage d’un parcours en largeur en Python⚓︎

Remarque : ce code est donné uniquement à titre illustratif : il n’est pas nécessaire de l’apprendre par cœur. Par ailleurs, dans une partie cachée, il y a le codage des primitives des files et des graphes.

def parcours_largeur(G,s):
    f = creer_file_vide()
    enfiler(f,s)
    tab_decouverts = [s]
    while not est_vide(f):
        s = defiler(f)
        print(s, end=" - ")
        for v in liste_voisins(G,s) :
            if v not in tab_decouverts :
                enfiler(f,v)
                tab_decouverts.append(v)
    return None

# modélisation du graphe par un dictionnaire
graphe = {"B" : ["A", "D", "E"], "A" : ["B", "C"], "C" : ["A", "D"], "D":["B", "C", "E"],
"E" : ["B", "F", "G"], "F" : ["E", "G"], "G" : ["E", "F", "H"], "H":["G"]}
# parcours du graphe
parcours_largeur(graphe, "B")

2.3. Le parcours en profondeur⚓︎

Exemple de parcours en profondeur

Rappel : dans un parcours en profondeur, chaque nouveau voisin découvert est ajouté au sommet d’une pile.

On prend comme exemple le même graphe que dans l’exemple précédent, avec un départ du sommet B. On convient que, quand il y a plusieurs sommets à empiler en même temps, on les empile dans l’ordre alphabétique.

• B est visité et on empile les voisins de B : la pile contient alors A (bas de la pile), D, E (sommet de la pile).
• E est dépilé (il est visité) et on empile ses voisins qui ne sont pas déjà dans la pile : la pile contient alors A (bas de la pile), D, F, G (sommet de la pile).
• G est dépilé (il est visité) et on empile H, son seul voisin pas encore découvert : la pile contient alors A (bas de la pile), D, F, H (sommet de la pile).
• H est dépilé et il n’y a pas de nouveau voisins à empiler : la pile contient alors A (bas de la pile), D, F (sommet de la pile).
• et ainsi de suite

Au final, on obtient l’ordre de visite suivant : B ; E ; G ; H ; F ; D ; C ; A.

2.4. Codage d’un parcours en profondeur en Python⚓︎

Remarque : ce code est donné uniquement à titre illustratif : il n’est pas nécessaire de l’apprendre par cœur.

def parcours_profondeur(G,s):
    p = creer_pile_vide()
    empiler(p,s)
    tab_decouverts = [s]
    while not est_vide(p):
        s = depiler(p)
        print(s, end=" - ")
        for v in liste_voisins(G,s) :
            if v not in tab_decouverts :
                empiler(p,v)
                tab_decouverts.append(v)
    return None

# modélisation du graphe par un dictionnaire
graphe = {"B" : ["A", "D", "E"], "A" : ["B", "C"], "C" : ["A", "D"], "D":["B", "C", "E"],
"E" : ["B", "F", "G"], "F" : ["E", "G"], "G" : ["E", "F", "H"], "H":["G"]}
# parcours du graphe
parcours_profondeur(graphe, "B")

2.5. Applications⚓︎

Graphe connexe ou pas ?

On donne ci-dessous le code d’un graphe non orienté graphe1.

En comparant les résultats des appels des fonctions liste_sommets et parcours depuis le sommet A (soit en largeur, soit en profondeur), déterminer si ce graphe est connexe ou pas.

# modélisation d'un graphe par un dictionnaire
graphe1 = {"A": ["C", "H", "I"],"B": ["J", "L"],"C": ["A", "D", "G", "I"],"D": ["C", "E"],
    "E": ["D", "H"], "F": ["G", "H"], "G": ["C", "F"], "H": ["A", "E", "F"], "I": ["A", "C"],
    "J": ["B", "K", "L"], "K": ["J"], "L": ["B", "J"]}
# ce graphe non orienté est-il connexe ?

Solution : On observe que le parcours du graphe depuis le sommet A fournit moins de sommets que la liste des sommets. Ce graphe n’est donc pas connexe.

Sommet atteignable ou pas ?

On donne ci-dessous le code d’un graphe connexe orienté graphe2.

En effectuant un parcours depuis le sommet A (soit en largeur, soit en profondeur), déterminer s’il est possible d’atteindre le sommet B depuis ce sommet A.

Ce même sommet B est-il atteignable depuis le sommet N ?

# modélisation d'un graphe par un dictionnaire
graphe2 = {
    "A": ["G", "K", "L"],  "B": ["L", "N"], "C": ["A", "D", "I"], "D": ["C"], "E": ["D", "F", "G"],
    "F": ["H"], "G": ["D"], "H": ["E", "G"], "I": ["A", "G", "H"], "J": ["B", "M", "N"],
    "K": ["I"], "L": [], "M": ["B"], "N": ["M"]
}
# dans ce graphe orienté, est-il possible d'aller de A vers B ? et de N vers B ?

Solution

On observe que le sommet B n’apparait pas dans le parcours du graphe depuis le sommet A : B n’est donc pas atteignable depuis A.

Mais B est atteignable depuis le sommet N, comme le montre un parcours depuis N.

3. TP: graphe et labyrinthe⚓︎

Télécharger le carnet Jupyter, à ouvrir sur Basthon.

Il faudra aussi charger dans Basthon les trois modules Python suivants (Ouvrir… puis Installer le module) : laby2d.py, laby3d.py et solution.py.

4. Algorithme de recherche d’un plus court chemin : algorithme de Dijkstra⚓︎

Vous avez déjà effectué la recherche d’un plus court chemin dans un graphe pondéré, quand il s’agissait de trouver le chemin emprunté pour aller d’un routeur A à un routeur B selon le protocole OSPF.

On peut systématiser la détermination du plus court chemin d’un point à un autre en appliquant l’algorithme de Dijkstra (mis au point par Edsger Dijkstra en 1959), comme expliqué dans la vidéo suivante :

Application de l’algorithme de Dijkstra

Donner le plus court chemin pour aller de E à F dans le graphe ci-dessous :

Solution

Le meilleur trajet est donc E-D-A-C-B-F, pour une distance totale de 70.
Attention ce trajet correspond à la colonne choix (dans l’ordre) mais ce n’est pas toujours le cas.

Deuxième application de l’algorithme de Dijkstra

Déterminer le plus court chemin entre A et G dans le graphe pondéré ci-dessous (en version papier).

Solution

Le meilleur trajet est donc A – C – H – F – G, pour une distance totale de 16.

L’algorithme de Dijkstra, ici exécuté de manière manuelle, est bien sûr programmable. Mais cela dépasse le niveau attendu en fin de Terminale.

5. Exercices⚓︎

• Exercices de base : énoncé.
• Exercice type Bac n°1: énoncé.
• Exercice type Bac n°2: énoncé.

programmes ressources

Graphe représenté par une matrice d’adjacence

class Graphe:
    """un graphe représenté par une matrice d’adjacence,
    où les sommets sont les entiers 0,1,...,n-1"""

    def __init__(self, n):
        self.n = n
        self.adj = [[False] * n for _ in range(n)]

    def ajouter_arc(self, s1, s2):
        self.adj[s1][s2] = True
        def arc(self, s1, s2):
        return self.adj[s1][s2]

    def voisins(self, s):
        v = []
        for i in range(self.n):
            if self.adj[s][i]:
                v.append(i)
        return v

Graphe représenté par un dictionnaire d’adjacence

class Graphe:
    """un graphe comme un dictionnaire d’adjacence"""

    def __init__(self):
        self.adj = {}

    def ajouter_sommet(self, s):
        if s not in self.adj:
            self.adj[s] = set()

    def ajouter_arc(self, s1, s2):
        self.ajouter_sommet(s1)
        self.ajouter_sommet(s2)
        self.adj[s1].add(s2)

    def arc(self, s1, s2):
        return s2 in self.adj[s1]

    def sommets(self):
        return list (self.adj)

    def voisins(self, s):
        return self.adj[s]

Exercice 1 Dessiner tous les graphes non orientés ayant exactement trois sommets.  

Solution : 8 au total :

Exercice 2 Combien y a-t-il de graphes orientés ayant exactement trois sommets ? On ne demande pas de les dessiner tous, mais seulement de les dénombrer.  

Solution : Il y a six arcs possibles (0 → 1, 1 → 0, 1 → 2, 2 → 1, 2 → 0, 0 → 2), chacun pouvant être présent ou absent, soit  possibilités au total.

Exercice 3 Ajouter à la classe Graphe du programme matrice d’adjacence donné avant les consignes des exercices, une méthode afficher pour afficher le graphe sous la forme suivante

0 -> 1 3

1 -> 2 3

2 -> 3

3 -> 1

c’est-à-dire une ligne par sommet, avec pour chacun la liste de ses voisins.

def afficher(self):
    for s in range(self.n):
        print(s, "->", end="")
    for v in range(self.n):
        if self.adj[s][v]:
            print("", v, end="")
    print()

Exercice 04 Ajouter à la classe Graphe du programme dictionnaire d’adjacence donné avant les consignes des exercices une méthode afficher pour afficher le graphe sous la forme suivante

0 {1, 3}

1 {2, 3}

3 {1}

2 {3}

c’est-à-dire une ligne par sommet, avec pour chacun l’ensemble de ses voisins.

L’ordre des sommets n’est pas important. L’ensemble des voisins peut être affiché directement avec print.  

Correction : On fait un cas particulier pour l’ensemble vide, histoire qu’il ne soit pas affiché comme set() mais comme {}.

def afficher(self):
    for s in self.adj:
        if len(self.adj[s]) == 0:
            print(s, "{}")
        else:
            print(s, self.adj[s])

Exercice 05 Ajouter à la classe Graphe du programme dictionnaire d’adjacence donné avant les consignes des exercices une méthode nb_sommets() qui donne le nombre de sommets du graphe.

Correction : Le nombre de sommets est égal au nombre d’entrées dans le dictionnaire :

def nb_sommets(self):
    return len(self.adj)

Exercice 06 Ajouter à la classe Graphe du programme matrice d’adjacence donné avant les consignes des exercices une méthode degre(s) qui donne le nombre d’arcs issus du sommet s. On appelle cela le degré du sommet s.  

Correction : Le code est très semblable à celui de la méthode voisins :

def degre(self, s):
    d = 0
    for i in range(self.n):
        if self.adj[s][i]:
            d += 1
    return d

Exercice 07 En utilisant l’exercice précédent, ajouter à la classe Graphe du programme matrice d’adjacence donné avant les consignes des exercices une méthode nb_arcs() qui donne le nombre total d’arcs du graphe.  

Correction : Il suffit de faire la somme de tous les degrés.

def nb_arcs(self):
    n = 0
    for s in range(self.n):
        n += self.degre(s)
    return n

Exercice 08 Ajouter à la classe Graphe du programme dictionnaire d’adjacence donné avant les consignes des exercices une méthode degre(s) qui donne le nombre d’arcs issus du sommet s. On appelle cela le degré du sommet s.  

Correction : C’est exactement le cardinal de l’ensemble adj[s] :

def degre(self, s):
    return len(self.adj[s])

Exercice 09 En utilisant l’exercice précédent, ajouter à la classe Graphe du programme dictionnaire d’adjacence donné avant les consignes des exercices une méthode nb_arcs() qui donne le nombre total d’arcs du graphe.  

Correction : comme il y a deux exercice, on fait la somme de tous les degrés.

def nb_arcs(self):
    n = 0
    for s in self.adj:
        n += self.degre(s)
    return n

Exercice 10 Ajouter aux classes Graphe des programmes dictionnaire et matrice d’adjacence une méthode supprimer_arc(s1, s2) pour supprimer l’arc entre les sommets s1 et s2. S’il n’y a pas d’arc entre ces sommets, la méthode n’a aucun effet. On supprime un élément d’un ensemble avec sa méthode remove.

Correction : Pour la matrice d’adjacence, on affecte le booléen False dans la matrice :

def supprimer_arc(self, s1, s2):
    self.adj[s1][s2] = False

def supprimer_arc(self, s1, s2):
    if self.arc(s1, s2):
        self.adj[s1].remove(s2)

Pour le dictionnaire d’adjacence, on supprime s2 de l’ensemble des voisins de s1, si l’arc existe :

def supprimer_arc(self, s1, s2):
    if self.arc(s1, s2):
        self.adj[s1].remove(s2)

Exercice 11 Donner une coloration du graphe des régions ci-dessus qui n’utilise que quatre couleurs.  

Correction : Il suffit de reprendre les couleurs obtenues avec l’algorithme glouton (figure 11.2 page 204) et de faire seulement deux changements :

Bretagne 1 (au lieu de 0)

Normandie 0 (au lieu de 4)

Exercice 12 : coloriage de graphes

écrivons un programme qui colorie un graphe avec un algorithme glouton. Colorier un graphe veut dire associer une couleur à chacun de ses sommets, de façon à ce que deux sommets reliés par un arc n’aient pas la même couleur. Colorier un graphe avec un minimum de couleurs est un problème difficile, mais si on accepte l’idée d’utiliser éventuellement plus de couleurs que nécessaire, alors on peut colorier un graphe efficacement. Le principe d’un coloriage glouton est simple. On parcourt les sommets dans un ordre arbitraire et, pour chaque sommet, on lui attribue la première couleur qui n’est pas utilisée par ses voisins.

def mex(voisins, couleur):
    """la plus petite couleur non utilisée par les voisins"""
    n = len(voisins)
    dispo = [True] * (n + 1)
    for v in voisins:
        if v in couleur and couleur[v] <= n:
            dispo[couleur[v]] = False
    for c in range(n + 1):
        if dispo[c]:
            return c
        assert False # on n’arrivera jamais ici

def coloriage(g):
    """colorie graphe g avec un algorithme glouton"""
    couleur = {}
    n = 0
    for s in g.sommets():
        c = mex(g.voisins(s), couleur)
        couleur[s] = c
        n = max(n, c + 1)
    return couleur, n

programmes de référence :

Programme 39 — Parcours en profondeur

def parcours(g, vus, s):
    """parcours en profondeur depuis le sommet s"""
    if s not in vus:
        vus.add(s)
    for v in g.voisins(s):
        parcours(g, vus, v)

def existe_chemin(g, u, v):
    """existe-t-il un chemin de u à v ?"""
    vus = set()
    parcours(g, vus, u)

def parcours(g, vus, s):
    """parcours en profondeur depuis le sommet s"""
    if s not in vus:
        vus.add(s)
    for v in g.voisins(s):
        parcours(g, vus, v)

def existe_chemin(g, u, v):
    """existe-t-il un chemin de u à v ?"""
    vus = set()
    parcours(g, vus, u)
    return v in vus

Programme 40 — Parcours en profondeur avec une pile

def parcours(g, vus, s):
    """parcours en profondeur depuis le sommet s"""
    pile = Pile()
    pile.empiler(s)
    while not pile.est_vide():
    s = pile.depiler()
    if s in vus:
        continue
    vus.add(s)

for v in g.voisins(s):
    pile.empiler(v)

Programme 41 — Détecter la présence d’un cycle dans un graphe

BLANC, GRIS, NOIR = 1, 2, 3

def parcours_cy(g, couleur, s):
    """parcours en profondeur depuis le sommet s"""
    if couleur[s] == GRIS:
        return True
    if couleur[s] == NOIR:
        return False
    couleur[s] = GRIS
    for v in g.voisins(s):
        if parcours_cy(g, couleur, v):
            return True
    couleur[s] = NOIR
    return False

def cycle(g):
    couleur = {}
    for s in g.sommets():
        couleur[s] = BLANC
    for s in g.sommets():
        if parcours_cy(g, couleur, s):
            return True
    return False

Programme 42 — Parcours en largeur

def parcours_largeur(g, source):
    """parcours en largeur depuis le sommet source"""
    dist = {source: 0}
    courant = {source}
    suivant = set()
    while len(courant) > 0:
        s = courant.pop()
    for v in g.voisins(s):
        if v not in dist:
            suivant.add(v)
    dist[v] = dist[s] + 1
    if len(courant) == 0:
        courant, suivant = suivant, set()
    return dist

def distance(g, u, v):
    """distance de u à v (et None si pas de chemin)"""
    dist = parcours_largeur(g, u)
    return dist[v] if v in dist else None

Exercice 104 Dérouler à la main le parcours en profondeur sur le graphe suivant

pour différentes valeurs du sommet de départ. Donner à chaque fois la valeur finale de l’ensemble vus, c’est-à-dire l’ensemble des sommets atteints par le parcours.

Correction :

Exercice 105 Dérouler à la main le parcours en largeur sur le graphe suivant

pour différentes valeurs du sommet de départ. Donner à chaque fois la valeur finale du dictionnaire dist, c’est-à-dire la distance à la source de chaque sommet atteint par le parcours.

Correction :

Exercice 106 On peut se servir d’un parcours en profondeur pour déterminer si un graphe non orienté est connexe, c’est-à-dire si tous ses sommets sont reliés entre eux par des chemins. Pour cela, il suffit de faire un parcours en profondeur à partir d’un sommet quelconque, puis de vérifier que tous les sommets ont été atteints par ce parcours. Écrire une fonction est_connexe() qui réalise cet algorithme. On pourra se servir de la méthode sommets() de la classe Graphe et de la fonction parcours du programme Parcours en profondeur.

Correction : On suit l’algorithme proposé, en faisant uniquement attention au cas pathologique d’un graphe qui ne contiendrait aucun sommet.

def est_connexe(g):
    """le graphe est-il connexe ?
    (uniquement pour un graphe non orienté)"""
    ts = g.sommets()
    if len(ts) == 0:
        return True
    s = ts.pop()
    vus = set()
    parcours(g, vus, s)
    for s in ts:
        if s not in vus:
            return False
    return True

Exercice 107 Dans cet exercice, on se propose d’utiliser le parcours en profondeur pour construire un chemin entre deux sommets, lorsque c’est possible. On le fait avec deux fonctions, comme dans le programme Parcours en profondeur.

def parcours_ch(g, vus, org, s):

«  » »parcours depuis le sommet s, en venant de org » » »

…

def chemin(g, u, v):

«  » »un chemin de u à v, le cas échéant, None sinon » » »

…

L’idée est que l’attribut vus n’est plus un ensemble mais un dictionnaire, qui associe à chaque sommet visité le sommet qui a permis de l’atteindre pendant le parcours en profondeur. La fonction parcours_ch prend un argument supplémentaire, org (pour origine), qui est justement le sommet qui a permis d’atteindre s, en empruntant l’arc org → s. Écrire le code de la fonction parcours_ch ; il est très semblable à celui de la fonction parcours du programme 39. Écrire ensuite le code de la fonction chemin qui renvoie un chemin entre les sommets u et v, le cas échéant, et None s’il n’existe pas de chemin entre ces deux sommets. Pour cela, lancer un parcours en profondeur à partir du sommet u, en donnant à org la valeur None, puis, si le sommet v a été atteint, construire le chemin dans un tableau en« remontant » le dictionnaire vus de v jusqu’à u.

Correction : Pour parcours_ch, l’ajout dans un ensemble devient

un ajout dans un dictionnaire.

def parcours_ch(g, vus, org, s):
    """parcours depuis le sommet s, en venant de org"""
    if s not in vus:
        vus[s] = org
        for v in g.voisins(s):
            parcours_ch(g, vus, s, v)

Pour chemin, on prend soin de tester si v a été atteint par le parcours. Dans le cas contraire, on renvoie None. Sinon, on construit le chemin avec une boucle while.

def chemin(g, u, v):
    """un chemin de u à v, le cas échéant, None sinon"""
    vus = {}
    parcours_ch(g, vus, None, u)
    if v not in vus:
        return None
    ch = []
    s = v
    while s is not None:
        ch.append(s)
        s = vus[s]
    ch.reverse()
    return ch

De fait, le chemin est construit à l’envers. On prend soin de le renverser avec la méthode reverse avant de le renvoyer.

Exercice 108 Dans cet exercice, on se propose d’utiliser le parcours en largeur pour construire un chemin de longueur minimale entre deux sommets. On le fait avec deux fonctions, comme dans le programme Parcours en largeur.

def parcours_largeur_ch(g, source):

«  » »parcours depuis le sommet source » » »

…

def chemin(g, u, v):

«  » »un chemin de u à v, le cas échéant, None sinon » » »

…

L’idée est qu’un dictionnaire vus remplace le dictionnaire dist. Ce dictionnaire vus associe à chaque sommet visité le sommet qui a permis de l’atteindre pendant le parcours en largeur. Écrire le code de la fonction parcours_largeur_ch ; il est très semblable à celui de la fonction parcours_largeur du programme 42. Pour le sommet source, on lui associe la valeur None dans le dictionnaire vus. Écrire ensuite le code de la fonction chemin qui renvoie un chemin réalisant la distance entre les sommets u et v, le cas échéant, et None s’il n’existe pas de chemin entre ces deux sommets. Pour cela, lancer un parcours en largeur à partir du sommet u puis, si le sommet v a été atteint, construire le chemin dans un tableau en« remontant » le dictionnaire vus de v jusqu’à u.

Correction : On garde la structure du programme 42, le dictionnaire vus prenant la place du dictionnaire dist.

def parcours_largeur_ch(g, source):
    """parcours depuis le sommet source"""
    vus = {source: None}
    courant = {source}
    suivant = set()
    while len(courant) > 0:
        s = courant.pop()
        for v in g.voisins(s):
            if v not in vus:
                suivant.add(v)
                vus[v] = s
        if len(courant) == 0:
                courant, suivant = suivant, set()
    return vus

La seconde partie, à savoir la reconstruction du chemin, n’est pas différente de celle effectuée dans l’exercice précédent pour un parcours en profondeur.

def chemin(g, u, v):
    """un chemin de u à v, le cas échéant, None sinon"""
    vus = parcours_largeur_ch(g, u)
    if v not in vus:
        return None
    ch = []
    s = v
    while s is not None:
        ch.append(s)
        s = vus[s]
    ch.reverse()
    return ch

Exercice 109 Les nœuds d’un arbre binaire peuvent être vus comme les sommets d’un graphe non orienté. En particulier, on peut donc parcourir largeur les nœuds d’un arbre avec un parcours en profondeur ou en largeur. Pour le parcours en profondeur, il s’agit d’un parcours que nous avons déjà présenté, à savoir le parcours préfixe . Dans cet exercice, on se propose de parcourir les nœuds d’un arbre binaire avec un parcours en largeur.

Écrire une fonction largeur(a) qui reçoit un arbre binaire a en argument et imprime les valeurs de ses différents nœuds dans un ordre donné par un parcours en largeur, c’est-à-dire la valeur contenue dans la racine, puis les valeurs contenues dans les nœuds immédiatement en-dessous (profondeur 1), puis celles contenues dans les nœuds encore en-dessous (profondeur 2), etc.

Adapter pour cela le code du programme Parcours en largeur.

Correction

La subtilité consiste ici à correctement traiter les arbres vides. On a le choix de le faire avant ou après l’insertion dans les ensembles.

On choisit ici de le faire après, ce qui évite de faire un cas particulier pour un arbre qui serait intégralement vide.

def largeur(a):
    courant = []
    suivant = []
    courant.append(a)
    while len(courant) > 0:
        n = courant.pop()
        if n is None:
            continue
        print(n.valeur)
        suivant.append(n.gauche)
        suivant.append(n.droit)
        if len(courant) == 0:
            courant, suivant = suivant, []

pour la suite on utilisera une nouvelle version de ce qui a été fait sur les liste chainée. Celle ci est décomposée en deux classes : Maillons() et ListeC().

On pourra ranger tout ça dans un fichier nommé listes_chainees.py

class Maillon():
    def __init__(self, data = None):
        self.data = data
        self.suiv = None # adresse (en Python, on pointe directement vers un Maillon)

    def __repr__(self):
        t = str(self.data)
        if self.suiv is not None:
            return t + "→"
        return t + "x"



class ListeC():
    def __init__(self):
        self.tete = None # adresse (en Python, on pointe directement vers un Maillon)

    def __repr__(self):
        m = self.tete
        l = []
        while m is not None:
            l.append(str(m))
            m = m.suiv
        return "\n".join(l)

    def est_vide(self):
        """ Renvoie True si la liste est vide"""
        return self.tete is None

    def taille(self):
        """ Renvoie le nombre de maillons de la liste"""
        m = self.tete
        l = 0
        while m is not None:
            l += 1
            m = m.suiv
        return l

    def get_dernier(self):
        """Renvoie le der Maillon de la liste IndexError si liste est vide"""
        if self.est_vide():
            raise IndexError("listeC index out of range")
        m = self.tete
        while m.suiv is not None:
            m = m.suiv
        return m

    def ajouter_fin(self, v):
        """ Ajoute un élément à la fin de la liste chaînée"""
        nM = Maillon(v)
        if self.est_vide():
            self.tete = nM
        else:
            dm = self.get_dernier()
            dm.suiv = nM

    def ajouter_debut(self, v):
        """ Ajoute un élément au début de la liste chaînée"""
        nM = Maillon(v)
        if self.est_vide():
            self.tete = nM
        else:
            nM.suiv = self.tete
            self.tete = nM

    def supprimer_debut(self):
        """ Supprime et renvoie le premier élément de la liste chaînée
        IndexError si la liste est vide"""
        if self.tete is not None:
            m = self.tete
            self.tete = self.tete.suiv
            return m.data
        else:
            raise IndexError("listeC index out of range")

    def supprimer_fin(self):
        """ Supprime et renvoie le dernier élément de la liste chaînée
        IndexError si la liste est vide"""
        if self.est_vide():
            raise IndexError("listeC index out of range")
        m = self.tete
        if m.suiv is None: # 1 seul élément
            self.tete = None
            return m.data
        a = None # avant dernier
        while m.suiv is not None:
            a = m
            m = m.suiv
            a.suiv = None
        return m.data

M1,M2,M3=Maillon(4),Maillon(5),Maillon(7)
M4,M5,M6=Maillon(8),Maillon(-6),Maillon(-13)
M4.suiv=M5
M5.suiv=M6
liste1=ListeC()
liste1.ajouter_fin(M1)
liste1.ajouter_fin(M2)
liste1.ajouter_fin(M3)
print(repr(liste1))
print(repr(M1))
print(repr(M4))
print(repr(M6))

Définir en Python une classe Pile en utilisant une liste chaînée (objet de type ListeC du module listes_chainees ) comme conteneur de données.

À l’aide de seulement 3 méthodes de la classe ListeC , réaliser l’interface complète de cette pile (méthodes est_vide, empiler, et depiler).

À l’aide uniquement des 3 méthodes de l’interface de Pile , réaliser une méthode de représentation (repr).
On pourra utiliser les caractères unicode de « boite » suivants : « ─ » , « └ » , « ┘ » et « │ » Avec un Tableau

Définir en Python une classe Pile en utilisant une liste Python comme conteneur de données.
À l’aide de seulement 2 méthodes et une fonction, réaliser l’interface complète de cette pile.

class Pile:
    def __init__(self):




    def __repr__(self):



    def est_vide(self):


    def depiler(self):


    def empiler(self, n):

correction

from listes_chainees import *



class Pile:
    def __init__(self):
        self.__l = [] # attribut privé : on ne doit utiliser que l'interface élémentaire
        # Pour internationaliser les méthodes :
        self.pop = self.depiler
        self.push = self.empiler
        self.is_empty = self.est_vide

    def __repr__(self):
        l = []
        p = Pile()
        m = 0
        while not self.est_vide():
            c = self.depiler()
            l.append(str(c))
            p.empiler(c)
            m = max(m, len(str(c)))
        # on reconstruit la Pile d'origine
        while not p.est_vide():
            self.empiler(p.depiler())
        # Pour afficher une bordure :
        for i in range(len(l)):
            l[i] = "│" + l[i].ljust(m) +"│"
        return "\n".join(l) + "\n└"+ m*"─" + "┘"

    def est_vide(self):
        return len(self.__l) == 0

    def depiler(self):
        return self.__l.pop()

    def empiler(self, n):
        self.__l.append(n)

activité

Corrigé de l’Exercice 1 : Le Problème de la Coupe de Barres d’Acier (Rod Cutting)

Ce problème vise à trouver le revenu maximal rn​ qu’on peut obtenir en coupant une barre de longueur n.

Exporter vers Sheets

Partie I : Analyse et Récursivité Naïve

1. Exploration des possibilités pour n=4 :

Exporter vers Sheets

Le revenu maximum possible pour une barre de 4 m est de r4​=10€ (obtenu par la découpe 2+2).

2. Retrouver r4​ avec la Relation de Récurrence :

La relation est rn​=max(pn​,r1​+rn−1​,r2​+rn−2​,…,rn−1​+r1​). On utilise la forme simplifiée : rn​=max1≤i≤n​(pi​+rn−i​), avec r0​=0.

Pour n=4, on a :

r4​=max(p1​+r3​, p2​+r2​, p3​+r1​, p4​+r0​)r4​=max(1+8, 5+5, 8+1, 9+0)r4​=max(9, 10, 9, 9)=10

3. Compléter la Fonction Récursive (Naïve) :

La fonction implémente la relation rn​=max1≤i≤n​(pi​+rn−i​). Le terme manquant dans la boucle est la valeur récursive du reste de la barre : revenu_barre(n-i).

Python

def revenu_barre(n):    
   prix = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] # Indice 0 inutilisé
   if n == 0:
        return 0 # Cas de base: revenu pour une barre de longueur 0 est 0
    
   r = float('-inf')
   for i in range(1, n + 1):
       # r = max(r, prix[longueur_du_premier_morceau] + revenu_max_du_reste)
       r = max(r, prix[i] + revenu_barre(n - i)) 
   return r

4. Application des Tarifs Initiaux :

En exécutant la fonction revenu_barre(n) avec les tarifs initiaux :

• r5​=13€ (Découpe : 2+3 ou 3+2)
• r6​=17€ (Découpe : 6 entier)
• r7​=18€ (Découpe : 1+6 ou 6+1)
• r8​=22€ (Découpe : 2+6 ou 6+2)
• r9​=25€ (Découpe : 1+8 ou 8+1)
• r10​=30€ (Découpe : 10 entier)

5. Changement de Tarifs :

Le tableau prix doit être mis à jour. Nouvelle liste des prix : prix = [0, 1, 6, 9, 11, 12, 19, 20, 23, 24, 26]

En réexécutant la fonction avec les nouveaux prix :

• r5​=15€ (Découpe : 2+3)
• r6​=19€ (Découpe : 6 entier)
• r7​=21€ (Découpe : 1+6 ou 6+1)
• r8​=25€ (Découpe : 2+6 ou 6+2)
• r9​=28€ (Découpe : 3+6 ou 6+3)
• r10​=31€ (Découpe : 2+8 ou 8+2)

Partie II : Optimisation par Programmation Dynamique

6. Approche Descendante (Mémorisation) :

On utilise un tableau mem pour stocker les résultats et éviter de recalculer rk​.

Python

def revenu_barre_dyn_desc(n):
    prix = [0, 1, 6, 9, 11, 12, 19, 20, 23, 24, 26]
    mem = [-1] * (n + 1) # -1 indique que le revenu n'a pas encore été calculé
    
    def r_mem(k):
        if k == 0:
            return 0
        
        # 1. Vérification : Si déjà calculé, retourner le résultat mémorisé
        if mem[k] != -1:
            return mem[k]
        
        # 2. Calcul : Sinon, calculer le revenu maximal
        r_max = float('-inf')
        for i in range(1, k + 1):
            # Utiliser r_mem(k - i) pour l'appel récursif (mémorisé)
            r_max = max(r_max, prix[i] + r_mem(k - i))
        
        # 3. Mémorisation : Stocker le résultat avant de le retourner
        mem[k] = r_max
        return r_max
        
    return r_mem(n)

7. Approche Ascendante (Itérative) :

On construit le tableau des revenus maximaux tab de bas en haut, de r1​ à rn​.

Python

def revenu_barre_dyn_asc(n):
    prix = [0, 1, 6, 9, 11, 12, 19, 20, 23, 24, 26]
    tab = [0] * (n + 1) # tab[i] stockera le revenu maximal ri
    # tab[0] est déjà à 0 (r0 = 0)
    
    # On itère de la longueur m=1 à m=n
    for m in range(1, n + 1):
        r_max = float('-inf')
        # On calcule le revenu maximal pour la longueur m
        for i in range(1, m + 1):
            # Calcul r_max = max(pi + r_m-i)
            # tab[m-i] contient le revenu r_m-i déjà calculé
            r_max = max(r_max, prix[i] + tab[m - i]) 
            
        tab[m] = r_max
        
    return tab[n]

Corrigé de l’Exercice 2 : Score Maximal dans une Pyramide de Nombres

Pyramides utilisées :

• ex1 = [[4],[6,2],[3,5,7],[5,1,6,2],[4,7,3,5,2]]
• ex2 = [[3],[1,2],[4,5,9],[3,6,2,1]]

Partie I : Représentation et Fonctions de Base

1. Dessiner la pyramide ex2 :

      [3]
     [1, 2]
    [4, 5, 9]
   [3, 6, 2, 1]

2. Dessiner le chemin ch2 = [0,1,2,2] dans ex2 :

Exporter vers Sheets

Le chemin est : 3→2→9→2.

3. Calculer le score de ch2 :

3+2+9+2=16

4. Fonction est_chemin(ch, p) :

Python

def est_chemin(ch, p):
    # Règle 1: La longueur doit correspondre au nombre de niveaux
    if len(ch) != len(p):
        return False
    
    # Règle 2: Doit commencer par 0
    if ch[0] != 0:
        return False
        
    # Règle 3: Vérification du déplacement
    for i in range(len(ch) - 1):
        a = ch[i]
        b = ch[i+1]
        
        # Le nouvel indice (b) doit être a ou a + 1
        if not (b == a or b == a + 1):
            return False
            
    # Si toutes les règles sont respectées
    return True

# Tests :
# est_chemin([0,1,2,2], ex2) -> True
# est_chemin([0, 0, 0, 2], ex2) -> False (problème à l'étape 3, 0 -> 2)

5. Fonction score(ch, p) :

Python

def score(ch, p):
    s = 0
    # Parcourt chaque niveau (i) de la pyramide et l'indice (j) du chemin
    for i in range(len(p)):
        j = ch[i]
        s += p[i][j]
    return s

# Test :
# score([0,1,1,1,2], ex1) -> 4 + 2 + 5 + 1 + 3 = 15

Partie II : Programmation Dynamique pour l’Optimisation

6. Fonction calcule_score_max(p) (Récursive Naïve) :

On utilise la relation récursive score_max(i,j)=p[i][j]+max(score_max(i+1,j),score_max(i+1,j+1)).

Python

def calcule_score_max(p, i=0, j=0):
    # Cas de base (dernier niveau)
    if i == len(p) - 1:
        return p[i][j]
    
    # Cas récursif: valeur du niveau courant + max des scores des deux sous-pyramides
    gauche = calcule_score_max(p, i + 1, j)
    droite = calcule_score_max(p, i + 1, j + 1)
    
    return p[i][j] + max(gauche, droite)

# Le score maximal est obtenu par calcule_score_max(ex1)

7. Fonction pyramide_nulle(n) :

La pyramide doit avoir n niveaux, avec i+1 éléments au niveau i.

Python

def pyramide_nulle(n):
    pyramide = []
    for i in range(n):
        # Chaque niveau i a une taille de i + 1
        pyramide.append([0] * (i + 1)) 
    return pyramide

# Exemple: pyramide_nulle(4) -> [[0],[0,0],[0,0,0],[0,0,0,0]]

8. Fonction prog_dyn(p) (Ascendante) :

On remplit la pyramide des scores s de bas en haut (du dernier niveau au sommet).

Python

def prog_dyn(p):
    n = len(p)
    if n == 0:
        return 0
        
    # Création de la pyramide des scores maximaux (s)
    # L'approche ascendante utilise souvent un tableau de la taille des données d'entrée.
    # Pour simplifier, on peut initialiser s avec la structure de p (ou une copie)
    s = [list(niveau) for niveau in p] 
    
    # On commence par l'avant-dernier niveau et on remonte jusqu'au sommet (niveau 0)
    for i in range(n - 2, -1, -1):
        # Pour chaque élément (j) du niveau i
        for j in range(len(s[i])):
            
            # Application de la relation de récurrence (score_max)
            # p[i][j] + max(score_max(i+1, j), score_max(i+1, j+1))
            
            # Les valeurs score_max(i+1, ...) sont déjà calculées au niveau i+1 de s.
            max_suivants = max(s[i+1][j], s[i+1][j+1])
            
            # Mise à jour du score maximal pour l'élément (i, j)
            s[i][j] = p[i][j] + max_suivants
            
    # Le score maximal pour la pyramide entière est au sommet
    return s[0][0]

# Test : prog_dyn(ex1) -> 4 + max(6, 2) + ... -> 23

9. Ordre de grandeur du coût de prog_dyn(p) :

La fonction prog_dyn(p) effectue deux boucles imbriquées :

1. La boucle extérieure parcourt les niveaux, de i=n−2 à 0 (soit ≈n niveaux).
2. La boucle intérieure parcourt les éléments j à chaque niveau. Au niveau i, il y a i+1 éléments.

Le nombre total d’opérations est proportionnel à la somme du nombre d’éléments dans la pyramide :

Le coût est donc dominé par n2. L’ordre de grandeur du coût est O(n2) (où n est le nombre de niveaux), ce qui est bien plus performant que l’approche récursive naïve en O(2n).

exercices

Exercice 1 Appels Redondants

Analyse des Appels Récursifs : L’exécution de rendu_monnaie([1, 2], 3) génère la séquence d’appels suivante :

1. rendu_monnaie(..., 3)
   • Appelle rendu_monnaie(..., 3 - 1 = 2)
   • Appelle rendu_monnaie(..., 3 - 2 = 1)
2. rendu_monnaie(..., 2)
   • Appelle rendu_monnaie(..., 2 - 1 = 1)
   • Appelle rendu_monnaie(..., 2 - 2 = 0)
3. rendu_monnaie(..., 1)
   • Appelle rendu_monnaie(..., 1 - 1 = 0)
4. rendu_monnaie(..., 0) → Retourne 0
5. rendu_monnaie(..., 1) (Appelé depuis s=2)
   • Appelle rendu_monnaie(..., 1 - 1 = 0)
6. rendu_monnaie(..., 0) → Retourne 0
7. rendu_monnaie(..., 0) → Retourne 0

Conclusion sur la Redondance : Sur les 7 appels totaux (en comptant le premier), on constate que :

• Le sous-problème pour la somme s=1 a été calculé 2 fois.
• Le sous-problème pour la somme s=0 a été calculé 3 fois.

Ceci illustre le principe des sous-problèmes qui se chevauchent, caractéristique des problèmes résolus par Programmation Dynamique.

.

Corrigé 2 : Calcul du Tableau nb

Système de pièces : P={1,6,10}. Somme finale : S=12. Le tableau nb a une taille S+1=13 (indices 0 à 12). nb[0]=0.

Exporter vers Sheets

Tableau Final nb :

[0,1,2,3,4,5,1,2,3,4,1,2,2]

Le résultat final est nb[12]=2 (par exemple, 6+6 ou 10+2).

.

Corrigé 3 : Code Python avec Solution

Pour suivre la solution optimale, nous ajoutons un deuxième tableau, sol, qui mémorise la liste des pièces pour chaque somme n. Lorsque nous trouvons un meilleur score (1 + nb[n - p] < nb[n]), nous mettons à jour la solution en copiant la solution du sous-problème (sol[n - p]) et en lui ajoutant la pièce p qui a permis cette amélioration.

Python

def rendu_monnaie_solution(pieces, s):
    """
    Renvoie la liste minimale de pièces pour faire la somme s 
    avec le système 'pieces' (Programmation Dynamique).
    """
    # Initialisation au pire cas (n pièces de 1)
    nb = [n for n in range(s + 1)]          # Nombre minimal de pièces
    sol = [[1] * n for n in range(s + 1)] # Liste des pièces utilisées pour chaque somme
    sol[0] = []

    for n in range(1, s + 1):
        for p in pieces:
            if p <= n:
                # Si prendre la pièce p mène à un meilleur nombre total de pièces
                if 1 + nb[n - p] < nb[n]:
                    nb[n] = 1 + nb[n - p]
                    
                    # Mise à jour de la solution : 
                    # Prendre la solution optimale pour le reste (n-p) et ajouter la pièce p
                    sol[n] = sol[n - p].copy() 
                    sol[n].append(p)
                    
    # Retourne la solution optimale pour la somme s
    return sol[s]

Corrigé 4 : Code Python pour Fibonacci

La solution utilise un tableau f pour stocker toutes les valeurs F0​,F1​,…,Fn​ et les calculer de manière itérative, de bas en haut.

Python

def fibonacci(n):
    if n < 0:
        raise ValueError("n doit être positif")
    if n == 0:
        return 0
    
    # Création du tableau de mémorisation F[0] à F[n]
    f = [0] * (n + 1)
    
    # Initialisation des cas de base
    # f[0] = 0 (déjà fait par l'initialisation)
    f[1] = 1
    
    # Calcul itératif de F[2] jusqu'à F[n]
    for i in range(2, n + 1):
        # f[i] = f[i-2] + f[i-1] (Approche ascendante)
        f[i] = f[i - 2] + f[i - 1]
        
    return f[n]

Corrigé 5 : Tableau des Scores d’Alignement

Mots : s1​= »CHAT » (n1​=4) et s2​= »CAT » (n2​=3).

Calculs clés :

• sc[1][1] (C vs C) : max(−1+sc[0][1],−1+sc[1][0],1+sc[0][0])max(−1−1,−1−1,1+0)=max(−2,−2,1)=1
• sc[2][2] (H vs A) : max(−1+sc[1][2],−1+sc[2][1],−1+sc[1][1])max(−1+0,−1+0,−1+1)=max(−1,−1,0)=0
• sc[4][3] (T vs T) : max(−1+sc[3][3],−1+sc[4][2],1+sc[3][2])max(−1+0,−1+0,1+1)=max(−1,−1,2)=2

Le score maximal d’alignement (valeur dans la dernière case) est 2. (Un alignement optimal est : CH-AT contre C-AT, score 1−1+1+1=2).

Corrigé 6 : Alignement AAAAAAAAAA vs BBBBBBBBBB

Score Maximal : Puisque tous les caractères sont différents, il n’y a aucun match possible. Chaque paire alignée (A,B) est un mismatch avec un score de −1. Un alignement optimal sera l’un des deux suivants :

1. 10 Mismatchs : Score 10×(−1)=−10.
2. Gaps : L’alignement sera au maximum 10×(−1)=−10.

Le score maximal est −10.

Forme du Tableau (sc) : Le tableau sc a une taille 11×11.

Explication de la Forme :

• Bords (Ligne 0 et Colonne 0) : Remplis par les scores de gap : −i ou −j.
• Intérieur : Pour chaque case sc[i][j], la valeur est max(−1+sc[i−1][j],−1+sc[i][j−1],−1+sc[i−1][j−1]).
  • La meilleure option est toujours de prolonger l’alignement existant ou de le commencer.
  • La valeur sc[i][j] est max(sc[i−1][j],sc[i][j−1],sc[i−1][j−1])−1.
  • La structure triangulaire de −i sur la diagonale supérieure puis −j sur la diagonale inférieure n’est pas correcte. En réalité, le score sera simplement −max(i,j), car on peut toujours aligner la partie la plus courte avec des gaps et terminer avec des mismatchs. Dans ce cas particulier, sc[i][j]=−max(i,j).

(La correction fournie dans l’énoncé original semble contenir une erreur dans sa description de la structure générale du tableau pour ce cas).

Corrigé 7 : Fonction d’Affichage Formattée

La fonction utilise la méthode de formatage {:>3} pour assurer que chaque élément (caractère ou score) occupe exactement 3 espaces, aligné à droite.

Python

def affiche(s1, s2, sc):
    """Affiche la table des scores d'alignement de manière formattée."""
    
    # 1. Affichage de l'en-tête de colonne (s2)
    print(" ", end="") # Espace pour l'angle supérieur gauche
    for c in s2:
        print('{:>3}'.format(c), end="")
    print() # Retour à la ligne pour le début du tableau
    
    # 2. Affichage des lignes (s1 et scores)
    for i in range(len(sc)): # i va de 0 à len(s1)
        
        # Affichage du caractère de début de ligne (s1[i-1] ou espace/tirets pour la ligne 0)
        if i > 0:
            print('{:>3}'.format(s1[i - 1]), end="")
        else:
            print(" ", end="") # Espace pour la première ligne (index 0)

        # Affichage des scores de la ligne
        for v in sc[i]:
            print('{:>3}'.format(v), end="")
        print() # Retour à la ligne pour la ligne suivante
        
# Exemple d'utilisation (avec les données de l'exercice 5) :
# s1 = "CHAT", s2 = "CAT", sc = [[0,-1,-2,-3],[-1,1,0,-1],[-2,0,0,0],[-3,-1,1,0],[-4,-2,0,2]]
# affiche(s1, s2, sc)
#     C  A  T
#   0 -1 -2 -3
# C -1  1  0 -1
# H -2  0  0  0
# A -3 -1  1  0
# T -4 -2  0  2

Corrigé 8 : Reconstruction de la Solution

Nous introduisons un deuxième tableau, sol, qui, pour chaque paire d’indices (i,j), stocke la meilleure séquence d’alignement trouvée jusqu’à cet état (s1​[0:i],s2​[0:j]).

Python

def aligne_solution(s1, s2):
    n1, n2 = len(s1), len(s2)
    sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
    # sol[i][j] stockera le couple (align_s1, align_s2) optimal jusqu'à s1[i-1], s2[j-1]
    sol = [[("", "")] * (n2 + 1) for _ in range(n1 + 1)]

    # Initialisation des bords (Gaps)
    for i in range(1, n1 + 1):
        sc[i][0] = -i
        sol[i][0] = (s1[0:i], "-" * i) # Alignement de s1[0:i] avec des gaps
    for j in range(1, n2 + 1):
        sc[0][j] = -j
        sol[0][j] = ("-" * j, s2[0:j]) # Alignement de s2[0:j] avec des gaps

    # Reste du tableau
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            
            # Options possibles et leurs scores
            score_gap_s1 = -1 + sc[i - 1][j]           # Gap dans s2 (vertical)
            score_gap_s2 = -1 + sc[i][j - 1]           # Gap dans s1 (horizontal)
            
            # Match ou Mismatch
            sim_score = 1 if s1[i - 1] == s2[j - 1] else -1
            score_diag = sim_score + sc[i - 1][j - 1] # Diagonale

            # Détermination du score maximal et de la solution correspondante
            
            # 1. Initialisation avec le meilleur score connu (souvent un gap)
            s_max = score_gap_s1
            (x, y) = sol[i - 1][j]
            sol[i][j] = (x + s1[i - 1], y + "-") # Aligne s1[i-1] avec un gap

            # 2. Test du Gap dans s1
            if score_gap_s2 > s_max:
                s_max = score_gap_s2
                (x, y) = sol[i][j - 1]
                sol[i][j] = (x + "-", y + s2[j - 1]) # Aligne s2[j-1] avec un gap

            # 3. Test de la Diagonale (Match ou Mismatch)
            if score_diag > s_max:
                s_max = score_diag
                (x, y) = sol[i - 1][j - 1]
                sol[i][j] = (x + s1[i - 1], y + s2[j - 1]) # Aligne les deux caractères

            sc[i][j] = s_max

    # Retourne le score et le couple de chaînes alignées
    return sc[n1][n2], sol[n1][n2]

Corrigé 9 : Adaptation du Programme pour la Biologie

Représentation de la Matrice de Similarités : Le format le plus pratique est un dictionnaire imbriqué (un dictionnaire de dictionnaires), permettant un accès facile O(1) par caractère :

Python

sim = {
    'A': {'A': 10, 'G': -1, 'C': -3, 'T': -4},
    'G': {'A': -1, 'G': 7,  'C': -5, 'T': -3},
    'C': {'A': -3, 'G': -5, 'C': 9,  'T': 0},
    'T': {'A': -4, 'G': -3, 'C': 0,  'T': 8}
}
gap = -5 # Coût du gap

Modification du Programme 48 : On remplace le score fixe de −1 pour les gaps et le score conditionnel de ±1 pour la diagonale par les valeurs de gap et de la matrice sim.

Python

def aligne_custom(s1, s2, sim, gap):
    n1, n2 = len(s1), len(s2)
    sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

    # Initialisation des bords avec le coût de gap
    for i in range(1, n1 + 1):
        sc[i][0] = i * gap # -1 est remplacé par gap
    for j in range(1, n2 + 1):
        sc[0][j] = j * gap # -1 est remplacé par gap

    # Le reste
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            
            # 1. Score de Gap dans s2 (déplacement vertical)
            score_gap_s2 = gap + sc[i - 1][j]
            
            # 2. Score de Gap dans s1 (déplacement horizontal)
            score_gap_s1 = gap + sc[i][j - 1]
            
            # 3. Score d'alignement (déplacement diagonal)
            # Utilisation de la matrice sim
            score_sim = sim[s1[i - 1]][s2[j - 1]] + sc[i - 1][j - 1]
            
            # Score maximal parmi les trois options
            sc[i][j] = max(score_gap_s1, score_gap_s2, score_sim)
            
    return sc[n1][n2]

Corrigé 10 : Dénombrement sur Grille

Ce problème est résolu par la relation de récurrence : le nombre de chemins pour atteindre une case (i,j) est la somme des chemins pour atteindre la case du dessus (i−1,j) et la case de gauche (i,j−1).

chemins(i,j)=chemins(i−1,j)+chemins(i,j−1)

Cas de base :

• Le nombre de chemins pour atteindre n’importe quelle case sur la première ligne (i=0) ou la première colonne (j=0) est toujours 1.

Python

def chemins(n, m):
    """
    Calcule le nombre de chemins de (0, 0) à (n, m) sur une grille, 
    avec déplacements uniquement à droite ou en bas.
    """
    # La grille aura (n+1) lignes et (m+1) colonnes
    grille = [[0] * (m + 1) for _ in range(n + 1)]
    
    # Initialisation des bords (Cas de base: 1 chemin pour atteindre n'importe quelle case de la bordure)
    for i in range(n + 1):
        grille[i][0] = 1
    for j in range(m + 1):
        grille[0][j] = 1
        
    # Remplissage de la grille par approche ascendante
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # Le nombre de chemins pour (i, j) est la somme des chemins depuis le haut et la gauche
            grille[i][j] = grille[i - 1][j] + grille[i][j - 1]
            
    return grille[n][m]

# Vérification : chemins(2, 2) = 6 (Comme mentionné en introduction)

Exercice 1 : Le Problème de la Coupe de Barres d’Acier (Rod Cutting)

Ce problème, inspiré du livre « Introduction to Algorithms, » vise à maximiser le revenu obtenu en coupant une barre d’acier de longueur n en morceaux plus petits.

Données tarifaires :

L’entreprise Sun & Steel peut vendre une barre entière ou la découper pour maximiser son revenu.

Partie I : Analyse et Récursivité Naïve

1) Exploration des possibilités pour n=4 : La barre de 4 m peut être coupée de plusieurs façons. Continuez la liste ci-dessous pour trouver toutes les combinaisons de découpes et déterminez le revenu maximum r4​ possible :

• Vente entière (4): 9€
• Découpe en 2 morceaux (2+2): 5+5=10€
• Découpe en 2 morceaux (1+3): 1+8=9€
• Découpe en 3 morceaux (1+1+2): 1+1+5=7€
• … Ajoutez les combinaisons manquantes (par ex. 1+1+1+1, 1+2+1, etc.)
  

2) Formulation de la Relation de Récurrence : Le revenu maximum rn​ pour une barre de longueur n peut être calculé en considérant toutes les premières coupes possibles. On coupe la barre de longueur n en un premier morceau de longueur i (vendu au prix pi​) et on optimise le revenu sur le morceau restant de longueur n−i (qui rapporte rn−i​).La relation de récurrence est donc : rn​=max​(pi​+rn−i​) où 1≤i≤n et r0​=0 (revenu pour une barre de longueur nulle).Utilisez cette relation pour retrouver la valeur de r4​ en utilisant les revenus maximaux déjà calculés : r1​=1,r2​=5,r3​=8.

r4​=max(p1​+r3​, p2​+r2​, p3​+r1​, p4​+r0​)

3) Implémentation Récursive (Naïve) : Complétez la fonction récursive ci-dessous, qui implémente directement la relation rn​=max1≤i≤n​(pi​+rn−i​).

def revenu_barre(n):
    prix = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] # Indice 0 inutilisé, prix[1] = p1, etc.
    if n == 0:
        return … # Cas de base
    r = float('-inf') # Initialisation au minimum possible
    for i in range(1, n + 1):
        # i est la longueur du premier morceau coupé
        r = max(r, prix[i] + ...) # Terme récursif à ajouter
    return r

4) Application : Utilisez la fonction revenu_barre pour calculer les revenus maximaux r5​,r6​,r7​,r8​,r9​ et r10​.

5) Changement de Tarifs : Le nouveau tableau de prix est proposé dans le tableau proposé plus bas.
Modifiez le tableau prix dans la fonction revenu_barre et recalculez les revenus maximaux rn​ pour n allant de 5 à 10.

Partie II : Optimisation par Programmation Dynamique

L’approche récursive simple entraîne de nombreux recalculs inutiles (sous-problèmes qui se chevauchent).

Pour une barre de 4 m, l’arbre de calcul montre que r1​ est calculé 4 fois et r2​ est calculé 2 fois. La programmation dynamique permet d’éviter cette redondance.

6. Approche Descendante (Mémorisation) : Écrivez une fonction revenu_barre_dyn_desc(n) qui utilise la mémorisation (un tableau mem) pour stocker et réutiliser les valeurs de ri​ déjà calculées, évitant ainsi les appels récursifs redondants.
   • Indice : La structure sera similaire à fib_mem du cours. Le tableau mem stocke ri​. Avant tout appel récursif, vérifiez si mem[n] est déjà calculé.
7. Approche Ascendante (Itérative) : Écrivez une fonction revenu_barre_dyn_asc(n) qui utilise une méthode itérative (boucles) pour calculer ri​ séquentiellement, de r1​ à rn​, en stockant les résultats dans un tableau.
   • Indice : Initialisez un tableau tab de taille n+1 avec tab[0]=0. Utilisez une boucle for allant de m=1 à n pour calculer tab[m] en utilisant la relation de récurrence et les valeurs déjà présentes dans le tableau.

Exercice 2 : Score Maximal dans une Pyramide de Nombres

Ce problème consiste à trouver le chemin de score maximal en partant du sommet d’une pyramide et en descendant en choisissant, à chaque niveau, l’élément immédiatement à gauche ou à droite.

La pyramide est représentée par une liste de listes. Exemple : ex1 = [[4],[6,2],[3,5,7],[5,1,6,2],[4,7,3,5,2]]

En gris on peut lire un des chemins possibles (qui est loin d’être le plus long) son score sera : 4 + 2 + 5 + 1 + 3 = 15.

Partie I : Représentation et Fonctions de Base

1. Représentation : Dessinez la pyramide représentée par la liste de listes ex2 = [[3],[1,2],[4,5,9],[3,6,2,1]].
2. Chemins et Indices : Un chemin est représenté par la liste des indices choisis à chaque niveau. Par exemple, le chemin gris dans ex1 est ch1 = [0,1,1,1,2]. Dessinez le chemin ch2 = [0,1,2,2] dans la pyramide ex2.
3. Calcul du Score : Calculez le score du chemin ch2 = [0,1,2,2] dans la pyramide ex2.
4. Fonction de Validation : Écrivez une fonction est_chemin(ch, p) qui vérifie si une liste d’indices ch est un chemin valide dans la pyramide p. Les règles sont :
   • Doit commencer par 0 (ch[0] == 0).
   • La longueur de ch doit être égale au nombre de niveaux de p.
   • Chaque indice consécutif b (au niveau i+1) doit être a ou a+1 par rapport à l’indice précédent a (au niveau i).
   • Tests : est_chemin(ch2, ex2) doit renvoyer True. est_chemin([0, 0, 0, 2], ex2) doit renvoyer False.
5. Fonction de Score : Écrivez une fonction score(ch, p) qui prend un chemin valide et la pyramide, et renvoie le score total.
   • Test : score(ch1, ex1) doit renvoyer 15.

Partie II : Programmation Dynamique pour l’Optimisation

Le problème du chemin maximal présente une structure de sous-problèmes optimaux. Le chemin optimal de la pyramide entière est composé du sommet et du chemin optimal de l’une des deux sous-pyramides adjacentes.

Soit score_max(i,j) le score maximal possible à partir du nombre situé à l’indice j du niveau i.

Les relations sont :

• Cas de base (dernier niveau) : score_max(len(p)−1,j)=p[len(p)−1][j]
• Cas récursif : score_max(i,j)=p[i][j]+max(score_max(i+1,j),score_max(i+1,j+1))

6. Implémentation Récursive (Naïve) : Écrivez une fonction calcule_score_max(p) qui utilise directement la relation de récurrence pour trouver le score maximal score_max(0,0).
7. Préparation pour la PD : Écrivez une fonction pyramide_nulle(n) qui crée une structure de pyramide (liste de listes) de n niveaux, remplie de zéros. Cette pyramide servira de tableau de mémorisation.
8. Approche Ascendante (Programmation Dynamique) : Écrivez une fonction prog_dyn(p) qui calcule le score maximal en utilisant la programmation dynamique ascendante (du bas vers le haut).
   • Créez une pyramide de mémorisation s de la même taille que p.
   • Commencez par initialiser le dernier niveau de s avec les valeurs du dernier niveau de p.
   • Remontez itérativement niveau par niveau (de len(p)−2 jusqu’à 0), en appliquant la formule score_max(i,j).
   • Le résultat final sera s[0][0].
9. Analyse de Complexité : Déterminez l’ordre de grandeur du coût (complexité en temps) de la fonction prog_dyn(p) pour une pyramide à n niveaux (sachant que le nombre d’éléments au niveau i est i+1).

Exercice 1 : Analyse de la Récursivité Naïve (Rendu de Monnaie)

Objectif : Identifier l’inefficacité des algorithmes récursifs sans mémorisation.

Énoncé : Soit la fonction récursive rendu_monnaie qui calcule le nombre minimal de pièces pour une somme donnée, sans utiliser la programmation dynamique :

Python

def rendu_monnaie(pieces, s):
    """
    Renvoie le nombre minimal de pièces pour faire la somme s 
    avec le système 'pieces' (approche récursive naïve).
    """
    if s == 0:
        return 0
    
    r = s # Initialisation au pire cas (1+1+...+1)
    for p in pieces:
        if p <= s:
            r = min(r, 1 + rendu_monnaie(pieces, s - p))
    return r

Question : Explicitez (à la main) tous les appels récursifs effectués par la fonction lorsque vous exécutez rendu_monnaie([1, 2], 3). Identifiez clairement les calculs redondants (les sous-problèmes qui sont résolus plusieurs fois).

Exercice 2 : Rendu de Monnaie par Programmation Dynamique (Ascendante)

Objectif : Comprendre le remplissage du tableau de mémorisation dans l’approche ascendante (Bottom-up).

Énoncé : Soit le programme d’approche ascendante (Programmation Dynamique) pour le rendu de monnaie :

Python

def rendu_monnaie(pieces, s):
    """
    Renvoie le nombre minimal de pièces pour faire la somme s 
    avec le système 'pieces' (approche dynamique ascendante).
    """
    nb = [0] * (s + 1) # Tableau de mémorisation
    
    for n in range(1, s + 1):
        nb[n] = n # Initialisation au pire cas (1+1+...+1)
        for p in pieces:
            if p <= n:
                # Mise à jour: 1 + nb[n - p] est le nombre de pièces si on prend la pièce p
                nb[n] = min(nb[n], 1 + nb[n - p])
    return nb[s]

Question : Calculez à la main et présentez l’état final du tableau nb lorsque l’on exécute rendu_monnaie([1, 6, 10], 12).

Exercice 3 : Rendu de Monnaie avec Solution Optimale

Objectif : Étendre l’approche dynamique pour tracer et reconstruire la solution (les pièces utilisées).

Énoncé : Modifiez le programme rendu_monnaie de l’Exercice 2 pour qu’il renvoie non seulement le nombre minimal de pièces, mais aussi la liste exacte des pièces qui composent cette solution optimale. Vous pouvez vous inspirer de l’exemple fourni (rendu_monnaie_solution).

Exercice 4 : Suite de Fibonacci par Programmation Dynamique

Objectif : Appliquer la PD à la suite de Fibonacci en utilisant l’approche ascendante (itérative).

Énoncé : La suite de Fibonacci est définie par F0​=0,F1​=1 et Fn​=Fn−1​+Fn−2​ pour n≥2. Écrivez une fonction fibonacci(n) qui calcule la valeur de Fn​ en utilisant la programmation dynamique (approche itérative, sans récursion).

voici un programme d’alignement de séquences fondamental sur lequel vont venir s’appuyer les exercices à suivre

def aligne(s1, s2):
    """le score du meilleur alignement de s1 et s2"""
    n1, n2 = len(s1), len(s2)
    sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
    # première ligne et première colonne
    for i in range(1, n1 + 1):
        sc[i][0] = -i
    for j in range(1, n2 + 1):
        sc[0][j] = -j
    # le reste
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])
            if s1[i - 1] == s2[j - 1]:
                sc[i][j] = max(s, 1 + sc[i - 1][j - 1])
            else:
                sc[i][j] = max(s, -1 + sc[i - 1][j - 1])
    return sc[n1][n2]

Exercice 5 : Calcul du Tableau d’Alignement (Sequence Alignment)

Objectif : Appliquer manuellement la formule de récurrence du Programme 48 sur un petit exemple.

Énoncé : Le programme d’Alignement de Séquences (voir avant l’exercice 5) utilise la Programmation Dynamique pour calculer le score maximal d’alignement entre deux chaînes. Les règles de score utilisées par ce programme sont :

• Match : +1
• Mismatch : −1
• Gap (-) : −1

Question : Calculez à la main le tableau des scores d’alignement (sc) pour les deux mots « CHAT » et « CAT ». Quel est le score maximal final ?

Exercice 6 : Alignement de Séquences Identiques (Mismatchs)

Objectif : Déterminer la structure du tableau lorsque tous les alignements sont des mismatchs ou des gaps.

Énoncé : En utilisant les règles de score du programme d’Alignement de Séquences (voir avant l’exercice 5) (+1 pour match, -1 pour mismatch/gap), quel est le score maximal d’alignement des mots s1​= »AAAAAAAAAA » et s2​= »BBBBBBBBBB » (10 caractères chacun) ? Décrivez la forme du tableau calculé.

Exercice 7 : Affichage Formatté de la Table de Scores

Objectif : Créer une fonction utilitaire pour visualiser le tableau de Programmation Dynamique.

Énoncé : Écrivez une fonction affiche(s1, s2, sc) qui prend les deux séquences (s1, s2) et le tableau des scores (sc) calculé par le Programme 48, et affiche la table sous un format lisible et aligné.

Exercice 8 : Alignement avec Solution (Reconstruction)

Objectif : Modifier le programme d’alignement pour reconstruire la séquence d’opérations menant au score optimal.

Énoncé : Modifiez Le programme d’Alignement de Séquences (voir avant l’exercice 5) pour qu’il renvoie également la solution optimale sous la forme d’un couple de chaînes alignées (avec le caractère - pour les gaps).

Exercice 9 : Alignement avec Matrice de Similarités et Coût de Gap

Objectif : Généraliser le Programme 48 pour utiliser une matrice de similarités personnalisée et un coût de gap variable.

Énoncé : Dans les alignements biologiques (ADN), les scores ne sont pas fixes. Nous utilisons :

1. Une matrice de similarités (sim) pour le score d’alignement entre deux caractères spécifiques.
2. Une variable globale gap pour le coût de création d’un gap (-).

Question : Indiquez comment représenter la matrice de similarités en Python et modifiez le programme d’Alignement de Séquences (voir avant l’exercice 5) pour utiliser ces variables (sim et gap).

Exercice 10 : Nombre de Chemins sur une Grille

Objectif : Résoudre un problème de dénombrement par Programmation Dynamique.

Énoncé : Écrivez une fonction chemins(n, m) qui calcule le nombre de chemins possibles sur une grille de taille n×m (partant du coin supérieur gauche 0,0 jusqu’au coin inférieur droit n,m), en se déplaçant uniquement vers la droite ou vers le bas.

technique pour améliorer les Algorithmes Récursifs

La programmation dynamique est une puissante technique algorithmique qui transforme des solutions récursives « naïves » mais correctes en des solutions beaucoup plus efficaces en évitant les recalculs inutiles. Nous allons explorer cette méthode à travers un exemple classique, la suite de Fibonacci, et ensuite l’appliquer à un problème d’optimisation : le problème du sac à dos (Knapsack Problem).

1) La Suite de Fibonacci et le Recalcul Inutile

L’Approche Récursive Simple

La suite de Fibonacci (Fn​) est définie par F0​=0, F1​=1, et Fn​=Fn−1​+Fn−2​ pour n≥2. Une implémentation récursive directe en Python est la suivante :

Python

def fib_recursif(n):
    if n < 2:
        return n
    else:
        return fib_recursif(n-1) + fib_recursif(n-2)

Pour calculer F6​, l’exécution de ce code crée une structure arborescente d’appels. Si l’on déploie cet arbre pour F6​, on constate une forte redondance des calculs.

Par exemple, le calcul de F4​ est effectué deux fois, celui de F3​ est effectué trois fois, etc. Cette duplication des efforts entraîne une complexité temporelle qui augmente de manière exponentielle (O(2n)), rendant cette approche impraticable pour de grandes valeurs de n.

En observant attentivement le schéma ci-dessus, vous avez remarqué que de nombreux calculs sont inutiles, car effectués 2 fois : par exemple, on retrouve le calcul de fib(4) à 2 endroits (en haut à droite et un peu plus bas à gauche) :

L’Optimisation par Mémorisation (Approche Descendante)

L’idée fondamentale est d’éviter de recalculer un résultat une fois qu’il a été obtenu. Nous allons « mémoriser » la solution de chaque sous-problème (Fk​) dans un tableau ou un dictionnaire au fur et à mesure que nous le calculons.

Python

def fib_mem(n):
    # Initialise un tableau pour stocker les résultats.
    # Tous les résultats sont initialisés à 0 (ou une valeur "jamais calculée").
    memo = [0] * (n + 1)
    
    def f_mem(k):
        if k == 0 or k == 1:
            # Cas de base : on mémorise et retourne la valeur
            memo[k] = k
            return k
        
        # Vérification 1 : Si le résultat est déjà mémorisé, on le retourne directement.
        elif memo[k] > 0: # > 0 car F0=0 et on suppose n>0 pour les autres
            return memo[k]
        
        # Calcul : Si le résultat n'est pas mémorisé, on le calcule
        else:
            memo[k] = f_mem(k - 1) + f_mem(k - 2)
            return memo[k]
            
    return f_mem(n)

Principe de la Mémorisation :

1. Si la valeur de Fk​ a déjà été calculée (si elle est dans le tableau memo), on l’utilise sans faire de calcul supplémentaire.
2. Si la valeur de Fk​ n’a jamais été calculée, elle est calculée une unique fois, puis stockée dans le tableau memo pour une utilisation ultérieure.

Cette technique, appelée mémorisation (ou memoization), résout le problème Fk​ une seule fois, transformant la complexité exponentielle en une complexité beaucoup plus efficace, linéaire (O(n)). On parle ici de programmation dynamique descendante (top-down), car nous partons du problème principal (Fn​) et le décomposons jusqu’aux cas de base (F0​,F1​).

2) La Programmation Dynamique

a) Introduction et Concepts Fondamentaux

La Programmation Dynamique (PD) est une méthode algorithmique pour résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples. Inventée par Richard Bellman dans les années 1950, le terme « programmation » est à prendre dans le sens de planification ou d’ordonnancement d’un processus, et non de codage.

La PD s’applique efficacement aux problèmes qui présentent deux caractéristiques principales :

1. Sous-problèmes Optimaux : Une solution optimale au problème principal doit être construite à partir de solutions optimales à ses sous-problèmes (principe de Bellman).
2. Sous-problèmes Réciproques (Overlapping Subproblems) : Les sous-problèmes se recoupent, c’est-à-dire que le même sous-problème est rencontré et doit être résolu plusieurs fois.

La PD résout chaque sous-problème une seule fois et mémorise sa réponse, évitant ainsi le coût du recalcul.

b) Approche Ascendante (Bottom-Up)

L’approche ascendante (ou bottom-up) est la deuxième facette de la programmation dynamique. Au lieu d’utiliser la récursivité et la mémorisation (descendante), elle utilise une approche itérative (boucles) pour construire la solution des plus petits sous-problèmes vers le problème principal.

Fibonacci avec l’Approche Ascendante

Pour Fibonacci, l’idée est de remplir le tableau des résultats en partant de F0​ et F1​ et en montant jusqu’à Fn​.

Python

def fib_asc(n):
    if n < 2:
        return n
        
    # Crée un tableau pour stocker F0, F1, ..., Fn
    tab = [0] * (n + 1)
    tab[1] = 1 # Initialise F1
    
    # Calcule F2, F3, ..., Fn de manière itérative
    for i in range(2, n + 1):
        tab[i] = tab[i - 1] + tab[i - 2]
        
    return tab[n]

Ce programme est très simple. On construit Fi​ à partir de Fi−1​ et Fi−2​ qui ont déjà été calculés et stockés dans le tableau tab. Chaque Fi​ est calculé une seule fois.

3) Application à l’Optimisation : Le Problème du Sac à Dos (Knapsack Problem 0/1)

Le problème du sac à dos (0/1) est un problème d’optimisation classique : Étant donné un sac à dos de capacité maximale W et une liste d’objets, chacun avec un poids pi​ et une valeur vi​, déterminer quels objets inclure dans le sac afin de maximiser la valeur totale sans dépasser la capacité W.

Ce problème ne peut pas être résolu de manière gloutonne (greedy) de manière fiable (par exemple, prendre toujours l’objet de plus grande valeur ou le meilleur rapport valeur/poids ne garantit pas la solution optimale globale).

Formulation Récursive et Sous-problèmes

Pour déterminer la valeur maximale que l’on peut obtenir avec une capacité w et les i premiers objets, nous avons deux choix pour l’objet i :

1. On inclut l’objet i : La valeur totale sera vi​ plus la valeur maximale obtenue avec la capacité restante w−pi​ et les i−1 premiers objets. (Possible seulement si pi​≤w).
2. On n’inclut pas l’objet i : La valeur totale sera la valeur maximale obtenue avec la capacité w et les i−1 premiers objets.

La relation de récurrence (pour un objet i de poids pi​ et valeur vi​, et une capacité w ) est :

Résolution par Programmation Dynamique Ascendante

Nous allons utiliser l’approche ascendante pour construire un tableau bidimensionnel DP, où DP[i][w] représente la valeur maximale que l’on peut obtenir en utilisant les i premiers objets pour une capacité de sac à dos w.

Exemple : Capacité W=5. Objets : O1​(p=2,v=3), O2​(p=3,v=4), O3​(p=4,v=5).

Exporter vers Sheets

Analyse du tableau :

• DP[1][2]: Pour w=2 et seul l’objet O1​ disponible. Puisque p1​=2≤2, DP[1][2]=max(DP[0][2],v1​+DP[0][2−2])=max(0,3+0)=3.
• DP[2][5]: Pour w=5 et les objets O1​,O2​ disponibles. Puisque p2​=3≤5, DP[2][5]=max(DP[1][5],v2​+DP[1][5−3])=max(3,4+DP[1][2]). DP[1][2]=3. Donc max(3,4+3)=7. (On prend O2​ et on utilise la meilleure valeur pour la capacité restante de 2 avec l’objet O1​).

La solution optimale est donnée par DP[N][W] (ici DP[3][5]=7). Le problème est résolu avec une complexité en temps de O(N×W), où N est le nombre d’objets et W la capacité maximale, bien plus efficace qu’une approche par force brute (tester toutes les combinaisons).

Coût vs Bénéfice

Comme pour Fibonacci, la programmation dynamique permet un gain spectaculaire en complexité temporelle (le temps d’exécution). Cependant, elle nécessite l’utilisation d’une structure de données (le tableau memo ou le tableau DP) pour stocker les résultats des sous-problèmes.

Conclusion : La programmation dynamique échange de l’efficacité en temps contre une augmentation de l’utilisation de la mémoire (complexité spatiale).

L’Alignement de Séquences : Le Détective de l’ADN 🕵️‍♀️

1. Le Problème : Comparer l’ADN (ou des Mots !)

Imaginez que vous êtes un détective et que vous avez deux longues chaînes de caractères (comme des brins d’ADN, ou simplement deux mots) que vous devez comparer pour voir à quel point elles sont similaires.

C’est le problème de l’Alignement de Séquences : comment mettre en face les caractères de deux chaînes pour maximiser les correspondances.

La Règle du Jeu : L’Alignement

Pour comparer deux mots (par exemple, « GENOME » et « ENORME »), nous allons les écrire l’un sous l’autre. Nous pouvons insérer des trous (représentés par un tiret, -) dans l’une ou l’autre chaîne.

• Contrainte essentielle : L’ordre des lettres ne doit jamais changer !
• Contrainte essentielle : On n’aligne jamais deux trous ensemble (-- est interdit).

Exporter vers Sheets

Comment Compter les Points (Le Score)

Pour trouver le « meilleur » alignement, on utilise un système de points simple :

Exporter vers Sheets

Exemple d’évaluation (GENO-ME vs -ENORME) :

Exporter vers Sheets

Score Total : (−1)+(+1)+(+1)+(+1)+(−1)+(+1)+(+1)=3

Le but de l’algorithme est de trouver l’alignement qui donne le score maximal possible.

2. L’Approche « Bête et Méchante » (Récursivité Naïve)

Comment un ordinateur chercherait-il la meilleure solution ?

Il pourrait essayer de le faire de manière récursive, c’est-à-dire en se ramenant à un problème plus petit à chaque étape.

La Décomposition Récursive

Pour trouver le meilleur score entre deux mots M1​ et M2​, il suffit de regarder leurs derniers caractères (c1​ et c2​). Il y a toujours trois choix possibles pour l’alignement final :

Exporter vers Sheets

Le Score Maximal pour M1​ et M2​ est simplement le maximum des scores obtenus par ces trois choix. On répète ensuite l’opération (récursion) sur les mots plus courts.

Le Problème des Recalculs (Pourquoi ça explose 💣)

Si on utilise cette approche, l’ordinateur va vite se retrouver à faire la même chose encore et encore.

Exemple : Pour aligner « GENOME » et « ENORME » :

1. Le Choix 1 vous demande d’aligner « GENOM » et « ENORM ».
2. Le Choix 2 vous demande d’aligner « GENOM » et « ENORME ».
3. Le Choix 3 vous demande d’aligner « GENOME » et « ENORM ».

Regardez le problème « GENOM » et « ENORM » : Il est calculé comme sous-problème dans les trois cas ! Ce problème est dit un sous-problème qui se chevauche.

Pour des mots de 20 lettres, ce phénomène de duplication se répète des milliards de fois, et le temps de calcul devient exponentiel (beaucoup trop lent !).

3. La Solution Intelligente : La Programmation Dynamique 🧠

Comme pour le problème du Rendu de Monnaie, nous allons utiliser la Programmation Dynamique (PD) pour éviter de recalculer les mêmes sous-problèmes. L’idée est de mémoriser chaque résultat.

Le Tableau de Scores (La « Carte »)

Au lieu de faire des appels récursifs et de tout oublier, nous allons construire un grand tableau à deux dimensions, appelé le tableau de scores (sc).

• Si le premier mot (s1​) a N lettres et le deuxième mot (s2​) a M lettres, le tableau aura une taille de (N+1)×(M+1).
• La case sc[i][j] va stocker le score maximal obtenu en alignant les i premières lettres de s1​ avec les j premières lettres de s2​.

Exporter vers Sheets

Le résultat que nous cherchons est toujours la case en bas à droite : sc[N][M].

L’Initialisation des Bords (Les Cas Simples)

On commence par remplir la première ligne et la première colonne (les cas où l’on aligne un mot avec un mot vide).

• sc[0][0]=0 : Aligner deux mots vides donne un score de 0.
• sc[i][0]=−i : Pour aligner les i premières lettres de s1​ avec un mot vide, nous devons faire i gaps (trous). Le coût est donc i×(−1)=−i.
• sc[0][j]=−j : De même, aligner s2​ avec un mot vide coûte −j.

Le Remplissage des Cases (Le Cœur du Calcul)

Pour remplir une case sc[i][j], nous utilisons la logique récursive des trois choix, mais au lieu d’appeler la fonction, nous regardons simplement les trois cases voisines qui ont déjà été calculées :

1. Voisin du Dessus (sc[i-1][j]) → Correspond au Choix 2 (Gap dans s2​).
2. Voisin de Gauche (sc[i][j-1]) → Correspond au Choix 3 (Gap dans s1​).
3. Voisin en Diagonale (sc[i-1][j-1]) → Correspond au Choix 1 (Alignement des deux derniers caractères s1​[i−1] et s2​[j−1]).

La formule de calcul (la relation de récurrence) devient :

Où score_match=+1 si s1​[i−1]=s2​[j−1], et −1 sinon.

L’Efficacité : Un Gain Incroyable 🚀

Grâce à cette méthode :

• Chaque case du tableau n’est calculée qu’une seule fois !
• Pour des mots de longueur N et M, le temps de calcul est proportionnel à la taille du tableau, soit N×M.

C’est une amélioration massive :

• Récursivité naïve : Temps exponentiel (O(2max(N,M))). Impraticable au-delà de 20 lettres.
• Programmation Dynamique : Temps polynomial (O(N×M)). C’est presque instantané même pour des séquences de milliers de caractères !

Ce tableau ne sert pas seulement à trouver le score maximal ; en remontant de la case finale à la case initiale en suivant les flèches du meilleur score à chaque fois, on peut reconstruire l’alignement optimal lui-même (comme vous le verrez dans certains exercices).

La méthode « Diviser pour régner » est un paradigme algorithmique puissant, souvent utilisé pour résoudre des problèmes complexes de manière élégante et efficace. L’idée est de décomposer un problème en plusieurs sous-problèmes, de les résoudre individuellement, puis de combiner leurs solutions pour obtenir la solution du problème initial.

Ce processus se décompose en trois phases principales :

• DIVISER : Le problème initial est scindé en plusieurs sous-problèmes plus petits, généralement de nature similaire à l’original.
• RÉGNER : Chaque sous-problème est résolu, souvent de manière récursive. La clé est que ces sous-problèmes sont plus simples à gérer que le problème de départ.
• COMBINER : Les solutions des sous-problèmes sont fusionnées pour construire la solution finale du problème d’origine.

Les algorithmes qui emploient cette approche sont très souvent de nature récursive. Un exemple classique de cette méthode est le tri-fusion.

Le Tri-Fusion

Présentation

Le tri-fusion est un algorithme de tri efficace qui repose sur le principe « Diviser pour régner ». Il prend un tableau non trié en entrée et renvoie le même tableau, mais cette fois, dans l’ordre croissant.

Voici une implémentation simplifiée en pseudo-code des deux fonctions qui composent cet algorithme : FUSION et TRI-FUSION.

VARIABLE
A : tableau d'entiers
L, R : tableaux d'entiers
p, q, r, n1, n2 : entiers
k, i, j : entiers

DEBUTFUSION (A, p, q, r):
    n1 ← q - p + 1
    n2 ← r - q
    créer tableau L[1..n1+1] et R[1..n2+1]
    pour i ← 1 à n1:
        L[i] ← A[p+i-1]
    fin pour
    pour j ← 1 à n2:
        R[j] ← A[q+j]
    fin pour
    L[n1+1] ← ∞
    R[n2+1] ← ∞
    i ← 1
    j ← 1
    pour k ← p à r:
        si L[i] ⩽ R[j]:
            A[k] ← L[i]
            i ← i + 1
        sinon:
            A[k] ← R[j]
            j ← j + 1
        fin si
    fin pour
fin FUSION

TRI-FUSION(A, p, r):
    si p < r:
        q = (p + r) / 2
        TRI-FUSION(A, p, q)
        TRI-FUSION(A, q+1, r)
        FUSION(A, p, q, r)
    fin si
fin TRI-FUSION

L’appel initial pour trier un tableau A est TRI-FUSION(A, 1, A.longueur). Notez que dans cet algorithme, la fonction TRI-FUSION gère la phase de DIVISER, tandis que la fonction FUSION combine les phases de RÉGNER et de COMBINER.

Un aspect intéressant du tri-fusion est que la phase de « Régner » est trivialement simple : le processus de division se poursuit jusqu’à ce que les sous-problèmes ne contiennent qu’un seul élément. Trier un tableau d’un seul élément ne demande aucune opération, ce qui simplifie grandement la tâche.

La véritable magie opère lors de la phase de fusion. Imaginons que nous ayons deux tableaux déjà triés, B et C, et que nous souhaitions les fusionner en un nouveau tableau T. On compare simplement le premier élément de B avec le premier de C, on ajoute le plus petit des deux à T, puis on recommence avec les éléments restants. On continue jusqu’à ce que l’un des tableaux soit vide, puis on ajoute les éléments restants de l’autre tableau à la fin de T.

Complexité

Bien que le calcul rigoureux soit hors de la portée de ce cours, nous pouvons en estimer la complexité de manière intuitive. La phase de division, où les tableaux sont coupés en deux à plusieurs reprises, est liée à la fonction logarithmique en base 2, soit log_2(n). La phase de fusion, pour un tableau de n éléments, nécessite un nombre de comparaisons proportionnel à n. En combinant ces deux observations, nous arrivons à une complexité approximative de l’ordre de O(nlog(n)).

Comme le montre la comparaison des courbes, un algorithme en O(nlog(n)) est beaucoup plus performant pour de grandes valeurs de n qu’un algorithme en O(n²), comme le tri par insertion ou le tri par sélection.

Retour sur la dichotomie

Présentation

C’est une méthode pour trouver un nombre N dans une liste triée si elle y est présente ou pour prouver son absence. Le principe est de regarder la valeur centrale, soit c’est celle qu’on cherche soit la valeur trouvée nous permettra de déterminer dans laquelle des sous listes de part et d’autre de la valeur devrait se situer N. Une fois fait on applique la même démarche sur la sous liste en question. On continuera jusqu’à soit tomber sur N ou obtenir une liste ne divise cette sous liste et on repère dans laquelle des parties devrait se situer la valeur. On continue, avec des sous listes de plus en plus petites et se dirigeant progressivement vers des listes vides. Soit on tombe sur N avant cela, sinon la valeur n’est pas présente. Cette recherche repose sur le principe « Diviser pour régner ».

exercice (corrigé ici)

compléter le code ci dessous

def recherche(t, v, g, d):
    """renvoie une position de v dans t[g..d],
    supposé trié, et None si elle ne s’y trouve pas"""
    if g > d:
        return None
    m = (g + d) // 2
    if t[m] < v:
        return recherche(t, v, m + 1, d)
    elif t[m] > v:
        return recherche(t, v, g, m - 1)
    else:
        return m

def recherche_dichotomique(t, v):
    """renvoie une position de v dans le tableau t,
    supposé trié, et None si elle ne s’y trouve pas"""
    return recherche(t, v, 0, len(t) - 1)

L’appel initial pour trier un tableau A est TRI-FUSION(A, 1, A.longueur). Notez que dans cet algorithme, la fonction TRI-FUSION gère la phase de DIVISER, tandis que la fonction FUSION combine les phases de RÉGNER et de COMBINE

Activités et Exercices

Activité 1

Appliquez l’algorithme de tri-fusion au tableau T= [23, 12, 4, 56, 35, 32, 42, 57, 3]. Vous pouvez créer un schéma et expliquer en détail la fusion de deux tableaux triés.

1. La phase de division

Le tri fusion commence par diviser de manière récursive le tableau initial en deux moitiés égales. Ce processus se poursuit jusqu’à ce que chaque sous-tableau ne contienne qu’un seul élément. À ce stade, le sous-tableau est considéré comme trié. C’est la partie « régner » de l’algorithme, qui est ici triviale.

2. La phase de fusion

Une fois que tous les sous-tableaux d’un seul élément sont formés, le tri fusion passe à la phase la plus importante : la fusion. L’idée est de fusionner deux sous-tableaux déjà triés en un seul grand tableau trié. C’est un processus simple qui se déroule en comparant les premiers éléments de chaque sous-tableau.

Prenons l’exemple de la fusion des deux tableaux triés suivants :

• B = [4, 12, 23, 35, 56]
• C = [3, 32, 42, 57]

Nous allons construire un nouveau tableau, T, qui contiendra le résultat de la fusion.

1. On compare le premier élément de B (4) avec le premier élément de C (3). Comme 3 est plus petit que 4, on le place dans T.
   • T = [3]
   • B = [4, 12, 23, 35, 56]
   • C = [32, 42, 57]
2. On compare à nouveau le premier élément restant de B (4) avec le premier élément de C (32). Comme 4 est plus petit, on le place dans T.
   • T = [3, 4]
   • B = [12, 23, 35, 56]
   • C = [32, 42, 57]
3. On continue ce processus :
   • On compare 12 et 32 : 12 est plus petit. On ajoute 12 à T.
   • On compare 23 et 32 : 23 est plus petit. On ajoute 23 à T.
   • On compare 35 et 32 : 32 est plus petit. On ajoute 32 à T.
   • On compare 35 et 42 : 35 est plus petit. On ajoute 35 à T.
   • On compare 56 et 42 : 42 est plus petit. On ajoute 42 à T.
   • On compare 56 et 57 : 56 est plus petit. On ajoute 56 à T.

À ce stade, le tableau B est vide. Il ne reste plus qu’un seul élément dans C (57). On l’ajoute directement à la fin du tableau T.

• Le tableau final trié est donc : T = [3, 4, 12, 23, 32, 35, 42, 56, 57].

Ce processus de comparaison et d’ajout est répété pour toutes les fusions successives jusqu’à ce que tous les éléments soient rassemblés dans un seul tableau final trié.

Activité 2

Complétez le code Python suivant pour la fonction de tri-fusion :

def tri_fusion(tab):
    def fusion(tab, p, q, r):
        n1 = q-p+1
        n2 = r-q
        L = [0]*n1
        R = [0]*n2
        for i in range(n1):
            L[i] = tab[p+i]
        for j in range(n2):
            R[j] = tab[q+j+1]
        L.append(float("inf"))
        R.append(float("inf"))
        i = 0
        j = 0
        for k in range(p, r+1):
            if L[i] <= R[j]:
                tab[k] = L[i]
                i = i + 1
            else:
                tab[k]=R[j]
                j = j + 1

    def tri_f(tab, p, r) :
        if p < r:
            q = (p + r) // 2
            tri_f(tab, p, q)
            tri_f(tab, q + 1, r)
            fusion(tab, p, q, r)

    tri_f(tab, p = 0, r = len(tab) - 1)
    return tab

Activité 3

Complétez cette autre version du tri-fusion en Python, en utilisant le « slicing » :

def tri_fusion_slice(tab):
    n = len(tab)
    if n > 1:
        mil = n // 2
        L = tab[:mil]
        R = tab[mil:]
        tri_fusion_slice(L)
        tri_fusion_slice(R)
        i = 0
        j = 0
        k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                tab[k] = L[i]
                i += 1
            else:
                tab[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            tab[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            tab[k] = R[j]
            j += 1
            k += 1

Activité 4

En vous basant sur la vidéo disponible à cette adresse, implémentez l’algorithme de tri rapide (Quicksort) en Python, un autre algorithme basé sur le principe « Diviser pour régner ».

Exercices

• Exercice 1 : Donnez la séquence des appels à la fonction de recherche dichotomique du cours pour les appels recherche_dichotomique([0,1,1,2,3,5,8,13,21], 13) et recherche_dichotomique([0,1,1,2,3,5,8,13,21], 12).
• Exercice 2 : Quelles sont les deux listes renvoyées par une fonction coupe() à laquelle on passe la liste [8, 1, 3, 0, 1, 2, 5] ? L’ordre relatif est-il préservé ? Est-ce important ?
• Exercice 3 : Réécrivez la fonction fusion en utilisant une boucle while au lieu de la récursivité.
• Exercice 4 : Le problème des Tours de Hanoï est un jeu célèbre impliquant trois tiges et des disques de tailles différentes. Écrivez une fonction hanoi(n) qui affiche la solution pour n disques.
• Exercice 5 : Combien de déplacements élémentaires faut-il au total pour déplacer N disques de la tour de départ à la tour d’arrivée dans le problème des Tours de Hanoï ?
• Exercice 6 : Réécrivez l’exercice 4 en utilisant des piles (voir chapitre 5).
• Exercice 7 : Écrivez une fonction qui effectue la rotation d’une image de 90 degrés en utilisant le principe « Diviser pour régner ».
• Exercice 8 : Appliquez le principe « Diviser pour régner » pour multiplier deux entiers en utilisant la méthode de Karatsuba.

corrections

Exercice 1

• Pour recherche_dichotomique([0,1,1,2,3,5,8,13,21], 13) :
  • recherche(t, 13, 0, 8)
  • recherche(t, 13, 5, 8)
  • recherche(t, 13, 7, 8)
  • À ce moment, l’index m est 7, où se trouve la valeur 13.
• Pour recherche_dichotomique([0,1,1,2,3,5,8,13,21], 12) :
  • recherche(t, 12, 0, 8)
  • recherche(t, 12, 5, 8)
  • recherche(t, 12, 7, 8)
  • recherche(t, 12, 7, 6)
  • À ce moment, l’indice de gauche g est supérieur à l’indice de droite d, et la recherche se termine avec le résultat None.

Exercice 2

Les deux listes renvoyées sont [5, 1, 3, 8] et [2, 0, 1]. L’ordre relatif des éléments est inversé, car la fonction ajoute les éléments au début des nouvelles listes. Cependant, ce n’est pas important pour le tri-fusion, car les deux listes sont triées avant d’être fusionnées, ce qui annule l’inversion initiale.

Exercice 3

def fusion(l1, l2):
    lst = None
    while l1 is not None or l2 is not None:
        if l1 is not None and (l2 is None or l1.valeur <= l2.valeur):
            lst, l1 = Cellule(l1.valeur, lst), l1.suivante
        else:
            lst, l2 = Cellule(l2.valeur, lst), l2.suivante

    # Puis on inverse la liste lst
    r = None
    while lst is not None:
        r, lst = Cellule(lst.valeur, r), lst.suivante
    return r

Exercice 4

def deplace(a, b, c, k):
    """Déplace k disques de la tour a vers la tour b, en se servant de la tour c comme intermédiaire"""
    if k > 0:
        deplace(a, c, b, k - 1)
        print("déplace de", a, "vers", b)
        deplace(c, b, a, k - 1)

def hanoi(n):
    deplace(1, 3, 2, n)

Exercice 5

Pour déplacer $N$ disques, il faut au total $2^N - 1$ déplacements élémentaires. La preuve se fait par récurrence :
* Pour $N=1$, il faut $2^1 - 1 = 1$ déplacement.
* Si l'on suppose qu'il faut $2^{N-1} - 1$ déplacements pour $N-1$ disques, alors pour $N$ disques, on aura :
    * $2^{N-1} - 1$ déplacements pour déplacer les $N-1$ premiers disques de la tour de départ à la tour intermédiaire.
    * 1 déplacement pour le plus grand disque de la tour de départ à la tour d'arrivée.
    * $2^{N-1} - 1$ déplacements pour déplacer les $N-1$ disques de la tour intermédiaire à la tour d'arrivée.
    * Total : $(2^{N-1} - 1) + 1 + (2^{N-1} - 1) = 2 \times 2^{N-1} - 1 = 2^N - 1$.

Exercice 6

def hanoi_piles(n):
    a = Pile()
    for i in range(n, 0, -1):
        a.empiler(i)
    
    deplace(a, Pile(), Pile(), n)

def deplace(a, b, c, k):
    """déplace k disques de la pile a vers la pile b, en se servant de la pile c comme intermédiaire"""
    if k > 0:
        deplace(a, c, b, k - 1)
        b.empiler(a.depiler())
        deplace(c, b, a, k - 1)

Exercice 7

def rotation_aux(px, x, y, t):
    '''on va faire la rotation de l'image située entre les pixels de coordonnées (x,y) et (x+t,y+t)'''
    if t == 1:
        return
    
    t //= 2
    rotation_aux(px, x, y, t)
    rotation_aux(px, x + t, y, t)
    rotation_aux(px, x, y + t, t)
    rotation_aux(px, x + t, y + t, t)

    for x1 in range(x, x + t):
        for y1 in range(y, y + t):
            px[x1, y1 + t]=px[x1, y1]  
            px[x1 + t, y1 + t]= px[x1, y1 + t]
            px[x1 + t, y1]=  px[x1 + t, y1 + t]
            px[x1, y1] =px[x1 + t, y1]

def rotation(px, taille):
    rotation_aux(px, 0, 0, taille)

Exercice 8

voici deux version du programme en Python. Il faudra copier l’une ou l’autre (car les noms de fonctions sont les mêmes dans les deux versions)

#en base 10
def taille(x):
    n = 1
    while x > 0:
        x //= 10
        n += 1
    return n

def karatsuba(x, y, n):
    """multiplie x et y par la méthode de Karatsuba"""
    if n <= 1:
        return x * y

    n //= 2
    a, b = x // 10**n, x % 10**n
    c, d = y // 10**n, y % 10**n

    ac = karatsuba(a, c, n)
    bd = karatsuba(b, d, n)
    abcd = karatsuba(a - b, c - d, n)

    return (ac * 10 ** (2 * n)) + ((ac + bd - abcd) * 10**n) + bd

def mult(x, y):
    n = max(taille(abs(x)), taille(abs(y)))
    return karatsuba(x, y, n)

print(mult(2457,6819))


# en base 2



def taille(x):
    n = 1
    while x > 0:
        x //= 2
        n += 1
    return n

def karatsuba(x, y, n):
    """multiplie x et y par la méthode de Karatsuba"""
    if n <= 1:
        return x * y
    
    n //= 2
    m = 1 << n
    a, b = x >> n, x % m
    c, d = y >> n, y % m
    
    ac = karatsuba(a, c, n)
    bd = karatsuba(b, d, n)
    abcd = karatsuba(a - b, c - d, n)
    
    return (ac << (2 * n)) + ((ac + bd - abcd) << n) + bd

def mult(x, y):
    n = max(taille(abs(x)), taille(abs(y)))
    return karatsuba(x, y, n)