Algorithmique

Écrire une fonction indice_du_minimum(tableau) qui renvoie l'indice (et non la valeur) du plus petit élément d'un tableau non vide, quel que soit l'ordre des éléments. Tester sur [9, 4, 7, 2, 8] (résultat attendu : 3).

Écris une fonction indiceMax(T) qui retourne l'indice de l'élément maximum dans un tableau de nombres.

Exemple : pour T = [5, 11, 78, 15, 9, 2010], indiceMax(T) doit renvoyer 5.

Écris une fonction moyenne(L) qui renvoie la moyenne des éléments d'une liste, sans utiliser la fonction native sum().

Exemple : moyenne([4, 6, 2]) doit renvoyer 4.

Écris une fonction valeurMax(L) qui renvoie la valeur maximale d'une liste, sans utiliser la fonction native max().

Exemple : valeurMax([3, 12, 5, 9]) doit renvoyer 12.

On suppose qu'une liste contient au moins deux éléments de valeurs différentes. Écris une fonction deuxiemeMax(L) qui renvoie la deuxième plus grande valeur de cette liste — c'est-à-dire la plus grande valeur strictement inférieure au maximum —, sans utiliser la méthode sort().

Exemple : deuxiemeMax([4, 9, 2, 7, 9, 5]) doit renvoyer 7.

Écris une fonction estTriee(L) qui renvoie True si la liste est triée par ordre croissant, False sinon.

Exemples : estTriee([1, 3, 5, 8]) doit renvoyer True ; estTriee([1, 5, 3, 8]) doit renvoyer False.

QCM Thème A du DS NSI Première (École AlJabr, 2025/2026) — parcours de liste : accumulation et recherche du maximum via une fonction de comparaison. Photo à relire avant publication.

Question A.4. On écrit la fonction suivante :

def externe(t, test):
    m = t[0]
    for x in t:
        if test(x, m):
            m = x
    return m

On dispose d'une liste L dont les éléments sont des couples (nom, note) :

L = [('Alice', 17), ('Barnabé', 18), ('Casimir', 17), ('Doriane', 20), ('Emilien', 15), ('Fabienne', 16)]

On souhaite que l'appel externe(L, test) renvoie le couple représentant la note maximale. Quelle définition de la fonction test peut-on utiliser ?

A. def test(a, b): return a[0] < b[0] B. def test(a, b): return a[1] < b[1] C. def test(a, b): return a[0] > b[0] D. def test(a, b): return a[1] > b[1]

Question A.11. On exécute le code suivant :

tab = [1, 4, 3, 8, 2]
S = 0
for i in range(len(tab)):
    S = S + tab[i]

Que vaut la variable S à la fin de l'exécution ?

A. 1 B. 8 C. 18 D. 36

QCM Thème A du DS NSI Première (École AlJabr, 2025/2026) — compréhension de liste et algorithmes de recherche d'extremum (maximum, minimum). Photo à relire avant publication.

Question A.12. On définit :

stock = [
    {'nom': 'flageolets', 'quantité': 50, 'prix': 5.68},
    {'nom': 'caviar', 'quantité': 0, 'prix': 99.99},
    # ...
    {'nom': 'biscuits', 'quantité': 100, 'prix': 7.71},
]

Quelle expression permet d'obtenir la liste des noms des produits effectivement présents dans le stock (c'est-à-dire ceux dont la quantité n'est pas nulle) ?

A. ['nom' for p in stock if 'quantité' != 0] B. [p for p in stock if p['quantité'] != 0] C. [p['nom'] for p in stock if 'quantité' != 0] D. [p['nom'] for p in stock if p['quantité'] != 0]

Question A.13. La fonction maximum doit renvoyer la valeur maximale d'un tableau de nombres. Par quoi doit-on remplacer les pointillés pour qu'elle donne le résultat attendu ?

def maximum(T):
    maxi = T[0]
    for i in range(len(T)):
        .... T[i] > maxi:
            ......
    return maxi

A. if puis, sur la ligne suivante, maxi = T[i] B. while puis, sur la ligne suivante, maxi = T[i] C. if puis, sur la ligne suivante, maxi = maxi + 1 D. while puis, sur la ligne suivante, maxi = maxi + 1

Question A.14. Soit l'algorithme suivant, qui permet de retrouver l'index de l'élément minimum dans un tableau de données :

def minimum(T):
    index = 0
    for i in range(len(T)):
        if ......:
            index = i
    return index

Compléter l'instruction conditionnelle pour que la fonction calcule le résultat attendu :

A. i > index B. T[i] < T[index] C. T[i] > T[index] D. T[index] > T[i]

