Terminale

Algorithmique

Après avoir étudié les structures de données (arbres, graphes) dans le chapitre précédent, nous nous intéressons ici aux algorithmes qui les exploitent : parcourir un arbre ou un graphe, y rechercher une information, mais aussi deux grandes méthodes de conception d'algorithmes efficaces — diviser pour régner et programmation dynamique — et un algorithme incontournable de recherche textuelle, celui de Boyer-Moore.

Parcours et recherche dans les arbres binaires

Rappel : la classe `Noeud`

On reprend la représentation des arbres binaires vue dans le chapitre Structures de données : un arbre binaire est soit vide (None), soit un nœud portant une étiquette et deux sous-arbres.

class Noeud:
    def __init__(self, etiquette, gauche=None, droite=None):
        self.etiquette = etiquette
        self.gauche = gauche
        self.droite = droite

Ce chapitre complète les algorithmes déjà rencontrés (calcul de la taille, de la hauteur, parcours préfixe/infixe/postfixe) par le parcours en largeur et par la recherche dans un arbre binaire de recherche.

Parcours en largeur (BFS)

Le parcours en largeur (Breadth-First Search) visite les nœuds niveau par niveau, de la racine vers les feuilles, de gauche à droite. Contrairement aux parcours en profondeur (récursifs, qui utilisent implicitement une pile d'appels), le parcours en largeur utilise explicitement une file : on y dépose les sous-arbres restant à visiter, dans l'ordre où on les découvre.

from collections import deque
 
def parcours_largeur(arbre):
    """Renvoie la liste des etiquettes d'un arbre binaire, parcouru en largeur"""
    if arbre is None:
        return []
    resultat = []
    file = deque([arbre])          # file d'attente des sous-arbres a visiter
    while file:
        noeud = file.popleft()     # on defile le sous-arbre le plus ancien
        resultat.append(noeud.etiquette)
        if noeud.gauche is not None:
            file.append(noeud.gauche)
        if noeud.droite is not None:
            file.append(noeud.droite)
    return resultat

Sur l'arbre T(Y(P,·),O(H,N)) du chapitre précédent, le parcours en largeur donne T, Y, O, P, H, N (la racine, puis ses deux fils, puis les petits-enfants).

Arbres binaires de recherche (ABR)

Un arbre binaire de recherche (ABR) est un arbre binaire étiqueté par des clés, tel que pour chaque nœud :

toutes les clés de son sous-arbre gauche sont inférieures ou égales à la sienne ;
toutes les clés de son sous-arbre droit sont strictement supérieures à la sienne ;
ses deux sous-arbres sont eux-mêmes des arbres binaires de recherche.

Cette propriété (invariant) permet de rechercher ou d'insérer une clé sans avoir à examiner tout l'arbre : à chaque nœud, on sait immédiatement dans quel sous-arbre continuer.

Rechercher une clé

def recherche(arbre, cle):
    """Renvoie True si cle est presente dans l'ABR arbre, False sinon"""
    if arbre is None:
        return False
    if cle == arbre.etiquette:
        return True
    if cle < arbre.etiquette:
        return recherche(arbre.gauche, cle)
    return recherche(arbre.droite, cle)

Insérer une clé

Insérer une clé revient à descendre dans l'arbre comme pour une recherche, jusqu'à trouver l'emplacement (vide) où l'insérer, en respectant l'invariant.

def insere(arbre, cle):
    """Renvoie l'ABR obtenu en inserant cle dans l'ABR arbre"""
    if arbre is None:
        return Noeud(cle)
    if cle <= arbre.etiquette:
        arbre.gauche = insere(arbre.gauche, cle)
    else:
        arbre.droite = insere(arbre.droite, cle)
    return arbre

Complexité

Ces deux opérations descendent d'un niveau à chaque étape : leur coût est donc proportionnel à la hauteur $h$ de l'arbre, soit $O(h)$ . Si l'arbre est équilibré, $h \approx \log_2(n)$ pour $n$ nœuds, et la recherche est très rapide (temps logarithmique). Mais un ABR construit en insérant des clés déjà triées dégénère en un « peigne » de hauteur $n-1$ : la recherche redevient alors linéaire, $O(n)$ .

Exercice — Construire et interroger un arbre binaire de recherche

On insère successivement, dans un ABR initialement vide, les clés 8, 3, 10, 1, 6, 14, 4 (dans cet ordre), à l'aide de la fonction insere du cours.

Représenter l'arbre obtenu (on ne demande pas de code, juste le schéma).
Donner le résultat du parcours infixe de cet arbre. Que remarque-t-on ?
En utilisant la fonction recherche du cours, combien de comparaisons faut-il pour savoir que la clé 5 est absente de l'arbre ?

Exercice — Bac NSI — Métropole 2022 (exercice 4)

Exercice tiré du bac NSI Métropole 2022 (Jour 1), sur le parcours des arbres binaires, le principe « diviser pour régner » et la récursivité.

Arbre : racine 3, fils gauche 6 (feuilles 7 et 4), fils droit 2 (feuilles 9 et 1).

Partie A.

1. Donner la somme de l'arbre (justifier le calcul). 2. Associer chaque terme à sa position sur le schéma : « racine », « nœud », « feuille », « SAG », « SAD ». 3. Un seul parcours ci-dessous est un parcours en largeur d'abord : lequel ? A. 7-6-4-3-9-2-1 B. 3-6-7-4-2-9-1 C. 3-6-2-7-4-9-1 D. 7-4-6-9-1-2-3 4. Écrire somme(liste), renvoyant la somme des éléments d'une liste de nombres. 5. parcourir(arbre) enfile la racine dans une file, puis répète : défiler un sous-arbre S, ajouter sa valeur à une liste L, enfiler chaque sous-arbre non vide de S. Quel type de parcours obtient-on ?

Partie B.

6. « Diviser pour régner » signifie : A. diviser une fonction en deux fonctions plus petites. B. utiliser plusieurs modules. C. séparer les informations selon leur type. D. diviser un problème en deux problèmes plus petits et indépendants. Laquelle est correcte ? 7. Donner l'égalité liant la somme de l'arbre à celle de ses sous-arbres et à la valeur de la racine. 8. Écrire calcul_somme(arbre) récursive, avec est_vide, valeur_racine, arbre_gauche, arbre_droit.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 23, exercice 1 : insérer dans un arbre binaire de recherche représenté par des triplets

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°23, exercice 1.

Dans cet exercice, on considère des arbres binaires de recherche qui sont :

soit l'arbre vide identifié par None ;
soit un nœud, contenant une clé et deux sous-arbres gauche et droit et représenté par un triplet (g, v, d) où g et d sont les sous-arbres gauche et droit et v la clé.

L'arbre binaire de recherche abr1

Ainsi, l'arbre binaire de recherche abr1 ci-dessus est créé par le code Python ci-dessous :

n0 = (None, 0, None)
n3 = (None, 3, None)
n2 = (None, 2, n3)
abr1 = (n0, 1, n2)

Écrire une fonction récursive insertion_abr(a, cle) qui prend en paramètres une clé cle et un arbre binaire de recherche a, et qui renvoie un arbre binaire de recherche dans lequel cle a été insérée.

Dans le cas où cle est déjà présente dans a, la fonction renvoie l'arbre a inchangé.

Résultats à obtenir :

>>> insertion_abr(abr1, 4)
((None,0,None),1,(None,2,(None,3,(None,4,None))))
>>> insertion_abr(abr1, -5)
(((None,-5,None),0,None),1,(None,2,(None,3,None)))
>>> insertion_abr(abr1, 2)
((None,0,None),1,(None,2,(None,3,None)))

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 24, exercice 1 : parcours en largeur d'un arbre binaire

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°24, exercice 1.

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud représenté par un triplet (g, x, d) où x est l'étiquette du nœud et g et d sont les sous-arbres gauche et droit.

On souhaite écrire une fonction parcours_largeur qui prend en paramètre un arbre binaire et qui renvoie la liste des étiquettes des nœuds de l'arbre parcourus en largeur.

Exemples :

>>> arbre = ( ( (None, 1, None), 2, (None, 3, None) ),
              4,
              ( (None, 5, None), 6, (None, 7, None) ) )
>>> parcours_largeur(arbre)
[4, 2, 6, 1, 3, 5, 7]

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 44, exercice 2 : insérer dans un arbre binaire de recherche

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°44, exercice 2.

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance de la classe Noeud donnée ci-dessous.

class Noeud:
    """Classe représentant un noeud d'un arbre binaire"""
    def __init__(self, etiquette, gauche, droit):
        """Crée un noeud de valeur etiquette avec
        gauche et droit comme fils."""
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit
 
def parcours(arbre, liste):
    """parcours récursivement l'arbre en ajoutant les étiquettes
    de ses noeuds à la liste passée en argument en ordre infixe."""
    if arbre != None:
        parcours(arbre.gauche, liste)
        liste.append(arbre.etiquette)
        parcours(arbre.droit, liste)
    return liste

La fonction récursive parcours renvoie la liste des étiquettes des nœuds de l'arbre implémenté par l'instance arbre dans l'ordre du parcours en profondeur infixe à partir d'une liste vide passée en argument.

Compléter le code de la fonction insere, présenté ci-dessous, qui prend en argument un arbre binaire de recherche arbre représenté ainsi et une étiquette cle, non présente dans l'arbre, et qui :

renvoie une nouvelle feuille d'étiquette cle s'il est vide ;
renvoie l'arbre après l'avoir modifié en insérant cle sinon ;
garantit que l'arbre ainsi complété soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement des nœuds d'étiquette 1, 4, 6 et 8 dans l'arbre binaire de recherche représenté ci-dessous :

Arbre binaire de recherche de départ

def insere(arbre, cle):
    """insere la cle dans l'arbre binaire de recherche
    représenté par arbre.
    Retourne l'arbre modifié."""
    if arbre == None:
        return Noeud(cle, None, None) # creation d'une feuille
    else:
        if ...:
            arbre.gauche = insere(arbre.gauche, cle)
        else:
            arbre.droit = ...
        return arbre

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

QCM — Parcours en largeur et ABR

1. Quelle structure de données est utilisée pour réaliser un parcours en largeur d'un arbre binaire ?

2. Dans un arbre binaire de recherche, où se trouvent les clés strictement supérieures à celle d'un nœud donné ?

3. En insérant, dans l'ordre croissant, les clés 1, 2, 3, 4 et 5 dans un arbre binaire de recherche initialement vide, à l'aide de l'algorithme d'insertion du cours, quelles sont la hauteur de l'arbre obtenu et la complexité d'une recherche dans cet arbre ?

Parcours de graphes : profondeur, largeur et détection de cycle

On représente un graphe par sa liste de successeurs, comme dans le chapitre Structures de données : successeurs[i] est la liste des sommets reliés au sommet i.

Parcours en profondeur (DFS) à l'aide d'une pile

def parcours_profondeur(successeurs, depart):
    """Renvoie l'ordre de visite des sommets, parcours en profondeur depuis depart"""
    n = len(successeurs)
    vus = [False] * n
    pile = [depart]
    parcours = []
    while pile:
        sommet = pile.pop()          # on depile le dernier sommet ajoute
        if not vus[sommet]:
            vus[sommet] = True
            parcours.append(sommet)
            for voisin in successeurs[sommet]:
                if not vus[voisin]:
                    pile.append(voisin)
    return parcours

Pour suivre cette exploration pas à pas — y compris sur un graphe qui contient un cycle, comme ceux étudiés plus bas dans cette notion — voici une visualisation d'un parcours en profondeur :

Parcours en profondeur (DFS) d'un graphe

Parcours en profondeur (DFS) depuis « M »

Cliquez sur « Suivant » pour commencer le parcours.

0/5

Parcours en largeur (BFS) à l'aide d'une file

from collections import deque
 
def parcours_largeur(successeurs, depart):
    """Renvoie l'ordre de visite des sommets, parcours en largeur depuis depart"""
    n = len(successeurs)
    vus = [False] * n
    vus[depart] = True
    file = deque([depart])
    parcours = [depart]
    while file:
        sommet = file.popleft()
        for voisin in successeurs[sommet]:
            if not vus[voisin]:
                vus[voisin] = True
                parcours.append(voisin)
                file.append(voisin)
    return parcours

Ces deux parcours permettent de trouver la composante connexe d'un sommet (l'ensemble des sommets qu'il est possible d'atteindre). Le parcours en largeur, de plus, trouve les plus courts chemins (en nombre d'arêtes) depuis le sommet de départ : c'est l'algorithme de base pour trouver la sortie d'un labyrinthe ou le plus court chemin dans un réseau non pondéré.

Rechercher un chemin entre deux sommets

Pour savoir s'il existe un chemin entre deux sommets depart et arrivee, il suffit de vérifier si arrivee apparaît dans le parcours (profondeur ou largeur) depuis depart :

def chemin_existe(successeurs, depart, arrivee):
    """Renvoie True s'il existe un chemin de depart vers arrivee"""
    return arrivee in parcours_profondeur(successeurs, depart)

Détecter un cycle

Un cycle est une suite d'arêtes qui part d'un sommet et y revient sans repasser deux fois par la même arête. Pour un graphe non orienté, on adapte le parcours en profondeur : en explorant les voisins d'un sommet, si l'on retombe sur un sommet déjà vu qui n'est pas le père direct dans le parcours, c'est qu'il existe un cycle.

def contient_cycle(successeurs):
    """Renvoie True si le graphe non oriente possede un cycle"""
    n = len(successeurs)
    vus = [False] * n
 
    def explore(sommet, pere):
        vus[sommet] = True
        for voisin in successeurs[sommet]:
            if not vus[voisin]:
                if explore(voisin, sommet):
                    return True
            elif voisin != pere:
                return True          # sommet deja vu, autre que le pere : cycle
        return False
 
    for depart in range(n):
        if not vus[depart]:
            if explore(depart, -1):
                return True
    return False

On parcourt tous les sommets (et pas seulement depuis un sommet fixé) pour couvrir aussi les graphes non connexes, qui peuvent avoir un cycle dans l'une de leurs composantes seulement.

Exercice — Parcours et détection de cycle dans un graphe

On considère le graphe non orienté à 4 sommets (numérotés 0 à 3) donné par sa liste de successeurs successeurs = [[1, 2], [0, 3], [0, 3], [1, 2]] (arêtes 0-1, 0-2, 1-3, 2-3).

Donner le résultat de parcours_profondeur(successeurs, 0) (on empilera les voisins dans l'ordre où ils apparaissent dans la liste successeurs).
Ce graphe contient-il un cycle ? Justifier en citant les arêtes concernées.
Vérifier votre réponse à l'aide de la fonction contient_cycle du cours.

Exercice — Bac NSI — Sujet 0.A 2024 (exercice 3)

Exercice tiré du sujet zéro 0.A du bac NSI (2024), sur les graphes, la recherche d'itinéraires et les bases de données.

Carte fictive de 7 villes A-G, graphe pondéré G1 : A-B(4km), A-E(4km), B-F(7km), B-G(5km), C-E(8km), C-D(4km), D-E(6km), D-F(8km), F-G(3km).

1. Déterminer le plus court chemin (en distance) entre A et D.

2. Donner la matrice d'adjacence pondérée de G1 (ordre alphabétique).

On travaille ensuite sur un graphe non pondéré G2 (9 villes A-I) : A-B, A-C, A-H, B-I, C-E, C-D, G-E, G-F, H-G, H-I, I-F.

3. Proposer une implémentation de G2 par un dictionnaire Python, et un parcours en largeur depuis A.

On veut les itinéraires traversant le moins de villes possible :

tab_itineraires = []
 
def cherche_itineraires(G, start, end, chaine=[]):
    chaine = chaine + [start]
    if start == end:
        return chaine
    for u in G[start]:
        if u not in chaine:
            nchemin = cherche_itineraires(G, u, end, chaine)
            if len(nchemin) != 0:
                tab_itineraires.append(nchemin)
    return []
 
def itineraires_court(G, dep, arr):
    cherche_itineraires(G, dep, arr)
    tab_court = ...
    mini = float('inf')
    for v in tab_itineraires:
        if len(v) <= ... :
            mini = ...
    for v in tab_itineraires:
        if len(v) == mini:
            tab_court.append(...)
    return tab_court

Exemple : itineraires_court(G2,'A','F') renvoie [['A','B','I','F'],['A','H','G','F'],['A','H','I','F']].

4. Pourquoi cherche_itineraires est-elle récursive ? Quel est son rôle ? Compléter itineraires_court.

5. En appelant itineraires_court(G2,'A','E') puis, sans relancer le programme, itineraires_court(G2,'A','F'), on obtient deux fois [['A','C','E']] — un bug. Expliquer.

6. Requêtes SQL sur les tables ville(id,nom,num_dep,nombre_hab,superficie) et sport(id,nom,type,note,id_ville) : lister les noms des piscines de la table sport ; mettre à jour la note de « Ballons perdus » (de 6 à 7) ; lister les noms des murs d'escalade disponibles à Annecy (jointure).

Exercice — Bac NSI — Amérique du Nord 2024 J1 (exercice 2)

Exercice tiré du bac NSI Amérique du Nord 2024 (jour 1), sur les graphes et le parcours en profondeur : un réseau d'amis.

Groupe de 8 personnes (Anas, Emma, Gabriel, Jade, Lou, Milo, Nina, Yanis), avec les amitiés : Gabriel-Jade, Gabriel-Yanis, Gabriel-Nina, Gabriel-Milo ; Jade-Yanis, Jade-Emma, Jade-Lou ; Yanis-Emma, Yanis-Nina, Yanis-Milo, Yanis-Anas ; Emma-Nina ; Milo-Anas.

Partie A. 1. Représenter ce graphe. 2. Compléter la matrice d'adjacence (sommets dans l'ordre G, J, Y, E, N, M, A, L), la première ligne (G) étant donnée : [0, 1, 1, 0, 1, 1, 0, 0]. 3. Avec sommets = ['G','J','Y','E','N','M','A','L'] et une fonction position(l, s) renvoyant la position de s (ou None), donner les retours de position(sommets, 'G') et position(sommets, 'Z'). 4. Compléter nb_amis(L, m, s), qui utilise position puis la matrice m pour compter les amis de s (None si absent). 5. Donner le retour de nb_amis(sommets, matrice_adj, 'G').

Partie B. 6. Dans un dictionnaire {c: v}, que représentent c et v ? 7. Compléter le dictionnaire de listes d'adjacence graphe du groupe d'amis. 8. Écrire nb_amis(d, s) (version dictionnaire) ; exemple : nb_amis(graphe, 'L') renvoie 1.

Milo se fâche avec Gabriel et Yanis, Anas avec Yanis, et Gabriel avec Yanis : nouveau dictionnaire graphe = {'G': ['J','N'], 'J': ['G','Y','E','L'], 'Y': ['J','E','N'], 'E': ['J','Y','N'], 'N': ['G','Y','E'], 'M': ['A'], 'A': ['M'], 'L': ['J']}.

Le « cercle d'amis » de Nom est l'ensemble des personnes atteignables depuis Nom par parcours en profondeur. Donner le cercle d'amis de Lou.
Compléter le code de parcours_en_profondeur(d, s, visites=[]), qui ajoute s à visites, parcourt récursivement chaque voisin non visité, et renvoie visites :

def parcours_en_profondeur(d, s, visites=[]):
    ...
    for v in d[s]:
        ...
        parcours_en_profondeur(d, v)
    ...

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — Amérique du Nord 2025 (exercice 3, partie graphes)

Exercice 3 (8 points, partie graphes) du sujet de bac NSI Amérique du Nord 2025, jour 1.

Afin de faciliter les préparations de sorties, une association d'enfants construit le graphe non orienté des mésententes : un dictionnaire (sommet → liste des voisins). Exemple, le graphe g1 :

g1 = {'Elise': ['Octavie', 'Virgile'],
      'Octavie': ['Elise', 'Pierre', 'Virgile'],
      'Pierre': ['Octavie', 'Raphael'],
      'Raphael': ['Pierre', 'Virgile'],
      'Sixtine': [],
      'Virgile': ['Elise', 'Octavie', 'Raphael']}

Expliquer pourquoi cette situation ne nécessite qu'un graphe non orienté.
Décrire le graphe g2 suivant (sommets et arêtes) :

g2 = {'Adrien': ['Elisabeth', 'Lea'],
      'Elisabeth': ['Adrien', 'Ian', 'Luca'],
      'Ian': ['Elisabeth', 'Joseph', 'Luca'],
      'Joseph': ['Ian'],
      'Lea': ['Adrien'],
      'Luca': ['Elisabeth', 'Ian']}

Écrire une fonction degre(g, s) qui renvoie le degré du sommet s dans le graphe g.
Recopier et compléter les lignes 7 à 10 de sommets_tries, qui renvoie les sommets de g triés par degré décroissant :

def sommets_tries(g):
    sommets = [sommet for sommet in g]
    n = len(sommets)
    for i in range(1, n):
        sommet_courant = sommets[i]
        j = i - 1
        while ... and ...:
            sommets[...] = sommets[...]
            j = j - 1
        ...
    return sommets

Préciser le tri utilisé, et son coût dans le pire des cas selon le nombre n de sommets (degre supposée de coût constant).

Pour former des groupes, on colore le graphe (deux sommets reliés par une arête n'ont jamais la même couleur). Les couleurs sont des entiers ≥ 0 ; −1 signifie « pas de couleur ».

Recopier et colorer g1 en n'utilisant que 3 couleurs (0, 1 et 2).

On dispose de :

def couleurs_voisins(g, dc, s):
    return [dc[v] for v in g[s]]
 
def plus_petite_couleur_hors_voisins(g, dc, s):
    couleur = 0
    n = len(g)
    cvoisins = couleurs_voisins(g, dc, s)
    while couleur < n:
        if couleur not in cvoisins:
            return couleur
        couleur = couleur + 1
    return couleur

Recopier et compléter colorer_graphe, qui colore g dans l'ordre des clés de dc (dont les valeurs sont toutes à −1 en pré-condition) :

def colorer_graphe(g, dc):
    for s in dc:
        couleur = ...
        ... = couleur

L'algorithme de Welsh-Powell colore les sommets par degré décroissant. Recopier et compléter :

def welsh_powell(g):
    dc = ...
    for ...
        ...
        ...
    return dc

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — 25-NSIPE2 (exercice 3, partie parcours)

Exercice 3 (8 points, partie parcours de graphe) du sujet de bac NSI 25-NSIPE2, session 2025.

Pour automatiser la création de balades (chemins du parc d'attractions) sans répétition, on propose un parcours de graphe à partir d'une attraction, avec un tableau représentant la balade en construction :

def parcours(attr, deja_vues, balade, nb):
    if not attr.nom in deja_vues:
        deja_vues[attr.nom] = True
        if nb == 0 or sont_voisines(attr, balade[nb-1]):
            balade[nb] = attr
            nb = nb + 1
        for voisine in attr.voisines:
            nb = parcours(voisine[0], deja_vues, balade, nb)
    return nb

On utilise les 4 attractions du parc (a1=Grand huit, a2=Petits chevaux, a3=Train fantôme, a4=Grande roue), avec a1.voisines=[(a2,7),(a3,5)], a2.voisines=[(a1,7),(a3,3),(a4,4)], a3.voisines=[(a1,5),(a2,3),(a4,6)], a4.voisines=[(a2,4),(a3,6)].

Donner le type de parcours effectué par parcours.
Déterminer le contenu de balade (initialisé à [None, None, None, None]) après parcours(a4, {}, balade, 0).
On modifie a2.voisines = [(a1,7), (a3,3)] et a4.voisines = [(a3,6)]. Déterminer le contenu de tableau (initialisé à [None, None, None, None]) après parcours(a3, {}, tableau, 0).
Déduire des appels précédents le nom de la structure de données utilisée pour deja_vues, et expliquer son rôle en une phrase.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — Centres étrangers 2024 J1 (exercice 1)

Exercice 1 (6 points) du sujet de bac NSI Centres étrangers (groupe 1) 2024, jour 1 — voir aussi l'annale complète.

On lutte contre un virus informatique qui se propage en migrant régulièrement vers un autre ordinateur, en choisissant au hasard sa nouvelle cible parmi les ordinateurs accessibles. On veut savoir quels ordinateurs protéger pour lutter le plus efficacement possible avec des ressources limitées.

Le réseau comprend 5 ordinateurs numérotés 0 à 4, avec les liaisons suivantes : 0 est relié à 1, 2, 3 et 4 ; 1 est de plus relié à 2 et à 3.

On représente ce réseau par un graphe stocké sous forme de listes de voisins. Compléter :

voisins = [[1, 2, 3, 4],
           [0, 2, 3],
           [0, 1],
           [...],
           [...]]

On ajoute un sixième ordinateur, numéroté 5, accessible seulement depuis les ordinateurs 0 et 2.

Décrire le nouveau graphe.
Donner la nouvelle définition de voisins.
Compléter voisin_alea(voisins, s), qui renvoie un voisin de s choisi aléatoirement (on pourra utiliser random.randrange(n), qui renvoie un entier aléatoire entre 0 inclus et n exclu) :

def voisin_alea(voisins, s):
    return ...

On donne :

def marche_alea(voisins, i, n):
    if n == 0:
        return i
    return marche_alea(voisins, voisin_alea(voisins, i), n-1)

Justifier que marche_alea est une fonction récursive.
Décrire ce que modélise cette fonction, en rapport avec le contexte de l'exercice.
Compléter simule, qui simule n_tests fois le déplacement d'un virus pendant n_pas étapes, démarrant au sommet i, et qui renvoie une liste contenant en position j le nombre de fois que le virus a terminé son parcours au sommet j, divisé par n_tests :

def simule(voisins, i, n_tests, n_pas):
    results = [0] * len(voisins)
    ...
    return ...

L'appel simule(voisins, 4, 1000, 1000) (sur le réseau à 6 ordinateurs) renvoie [0.328, 0.195, 0.18, 0.12, 0.059, 0.118]. Déduire de ce résultat l'ordinateur du réseau le plus rentable à protéger.

Au début, le virus n'est présent que sur un ordinateur. À chaque étape, il contamine tous ses voisins non déjà contaminés. On cherche le temps que met le virus à se propager à tout le réseau.

Un graphe voisins représente un réseau, et s un sommet de départ. Proposer un algorithme pour déterminer le temps, en étapes, que met un virus à se propager dans l'intégralité d'un réseau.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 21, exercice 2 : sommets accessibles par un parcours en profondeur

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°21, exercice 2.

Dans cet exercice, on considère un graphe non orienté représenté sous forme de listes d'adjacence. On suppose que les sommets sont numérotés de 0 à n-1.

Ainsi, le graphe suivant :

Graphe non orienté à 6 sommets

sera représenté par la liste d'adjacence suivante :

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

On souhaite déterminer les sommets accessibles depuis un sommet donné dans le graphe. Pour cela, on va procéder à un parcours en profondeur du graphe.

Compléter la fonction suivante.

def parcours(adj, x, acc):
    '''Réalise un parcours en profondeur récursif
    du graphe donné par les listes d'adjacence adj
    depuis le sommet x en accumulant les sommets
    rencontrés dans acc'''
    if x ...:
        acc.append(x)
        for y in ...:
            parcours(adj, ...)
 
def accessibles(adj, x):
    '''Renvoie la liste des sommets accessibles dans le
    graphe donné par les listes d'adjacence adj depuis
    le sommet x.'''
    acc = []
    parcours(adj, ...)
    return acc

Exemples :

>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0)
[0, 1, 2, 3]
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4)
[4, 5]

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

QCM — Parcours de graphes et cycles

1. Quelle structure permet de trouver, dans un graphe non pondéré, le plus court chemin (en nombre d'arêtes) entre deux sommets ?

2. Lors d'un parcours en profondeur d'un graphe non orienté, que signifie retomber sur un sommet déjà visité qui n'est pas le père direct ?

3. On exécute contient_cycle(successeurs) avec successeurs = [[1, 2], [0, 2], [0, 1]] (un graphe non orienté à 3 sommets, chacun relié aux deux autres). Que renvoie cet appel ?

Diviser pour régner et programmation dynamique

Le principe « diviser pour régner »

Le paradigme diviser pour régner (divide and conquer) consiste à résoudre un problème de taille $n$ en le décomposant en un ou plusieurs sous-problèmes indépendants, de taille plus petite (souvent $n/2$ ), qu'on résout récursivement, avant de combiner leurs résultats.

Exemple : l'exponentiation rapide. Calculer $a^n$ naïvement par $a^n = a \times a^{n-1}$ demande $n$ multiplications. On peut faire beaucoup mieux :

$a^0 = 1$ ;
si $n$ est pair, $a^n = (a \times a)^{n/2}$ ;
sinon, $a^n = a \times (a \times a)^{(n-1)/2}$ .

def puissance_rapide(a, n):
    """Calcule a**n en O(log n) multiplications"""
    if n == 0:
        return 1
    if n % 2 == 0:
        return puissance_rapide(a * a, n // 2)
    return a * puissance_rapide(a * a, (n - 1) // 2)

La taille du problème étant divisée par deux à chaque appel, la complexité est en $\Theta(\log_2 n)$ multiplications, contre $\Theta(n)$ pour la méthode naïve.

Le tri fusion

Le tri fusion (merge sort) est l'exemple emblématique de « diviser pour régner » appliqué au tri :

si la liste a au plus un élément, elle est déjà triée ;
sinon, on la coupe en deux moitiés de même taille (à un élément près), on trie récursivement chaque moitié, puis on interclasse les deux listes triées obtenues.

def interclassement(lst1, lst2):
    """Fusionne deux listes deja triees en une seule liste triee"""
    resultat = []
    i1, i2 = 0, 0
    while i1 < len(lst1) and i2 < len(lst2):
        if lst1[i1] <= lst2[i2]:
            resultat.append(lst1[i1])
            i1 += 1
        else:
            resultat.append(lst2[i2])
            i2 += 1
    return resultat + lst1[i1:] + lst2[i2:]
 
def tri_fusion(lst):
    """Trie la liste lst par la methode diviser pour regner"""
    if len(lst) <= 1:
        return lst
    m = len(lst) // 2
    return interclassement(tri_fusion(lst[:m]), tri_fusion(lst[m:]))

À chaque niveau de récursion, le travail d'interclassement est en $\Theta(n)$ , et il y a $\Theta(\log n)$ niveaux : la complexité totale du tri fusion est donc $\Theta(n \log n)$ , bien meilleure que les tris élémentaires (par sélection ou insertion), en $\Theta(n^2)$ .

De la récursivité à la programmation dynamique

Dans « diviser pour régner », les sous-problèmes sont indépendants. Mais il arrive que des sous-problèmes se recoupent : les résoudre plusieurs fois est alors du temps perdu. C'est le cas de la suite de Fibonacci, calculée naïvement :

def fibo(n):
    if n <= 1:
        return n
    return fibo(n - 1) + fibo(n - 2)

L'appel fibo(5) recalcule fibo(3) deux fois, fibo(2) trois fois... Le nombre d'appels croît de façon exponentielle avec $n$ .

La programmation dynamique résout ce problème en mémorisant (mémoïsation) le résultat de chaque sous-problème déjà résolu, pour ne jamais le recalculer.

Approche « haut vers bas » (mémoïsation)

Python fournit un décorateur tout prêt, lru_cache, qui mémoïse automatiquement une fonction :

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fibo_memo(n):
    if n <= 1:
        return n
    return fibo_memo(n - 1) + fibo_memo(n - 2)

Approche « bas vers haut » (itérative)

On peut aussi partir des plus petits sous-problèmes et remonter progressivement, en stockant les résultats dans un tableau :

def fibo_iteratif(n):
    """Calcule le n-ieme terme de Fibonacci, en temps lineaire"""
    valeurs = [0] * (n + 1)
    if n >= 1:
        valeurs[1] = 1
    for i in range(2, n + 1):
        valeurs[i] = valeurs[i - 1] + valeurs[i - 2]
    return valeurs[n]

Les deux approches ramènent la complexité de $\Theta(2^n)$ (version naïve) à $\Theta(n)$ : c'est l'apport essentiel de la programmation dynamique par rapport à une simple récursivité « diviser pour régner ».

Exercice — Programmation dynamique : compter les façons de monter un escalier

On dispose d'un escalier de $n$ marches. À chaque pas, on peut monter 1 ou 2 marches. On note $f(n)$ le nombre de façons différentes d'atteindre le sommet.

Justifier que $f(n) = f(n-1) + f(n-2)$ pour $n \geqslant 2$ , avec $f(0) = 1$ et $f(1) = 1$ .
Écrire une fonction récursive naïve facons(n) calculant $f(n)$ . Pourquoi est-elle inefficace pour de grandes valeurs de $n$ ?
Écrire une version facons_dp(n), efficace, utilisant la programmation dynamique (méthode itérative). Donner sa complexité.

Exercice — Bac NSI — Sujet zéro 2021 (exercice 2)

Exercice tiré du sujet zéro officiel du bac NSI (2021), sur la recherche du chemin de somme maximale dans un tableau (programmation dynamique).

Un chemin va de (0,0) à (n-1,p-1) en se déplaçant seulement vers la droite ou vers le bas ; sa somme est celle des valeurs traversées. Avec T = [[4,1,1,3],[2,0,2,1],[3,1,5,1]], un chemin possible est (0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(2,3), de somme 14.

1. Un chemin de (0,0) à (2,3) comprend 3 déplacements vers la droite. Combien vers le bas ? En déduire que tout tel chemin a 6 cases.

2. En énumérant les chemins de (0,0) à (2,3), trouver celui de somme maximale et sa valeur.

3. On pose T'[i][j] = somme maximale d'un chemin de (0,0) à (i,j). Justifier que, pour j ≠ 0, T'[0][j] = T[0][j] + T'[0][j-1], et compléter T' = [[4,5,6,?],[6,?,8,10],[9,10,?,16]].

4. Justifier que, pour i,j ≠ 0, T'[i][j] = T[i][j] + max(T'[i-1][j], T'[i][j-1]).

5. Écrire la fonction récursive somme_max(T, i, j) implémentant cette relation (en précisant le cas de base), et donner l'appel qui résout le problème complet.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — Sujet 0.B 2024 (exercice 1)

Exercice tiré du sujet zéro 0.B du bac NSI (2024), sur les listes, la récursivité et la programmation dynamique (pyramide de forage).

Une pyramide d'entiers (score de confiance) est représentée par une liste de niveaux, ex. ex2 = [[3],[1,2],[4,5,9],[3,6,2,1]]. Un conduit descend du sommet au dernier niveau (gauche ou droite à chaque étape) ; son score est la somme des valeurs traversées.

1. Déterminer un conduit de score maximal dans ex2, et son score.

2. Combien existe-t-il de conduits possibles dans une pyramide à n niveaux (codage binaire gauche/droite) ? Pourquoi tester tous les conduits n'est-il pas raisonnable ?

On pose score_max(i,j,p) = score maximal d'un conduit partant du nombre d'indice j du niveau i : cas de base score_max(len(p)-1,j,p)=p[len(p)-1][j] ; sinon score_max(i,j,p) = p[i][j] + max(score_max(i+1,j,p), score_max(i+1,j+1,p)).

3. Écrire la fonction récursive score_max.

4. Écrire pyramide_nulle(n) (pyramide à n niveaux remplie de 0), puis compléter prog_dyn(p) qui calcule le score maximal en remplissant une pyramide auxiliaire du bas vers le haut.

5. Montrer que le coût de prog_dyn est quadratique en n. Expliquer comment adapter score_max (en restant récursive) pour obtenir le même coût.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — Session 2021 (exercice 4)

Exercice tiré d'un bac NSI de la session 2021 (centre d'examen non confirmé), sur le tri fusion (diviser pour régner).

1. a) Ordre de grandeur du coût (en comparaisons) du tri fusion sur une liste de longueur n. b) Citer un autre algorithme de tri, son ordre de grandeur, et le comparer au tri fusion.

def tri_fusion(L):
    n = len(L)
    if n <= 1:
        return L
    print(L)
    mg = moitie_gauche(L)
    md = moitie_droite(L)
    L1 = tri_fusion(mg)
    L2 = tri_fusion(md)
    return fusion(L1, L2)

(moitie_gauche/moitie_droite renvoient les éléments d'indice < len(L)//2, resp. >= len(L)//2 ; fusion fusionne deux listes triées.)

2. Donner la liste des affichages produits par tri_fusion([7, 4, 2, 1, 8, 5, 6, 3]).

3. Écrire moitie_droite.

4. Compléter la fonction fusion(L1, L2) (squelette avec i1, i2, n1, n2 déjà en place, ainsi que les deux cas où un indice sort de sa liste) pour qu'elle insère les éléments de L1 et L2 dans L, dans l'ordre croissant.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — Amérique du Nord 2024 J2 (exercice 1)

Exercice tiré du bac NSI Amérique du Nord 2024 (jour 2), sur un algorithme de tri récursif inhabituel : le tri de Stooge.

Pour trier les indices i à j (i<j) d'un tableau tab : si tab[i] et tab[j] sont mal placés, on les échange ; puis, s'il y a au moins 3 éléments entre i et j (avec k = (j-i+1)//3), on trie récursivement les deux premiers tiers [i, j-k], puis les deux derniers tiers [i+k, j], puis à nouveau les deux premiers tiers [i, j-k].

1. Écrire echange(tab, i, j) (échange sur place, ne renvoie rien).

2. Compléter les 3 appels récursifs de triStooge(tab, i, j).

3. Cet algorithme est-il itératif ou récursif ? Justifier.

Soit triStooge(A, 0, 5) avec A = [5, 6, 4, 2, 3, 1].

4. Valeur de k lors de ce premier appel, en justifiant.

5. Sachant que l'arbre des appels a 3 niveaux de profondeur, que chaque nœud d'un niveau donne naissance à 3 appels tant que l'intervalle contient plus de 2 éléments, et qu'à ce niveau de profondeur tous les intervalles atteignent le cas de base, dénombrer le nombre total d'appels récursifs (hors appel initial).

6. Le second des 3 sous-appels du premier niveau est triStooge(A,2,5). Déterminer ses 3 sous-appels.

7. Avec A = [5, 4, 6, 2], tracer précisément l'exécution de triStooge(A,0,3) (échange initial puis 3 appels imbriqués), en donnant l'état de A avant et après chaque étape.

8. Le coût en pire cas du tri de Stooge est de l'ordre de n^e, e environ 8/3. Donner un algorithme de tri strictement meilleur.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — Amérique du Nord 2025 (exercice 2, partie glouton)

Exercice 2 (6 points, partie tri/récursivité/algorithme glouton) du sujet de bac NSI Amérique du Nord 2025, jour 1.

L'entreprise charge un camion (capacité en kg) avec un algorithme glouton : on charge les colis par ordre décroissant de poids, sans dépasser la capacité. Le tri est effectué par :

def tri_decroissant(liste):
    n = len(liste)
    for i in range(n - 1):
        min_pos = i
        for j in range(i + 1, n):
            if liste[j].poids > liste[min_pos].poids:
                min_pos = j
        temp = liste[i]
        liste[i] = liste[min_pos]
        liste[min_pos] = temp
    return liste

Donner le nom du tri utilisé dans tri_decroissant et son coût dans le pire des cas.
Citer un autre algorithme de tri possible, et son coût dans le pire des cas.

Le chargement récursif est défini par (liste triée par poids décroissants, rang un indice de 0 à len(liste) inclus, capacite la charge restante) :

def chargement_glouton(liste, rang, capacite):
    if rang == len(liste):
        return ...
    elif liste[rang].poids <= ...:
        return ... + chargement_glouton(liste, ..., ...)
    else:
        return chargement_glouton(liste, ..., ...)

Recopier et compléter chargement_glouton.
Expliquer pourquoi l'exécution de chargement_glouton peut lever RecursionError: maximum recursion depth exceeded.
Écrire une fonction chargement_glouton2 itérative (liste triée par poids décroissants, capacite), qui renvoie la liste des colis à charger sans dépasser la capacité.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — 25-NSIPE2 (exercice 1)

Exercice 1 (6 points) du sujet de bac NSI 25-NSIPE2, session 2025 — voir aussi l'annale complète.

En typographie, l'alignement justifié d'un texte donne à chaque ligne la même longueur (la justification), en ajoutant si besoin des espaces supplémentaires. Une espace désigne ici exactement un caractère ' '. On suppose tous les caractères (espaces comprises) de largeur identique, et les mots ne sont ni coupés ni décorés.

Règle de répartition des espaces supplémentaires : s'il n'y a qu'un mot, on insère toutes les espaces à sa droite ; sinon, on effectue la division euclidienne du nombre total d'espaces à ajouter par le nombre d'emplacements inter-mots, on répartit le quotient entre chaque emplacement, puis on distribue le reste une espace à la fois, de gauche à droite.

Partie A

Avec les 4 mots 'An', 'algorithm', 'must', 'be' et une justification de 25 caractères, montrer que le nombre d'espaces nécessaires est 8.
Parmi les 4 propositions suivantes (- représente une espace), déterminer la seule qui respecte les règles de l'alignement justifié pour une justification de 25 caractères : An--algorithm---must---be ; An----algorithm--must--be ; An---algorithm---must--be ; An---algorithm--must---be.

def ajout_espace(liste_mots: list[str],
                  justification: int) -> str:
    nb_caracteres = sum([len(mot) for mot in liste_mots])
    nb_mots = len(liste_mots)
    assert nb_caracteres + ...
    nb_espace_total = justification - nb_caracteres
    if nb_mots == 1:
        return ... + " " * nb_espace_total
    else:
        q = nb_espace_total // (nb_mots - 1)
        r = nb_espace_total % (nb_mots - 1)
        reponse = liste_mots[0]
        for i in range(1, r + 1):
            reponse = reponse + " " * ... \
                + liste_mots[i]
        for i in range(r + 1, nb_mots):
            reponse = reponse + " " * ... \
                + liste_mots[i]
        return reponse

La liste liste_mots peut être trop longue pour tenir sur une ligne. Compléter la précondition (ligne 5) avec le critère à vérifier.
Recopier et compléter les lignes 8, 14 et 17 de ajout_espace (rappel : dans le cas d'au moins 2 mots, avec q et r quotient et reste de la division de nb_espace_total par nb_mots - 1, on place q + 1 espaces pour les r premiers emplacements, puis q espaces pour les suivants).

Partie B

On suppose la justification toujours supérieure à la longueur de chaque mot.

Proposer, en langage naturel (sans code), un algorithme permettant de déterminer après quel mot revenir à la ligne, étant donné une justification.

On modélise le découpage en lignes par une liste de tuples (début, fin) : pour ['An', 'algorithm', 'must', 'be', 'seen', 'to', 'be', 'believed'], [(0, 2), (2, 5), (5, 7), (7, 8)] signifie ligne 1 = An algorithm, ligne 2 = must be seen, ligne 3 = to be, ligne 4 = believed.

Recopier et compléter les lignes 5 à 8 de affiche_justifie, qui affiche les lignes justifiées :

def affiche_justifie(liste_mots: list[str],
                      decoupage: list[(int, int)],
                      justification: int) -> None:
    for ... in decoupage:
        ligne_justifiee = \
            ajout_espace(liste_mots[ ... : ... ], ...)
        ...

Partie C

Le coût inesthétique d'une ligne est le carré du nombre d'espaces supplémentaires nécessaires à sa justification (une espace est toujours due entre deux mots consécutifs ; les espaces supplémentaires sont celles ajoutées en plus). Le coût inesthétique d'un texte pour un découpage donné est la somme des coûts de chaque ligne. On veut minimiser ce coût.

Pour une justification de 15 caractères, la liste ['An', 'algorithm', 'must', 'be', 'seen', 'to', 'be', 'believed'] et le découpage [(0, 2), (2, 4), (4, 7), (7, 8)], reproduire et compléter les trois dernières lignes du tableau (coût total : 147) :

début	fin	nb mots	nb caractères	espaces supplémentaires	coût
0	2	2	11	3	9
2	4
4	7
7	8

Écrire cout(i, j, liste_mots, justification), qui renvoie le coût inesthétique de la ligne liste_mots[i:j] si elle tient sur justification caractères, et un million sinon. Exemples : cout(0,2,liste_mots,15) vaut 9, cout(0,4,liste_mots,15) vaut 1000000, cout(5,8,liste_mots,15) vaut 1.
Pour n ≥ 50 mots, est-il raisonnable de tester tous les découpages possibles ?

On demande à une IA une fonction justifie_dynamique(liste_mots, justification) par programmation dynamique ; elle propose :

def justifie_dynamique(liste_mots, justification):
    n = len(liste_mots)
    cout_mini = [0] * n
    indice_retour_ligne_mini = [0] * n
    for i in range(n-1, -1, -1):
        cout_mini[i] = cout(i, n, liste_mots, justification)
        indice_mini = n
        for j in range(i+1, n):
            best = cout_mini[j] + cout(i, j, liste_mots, justification)
            if best < cout_mini[i]:
                cout_mini[i] = best
                indice_mini = j
        indice_retour_ligne_mini[i] = indice_mini
    decoupage = []
    k = 0
    while k < n:
        decoupage.append((k, indice_retour_ligne_mini[k]))
        k = indice_retour_ligne_mini[k]
    return decoupage

Donner l'ordre de grandeur du nombre d'appels à cout, en fonction de n.
Établir la relation entre les éléments de cout_mini.
Proposer une modification pour que la fonction renvoie aussi le coût inesthétique du découpage.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — 25-NSIPE2 (exercice 2, partie construction)

Exercice 2 (6 points, partie construction de l'arbre) du sujet de bac NSI 25-NSIPE2, session 2025.

On veut une fonction liste_occurrences(chaine) renvoyant la liste des tuples (c, nb_occu) (c un caractère de chaine, nb_occu son nombre d'occurrences). Exemple : liste_occurrences('julie fuit la pluie') renvoie [('j', 1), ('u', 3), ('l', 3), ('i', 3), ('e', 2), (' ', 3), ('f', 1), ('t', 1), ('a', 1), ('p', 1)].

def liste_occurrences(chaine):
    dico = ...
    for c in chaine:
        if c in ...:
            dico[c] = dico[c] + 1
        else:
            ...
    liste_res = ...
    for cle in dico:
        liste_res....
    return ...

Recopier et compléter liste_occurrences.

Pour élaborer l'arbre, on trie d'abord la liste des tuples par occurrence croissante, avec un tri par insertion (rappel : l.insert(i, ele) insère ele à la position i dans l) :

def tri_liste(liste_a_trier):
    liste_triee = []
    for i in range(0, ...):
        element = liste_a_trier[i]
        ...
        while (j < len(liste_triee) and
               element[1] >= liste_triee[j][1]):
            ...
        liste_triee.insert(..., ...)
    return liste_triee

Recopier et compléter tri_liste.
Écrire une fonction conversion_en_noeuds qui convertit une liste de tuples (c, nb_occu) en liste de nœuds.

On insère un nœud dans une liste de nœuds déjà triée par nb_occu croissant :

def insere_noeud(noeud, liste_noeud):
    j = 0
    while j < len(liste_noeud) and ... > ...:
        ...
    liste_noeud.insert(..., ...)

Recopier et compléter insere_noeud.

On construit l'arbre en répétant, jusqu'à n'avoir plus qu'un seul nœud (la racine) : extraire les deux nœuds de plus faible nb_occu, créer un nœud père les regroupant, l'insérer dans la liste.

def construit_arbre(liste):
    while ... > 1:
        noeud1 = liste.pop(0)
        noeud2 = liste.pop(0)
        nom_noeud_pere = noeud1.nom + "-" + noeud2.nom
        nb_occu_noeud_pere = ...
        noeud_pere = Noeud(...)
        insere_noeud(..., liste)
    return ...

Recopier et compléter construit_arbre, qui renvoie le nœud racine.

On admet disposer de codage_arbre(arbre), qui renvoie un dictionnaire des codes, par exemple pour arb_julie : {' ': '00', 'j': '0100', 'f': '0101', 'e': '011', 'l': '100', 'i': '101', 'p': '1100', 't': '11010', 'a': '11011', 'u': '111'}.

Indiquer la structure de données utilisée par codage_arbre.
Écrire une fonction compresse(texte, codage) qui renvoie la chaîne binaire compressée. Exemple : compresse('julie', {' ': '00', 'j': '0100', 'f': '0101', 'e': '011', 'l': '100', 'i': '101', 'p': '1100', 't': '11010', 'a': '11011', 'u': '111'}) renvoie '0100111100101011'.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 24, exercice 2 : plus grande somme d'éléments consécutifs

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°24, exercice 2.

On considère un tableau de nombres entiers, positifs ou négatifs, et on souhaite déterminer la plus grande somme possible de ses éléments consécutifs.

Par exemple, dans le tableau [1, -2, 3, 10, -4, 7, 2, -5], la plus grande somme est 18 obtenue en additionnant les éléments 3, 10, -4, 7, 2.

Pour cela, on va résoudre le problème par programmation dynamique. Si on note tab le tableau considéré et i un indice dans ce tableau, on se ramène à un problème plus simple : déterminer la plus grande somme possible de ses éléments consécutifs se terminant à l'indice i.

Si on connaît la plus grande somme possible de ses éléments consécutifs se terminant à l'indice i-1, on peut déterminer la plus grande somme possible de ses éléments consécutifs se terminant à l'indice i :

soit on obtient une plus grande somme en ajoutant tab[i] à cette somme précédente ;
soit on commence une nouvelle somme à partir de tab[i].

Compléter la fonction somme_max ci-dessous qui réalise cet algorithme.

def somme_max(tab):
    n = len(tab)
    sommes_max = [0]*n
    sommes_max[0] = tab[0]
    # on calcule la plus grande somme se terminant en i
    for i in range(1,n):
        if ... + ... > ...:
            sommes_max[i] = ...
        else:
            sommes_max[i] = ...
    # on en déduit la plus grande somme de celles-ci
    maximum = 0
    for i in range(1, n):
        if ... > ...:
            maximum = i
    return sommes_max[...]

Exemples :

>>> somme_max([1, 2, 3, 4, 5])
15
>>> somme_max([1, 2, -3, 4, 5])
9
>>> somme_max([1, 2, -2, 4, 5])
10
>>> somme_max([1, -2, 3, 10, -4, 7, 2, -5])
18

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 28, exercice 1 : terme de la suite de Fibonacci

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°28, exercice 1.

On s'intéresse à la suite d'entiers définie par :

les deux premières valeurs sont égales à 1 ;
ensuite, chaque valeur est obtenue en faisant la somme des deux valeurs qui la précèdent.

La troisième valeur est donc $1 + 1 = 2$ , la quatrième est $1 + 2 = 3$ , la cinquième est $2 + 3 = 5$ , la sixième est $3 + 5 = 8$ , et ainsi de suite.

Cette suite d'entiers est connue sous le nom de suite de Fibonacci.

Écrire en Python une fonction fibonacci qui prend en paramètre un entier n supposé strictement positif et qui renvoie le terme d'indice n de cette suite.

Exemples :

>>> fibonacci(1)
1
>>> fibonacci(2)
1
>>> fibonacci(25)
75025

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 30, exercice 1 : fusionner deux tableaux triés

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°30, exercice 1.

Programmer la fonction fusion prenant en paramètres deux tableaux non vides tab1 et tab2 (type list) d'entiers, chacun dans l'ordre croissant, et renvoyant un tableau trié dans l'ordre croissant et contenant l'ensemble des valeurs de tab1 et tab2.

Exemples :

>>> fusion([3, 5], [2, 5])
[2, 3, 5, 5]
>>> fusion([-2, 4], [-3, 5, 10])
[-3, -2, 4, 5, 10]
>>> fusion([4], [2, 6])
[2, 4, 6]
>>> fusion([], [])
[]
>>> fusion([1, 2, 3], [])
[1, 2, 3]

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 34, exercice 2 : fusion dans un tableau préalloué

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°34, exercice 2.

La fonction fusion prend deux tableaux tab1, tab2 (type list) d'entiers triés par ordre croissant et les fusionne en un tableau trié tab12 qu'elle renvoie.

Compléter le code de la fonction fusion ci-dessous.

def fusion(tab1,tab2):
    '''Fusionne deux tableaux triés et renvoie
    le nouveau tableau trié.'''
    n1 = len(tab1)
    n2 = len(tab2)
    tab12 = [0] * (n1 + n2)
    i1 = 0
    i2 = 0
    i = 0
    while i1 < n1 and ...:
        if tab1[i1] < tab2[i2]:
            tab12[i] = ...
            i1 = ...
        else:
            tab12[i] = tab2[i2]
            i2 = ...
        i += 1
    while i1 < n1:
        tab12[i] = ...
        i1 = i1 + 1
        i = ...
    while i2 < n2:
        tab12[i] = ...
        i2 = i2 + 1
        i = ...
    return tab12

Exemple :

>>> fusion([1,2,3],[])
[1, 2, 3]
>>> fusion([], [])
[]
>>> fusion([1, 6, 10],[0, 7, 8, 9])
[0, 1, 6, 7, 8, 9, 10]

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 40, exercice 2 : trouver l'intrus par dichotomie récursive

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°40, exercice 2.

On considère des tableaux de nombres dont tous les éléments sont présents exactement trois fois à la suite, sauf un élément qui est présent une unique fois et que l'on appelle « l'intrus ». Voici quelques exemples :

tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8]
#l'intrus est 7
tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]
#l'intrus est 8
tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]
#l'intrus est 3

On remarque qu'avec de tels tableaux :

pour les indices multiples de 3 situés strictement avant l'intrus, l'élément correspondant et son voisin de droite sont égaux ;
pour les indices multiples de 3 situés après l'intrus, l'élément correspondant et son voisin de droite, s'il existe, sont différents.

Ce que l'on peut observer ci-dessous en observant les valeurs des paires de voisins marquées par des caractères ^ :

[3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8]
 ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^
 0        3        6        9        12       15

Dans des tableaux comme ceux ci-dessus, un algorithme récursif pour trouver l'intrus consiste alors à choisir un indice i multiple de 3 situé approximativement au milieu des indices parmi lesquels se trouve l'intrus.

Puis, en fonction des valeurs de l'élément d'indice i et de son voisin de droite, à appliquer récursivement l'algorithme à la moitié droite ou à la moitié gauche des indices parmi lesquels se trouve l'intrus.

Par exemple, si on s'intéresse à l'indice 12, on voit les valeurs 2 et 4 qui sont différentes : l'intrus est donc à gauche de l'indice 12 (indice 12 compris).

En revanche, si on s'intéresse à l'indice 3, on voit les valeurs 9 et 9 qui sont identiques : l'intrus est donc à droite des indices 3-4-5, donc à partir de l'indice 6.

Compléter la fonction récursive trouver_intrus ci-dessous qui met en œuvre cet algorithme.

def trouver_intrus(tab, g, d):
    """Renvoie la valeur de l'intrus situé entre les indices g et d
    dans le tableau tab où :
    tab vérifie les conditions de l'exercice,
    g et d sont des multiples de 3."""
    if g == d:
        return ...
 
    else:
        nombre_de_triplets = (d - g) // ...
        indice = g + 3 * (nombre_de_triplets // 2)
        if ...:
            return ...
        else:
            return ...

Exemples :

>>> trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7,
        2, 2, 2, 4, 4, 4, 8, 8, 8], 0, 18)
7
>>> trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3],
                    0, 12)
8
>>> trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0,
        6, 6, 6, 3, 8, 8, 8], 0, 15)
