NSI - Bac 2025

Exercice 1 — Structures de données (6 points)

[Contexte] On s'intéresse à la gestion d'une bibliothèque municipale. Les livres sont représentés par des dictionnaires contenant les clés suivantes : 'titre', 'auteur', 'annee', 'isbn' (identifiant unique) et 'emprunte' (booléen).

La bibliothèque utilise une structure de données pour organiser ses livres. On considère le code Python suivant :

class Bibliotheque:
    def __init__(self):
        self.livres = []
        self.index_isbn = {}
    
    def ajouter_livre(self, livre):
        self.livres.append(livre)
        self.index_isbn[livre['isbn']] = len(self.livres) - 1
    
    def rechercher_par_isbn(self, isbn):
        if isbn in self.index_isbn:
            return self.livres[self.index_isbn[isbn]]
        return None
    
    def rechercher_par_titre(self, titre):
        resultats = []
        for livre in self.livres:
            if livre['titre'].lower() == titre.lower():
                resultats.append(livre)
        return resultats
    
    def emprunter_livre(self, isbn):
        livre = self.rechercher_par_isbn(isbn)
        if livre and not livre['emprunte']:
            livre['emprunte'] = True
            return True
        return False
    
    def livres_disponibles(self):
        disponibles = []
        for livre in self.livres:
            if not livre['emprunte']:
                disponibles.append(livre)
        return disponibles

1. Analyser la complexité temporelle des méthodes rechercher_par_isbn et rechercher_par_titre. Justifier votre réponse.

2. Proposer une modification de la structure de données pour améliorer la recherche par titre. Décrire l'algorithme de recherche correspondant et analyser sa complexité.

3. Compléter la classe Bibliotheque en ajoutant une méthode supprimer_livre(isbn) qui retire un livre de la bibliothèque. Cette méthode doit maintenir à jour toutes les structures de données internes. Le code doit gérer le cas où le livre n'existe pas.

Exercice 2 — Algorithmique (6 points)

On considère la fonction recherche_sequentielle qui prend en paramètre une liste liste d'entiers et un entier valeur, et qui renvoie l'indice de la première occurrence de valeur dans liste, ou -1 si valeur n'est pas présente.

def recherche_sequentielle(liste, valeur):
    '''
    Recherche séquentielle dans une liste non triée.
    '''
    for i in range(len(liste)):
        if liste[i] == valeur:
            return i
    return -1

On souhaite maintenant implémenter une version optimisée pour une liste triée par ordre croissant : la fonction recherche_dichotomique.

1. Expliquez pourquoi la recherche dichotomique est plus efficace que la recherche séquentielle sur une liste triée. Quelle est la complexité temporelle de chaque algorithme dans le pire des cas ?

2. Complétez la fonction recherche_dichotomique ci-dessous pour qu'elle renvoie l'indice de valeur dans liste (triée par ordre croissant) ou -1 si valeur n'est pas présente. Utilisez une approche itérative.

def recherche_dichotomique(liste, valeur):
    '''
    Recherche dichotomique dans une liste triée par ordre croissant.
    '''
    gauche = 0
    droite = len(liste) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == valeur:
            return milieu
        elif liste[milieu] < valeur:
            # À compléter
        else:
            # À compléter
    return -1

1. Modifiez la fonction recherche_dichotomique pour qu'elle renvoie également le nombre d'itérations effectuées dans la boucle while avant de terminer. La fonction devra renvoyer un tuple (indice, iterations).

Exercice 3 — Bases de données (6 points)

[Contexte] On considère une base de données relationnelle contenant deux tables :

• Etudiants(id_etudiant, nom, prenom, id_classe)
• Classes(id_classe, nom_classe, niveau)

On souhaite récupérer la liste des étudiants de terminale avec leur classe.

import sqlite3

def obtenir_etudiants_terminale():
    conn = sqlite3.connect('ecole.db')
    cursor = conn.cursor()
    
    requete = """
    SELECT Etudiants.nom, Etudiants.prenom, Classes.nom_classe
    FROM Etudiants
    JOIN Classes ON Etudiants.id_classe = Classes.id_classe
    WHERE Classes.niveau = 'Terminale'
    """
    
    cursor.execute(requete)
    resultats = cursor.fetchall()
    
    conn.close()
    return resultats

# Fonction à compléter
def ajouter_etudiant(nom, prenom, id_classe):
    """Ajoute un nouvel étudiant dans la base de données"""
    conn = sqlite3.connect('ecole.db')
    cursor = conn.cursor()
    
    # À compléter
    
    conn.close()

1. Expliquez ce que fait la fonction obtenir_etudiants_terminale() et décrivez la requête SQL utilisée.

2. Proposez une version modifiée de la fonction obtenir_etudiants_terminale() qui retourne les résultats sous forme de liste de dictionnaires plutôt que de tuples.

3. Complétez la fonction ajouter_etudiant(nom, prenom, id_classe) pour qu'elle insère effectivement un nouvel étudiant dans la table Etudiants. Générez automatiquement l'id_etudiant en prenant le maximum existant + 1.