Exercice « Thème C : Algorithmique » du DS NSI Première (École AlJabr, 2025/2026) — pseudo-code à trous à compléter (séparation d'un tableau en éléments de position paire puis impaire). Photo à relire avant publication.

Exercice — Positions paire et impaire dans un tableau

Écrire un algorithme qui permet de saisir des éléments réels dans un tableau, puis de ranger dans un autre tableau les éléments du premier tableau situés en position paire d'abord, puis ceux situés en position impaire.

Algorithme
    Titre : Position
    Tableau T1[100], T2[100] : Réel
    Variable N, i : Entier
Début
    Ecrire (" Saisir le nombre d'éléments du tableau T1 ; N<=100 : ")
    Lire(N)
    Pour ............. à ............. faire
        Ecrire ("Saisir l'élément .................")
        Lire (.................)
    Fin pour
    Pour ............. à ............. faire
        T2[i] ← T1[2*i]
        T2[.................] ← T1[.................]
    Fin pour
    Pour ..................... à ............. faire
        Ecrire ("T2[", i, "] = ", T2[i])
    Fin pour
Fin

Compléter les pointillés.

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

On considère des chaînes de caractères contenant uniquement des majuscules et des caractères *, appelées mots à trous. Par exemple INFO*MA*IQUE, ***I***E** et *S* sont des mots à trous.

Programmer une fonction correspond :

• qui prend en paramètres deux chaînes de caractères mot et mot_a_trous, où mot_a_trous est un mot à trous comme indiqué ci-dessus ;
• et qui renvoie True si on peut obtenir mot en remplaçant convenablement les caractères '*' de mot_a_trous, False sinon.

Exemple :

>>> correspond('INFORMATIQUE', 'INFO*MA*IQUE')
True
>>> correspond('AUTOMATIQUE', 'INFO*MA*IQUE')
False
>>> correspond('STOP', 'S*')
False
>>> correspond('AUTO', '*UT*')
True

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

Écrire la fonction maximum_tableau, prenant en paramètre un tableau non vide de nombres tab (de type list) et renvoyant le plus grand élément de ce tableau.

Exemples :

>>> maximum_tableau([98, 12, 104, 23, 131, 9])
131
>>> maximum_tableau([-27, 24, -3, 15])
24

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

Programmer la fonction recherche, prenant en paramètre un tableau non vide tab (type list) d'entiers et un entier n, et qui renvoie l'indice de la dernière occurrence de l'élément cherché. Si l'élément n'est pas présent, la fonction renvoie None.

Exemples :

>>> recherche([5, 3],1) # renvoie None
>>> recherche([2,4],2)
0
>>> recherche([2,3,5,2,4],2)
3

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

On souhaite programmer une fonction indiquant le point le plus proche d'un point de départ dans un tableau de points. Les points sont tous à coordonnées entières et sont donnés sous la forme d'un tuple de deux entiers. Le tableau des points à traiter est donc un tableau de tuples.

On rappelle que la distance $d$ entre deux points du plan de coordonnées $(x\,;y)$ et $(x'\,;y')$ vérifie la formule :

Compléter le code des fonctions distance_carre et point_le_plus_proche fournies ci-dessous pour qu'elles répondent à leurs spécifications.

def distance_carre(point1, point2):
    """ Calcule et renvoie la distance au carre entre
    deux points."""
    return (...)**2 + (...)**2
 
def point_le_plus_proche(depart, tab):
    """ Renvoie les coordonnées du premier point du tableau tab se
    trouvant à la plus courte distance du point depart."""
    min_point = tab[0]
    min_dist = ...
    for i in range(1, len(tab)):
        if distance_carre(tab[i], depart) < ...:
            min_point = ...
            min_dist = ...
    return min_point

Exemples :

>>> distance_carre((1, 0), (5, 3))
25
>>> distance_carre((1, 0), (0, 1))
2
>>> point_le_plus_proche((0, 0), [(7, 9), (2, 5), (5, 2)])
(2, 5)
>>> point_le_plus_proche((5, 2), [(7, 9), (2, 5), (5, 2)])
(5, 2)

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

Écrire une fonction max_et_indice qui prend en paramètre un tableau non vide tab (type Python list) de nombres entiers et qui renvoie la valeur du plus grand élément de ce tableau ainsi que l'indice de sa première apparition dans ce tableau.

L'utilisation de la fonction native max n'est pas autorisée.

Exemples :

>>> max_et_indice([1, 5, 6, 9, 1, 2, 3, 7, 9, 8])
(9, 3)
>>> max_et_indice([-2])
(-2, 0)
>>> max_et_indice([-1, -1, 3, 3, 3])
(3, 2)
>>> max_et_indice([1, 1, 1, 1])
(1, 0)

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

Écrire une fonction verifie qui prend en paramètre un tableau de valeurs numériques et qui renvoie True si ce tableau est trié dans l'ordre croissant, False sinon. Un tableau vide est considéré comme trié.

Exemples :

>>> verifie([0, 5, 8, 8, 9])
True
>>> verifie([8, 12, 4])
False
>>> verifie([-1, 4])
True
>>> verifie([])
True
>>> verifie([5])
True

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

Dans cet exercice, on considère des phrases composées de mots.

• On appelle mot une chaîne de caractères composée avec des caractères choisis parmi les 26 lettres minuscules ou majuscules de l'alphabet.
• On appelle phrase une chaîne de caractères :
  • composée d'un ou de plusieurs mots séparés entre eux par un seul caractère espace ' ' ;
  • se finissant soit par un point '.', qui est alors collé au dernier mot, soit par un point d'exclamation '!' ou d'interrogation '?', qui est alors séparé du dernier mot par un seul caractère espace ' '.

Voici deux exemples de phrases :

'Cet exercice est simple.'
'Le point d exclamation est separe !'

Après avoir remarqué le lien entre le nombre de mots et le nombre de caractères espace dans une phrase, programmer une fonction nombre_de_mots qui prend en paramètre une phrase et renvoie le nombre de mots présents dans cette phrase.

>>> nombre_de_mots('Cet exercice est simple.')
4
>>> nombre_de_mots('Le point d exclamation est séparé !')
6
>>> nombre_de_mots('Combien de mots y a t il dans cette phrase ?')
10
>>> nombre_de_mots('Fin.')
1

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

Écrire une fonction recherche qui prend en paramètres elt, un nombre entier, et tab, un tableau de nombres entiers (type list), et qui renvoie l'indice de la première occurrence de elt dans tab si elt est dans tab, et None sinon.

L'objectif de cet exercice est de parcourir un tableau : il est interdit d'utiliser la méthode index des listes Python.

Exemples :

>>> recherche(1, [2, 3, 4]) # renvoie None
>>> recherche(1, [10, 12, 1, 56])
2
>>> recherche(50, [1, 50, 1])
1
>>> recherche(15, [8, 9, 10, 15])
3

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

Écrire une fonction min_et_max qui prend en paramètre un tableau de nombres tab non vide, et qui renvoie la plus petite et la plus grande valeur du tableau sous la forme d'un dictionnaire à deux clés min et max. Les tableaux sont représentés sous forme de liste Python.

L'utilisation des fonctions natives min, max et sorted, ainsi que de la méthode sort, n'est pas autorisée.

Exemples :

>>> min_et_max([0, 1, 4, 2, -2, 9, 3, 1, 7, 1])
{'min': -2, 'max': 9}
>>> min_et_max([0, 1, 2, 3])
{'min': 0, 'max': 3}
>>> min_et_max([3])
{'min': 3, 'max': 3}
>>> min_et_max([1, 3, 2, 1, 3])
{'min': 1, 'max': 3}
>>> min_et_max([-1, -1, -1, -1, -1])
{'min': -1, 'max': -1}

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

Écrire une fonction moyenne qui prend en paramètre un tableau non vide de nombres flottants et qui renvoie la moyenne des valeurs du tableau. Les tableaux sont représentés sous forme de liste Python.

Exemples :

>>> moyenne([1.0])
1.0
>>> moyenne([1.0, 2.0, 4.0])
2.3333333333333335

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

Écrire une fonction Python appelée nb_repetitions qui prend en paramètres un élément elt et un tableau tab (type list) d'éléments du même type et qui renvoie le nombre de fois où l'élément apparaît dans le tableau.

Exemples :

>>> nb_repetitions(5, [2, 5, 3, 5, 6, 9, 5])
3
>>> nb_repetitions('A', ['B', 'A', 'B', 'A', 'R'])
2
>>> nb_repetitions(12, [1, '!', 7, 21, 36, 44])
0

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

Écrire une fonction recherche_indices_classement qui prend en paramètres un entier elt et un tableau d'entiers tab représenté par une liste Python, et qui renvoie trois listes Python d'entiers :

• la première liste contient les indices des valeurs du tableau tab strictement inférieures à elt ;
• la deuxième liste contient les indices des valeurs du tableau tab égales à elt ;
• la troisième liste contient les indices des valeurs du tableau tab strictement supérieures à elt.

Exemples :

>>> recherche_indices_classement(3, [1, 3, 4, 2, 4, 6, 3, 0])
([0, 3, 7], [1, 6], [2, 4, 5])
>>> recherche_indices_classement(3, [1, 4, 2, 4, 6, 0])
([0, 2, 5], [], [1, 3, 4])
>>> recherche_indices_classement(3, [1, 1, 1, 1])
([0, 1, 2, 3], [], [])
>>> recherche_indices_classement(3, [])
([], [], [])

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

Écrire une fonction recherche_min qui prend en paramètre un tableau de nombres tab, et qui renvoie l'indice de la première occurrence du minimum de ce tableau. Les tableaux seront représentés sous forme de liste Python.

Exemples :

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

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

On considère la fonction eleves_du_mois prenant en paramètres eleves et notes deux tableaux de même longueur, le premier contenant le nom des élèves et le second, des entiers positifs désignant leur note à un contrôle de sorte que eleves[i] a obtenu la note notes[i].

Cette fonction renvoie le couple constitué de la note maximale attribuée et des noms des élèves ayant obtenu cette note regroupés dans un tableau.

Ainsi, l'instruction eleves_du_mois(['a', 'b', 'c', 'd'], [15, 18, 12, 18]) renvoie le couple (18, ['b', 'd']).

Compléter le code suivant :

def eleves_du_mois(eleves, notes):
    note_maxi = 0
    meilleurs_eleves = ...
 
    for i in range(...):
        if notes[i] == ...:
            meilleurs_eleves.append(...)
        elif notes[i] > note_maxi:
            note_maxi = ...
            meilleurs_eleves = [...]
 
    return (note_maxi, meilleurs_eleves)

Exemples :

>>> eleves_nsi = ['a','b','c','d','e','f','g','h','i','j']
>>> notes_nsi = [30, 40, 80, 60, 58, 80, 75, 80, 60, 24]
>>> eleves_du_mois(eleves_nsi, notes_nsi)
(80, ['c', 'f', 'h'])
>>> eleves_du_mois([],[])
(0, [])

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

On a relevé les valeurs moyennes annuelles des températures à Paris pour la période allant de 2013 à 2019. Les résultats ont été récupérés sous la forme de deux tableaux (de type list) : l'un pour les températures, l'autre pour les années :

t_moy = [14.9, 13.3, 13.1, 12.5, 13.0, 13.6, 13.7]
annees = [2013, 2014, 2015, 2016, 2017, 2018, 2019]

Écrire la fonction annee_temperature_minimale qui prend en paramètres ces deux tableaux et qui renvoie la plus petite valeur relevée au cours de la période et l'année correspondante.

On suppose que la température minimale est atteinte une seule fois.

Exemple :

>>> annee_temperature_minimale(t_moy, annees)
(12.5, 2016)

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

Écrire une fonction occurrences(caractere, chaine) qui prend en paramètres caractere, une chaîne de caractère de longueur 1, et chaine, une chaîne de caractères.

Cette fonction renvoie le nombre d'occurrences de caractere dans chaine, c'est-à-dire le nombre de fois où caractere apparaît dans chaine.

Exemples :

>>> occurrences('e', "sciences")
2
>>> occurrences('i',"mississippi")
4
>>> occurrences('a',"mississippi")
0

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

Écrire une fonction indices_maxi qui prend en paramètre un tableau non vide de nombres entiers tab, représenté par une liste Python et qui renvoie un tuple (maxi, indices) où :

• maxi est le plus grand élément du tableau tab ;
• indices est une liste Python contenant les indices du tableau tab où apparaît ce plus grand élément.

Exemple :

>>> indices_maxi([1, 5, 6, 9, 1, 2, 3, 7, 9, 8])
(9, [3, 8])
>>> indices_maxi([7])
(7, [0])

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

Écrire une fonction recherche qui prend en paramètres elt un nombre entier et tab un tableau de nombres entiers (type list), et qui renvoie l'indice de la dernière occurrence de elt dans tab si elt est dans tab et None sinon.

Exemples :

>>> recherche(1, [2, 3, 4]) # renvoie None
>>> recherche(1, [10, 12, 1, 56])
2
>>> recherche(1, [1, 0, 42, 7])
0
>>> recherche(1, [1, 50, 1])
2
>>> recherche(1, [8, 1, 10, 1, 7, 1, 8])
5

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

Écrire une fonction moyenne qui prend en paramètre un tableau d'entiers non vide et qui renvoie un nombre flottant donnant la moyenne de ces entiers.

Attention : il est interdit d'utiliser la fonction sum ou la fonction mean (module statistics) de Python.

Exemples :

>>> moyenne([1])
1.0
>>> moyenne([1, 2, 3, 4, 5, 6, 7])
4.0
>>> moyenne([1, 2])
1.5

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

Écrire une fonction a_doublon qui prend en paramètre un tableau trié de nombres dans l'ordre croissant et renvoie True si ce tableau contient au moins deux nombres identiques, False sinon.

Exemple :

>>> a_doublon([])
False
>>> a_doublon([1])
False
>>> a_doublon([1, 2, 4, 6, 6])
True
>>> a_doublon([2, 5, 7, 7, 7, 9])
True
>>> a_doublon([0, 2, 3])
False

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

Écrire une fonction compte_occurrences prenant en paramètres une valeur x et un tableau tab (de type list) et renvoyant le nombre d'occurrences de x dans tab.

L'objectif de cet exercice étant de parcourir un tableau, il est interdit d'utiliser la méthode count des listes Python.

Exemples :

>>> compte_occurrences(5, [])
0
>>> compte_occurrences(5, [-2, 3, 1, 5, 3, 7, 4])
1
>>> compte_occurrences('a', ['a','b','c','a','d','e','a'])
3

Banque nationale de sujets 2026 de l'épreuve pratique, sujet n°10 (situation d'évaluation d'une heure).

Consommation d'eau

Les compteurs d'eau modernes permettent de mesurer automatiquement la consommation d'un foyer. Ils enregistrent, chaque heure, plusieurs informations.

Les données sont fournies sous forme d'une liste de dictionnaires. On considère que cette liste est triée par jour et heure croissants. Chaque mesure est un dictionnaire contenant :

• "jour" : le jour de la mesure (chaîne de caractères au format "AAAA-MM-JJ") ;
• "heure" : l'heure de la mesure (chaîne de caractères au format "HH:MM") ;
• "chaude" : le volume d'eau chaude consommé en litres depuis la mesure précédente (entier) ;
• "froide" : le volume d'eau froide consommé en litres depuis la mesure précédente (entier).

Exemple de mesure :

{"jour": "2025-02-04", "heure": "08:00", "chaude": 5, "froide": 8}

La consommation totale d'une mesure est la somme de l'eau chaude et de l'eau froide. L'objectif de ce sujet est d'écrire plusieurs fonctions manipulant ces données, puis d'analyser et de corriger une fonction existante qui contient une erreur.

Question 1. Écrire une fonction total_conso qui prend en paramètres donnees, une liste de mesures, et jour, une chaîne représentant le jour (ex. "2025-02-04"), et renvoie la consommation totale d'eau (somme de l'eau chaude et de l'eau froide) de toutes les mesures pour ce jour. Par convention, si aucune mesure n'existe pour ce jour, la fonction renvoie None. Par exemple :

>>> total_conso(donnees, "2025-02-04")
33
>>> total_conso(donnees, "2025-12-25")
>>>

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 2. On considère que la nuit, quand tout le monde dort, la consommation d'eau n'est pas censée être supérieure à zéro pendant plusieurs heures consécutives. Une fuite est donc suspectée lorsqu'il y a au moins 3 mesures consécutives entre 00:00 et 05:00 inclus où la consommation totale est toujours non nulle (eau chaude + eau froide > 0).

Écrire une fonction fuite_possible qui renvoie True si une fuite est possible ce jour-là, False sinon. Cette fonction prend en paramètres donnees, une liste de mesures, et jour, une chaîne de caractères représentant la date, au format "AAAA-MM-JJ".

Cet exemple renverrait False, car il n'y a pas trois mesures consécutives non nulles :

Cet exemple renverrait True, car il y a trois mesures consécutives non nulles (00:00, 01:00, 02:00) :

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 3. Le fichier analyse_eau.py contient une fonction appelée lissage_conso censée calculer une moyenne sur 3 valeurs pour lisser les mesures de la consommation. Pour les cas particuliers :

• premier élément : faire la moyenne du premier et du deuxième ;
• dernier élément : faire la moyenne du dernier et de l'avant-dernier ;
• éléments intermédiaires : faire la moyenne de trois valeurs (précédente, actuelle, suivante).

La fonction doit toujours renvoyer une liste de même taille que la liste d'origine. Pour chaque valeur, on fait la moyenne avec ses voisins (précédent et suivant). Cependant, cette fonction contient une erreur. Expliquer pourquoi la fonction lissage_conso, testée avec la liste suivante, présente un résultat incorrect, et proposer une correction.

test = [10, 20, 30, 40, 50]

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 4. La fonction lissage_conso prend en compte les cas limites dans lesquels la liste fournie contient seulement deux valeurs. Identifier un autre cas limite qui n'est pas pris en compte par la fonction, et proposer une solution pour y remédier.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Fichier fourni : analyse_eau.py

donnees = [
    {"jour": "2025-02-04", "heure": "00:00", "chaude": 2, "froide": 3},
    {"jour": "2025-02-04", "heure": "01:00", "chaude": 1, "froide": 2},
    {"jour": "2025-02-04", "heure": "02:00", "chaude": 0, "froide": 0},
    {"jour": "2025-02-04", "heure": "03:00", "chaude": 0, "froide": 0},
    {"jour": "2025-02-04", "heure": "04:00", "chaude": 0, "froide": 1},
    {"jour": "2025-02-04", "heure": "05:00", "chaude": 0, "froide": 0},
    {"jour": "2025-02-04", "heure": "06:00", "chaude": 4, "froide": 6},
    {"jour": "2025-02-04", "heure": "07:00", "chaude": 6, "froide": 8},
    {"jour": "2025-02-05", "heure": "00:00", "chaude": 0, "froide": 0},
    {"jour": "2025-02-05", "heure": "01:00", "chaude": 1, "froide": 1},
    {"jour": "2025-02-05", "heure": "02:00", "chaude": 1, "froide": 1},
    {"jour": "2025-02-05", "heure": "03:00", "chaude": 1, "froide": 1},
    {"jour": "2025-02-05", "heure": "04:00", "chaude": 0, "froide": 0},
    {"jour": "2025-02-05", "heure": "05:00", "chaude": 0, "froide": 0},
]
 
 
# -----------------------------
# Fonctions à compléter
# -----------------------------
 
def total_conso(donnees, jour):
    # À compléter
    pass
 
 
def fuite_possible(donnees, jour):
    # À compléter
    pass
 
 
# -----------------------------
# Fonction fournie (erronée)
# -----------------------------
 
def lissage_conso(valeurs):
    """
    Calcule une moyenne glissante sur les valeurs.
    Pour chaque valeur, on calcule la moyenne avec ses voisins.
    """
 
    lisse = []
    for i in range(len(valeurs)):
        if i == 0:
            m = (valeurs[i] + valeurs[i+1]) / 2
        elif i == len(valeurs)-1:
            m = (valeurs[i-1] + valeurs[i]) / 2
        else:
            m = (valeurs[i-1] + valeurs[i] + valeurs[i+1]) / 2
        lisse.append(m)
 
    return lisse
 
 
# -----------------------------
# Espace pour les tests
# -----------------------------
 
def test_lissage():
    # À compléter : écrire au moins 3 assertions (assert) avec des listes
    # de différentes tailles pour révéler les erreurs de la fonction
    pass

Banque nationale de sujets 2026 de l'épreuve pratique, sujet n°13 (situation d'évaluation d'une heure).

Relevés d'un ballon sonde

On considère dans ce sujet un fichier CSV de données climatiques (releves_ballon_sonde.csv) de Météo-France obtenues par ballon sonde. Il est gonflé à l'aide d'un gaz léger (hélium) et est équipé d'instruments pour acquérir des paramètres tels que la température en kelvins, l'altitude en mètres et sa géolocalisation. Lorsqu'il est lâché, ce ballon sonde s'élève et collecte des données tout au long de sa trajectoire, puis éclate à une altitude appropriée, ce qui entraîne sa chute au sol avec un parachute pour amortir sa vitesse de descente. Ces données relevées sont essentielles pour les prévisions météorologiques car elles fournissent des informations sur les conditions atmosphériques à différentes altitudes. Pour simplifier l'étude, on ne dispose que de données mesurées durant la montée. (Source : CNES - Planète Sciences.)

Ce sujet propose de concevoir un script Python qui exploite les données météorologiques relevées avec :

• la conversion des valeurs de températures dans une unité plus courante ;
• une recherche de basse température et d'altitude(s) correspondante(s) ;
• la génération d'un fichier d'extension kml (Keyhole Markup Language) compatible avec de nombreuses applications de cartographie.

On donne une première fonction Python recupere_donnees_fichier_csv(nom_fichier) qui permet d'ouvrir le fichier CSV, de supprimer les en-têtes et de récupérer les données relevées sous forme de 4 listes.

Question 1. En utilisant cette fonction recupere_donnees_fichier_csv, écrire la ou les lignes de code qui récupèrent les données relevées par le ballon sonde dans 4 listes différentes (altitudes, temperatures, longitudes et latitudes).

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

La température en kelvins correspond à la température en degrés Celsius à laquelle on ajoute la valeur 273,15.

Question 2. Écrire en Python une fonction nommée conversion_K_en_C qui prend en paramètre une liste de températures en kelvins (K) et retourne cette même liste de températures, mais converties en degrés Celsius (°C). Les valeurs de températures doivent être arrondies à 1 chiffre après la virgule (commande utilisable : round(valeur, nb chiffres après la virgule)). Écrire une ligne de code permettant de tester la fonction proposée.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

On souhaite disposer d'une fonction nommée altitude_la_plus_froide qui prend en paramètres une liste d'altitudes, ainsi qu'une liste des températures en degrés Celsius. Cette fonction doit renvoyer la température la plus froide, ainsi qu'une liste contenant la ou les altitudes correspondantes. Par exemple, avec les deux listes altitudes et temperatures suivantes :

>>> altitudes = [7000, 10125, 13896, 14211]
>>> temperatures = [-35.2, -52.1, -57.4, -57.4]
>>> altitude_la_plus_froide(altitudes, temperatures)
(-57.4, [13896, 14211])
>>> altitudes = [6000, 7250, 11542, 15214, 17300]
>>> temperatures = [-33.7, -45, -53, -58.5, -60.1]
>>> altitude_la_plus_froide(altitudes, temperatures)
(-60.1, [17300])

Question 3. Proposer une écriture de la fonction altitude_la_plus_froide.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

On donne une deuxième fonction Python genere_kml qui prend en paramètres 2 listes (liste_longitudes et liste_latitudes), qui sont les données relevées de géolocalisation du ballon sonde, et les utilise pour générer un fichier d'extension kml. Ce format normalisé utilise des balises ouvrantes et fermantes.

Question 4. Observer le corps de la fonction genere_kml, puis, à l'aide d'une assertion, insérer une ligne de code qui garantit que les deux listes liste_longitudes et liste_latitudes sont de même longueur.

Question 5. Écrire une ligne de code qui appelle la fonction genere_kml avec les deux listes de longitudes et latitudes obtenues à la question 1, puis ouvrir le fichier kml généré dans le même répertoire que le fichier Python.

Après analyse, il s'avère que ce fichier kml généré pose des problèmes de compatibilité avec certains logiciels de cartographie. En effet, la balise kml n'a pas été fermée en toute fin de fichier (</kml> absente).

Question 6. Proposer une amélioration du code visant à répondre à cette difficulté.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Fichiers fournis

Le dossier comporte une version PDF de l'énoncé, le code source de départ etude_climatique.py et le fichier de données météorologiques releves_ballon_sonde.csv.

etude_climatique.py

# ///////////////////////////////////////////////////////////////////////////
# FONCTIONS DONNEES
# ///////////////////////////////////////////////////////////////////////////
 
def recupere_donnees_fichier_csv(nom_fichier):
    """ Fonction qui récupère les données relevées du ballon sonde sans les en-têtes de la 1ère ligne """
    altitudes = []                                  # Initialisation des listes de valeurs relevées
    temperatures = []
    longitudes = []
    latitudes = []
    # Ouverture du fichier csv au format releves_ballon_sonde.csv en mode "read"
    contenu_fichier = open(nom_fichier, 'r')
    # Supprime la 1ère ligne avec les en-têtes
    contenu_fichier.readline()
    # Parcours des lignes du fichier csv contenant les donnees relevées
    for ligne in contenu_fichier.readlines():
        # rstrip() supprime les \n et espaces en fin de ligne
        ligne = ligne.rstrip()
        # création d'une listeValeurs. split(";") sépare les valeurs grâce au ;
        listeValeurs = ligne.split(";")
        # conversion string en int de l'altitude et insertion dans la liste correspondante
        altitudes.append(int(listeValeurs[0]))
        # conversion string en float de la température et insertion dans la liste correspondante
        temperatures.append(float(listeValeurs[1]))
        # conversion string en float de la longitude et insertion dans la liste correspondante
        longitudes.append(float(listeValeurs[2]))
        # conversion string en float de la latitude et insertion dans la liste correspondante
        latitudes.append(float(listeValeurs[3]))
 
    contenu_fichier.close()
    return altitudes, temperatures, longitudes, latitudes
 
 
def genere_kml(liste_longitudes, liste_latitudes):
    """ Fonction qui génère un fichier de données géographiques au format standard international KML
        Ce fichier est visionnable ensuite dans différents logiciels
    """
    fichier_kml = open(
        'ballon sonde.kml', 'w')    # Création et ouverture du fichier kml en mode "write"
    entete_fichier = '<?xml version="1.0" encoding="UTF-8"?>\n'
    entete_fichier += '<kml xmlns="http://www.opengis.net/kml/2.2">\n'
    entete_fichier += '<Document>\n'
    entete_fichier += '<name>Trajectoire ballon sonde</name>\n'
    # Ecriture du contenu de la variable entete_fichier dans le fichier kml
    fichier_kml.write(entete_fichier)
    for i in range(len(liste_longitudes)):
        corps_fichier = '<Placemark>\n'
        corps_fichier += f'<name>Point {i}</name>\n'
        corps_fichier += '<Point>\n'
        corps_fichier += f'<coordinates>{liste_longitudes[i]},{liste_latitudes[i]}</coordinates>\n'
        corps_fichier += '</Point>\n'
        corps_fichier += '</Placemark>\n'
        fichier_kml.write(corps_fichier)
    bas_fichier = '</Document>\n'
    fichier_kml.write(bas_fichier)
    fichier_kml.close()                         # Fermeture du fichier kml
 
 
# ///////////////////////////////////////////////////////////////////////////
# TRAVAIL DEMANDE
# ///////////////////////////////////////////////////////////////////////////
 
# QUESTION 1
# Compléter ici
 
# QUESTION 2
def conversion_K_en_C(liste_temperatures):
    pass  # Ajuster la fonction
 
# QUESTION 3
 
 
def altitude_la_plus_froide(liste_altitudes, liste_temperatures):
    pass  # Ajuster la fonction
 
# AUTRES ELEMENTS DE CODE

releves_ballon_sonde.csv (début du fichier, 20 relevés en tout)

Altitude_m;Temperature_K;Longitude;Latitude
0;288.15;4.760467;45.602117
200;286.85;4.760467;45.602167
500;284.85;4.761183;45.60125
1100;281.05;4.766717;45.600117
1800;276.55;4.765183;45.60085
...

Dérouler à la main le tri par insertion sur le tableau [4, 1, 3, 2], en indiquant l'état du tableau après chaque itération de la boucle for (pour j = 1, puis j = 2, puis j = 3). Vérifier ensuite le résultat avec la fonction tri_insertion du cours.

QCM Thème A du DS NSI Première (École AlJabr, 2025/2026) — complexité du tri par insertion et nombre d'échanges d'un tri par propagation (« tri à bulles »). Photo à relire avant publication.

Question A.15. Soit T le temps nécessaire pour trier, à l'aide de l'algorithme du tri par insertion, une liste de 1000 nombres entiers. Quel est l'ordre de grandeur du temps nécessaire, avec le même algorithme, pour trier une liste de 10 000 entiers, c'est-à-dire une liste dix fois plus grande ?

A. à peu près le même temps T B. environ 10 × T C. environ 100 × T D. environ T au carré

Question A.16. Quel est le coût (complexité) d'un algorithme de tri par insertion, dans le pire des cas ?

A. Constant B. Logarithmique C. Linéaire D. Quadratique

Question A.17. Combien d'échanges effectue la fonction Python suivante pour trier un tableau de 10 éléments, au pire des cas ?

def tri(tab):
    for i in range(1, len(tab)):
        for j in range(len(tab) - i):
            if tab[j] > tab[j+1]:
                tab[j], tab[j+1] = tab[j+1], tab[j]

A. 10 B. 45 C. 55 D. 100

Exercice « Thème B : Les Tris », Exercice B.1 (20 points), DS NSI Première (École AlJabr, 2025/2026) — tri par insertion pas à pas. Photo à relire avant publication.

Exercice B.1

On considère le tableau [22, 43, 10, 6, 18, 19]. En complétant, pour chaque étape, la valeur à insérer, les valeurs décalées, le rang d'insertion final et le nombre de comparaisons effectuées, dérouler pas à pas le tri par insertion de ce tableau jusqu'à ce qu'il soit entièrement trié. Nommer le type de tri utilisé, puis écrire le programme Python correspondant.

Exercice « Thème B : Les Tris », Exercice B.2 (10 points), DS NSI Première (École AlJabr, 2025/2026) — identifier un algorithme de tri à partir de son code. Photo à relire avant publication.

Exercice B.2

Soit le programme d'un tri suivant :

L1 = [56, 62, 18, 91, 84, 2, 3]
 
def tri(L):
    for i in range(0, len(L)-1):
        imin = i
        for j in range(i+1, len(L)):
            if L[j] > L[imin]:
                imin = j
        if imin != i:
            t = L[i]
            L[i] = L[imin]
            L[imin] = t
        print(L)
    return L
 
print(tri(L1))

Quel type de tri est utilisé ? Afficher le résultat détaillé de ce tri (c'est-à-dire tout ce qu'affiche l'exécution du programme).

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

On considère l'algorithme de tri de tableau suivant : à chaque étape, on parcourt le sous-tableau des éléments non rangés et on place le plus petit élément en première position de ce sous-tableau.

Exemple avec le tableau t = [41, 55, 21, 18, 12, 6, 25] :

• Étape 1 : on parcourt tous les éléments du tableau, on permute le plus petit élément avec le premier. Le tableau devient t = [6, 55, 21, 18, 12, 41, 25].
• Étape 2 : on parcourt tous les éléments sauf le premier, on permute le plus petit élément trouvé avec le second. Le tableau devient t = [6, 12, 21, 18, 55, 41, 25].

Et ainsi de suite. Le programme ci-dessous implémente cet algorithme.

def echange(tab, i, j):
    '''Echange les éléments d'indice i et j dans le tableau tab.'''
    temp = ...
    tab[i] = ...
    tab[j] = ...
 
def tri_selection(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri par sélection.'''
    N = len(tab)
    for k in range(...):
        imin = ...
        for i in range(..., N):
            if tab[i] < ...:
                imin = i
        echange(tab, ..., ...)

Compléter ce code de façon à obtenir :

>>> tab = [41, 55, 21, 18, 12, 6, 25]
>>> tri_selection(tab)
>>> tab
[6, 12, 18, 21, 25, 41, 55]

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

La fonction tri_insertion suivante prend en argument un tableau tab (type list) et trie ce tableau en utilisant la méthode du tri par insertion. Compléter cette fonction pour qu'elle réponde à la spécification demandée.

On rappelle le principe du tri par insertion : on considère les éléments à trier un par un, le premier élément constituant, à lui tout seul, un tableau trié de longueur 1. On range ensuite le second élément pour constituer un tableau trié de longueur 2, puis on range le troisième élément pour avoir un tableau trié de longueur 3, et ainsi de suite. À chaque étape, le premier élément du sous-tableau non trié est placé dans le sous-tableau des éléments déjà triés de sorte que ce sous-tableau demeure trié. Le principe du tri par insertion est donc d'insérer, à la n-ième itération, le n-ième élément à la bonne place.

def tri_insertion(tab):
    '''Trie le tableau tab par ordre croissant
    en appliquant l'algorithme de tri par insertion'''
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = ...
        # la variable j sert à déterminer
        # où placer la valeur à ranger
        j = ...
        # tant qu'on n'a pas trouvé la place de l'élément à
        # insérer on décale les valeurs du tableau vers la droite
        while j > ... and valeur_insertion < tab[...]:
            tab[j] = tab[j-1]
            j = ...
        tab[j] = ...

Exemple :

>>> tab = [98, 12, 104, 23, 131, 9]
>>> tri_insertion(tab)
>>> tab
[9, 12, 23, 98, 104, 131]

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

On veut trier par ordre croissant les notes d'une évaluation, qui sont des nombres entiers compris entre 0 et 10 (inclus). Ces notes sont contenues dans un tableau notes_eval (type list).

Écrire une fonction effectif_notes prenant en paramètre le tableau notes_eval et renvoyant un tableau de longueur 11 tel que la valeur d'indice i soit le nombre de notes valant i dans le tableau notes_eval.

Écrire ensuite une fonction notes_triees prenant en paramètre le tableau des effectifs des notes et renvoyant un tableau contenant les mêmes valeurs que notes_eval, mais triées dans l'ordre croissant.

Exemple :

>>> notes_eval = [2, 0, 5, 9, 6, 9, 10, 5, 7,
                  9, 9, 5, 0, 9, 6, 5, 4]
>>> eff = effectif_notes(notes_eval)
>>> eff
[2, 0, 1, 0, 1, 4, 2, 1, 0, 5, 1]
>>> notes_triees(eff)
[0, 0, 2, 4, 5, 5, 5, 5, 6, 6, 7, 9, 9, 9, 9, 9, 10]

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

Écrire une fonction tri_selection qui prend en paramètre un tableau tab de nombres entiers (type list) et qui le modifie afin qu'il soit trié par ordre croissant. On utilisera l'algorithme suivant :

• on recherche le plus petit élément du tableau, en le parcourant du rang 0 au dernier rang, et on l'échange avec l'élément d'indice 0 ;
• on recherche ensuite le plus petit élément du tableau restreint du rang 1 au dernier rang, et on l'échange avec l'élément d'indice 1 ;
• on continue de cette façon jusqu'à ce que le tableau soit entièrement trié.

Exemple :

>>> tab = [1, 52, 6, -9, 12]
>>> tri_selection(tab)
>>> tab
[-9, 1, 6, 12, 52]

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

On considère la fonction insere ci-dessous, qui prend en argument un tableau tab d'entiers triés par ordre croissant et un entier a. Cette fonction crée et renvoie un nouveau tableau à partir de celui fourni en paramètre, en y insérant la valeur a de sorte que le tableau renvoyé soit encore trié par ordre croissant. Les tableaux sont représentés sous la forme de listes Python.

def insere(tab, a):
    """
    Insère l'élément a (int) dans le tableau tab (list)
    trié par ordre croissant à sa place et renvoie le
    nouveau tableau.
    """
    tab_a = [ a ] + tab # nouveau tableau contenant a
                        # suivi des éléments de tab
    i = 0
    while i < ... and a > ...:
        tab_a[i] = ...
        tab_a[i+1] = a
        i = ...
    return tab_a

Compléter la fonction insere ci-dessus.

Exemples :

>>> insere([1, 2, 4, 5], 3)
[1, 2, 3, 4, 5]
>>> insere([1, 2, 7, 12, 14, 25], 30)
[1, 2, 7, 12, 14, 25, 30]
>>> insere([2, 3, 4], 1)
[1, 2, 3, 4]
>>> insere([], 1)
[1]

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

La fonction tri_bulles prend en paramètre un tableau tab d'entiers (type list) et le modifie pour le trier par ordre croissant.

Le tri à bulles est un tri en place qui commence par placer le plus grand élément en dernière position en parcourant le tableau de gauche à droite et en échangeant au passage les éléments voisins mal ordonnés (si l'élément d'indice i a une valeur strictement supérieure à celle de l'élément d'indice i + 1, ils sont échangés). Le tri place ensuite en avant-dernière position le plus grand élément du tableau privé de son dernier élément, en procédant encore à des échanges d'éléments voisins. Ce principe est répété jusqu'à placer le minimum en première position.

Exemple : pour trier le tableau [7, 9, 4, 3] :

• première étape : 7 et 9 ne sont pas échangés, puis 9 et 4 sont échangés, puis 9 et 3 sont échangés ; le tableau est alors [7, 4, 3, 9] ;
• deuxième étape : 7 et 4 sont échangés, puis 7 et 3 sont échangés ; le tableau est alors [4, 3, 7, 9] ;
• troisième étape : 4 et 3 sont échangés ; le tableau est alors [3, 4, 7, 9].

Compléter le code Python ci-dessous, qui implémente la fonction tri_bulles.

def echange(tab, i, j):
    '''Echange les éléments d'indice i et j dans le tableau tab.'''
    temp = ...
    tab[i] = ...
    tab[j] = ...
 
def tri_bulles(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri à bulles.'''
    n = len(tab)
    for i in range(...):
        for j in range(...):
            if ... > ...:
                echange(tab, j, ...)

Exemples :

>>> tab = []
>>> tri_bulles(tab)
>>> tab
[]
>>> tab2 = [9, 3, 7, 2, 3, 1, 6]
>>> tri_bulles(tab2)
>>> tab2
[1, 2, 3, 3, 6, 7, 9]
>>> tab3 = [9, 7, 4, 3]
>>> tri_bulles(tab3)
>>> tab3
[3, 4, 7, 9]

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

On considère un tableau d'entiers tab (de type list) dont les éléments sont des 0 ou des 1. On se propose de trier ce tableau selon l'algorithme suivant : à chaque étape du tri, le tableau est constitué de trois zones consécutives, la première ne contenant que des 0, la seconde n'étant pas triée et la dernière ne contenant que des 1. Au départ, les zones ne contenant que des 0 et des 1 sont vides.

[0, ..., 0, <zone non triée>, 1, ..., 1]

Tant que la zone non triée n'est pas réduite à un seul élément, on regarde son premier élément :

• si cet élément vaut 0, on considère qu'il appartient désormais à la zone ne contenant que des 0 ;
• si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on considère alors qu'il appartient à la zone ne contenant que des 1.

Dans tous les cas, la longueur de la zone non triée diminue de 1.

Compléter la fonction tri suivante :

def tri(tab):
    '''tab est un tableau d'entiers contenant des 0 et des 1.
    La fonction trie ce tableau en plaçant tous les 0 à gauche'''
    i = ... # premier indice de la zone non triée
    j = ... # dernier indice de la zone non triée
    while i < j:
        if tab[i] == 0:
            i = ...
        else:
            valeur = ...
            tab[j] = ...
            ...
            j = ...

Exemple :

>>> tab = [0,1,0,1,0,1,0,1,0]
>>> tri(tab)
>>> tab
[0, 0, 0, 0, 0, 1, 1, 1, 1]

Modifier la fonction recherche_dichotomique pour qu'elle renvoie, en plus du booléen trouvé/non trouvé, le nombre d'itérations effectuées par la boucle while. Tester sur le tableau [1, 2, 5, 9, 10, 14, 17, 24, 41] en recherchant la valeur 41.

On utilise la fonction recherche_dichotomique du cours sur le tableau [1, 2, 5, 9, 10, 14, 17, 24, 41], en recherchant la valeur 12, qui n'est pas présente dans ce tableau.

1. Dérouler l'exécution de la boucle : indiquer, à chaque tour, les valeurs de debut, fin, centre et tableau[centre], la comparaison effectuée, et l'action qui en résulte.
2. À quel moment la boucle s'arrête-t-elle ? Que vaut alors debut par rapport à fin ?
3. Que renvoie la fonction dans ce cas ?
4. En reprenant le variant de boucle $v = \text{fin} - \text{debut}$ défini dans le cours, donner la valeur de v au début de chacun des tours de boucle identifiés à la question 1. Vérifier qu'elle décroît strictement à chaque tour, et qu'elle serait devenue négative au tour suivant (ce qui explique l'arrêt de la boucle).

D'après une fiche d'exercices de NSI Première.

1. Recherche séquentielle. Écrire une fonction recherche(T, val) qui parcourt la liste T et renvoie True dès qu'elle trouve val, False si elle a tout parcouru sans la trouver. La tester sur T = [3, 5, 12, 15, 48] avec les valeurs 3, 12, 48 et 4. Dans le pire cas, combien de comparaisons fait-elle pour une liste de taille N ?

2. Recherche dichotomique. Un camarade a traduit en Python le pseudo-code suivant, trouvé sur une fiche :

i_debut ← 0 ; i_fin ← N-1 ; trouve ← faux
Tant que non trouve et i_debut <= i_fin :
    i_milieu ← (i_debut + i_fin) // 2
    si liste[i_milieu] == val : trouve ← vrai
    sinon si val > liste[i_milieu] : i_debut ← i_milieu + 1
    sinon : i_droit ← i_milieu - 1

Avec T = [3, 5, 12, 15, 48], son programme trouve 48 et 12, mais ne s'arrête jamais quand on cherche 3. Trouver l'erreur, puis écrire une fonction correcte recherche_dichotomique(liste, val) qui renvoie l'indice de val, ou None si elle est absente.

3. On appelle « étape » un passage dans la boucle. Compléter le tableau du nombre maximal d'étapes pour une liste triée de taille N :

Combien d'étapes pour 4096 éléments ? Pour $2^n$ éléments ? Comparer avec la recherche séquentielle.

4. Montrer que la boucle de la recherche dichotomique se termine, à l'aide d'un variant.

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

Soit tab un tableau non vide d'entiers triés dans l'ordre croissant et x un entier.

La fonction chercher ci-dessous doit renvoyer un indice où la valeur x apparaît dans tab si cette valeur y figure et None sinon.

Les paramètres de la fonction sont :

• tab, le tableau dans lequel s'effectue la recherche ;
• x, l'entier à chercher dans le tableau ;
• i, l'indice de début de la partie du tableau où s'effectue la recherche ;
• j, l'indice de fin de la partie du tableau où s'effectue la recherche.

L'algorithme demandé est une recherche dichotomique récursive.

Recopier et compléter le code de la fonction chercher suivante :

def chercher(tab, x, i, j):
    '''Renvoie l'indice de x dans tab, si x est dans tab,
    None sinon.
    On suppose que tab est trié dans l'ordre croissant.'''
    if i > j:
        return None
    m = (i + j) // ...
    if ... < x:
        return chercher(tab, x, ... , ...)
    elif tab[m] > x:
        return chercher(tab, x, ... , ...)
    else:
        return ...

Exemples :

>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 10)
>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 5)
>>> chercher([1, 5, 6, 6, 9, 12], 9, 0, 5)
4
>>> chercher([1, 5, 6, 6, 9, 12], 6, 0, 5)
2

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

On s'intéresse dans cet exercice à la recherche dichotomique dans un tableau trié d'entiers.

Compléter la fonction suivante en respectant la spécification.

def dichotomie(tab, x):
    """
    tab : tableau d'entiers trié dans l'ordre croissant
    x : nombre entier
    La fonction renvoie True si tab contient x et False sinon
    """
    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = ...
        if x == tab[m]:
            return ...
        if x > tab[m]:
            debut = m + 1
        else:
            fin = ...
    return ...

Exemples :

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27)
False

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

Le but de l'exercice est de compléter une fonction qui détermine si une valeur est présente dans un tableau de valeurs triées dans l'ordre croissant.

Compléter l'algorithme de dichotomie donné ci-après.

def dichotomie(tab, x):
    """applique une recherche dichotomique pour déterminer
    si x est dans le tableau trié tab.
    La fonction renvoie True si tab contient x et False sinon"""
    debut = 0
    fin = ...
    while debut <= fin:
        m = ...
        if x == tab[m]:
            return ...
        if x > tab[m]:
            debut = ...
        else:
            fin = ...
    return False

Exemples :

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27)
False
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 1)
False
>>> dichotomie([], 28)
False

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