3

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

QCM — Diviser pour régner et programmation dynamique

1. Quelle est la complexité en temps du tri fusion sur une liste de n éléments ?

2. Pourquoi la version naïve (récursive simple) de fibo(n) est-elle inefficace pour de grandes valeurs de n ?

3. En traçant l'exécution de puissance_rapide(2, 5) telle que définie dans le cours, quelle valeur renvoie cet appel ?

Recherche textuelle : l'algorithme de Boyer-Moore

Le problème

On cherche toutes les occurrences d'un motif $M$ (de longueur $m$ ) dans un texte $S$ (de longueur $n$ ), avec généralement $m \ll n$ . Ce problème se pose aussi bien pour la recherche dans un traitement de texte que pour la recherche de séquences dans un génome. On suppose que l'accès à un caractère de $S$ ou $M$ par son indice se fait en temps constant, $O(1)$ .

Exemple. Le motif "GACA" apparaît deux fois dans "GCCGACTGACACCAGACATCG" (aux positions 7 et 14, en numérotant à partir de 0).

La méthode naïve

On fait glisser une fenêtre de longueur $m$ le long du texte $S$ ; pour chaque position, on compare caractère par caractère avec $M$ , de gauche à droite :

def recherche_naive(S, M):
    """Affiche les positions ou M apparait dans S"""
    n, m = len(S), len(M)
    for i in range(n - m + 1):
        j = 0
        while j < m and S[i + j] == M[j]:
            j += 1
        if j == m:
            print(f"{M} trouve a la position {i}")