Écrire une fonction recherche qui prend en paramètres un tableau tab de nombres entiers triés par ordre croissant et un nombre entier n, et qui effectue une recherche dichotomique du nombre entier n dans le tableau non vide tab.

Cette fonction doit renvoyer un indice correspondant au nombre cherché s'il est dans le tableau, None sinon.

Exemples :

>>> recherche([2, 3, 4, 5, 6], 5)
3
>>> recherche([2, 3, 4, 6, 7], 5) # renvoie None

On reprend l'échantillon echantillon défini dans le cours. Écrire deux appels à predire_classe pour prédire la classe du point (1, 1), d'abord avec k = 1, puis avec k = 5. Expliquer pourquoi les deux résultats sont identiques ou différents.

On dispose d'un système de pièces fictif [1, 6, 10]. Utiliser la fonction rendu_monnaie du cours pour rendre la somme 12. Combien de pièces l'algorithme glouton utilise-t-il ? Existe-t-il une solution utilisant moins de pièces ? Conclure sur la fiabilité des algorithmes gloutons.

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

On dispose d'un ensemble d'objets dont on connaît, pour chacun, la masse. On souhaite ranger l'ensemble de ces objets dans des boîtes identiques de telle manière que la somme des masses des objets contenus dans une boîte ne dépasse pas la capacité c de la boîte. On souhaite utiliser le moins de boîtes possible pour ranger cet ensemble d'objets.

Pour résoudre ce problème, on utilisera un algorithme glouton consistant à placer chacun des objets dans la première boîte où cela est possible.

Par exemple, pour ranger dans des boîtes de capacité c = 5 un ensemble de trois objets dont les masses sont représentées en Python par la liste [1, 5, 2], on procède de la façon suivante :

• Le premier objet, de masse 1, va dans une première boîte.
• Le deuxième objet, de masse 5, ne peut pas aller dans la même boîte que le premier objet car cela dépasserait la capacité de la boîte. On place donc cet objet dans une deuxième boîte.
• Le troisième objet, de masse 2, va dans la première boîte.

On a donc utilisé deux boîtes de capacité c = 5 pour ranger les 3 objets.

Compléter la fonction Python empaqueter(liste_masses, c) suivante pour qu'elle renvoie le nombre de boîtes de capacité c nécessaires pour empaqueter un ensemble d'objets dont les masses sont contenues dans la liste liste_masses. On supposera que toutes les masses sont inférieures ou égales à c.

def empaqueter(liste_masses, c):
    """Renvoie le nombre minimal de boîtes nécessaires pour
    empaqueter les objets de la liste liste_masses, sachant
    que chaque boîte peut contenir au maximum c kilogrammes"""
    n = len(liste_masses)
    nb_boites = 0
    boites = [ 0 for _ in range(n) ]
    for masse in ...:
        i = 0
        while i < nb_boites and boites[i] + ... > c:
            i = i + 1
        if i == nb_boites:
            ...
        boites[i] = ...
    return ...