Dans le meilleur des cas (le premier caractère de $M$ n'apparaît jamais dans $S$ ), la complexité est en $\Omega(n - m)$ . Dans le pire des cas (motif très répétitif), on parcourt les deux boucles en entier : la complexité devient $O((n-m) \times m)$ , ce qui peut être coûteux pour de grandes chaînes.

L'algorithme de Boyer-Moore

L'idée de Boyer-Moore est de comparer le motif au texte de droite à gauche, et d'exploiter les échecs de comparaison pour faire glisser la fenêtre de plus d'un caractère à la fois, en toute sécurité.

L'heuristique du « mauvais caractère »

Lorsqu'une comparaison échoue en $S[i+j] \neq M[j]$ , on regarde le caractère $S[i+j]$ (le « mauvais caractère ») :

s'il n'apparaît pas du tout dans $M$ , on peut décaler la fenêtre de sa longueur $m$ tout entière (aucune correspondance n'est possible avant) ;
sinon, on décale la fenêtre pour aligner l'occurrence la plus à droite de ce caractère dans $M[0:j]$ avec la position $i+j$ du texte.

Exemple. En cherchant M = "EXEMPLE" dans S = "VOICI UN SIMPLE EXEMPLE", si l'on compare d'abord les derniers caractères et que U (dans $S$ ) ne correspond pas à E (dans $M$ ) alors que U n'apparaît jamais dans "EXEMPLE", on peut directement décaler le motif de 7 positions (sa longueur), sans manquer aucune occurrence.

def dernieres_positions(M):
    """Pour chaque caractere de M, renvoie son indice le plus a droite dans M"""
    positions = {}
    for indice, caractere in enumerate(M):
        positions[caractere] = indice
    return positions
 
def boyer_moore_mauvais_caractere(S, M):
    """Recherche de M dans S avec l'heuristique du mauvais caractere"""
    n, m = len(S), len(M)
    dernier = dernieres_positions(M)
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and S[i + j] == M[j]:
            j -= 1
        if j < 0:
            print(f"{M} trouve a la position {i}")
            i += 1                                  # on continue apres une occurrence
        else:
            decalage_carac = dernier.get(S[i + j], -1)
            decalage = max(1, j - decalage_carac)    # au moins 1, pour toujours avancer
            i += decalage

La figure suivante anime pas à pas la recherche du motif "EXEMPLE" dans le texte "VOICI UN SIMPLE EXEMPLE" (le même exemple qu'au-dessus) avec l'heuristique du mauvais caractère :

Recherche de EXEMPLE

Recherche de M = « EXEMPLE » dans S par l'heuristique du mauvais caractère. dernier = {'E': 6, 'X': 1, 'M': 3, 'P': 4, 'L': 5}

Recherche de M = « EXEMPLE » (m = 7) dans S = « VOICI UN SIMPLE EXEMPLE » (n = 23). On compare de droite à gauche, à partir de j = m - 1 = 6. dernier = dernieres_positions(M) = {'E': 6, 'X': 1, 'M': 3, 'P': 4, 'L': 5}.

Étape 1/18

L'algorithme réel de Boyer-Moore combine cette heuristique du « mauvais caractère » avec une seconde, celle du « bon suffixe », qui exploite la partie du motif déjà validée avant l'échec. En pratique, cette combinaison rend Boyer-Moore sous-linéaire en moyenne : il n'est pas nécessaire d'examiner tous les caractères du texte.

Exercice — Décaler la fenêtre avec l'heuristique du mauvais caractère

On cherche le motif M = "BAOBAB" dans un texte, en utilisant l'heuristique du « mauvais caractère » de Boyer-Moore.

Construire le dictionnaire dernier donnant, pour chaque lettre de M, son indice le plus à droite dans M (à l'aide de la fonction dernieres_positions du cours).
On aligne M sur une portion du texte et la comparaison de droite à gauche échoue dès le premier caractère comparé (le dernier de M, indice $j = 5$ ) : le caractère du texte à cette position est 'Z'. 'Z' n'apparaissant pas dans M, de combien de positions peut-on décaler la fenêtre ?
Même question si le caractère du texte, à cette position, est 'A' au lieu de 'Z'.

Exercice — Tracer l'exécution complète de l'heuristique du mauvais caractère

On reprend les fonctions dernieres_positions et boyer_moore_mauvais_caractere du cours. On cherche le motif M = "ABC" dans le texte S = "XXABCYABCZ" (10 caractères, indicés de 0 à 9).

Donner le dictionnaire dernier construit par dernieres_positions(M).
Tracer l'exécution de boyer_moore_mauvais_caractere(S, M) : pour chaque valeur de i testée par la boucle externe, indiquer la valeur de j à la fin de la comparaison interne, si une occurrence est trouvée en i, et le décalage appliqué pour passer à la valeur suivante de i.
En déduire la ou les position(s) où M apparaît dans S.

Exercice — Comparer méthode naïve et Boyer-Moore sur un motif répétitif

On cherche toutes les occurrences du motif M = "AAB" dans le texte S = "AAAAAB" (6 caractères). Ce motif est très répétitif : d'après le cours, c'est justement le cas où la méthode naïve est la plus coûteuse.

Tracer l'exécution de recherche_naive(S, M) : pour chaque valeur de i testée, indiquer la valeur finale de j et le nombre de comparaisons de caractères effectuées. En déduire le nombre total de comparaisons.
Tracer l'exécution de boyer_moore_mauvais_caractere(S, M) sur le même exemple (donner d'abord le dictionnaire dernier) : pour chaque itération de la boucle externe, indiquer la valeur de i, le nombre de comparaisons effectuées, et le décalage appliqué. En déduire le nombre total de comparaisons.
Comparer les deux nombres obtenus. Le gain apporté par l'heuristique du mauvais caractère est-il aussi spectaculaire que dans l'exemple "EXEMPLE"/"VOICI UN SIMPLE EXEMPLE" du cours, où un décalage de la longueur entière du motif était possible ? Expliquer pourquoi, dans le cas présent, les décalages appliqués restent presque toujours égaux à 1.

Exercice — Épreuve pratique NSI 2024 — Sujet 21, exercice 1 : positions d'un motif dans un texte

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°21, exercice 1.

Écrire une fonction recherche_motif qui prend en paramètre une chaîne de caractères motif non vide et une chaîne de caractères texte et qui renvoie la liste des positions de motif dans texte. Si motif n'apparaît pas, la fonction renvoie une liste vide.

Exemples :

>>> recherche_motif("ab", "")
[]
>>> recherche_motif("ab", "cdcdcdcd")
[]
>>> recherche_motif("ab", "abracadabra")
[0, 7]
>>> recherche_motif("ab", "abracadabraab")
[0, 7, 11]

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

QCM — Recherche textuelle et Boyer-Moore

1. Dans quel sens l'algorithme de Boyer-Moore compare-t-il le motif au texte ?

2. Que permet l'heuristique du « mauvais caractère » lorsque le caractère du texte n'apparaît pas du tout dans le motif ?

3. On cherche le motif M = "BANANE" (m = 6) avec l'heuristique du mauvais caractere. Lors d'une comparaison de droite a gauche a une position i, les caracteres S[i+5] et S[i+4] correspondent bien a M[5]='E' et M[4]='N', mais la comparaison echoue en j=3 : M[3]='A' alors que S[i+3]='B'. Quel decalage (la valeur ajoutee a i) l'algorithme applique-t-il ensuite ?

Exercices bilan

Parcourir un arbre binaire niveau par niveau

ApplicationCorrigé gratuit

On considère l'arbre binaire suivant :

Avec la classe Noeud du cours, il se code ainsi (rappel : l'arbre vide est représenté par None) :

class Noeud:
    def __init__(self, etiquette, gauche=None, droite=None):
        self.etiquette = etiquette
        self.gauche = gauche
        self.droite = droite
 
arbre = Noeud("R",
              Noeud("A", Noeud("N"), Noeud("E", Noeud("T"), None)),
              Noeud("C", None, Noeud("I", Noeud("S"), Noeud("O"))))

On rappelle également la fonction de parcours en largeur du cours :

from collections import deque
 
def parcours_largeur(arbre):
    """Renvoie la liste des etiquettes d'un arbre binaire, parcouru en largeur"""
    if arbre is None:
        return []
    resultat = []
    file = deque([arbre])
    while file:
        noeud = file.popleft()
        resultat.append(noeud.etiquette)
        if noeud.gauche is not None:
            file.append(noeud.gauche)
        if noeud.droite is not None:
            file.append(noeud.droite)
    return resultat

Donner la taille de cet arbre, sa hauteur et la liste de ses feuilles. Justifier que le nœud E n'est pas une feuille.
Donner le résultat de parcours_largeur(arbre). Détailler le contenu de la file au début de chaque tour de boucle.
Donner le parcours préfixe du même arbre et expliquer en une phrase ce qui distingue les deux ordres obtenus.
Écrire une fonction etiquettes_par_niveau(arbre) qui renvoie la liste des listes d'étiquettes, un niveau par sous-liste. Sur l'arbre ci-dessus, on doit obtenir une liste de $4$ sous-listes dont la première est ['R'].
Un élève remplace file.popleft() par file.pop() et laisse le reste inchangé. Donner l'ordre de visite obtenu et expliquer ce que réalise désormais la fonction.

Construire et interroger un arbre binaire de recherche

Application

Une bibliothèque range les numéros de référence de ses ouvrages dans un arbre binaire de recherche, afin de retrouver rapidement une référence. On rappelle les fonctions du cours, ainsi que la convention retenue : une clé inférieure ou égale à l'étiquette part à gauche.

class Noeud:
    def __init__(self, etiquette, gauche=None, droite=None):
        self.etiquette = etiquette
        self.gauche = gauche
        self.droite = droite
 
def insere(arbre, cle):
    """Renvoie l'ABR obtenu en inserant cle dans l'ABR arbre"""
    if arbre is None:
        return Noeud(cle)
    if cle <= arbre.etiquette:
        arbre.gauche = insere(arbre.gauche, cle)
    else:
        arbre.droite = insere(arbre.droite, cle)
    return arbre
 
def recherche(arbre, cle):
    """Renvoie True si cle est presente dans l'ABR arbre, False sinon"""
    if arbre is None:
        return False
    if cle == arbre.etiquette:
        return True
    if cle < arbre.etiquette:
        return recherche(arbre.gauche, cle)
    return recherche(arbre.droite, cle)

On part d'un arbre vide et l'on insère, dans cet ordre, les références :

42, \quad 17, \quad 63, \quad 8, \quad 25, \quad 55, \quad 90

catalogue = None
for reference in [42, 17, 63, 8, 25, 55, 90]:
    catalogue = insere(catalogue, reference)

Dessiner l'arbre obtenu, puis donner sa taille et sa hauteur.
Donner le parcours infixe de cet arbre. Quelle propriété remarquable observe-t-on, et pourquoi est-elle vraie pour tout arbre binaire de recherche ?
Donner, dans l'ordre, la liste des étiquettes comparées à la clé lors de l'appel recherche(catalogue, 55), puis lors de l'appel recherche(catalogue, 30), ainsi que la valeur renvoyée dans chaque cas.
On insère ensuite la référence $30$ . Indiquer de quel nœud elle devient le fils, et préciser la nouvelle hauteur de l'arbre.
La bibliothèque acquiert un second exemplaire, portant lui aussi la référence $17$ , et l'insère dans l'arbre de départ (celui de la question 1). En appliquant la convention du cours, indiquer précisément où ce doublon vient se placer. Vérifier que le parcours infixe reste trié.
On recommence tout depuis un arbre vide, mais en insérant les sept références par ordre croissant : $8, 17, 25, 42, 55, 63, 90$ . Décrire l'arbre obtenu, donner sa hauteur, et expliquer les conséquences sur le coût de recherche.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Explorer un réseau de stations en profondeur et en largeur

EntraînementCorrigé gratuit

Un réseau de $8$ stations, numérotées de $0$ à $7$ , est modélisé par un graphe non orienté : deux stations sont reliées lorsqu'une navette effectue le trajet direct entre elles.

   0 --- 1 --- 3
   |     |     |
   2 --- 4 --- 5

   6 --- 7

Comme dans le cours, le graphe est représenté par sa liste de successeurs :

successeurs = [[1, 2], [0, 3, 4], [0, 4], [1, 5], [1, 2, 5], [3, 4], [7], [6]]

On rappelle les deux parcours du cours :

from collections import deque
 
def parcours_profondeur(successeurs, depart):
    """Renvoie l'ordre de visite des sommets, parcours en profondeur depuis depart"""
    n = len(successeurs)
    vus = [False] * n
    pile = [depart]
    parcours = []
    while pile:
        sommet = pile.pop()
        if not vus[sommet]:
            vus[sommet] = True
            parcours.append(sommet)
            for voisin in successeurs[sommet]:
                if not vus[voisin]:
                    pile.append(voisin)
    return parcours
 
def parcours_largeur(successeurs, depart):
    """Renvoie l'ordre de visite des sommets, parcours en largeur depuis depart"""
    n = len(successeurs)
    vus = [False] * n
    vus[depart] = True
    file = deque([depart])
    parcours = [depart]
    while file:
        sommet = file.popleft()
        for voisin in successeurs[sommet]:
            if not vus[voisin]:
                vus[voisin] = True
                parcours.append(voisin)
                file.append(voisin)
    return parcours

Donner la liste des arêtes du réseau, son ordre, son nombre d'arêtes, et le degré de chaque sommet. Vérifier la cohérence entre la somme des degrés et le nombre d'arêtes.
Donner le résultat de parcours_profondeur(successeurs, 0) en détaillant le contenu de la pile à chaque tour de boucle. On expliquera pourquoi un même sommet peut figurer plusieurs fois dans la pile, et pourquoi cela ne fausse pas le résultat.
Donner le résultat de parcours_largeur(successeurs, 0) en détaillant le contenu de la file.
Donner la distance (en nombre d'arêtes) entre la station $0$ et chacune des stations qu'elle permet d'atteindre. Expliquer pourquoi c'est le parcours en largeur qui fournit cette information, et non celui en profondeur.
Écrire une fonction est_connexe(successeurs) qui renvoie True lorsque toutes les stations sont reliées entre elles. Que renvoie-t-elle sur ce réseau ? Que faudrait-il ajouter pour rendre le réseau connexe ?
Dans parcours_largeur, le marquage vus[voisin] = True est effectué au moment de l'enfilement. Expliquer ce qui se passerait si on le déplaçait au moment du défilement.

Détecter un cycle dans un réseau non orienté

Entraînement

Un opérateur installe des liaisons en fibre optique entre $6$ bâtiments, numérotés de $0$ à $5$ . Une liaison redondante — c'est-à-dire un cycle dans le graphe non orienté des liaisons — coûte cher, mais protège contre une coupure. L'opérateur veut donc savoir si son réseau en contient un.

Réseau A

Réseau B — identique au réseau A, avec une liaison supplémentaire entre $3$ et $5$ .

On rappelle la fonction du cours :

def contient_cycle(successeurs):
    """Renvoie True si le graphe non oriente possede un cycle"""
    n = len(successeurs)
    vus = [False] * n
 
    def explore(sommet, pere):
        vus[sommet] = True
        for voisin in successeurs[sommet]:
            if not vus[voisin]:
                if explore(voisin, sommet):
                    return True
            elif voisin != pere:
                return True          # sommet deja vu, autre que le pere : cycle
        return False
 
    for depart in range(n):
        if not vus[depart]:
            if explore(depart, -1):
                return True
    return False

Donner la liste de successeurs de chacun des deux réseaux, en rangeant les voisins de chaque sommet par ordre croissant. Donner aussi leur nombre d'arêtes.
Dérouler contient_cycle sur le réseau A : donner la suite des appels à explore, avec leurs deux arguments, et le résultat final.
Dérouler contient_cycle sur le réseau B : donner la suite des appels à explore, préciser lors de quel appel et sur quel voisin le cycle est détecté, et citer le cycle correspondant.
Expliquer le rôle de la condition voisin != pere. Que renverrait la fonction sur le réseau A si on l'écrivait simplement else: return True ?
Justifier l'utilité de la boucle for depart in range(n) placée à la fin. Construire un exemple de graphe à $5$ sommets sur lequel la fonction renverrait un résultat faux si l'on se contentait de l'appel explore(0, -1).
On admet qu'un graphe non orienté connexe à $n$ sommets est sans cycle si et seulement s'il possède exactement $n-1$ arêtes. Vérifier cette propriété sur les deux réseaux. L'opérateur peut-il se contenter de compter les arêtes pour répondre à sa question ?

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Compter les opérations de l'exponentiation rapide et du tri fusion

Entraînement

Le paradigme « diviser pour régner » promet des algorithmes plus rapides. Cet exercice propose de le vérifier en comptant les opérations, sur les deux exemples du cours.

Partie A — l'exponentiation rapide

def puissance_rapide(a, n):
    """Calcule a**n en O(log n) multiplications"""
    if n == 0:
        return 1
    if n % 2 == 0:
        return puissance_rapide(a * a, n // 2)
    return a * puissance_rapide(a * a, (n - 1) // 2)

A.1. Dérouler l'appel puissance_rapide(2, 13) : donner la suite des appels récursifs sous la forme d'un couple d'arguments, puis les valeurs renvoyées lors de la remontée. Vérifier que le résultat final vaut bien $2^{13}$ .

A.2. Compter le nombre total de multiplications effectuées lors de cet appel (on comptera le produit a * a et le produit final a * ... comme une multiplication chacun).

A.3. Combien de multiplications demanderait la méthode naïve, qui calcule $a^n$ en multipliant $a$ par lui-même de façon répétée ? Comparer.

A.4. Justifier que le nombre d'appels récursifs est de l'ordre de $\log_2(n)$ . Estimer le nombre de multiplications pour $n = 1000$ par chacune des deux méthodes.

Partie B — le tri fusion

def interclassement(lst1, lst2):
    """Fusionne deux listes deja triees en une seule liste triee"""
    resultat = []
    i1, i2 = 0, 0
    while i1 < len(lst1) and i2 < len(lst2):
        if lst1[i1] <= lst2[i2]:
            resultat.append(lst1[i1])
            i1 += 1
        else:
            resultat.append(lst2[i2])
            i2 += 1
    return resultat + lst1[i1:] + lst2[i2:]
 
def tri_fusion(lst):
    """Trie la liste lst par la methode diviser pour regner"""
    if len(lst) <= 1:
        return lst
    m = len(lst) // 2
    return interclassement(tri_fusion(lst[:m]), tri_fusion(lst[m:]))

B.1. On appelle tri_fusion([7, 2, 9, 4, 1, 6]). Donner les listes sur lesquelles portent les appels récursifs successifs, jusqu'aux listes de taille $1$ .

B.2. Donner, dans l'ordre où ils sont effectués, les cinq interclassements réalisés, avec leurs deux arguments et leur résultat.

B.3. Détailler comparaison par comparaison le dernier interclassement, celui des deux moitiés triées. Préciser ce que contient la liste resultat au moment où la boucle while s'arrête, et quel rôle joue alors la ligne return resultat + lst1[i1:] + lst2[i2:].

B.4. Compter le nombre total de comparaisons entre éléments effectuées par tri_fusion([7, 2, 9, 4, 1, 6]).

B.5. Justifier la complexité en $\Theta(n \log n)$ du tri fusion. Pour une liste de $1000$ éléments, combien de niveaux de découpage environ, et quel ordre de grandeur pour le nombre de comparaisons, comparé à un tri par insertion en $\Theta(n^2)$ ?

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Monter un escalier : de la récursivité naïve à la programmation dynamique

Entraînement

Un escalier comporte $n$ marches. On peut le gravir en montant, à chaque pas, une ou deux marches à la fois. On note $f(n)$ le nombre de façons différentes d'atteindre la $n$ -ième marche.

Par exemple, pour $n = 3$ , il y a $3$ façons de monter : $1+1+1$ , $1+2$ et $2+1$ .

Énumérer les façons de monter un escalier de $4$ marches, et en déduire $f(4)$ .
Justifier la relation $f(n) = f(n-1) + f(n-2)$ pour $n \geqslant 2$ , en raisonnant sur le dernier pas effectué. Préciser les valeurs de $f(0)$ et $f(1)$ ; on conviendra qu'il existe une seule façon de gravir un escalier de $0$ marche, celle qui consiste à ne rien faire.
Écrire une fonction récursive montees(n) qui traduit directement cette relation, puis donner les valeurs de montees(n) pour $n$ allant de $0$ à $6$ .
On instrumente la fonction pour compter ses appels. L'appel montees(5) en déclenche $15$ au total. Reconstituer le détail de ce comptage en indiquant, pour chaque valeur de l'argument, le nombre de fois où montees est appelée avec cette valeur. Commenter.
Écrire une version mémoïsée de la fonction, puis une version itérative « de bas en haut ». Pour chacune, donner le nombre d'additions effectuées lors du calcul de montees(5).
L'appel naïf montees(10) déclenche $177$ appels, et montees(30) en déclencherait plus de $2{,}7$ millions. Expliquer ce comportement, et donner la complexité des trois versions.
Écrire une dernière version qui ne conserve que deux valeurs en mémoire au lieu d'un tableau de taille $n+1$ . Dans quel cas ce raffinement est-il utile, et que perd-on ?

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Rechercher un motif dans une séquence d'ADN

Type bac

Cet exercice, composé de deux parties A et B, porte sur la recherche textuelle et l'algorithme de Boyer-Moore.

Un laboratoire recherche les occurrences d'un motif de bases azotées dans une séquence d'ADN. Les deux chaînes ne sont composées que des lettres A, C, G et T.

On travaille sur la séquence $S$ et le motif $M$ suivants, dont les caractères sont numérotés à partir de $0$ :

indice : 0 1 2 3 4 5 6 7 8 9 ...
S = A G C T T A G C G C A G C T T A G C A G C   (n = 21)
M = G C A G C                                   (m = 5)

Partie A : la méthode naïve

def recherche_naive(S, M):
    """Affiche les positions ou M apparait dans S"""
    n, m = len(S), len(M)
    for i in range(n - m + 1):
        j = 0
        while j < m and S[i + j] == M[j]:
            j += 1
        if j == m:
            print(f"{M} trouve a la position {i}")

A.1. Combien de positions i la boucle for examine-t-elle ? Justifier la borne n - m + 1 : que se passerait-il si l'on écrivait range(n) ?

A.2. Donner les positions auxquelles le motif $M$ apparaît dans $S$ . Vérifier l'une d'elles en écrivant la tranche correspondante de $S$ .

A.3. Pour la position $i = 1$ , détailler les comparaisons effectuées par la boucle while et indiquer la valeur de j à la sortie.

A.4. On appelle comparaison tout test S[i + j] == M[j], qu'il réussisse ou qu'il échoue. Montrer que, pour $12$ des positions examinées, la boucle while s'arrête dès la première comparaison. En déduire le nombre total de comparaisons effectuées par recherche_naive(S, M).

A.5. Rappeler la complexité de cette méthode dans le pire des cas et donner un exemple de couple $(S, M)$ qui l'atteint.

Partie B : l'heuristique du mauvais caractère

L'algorithme de Boyer-Moore compare le motif au texte de droite à gauche et exploite les échecs pour décaler la fenêtre de plusieurs caractères d'un coup.

def dernieres_positions(M):
    """Pour chaque caractere de M, renvoie son indice le plus a droite dans M"""
    positions = {}
    for indice, caractere in enumerate(M):
        positions[caractere] = indice
    return positions
 
def boyer_moore_mauvais_caractere(S, M):
    """Recherche de M dans S avec l'heuristique du mauvais caractere"""
    n, m = len(S), len(M)
    dernier = dernieres_positions(M)
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and S[i + j] == M[j]:
            j -= 1
        if j < 0:
            print(f"{M} trouve a la position {i}")
            i += 1
        else:
            decalage_carac = dernier.get(S[i + j], -1)
            decalage = max(1, j - decalage_carac)
            i += decalage

B.1. Donner le dictionnaire renvoyé par dernieres_positions("GCAGC"). Expliquer pourquoi la lettre G y est associée à l'indice $3$ et non à l'indice $0$ , et pourquoi c'est bien l'occurrence la plus à droite qui doit être retenue.

B.2. Dérouler boyer_moore_mauvais_caractere(S, M). Pour chacune des positions i successivement examinées, donner la fenêtre de $S$ concernée, la valeur de j à l'échec, le « mauvais caractère », le décalage calculé et la nouvelle valeur de i.

B.3. À la position $i = 5$ , le décalage calculé vaut $1$ alors que la formule j - decalage_carac donne une valeur négative. Expliquer d'où vient cette valeur négative et pourquoi l'appel à max est indispensable.

B.4. Compter le nombre total de comparaisons de caractères effectuées par l'algorithme de Boyer-Moore sur cet exemple, et le comparer au résultat de la question A.4.

B.5. Expliquer pourquoi le motif est comparé de droite à gauche, alors que la méthode naïve procède de gauche à droite.

B.6. Lorsque le mauvais caractère est un T, le décalage vaut $5$ , c'est-à-dire la longueur du motif. Expliquer pourquoi, et justifier qu'aucune occurrence ne peut être manquée.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Vous avez terminé le programme de NSI Terminale !

Retour à tous les chapitres de NSI

Algorithmique

Parcours et recherche dans les arbres binaires

Rappel : la classe Noeud

Parcours en largeur (BFS)

Arbres binaires de recherche (ABR)

Rechercher une clé

Insérer une clé

Complexité

QCM — Parcours en largeur et ABR

Parcours de graphes : profondeur, largeur et détection de cycle

Parcours en profondeur (DFS) à l'aide d'une pile

Parcours en largeur (BFS) à l'aide d'une file

Rechercher un chemin entre deux sommets

Détecter un cycle

QCM — Parcours de graphes et cycles

Diviser pour régner et programmation dynamique

Le principe « diviser pour régner »

Le tri fusion

De la récursivité à la programmation dynamique

Approche « haut vers bas » (mémoïsation)

Approche « bas vers haut » (itérative)

Partie A

Partie B

Partie C

QCM — Diviser pour régner et programmation dynamique

Recherche textuelle : l'algorithme de Boyer-Moore

Le problème

La méthode naïve

L'algorithme de Boyer-Moore

L'heuristique du « mauvais caractère »

QCM — Recherche textuelle et Boyer-Moore

Exercices bilan

Parcourir un arbre binaire niveau par niveau

Construire et interroger un arbre binaire de recherche

Explorer un réseau de stations en profondeur et en largeur

Détecter un cycle dans un réseau non orienté

Compter les opérations de l'exponentiation rapide et du tri fusion

Partie A — l'exponentiation rapide

Partie B — le tri fusion

Monter un escalier : de la récursivité naïve à la programmation dynamique

Rechercher un motif dans une séquence d'ADN

Partie A : la méthode naïve

Partie B : l'heuristique du mauvais caractère

Rappel : la classe `Noeud`