Exemples :

>>> empaqueter([1, 2, 3, 4, 5], 10)
2
>>> empaqueter([1, 2, 3, 4, 5], 5)
4
>>> empaqueter([7, 6, 3, 4, 8, 5, 9, 2], 11)
5

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

On s'intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d'une liste donnée de valeurs de pièces et de billets.

Le système monétaire est donné sous forme d'une liste valeurs = [100, 50, 20, 10, 5, 2, 1]. On suppose que les pièces et les billets sont disponibles sans limitation.

On cherche à donner la liste des valeurs à rendre pour une somme donnée en argument. L'algorithme utilisé est de type glouton.

Compléter le code Python ci-dessous de la fonction rendu_glouton qui implémente cet algorithme et renvoie la liste des pièces à rendre.

valeurs = [100, 50, 20, 10, 5, 2, 1]
 
def rendu_glouton(a_rendre, rang):
    if a_rendre == 0:
        return ...
    v = valeurs[rang]
    if v <= ...:
        return ... + rendu_glouton(a_rendre - v, rang)
    else:
        return rendu_glouton(a_rendre, ...)

On devra obtenir :

>>> rendu_glouton(67, 0)
[50, 10, 5, 2]
>>> rendu_glouton(291, 0)
[100, 100, 50, 20, 20, 1]
>>> rendu_glouton(291,1) # si on ne dispose pas de billets de 100
[50, 50, 50, 50, 50, 20, 20, 1]

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

On considère dans cet exercice un algorithme glouton pour le rendu de monnaie. Pour rendre une somme en monnaie, on utilise à chaque fois la plus grosse pièce possible et ainsi de suite jusqu'à ce que la somme restante à rendre soit nulle.

Les pièces de monnaie utilisées sont :

pieces = [1, 2, 5, 10, 20, 50, 100, 200]

On souhaite écrire une fonction rendu_monnaie qui prend en paramètres :

• un entier somme_due représentant la somme à payer ;
• un entier somme_versee représentant la somme versée qui est supérieure ou égale à somme_due ;

et qui renvoie un tableau de type list contenant les pièces qui composent le rendu de la monnaie restante, c'est-à-dire de somme_versee - somme_due.

Ainsi, l'instruction rendu_monnaie(452, 500) renvoie le tableau [20, 20, 5, 2, 1].

En effet, la somme à rendre est de 48 euros soit 20 + 20 + 5 + 2 + 1.

Le code de la fonction rendu_monnaie est donné ci-dessous :

def rendu_monnaie(somme_due, somme_versee):
    '''Renvoie la liste des pièces à rendre pour rendre la monnaie
    lorsqu'on doit rendre somme_versee - somme_due'''
    rendu = ...
    a_rendre = ...
    i = len(pieces) - 1
    while a_rendre > ...:
        while pieces[i] > a_rendre:
            i = i - 1
        rendu.append(...)
        a_rendre = ...
    return rendu

Compléter ce code et le tester :

>>> rendu_monnaie(700, 700)
[]
>>> rendu_monnaie(102, 500)
[200, 100, 50, 20, 20, 5, 2, 1]

Banque nationale de sujets 2026 de l'épreuve pratique, sujet n°11 (situation d'évaluation d'une heure).

Habitats du renard

Le renard est un animal qui peut habiter dans plusieurs types d'habitats pouvant être des plaines, des montagnes, des environnements ruraux, périurbains, voire urbains. La loi Biodiversité de 2016 ainsi que l'arrêté du 3 août 2023 prévoient que le renard n'est plus un animal « nuisible » mais « susceptible d'être nuisible ».

Malgré la loi, le renard est souvent chassé des zones où il pourrait normalement évoluer et réguler la faune. Pour éviter certaines dérives, il est recommandé de surveiller la population de renards dans les zones concernées et donc de prédire si un renard peut habiter cette zone.

Pour la prédiction des zones habitables d'un renard, on considère les caractéristiques suivantes : la végétation, la proximité de l'eau, la densité urbaine et la disponibilité de proies. Ces caractéristiques sont toutes mesurées sur une échelle de 1 à 10. De plus, on dispose pour les zones connues d'une caractéristique supplémentaire indiquant, par un booléen, la présence d'un renard.

Pour évaluer la possibilité qu'un renard puisse habiter une zone non encore connue, on va utiliser la méthode des $k$ plus proches voisins en la comparant aux zones connues.

Le jeu de données est fourni dans le fichier donnees_habitats.py, dont une partie du contenu est ci-après :

zones_connues = [
    {'vegetation': 9, 'proximite_eau': 6, 'densite_urbaine': 0,
     'disponibilite_proies': 4, 'presence_renard': True},
    {'vegetation': 10, 'proximite_eau': 5, 'densite_urbaine': 9,
     'disponibilite_proies': 10, 'presence_renard': False}
]

Le fichier prediction_habitat.py contient des fonctions qui seront nécessaires à l'évaluation de ces zones et qui devront être complétées, modifiées ou implémentées.

Si $h$ est un habitat de végétation $v$, de proximité de l'eau $p$, de densité urbaine $u$ et de disponibilité des proies $d$, et $h'$ un habitat ayant, de même, les caractéristiques $v'$, $p'$, $u'$, $d'$, on définit la distance $\delta$ entre $h$ et $h'$ par la formule :

Question 1. Écrire le code de la fonction distance qui prend en paramètres deux habitats sous la forme de dictionnaires contenant au moins les clés 'vegetation', 'proximite_eau', 'densite_urbaine', 'disponibilite_proies' et qui renvoie la distance entre ces deux habitats selon la formule présentée au-dessus. On rappelle que la racine carrée peut être calculée avec la fonction sqrt du module math.

Question 2. Écrire le code de la fonction distance_d_un_habitat qui prend en paramètres un habitat sous la forme de dictionnaire et une liste d'habitats sous la forme de liste de dictionnaires. La fonction doit renvoyer une liste de tuples où chaque tuple contient :

• la distance entre l'habitat fourni et un habitat de la liste donnée ;
• le dictionnaire représentant l'habitat.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 3. Tester la fonction distance_d_un_habitat avec l'habitat nouveau et la liste d'habitats fournis, en affichant les 3 premiers tuples de la liste. Les résultats attendus sont indiqués ci-dessous.

(7.211102550927978, {'vegetation': 9, 'proximite_eau': 6,
  'densite_urbaine': 0, 'disponibilite_proies': 4, 'presence_renard': True})
(8.660254037844387, {'vegetation': 10, 'proximite_eau': 5,
  'densite_urbaine': 9, 'disponibilite_proies': 10, 'presence_renard': False})
(5.196152422706632, {'vegetation': 8, 'proximite_eau': 5,
  'densite_urbaine': 1, 'disponibilite_proies': 6, 'presence_renard': False})

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

La fonction presence_renard renvoie True s'il y a un renard qui habite dans plus de la moitié des $k$ habitats traités, False sinon.

Question 4. La fonction presence_renard contient une erreur de traitement des tuples. Corriger la fonction presence_renard.

Question 5. L'habitat nouveau proposé est-il susceptible ou non de contenir une population de renards ? Expliquer en utilisant la fonction précédente avec plusieurs valeurs pour $k$.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Fichiers fournis

Le dossier comporte une version PDF de l'énoncé, le code source de départ prediction_habitat.py et le jeu de données donnees_habitats.py (1 001 zones connues), qui doit être importé.

prediction_habitat.py

from math import sqrt
from donnees_habitats import zones_connues
 
nouveau = {'vegetation': 5, 'proximite_eau': 2,
           'densite_urbaine': 4, 'disponibilite_proies': 6}
 
 
def distance(habitat_1, habitat_2):
    '''
    Calcule la distance euclidienne entre deux habitats.
    entrée : 
        - habitat_1 : dictionnaire représentant un habitat.
        - habitat_2 : dictionnaire représentant un autre habitat.
    sortie : 
        - float : distance euclidienne entre habitat_1 et habitat_2.
    '''
    pass  # à remplacer par votre code
 
 
def distance_d_un_habitat(habitat, habitats):
    '''
    Calcule la distance entre un habitat et chaque habitat de la liste.
    entrée : 
        - habitat : dictionnaire représentant un habitat.
        - habitats : liste de dictionnaires représentant des habitats.
    sortie : 
        - list[tuple] : liste de tuples (distance, habitat) où distance est la distance entre habitat et chaque habitat de la liste.
    '''
    pass  # à remplacer par votre code
 
 
def premiere_composante(c):
    '''Fonction utilitaire renvoyant la première composante d'un tuple'''
    return c[0]
 
 
def k_plus_proches(k, habitat, habitats):
    '''
    Calcule les k habitats les plus proches de l'habitat donné.
    entrée : 
        - k : entier représentant le nombre d'habitats à retourner.
        - habitat : dictionnaire représentant un habitat.
        - habitats : liste de dictionnaires représentant des habitats.
    sortie : 
        - list[tuple] : liste de tuples (distance, habitat) l'élément à l'indice 0 est la distance euclidienne entre habitat 
                        et chaque habitat de la liste et l'élément à l'indice 1 est le dictionnaire correspondant à l'habitat correspondant.
    '''
    # On calcule les distances
    distances = distance_d_un_habitat(habitat, habitats)
    # On cherche à trier les distances en fonction de la distance euclidienne.
    distances.sort(key=premiere_composante)
    # renvoie les distances jusque la borne k non comprise
    return distances[:k]
 
 
def presence_renard(k, habitat, habitats):
    '''
    Vérifie si l'habitat donné a plus de k/2 voisins avec des renards.
    entrée : 
        - k : entier représentant le nombre d'habitats à considérer.
        - habitat : dictionnaire représentant un habitat.
        - habitats : liste de dictionnaires représentant des habitats.
    sortie : 
        - bool : True si l'habitat a plus de k/2 voisins avec des renards, False sinon.
    '''
    habitats = k_plus_proches(k, habitat, habitats)
    n_renards = 0
    for habitat in habitats:
        distance = habitat[0]
        caracteristiques = habitat[1]
        if distance['presence_renard']:
            n_renards += 1
    return n_renards > k/2