Coût des algorithmes, tris et recherche : exercices type Bac Numérique et Sciences Informatiques corrigés

Tous les exercices de Coût des algorithmes, tris et recherche tombés au Bac de Numérique et Sciences Informatiques de 2021 à 2026 (Métropole, Amérique du Nord, Asie, Polynésie…), avec le corrigé de chaque question. Fais-les dans l’ordre pour voir comment le thème est posé d’une année à l’autre.

Toutes les annales du Bac de Numérique et Sciences Informatiques · Bac blanc de Numérique et Sciences Informatiques

Coût des algorithmes, tris et recherche au Bac 2026

Exercice 2 - Coût et tri par… · Amérique du Nord 2026 (jour 2) · Questions 4 et 5 de l'exercice 2 : préciser le coût temporel dans le pire des cas du tri par insertion d'une liste de n éléments, puis…
Exercice 1 - Algorithmes et… · Asie 2026 (jour 1) · Questions 8 et 9 : Identifier le type d'algorithme correspondant à la stratégie de chargement proposée (algorithme glouton), puis citer un…
Exercice 2 - Coût d'exécution · Asie 2026 (jour 1) · Donner le coût d'exécution temporel de la méthode prediction en fonction de la taille n des entrées.
Exercice 1 - Tri par sélection… · Centres étrangers (Afrique) 2026 (jour 1) · Questions 4 à 6 : Compléter la ligne 6 de la fonction classer(), identifier l'algorithme de tri utilisé et déterminer son coût en nombre…

Coût des algorithmes, tris et recherche au Bac 2025

Exercice 2 - Coût des… · Amérique du Nord 2025 (jour 1) · Questions 6 et 7 : Identification de l'algorithme de tri utilisé dans tri_decroissant, son coût dans le pire des cas, proposition d'un…
Exercice 3 - Coût des… · Amérique du Nord 2025 (jour 1) · Questions 13 et 14 : Compléter les lignes 7 à 10 de la fonction sommets_tries réalisant un tri par ordre décroissant de degré, puis…
Exercice 3 - Tri et coût des… · Métropole 1 remplacement 2025 · Partie B : Algorithme de tri par insertion (compléter les lignes 12, 13, 15 et 17 de tri_collec), identification du tri, étude de sa…
Exercice 3 - Vérification d'une… · Nouvelle-Calédonie 2025 (jour 1) · Écrire une fonction Python teste_solution(plateau, ciblesLignes, ciblesColonnes) qui renvoie True si les sommes de chaque ligne et de…
Exercice 2 - Programmation Python · Polynésie 2025 (jour 1) · Exercice 2 : Programmation Python et modélisation du jeu du baguenaudier. Questions 1 à 6 portant sur la manipulation de listes, les…

Coût des algorithmes, tris et recherche au Bac 2024

Exercice 1 - Coût des… · Amérique du Nord 2024 (jour 2) · Donner un algorithme de tri dont le coût est strictement meilleur que celui du tri de Stooge (coût en pire cas de l'ordre de n^(8/3)).
Exercice 2 - Partie B · Métropole 2024 (sujet 2) · Partie B de l'exercice 2 : analyse d'un algorithme glouton pour le problème du sac à dos (chargement sous contrainte de volume maximal de…
Exercice 1 - Coût des… · Suède 2024 (jour 2) · Nommer et justifier un algorithme de tri classique adapté au cas où une liste est déjà triée sauf un seul élément.
Exercice 2 - Coût des… · Sujets zéro et spécimens sujet 2024 (sujet 1) · Questions 10 à 12 : Compléter la fonction Python renote_express2 implémentant une recherche dichotomique pour calculer la note d'un…

Coût des algorithmes, tris et recherche au Bac 2023

Exercice 3 · Amérique du Sud 2023 (jour 1) · Exercice sur l'algorithme de recadrage intelligent (seam carving) : calcul de la taille en mégaoctets d'une image, encadrement des indices…
Exercice 3 · Asie 2023 (jour 2) · Exercice 3 : algorithmes de parcours de liste, calcul de score et optimisation aléatoire sur un jeu de plateau.
Exercice 3 - Chaînes de… · Centres étrangers (Afrique) 2023 (jour 2) · Exercice portant sur les questions 1 et 4 : manipulation des chaînes de caractères en Python, calcul d'occurrences de lettres, puis…
Exercice 2 - Coût des algorithmes · Nouvelle-Calédonie 2023 (jour 2) · Indiquer sans justification la complexité en temps de calcul de la fonction itérative palindrome pour un mot de longueur n…
Exercice 3 - Questions 2.b, 2.c… · Polynésie 2023 (jour 1) · Questions 2.b, 2.c et 2.d : compléter la fonction liste_segments (génération exhaustive de toutes les paires non ordonnées de points…

Coût des algorithmes, tris et recherche au Bac 2022

Exercice 1 · Amérique du Sud 2022 (jour 2) · Exercice portant sur l'algorithme des k plus proches voisins : écriture du bloc de recherche du plus proche voisin (k=1), analyse de…
Exercice 2 · Amérique du Sud 2022 (jour 1) · Gestion d'une file d'attente aux urgences modélisée en Python par des tuples (identifiant, priorité) : insertion, algorithme de tri par…
Exercice 1 · Asie 2022 (jour 1) · Exercice 1 : Algorithme de détection de palindrome. Trace d'exécution sur le mot 'rotor', dénombrement des comparaisons de caractères…

Coût des algorithmes, tris et recherche au Bac 2021

Exercice 3 · Amérique du Nord 2021 (jour 1) · Programmation Python sur les tableaux : calculs de remises, recherche de minimum et ordonnancement/tri d'une liste de prix.
Exercice 2 - Recherche… · Métropole 1 remplacement 2021 · Parties A et B de l'exercice 2 : analyse de la méthode de recherche dichotomique (précondition de tri, complexité logarithmique, variant…
Exercice 1 - Tri par insertion · Polynésie 2021 (jour 2) · Parties A et B de l'exercice 1 : manipulation d'une liste Python (modification d'un élément, taille, affichage d'une tranche) et…

S’entraîner sur ce thème, avec correction

Autres thèmes de Numérique et Sciences Informatiques

Bases de données relationnelles, SGBD et langage SQL · 92 exercices
Structures de données abstraites : listes, piles, files, dictionnaires · 72 exercices
Protocoles de routage : RIP et OSPF · 58 exercices
Arbres : vocabulaire, mesures et algorithmique · 55 exercices
Programmation orientée objet : classes, attributs, méthodes · 51 exercices
Réseaux : adressage IP et sous-réseaux · 44 exercices
Architectures matérielles et systèmes d'exploitation · 33 exercices
Graphes : modélisation, implémentations et parcours · 28 exercices
Récursivité · 27 exercices
Binaire, entiers et opérateurs booléens · 18 exercices
Mise au point des programmes : bugs, assertions et tests · 16 exercices
Sécurisation des communications : chiffrement et HTTPS · 10 exercices
Programmation dynamique · 9 exercices
Diviser pour régner · 9 exercices
Modularité, API et paradigmes de programmation · 6 exercices
Recherche textuelle et algorithme de Boyer-Moore · 3 exercices
Programme comme donnée, calculabilité et décidabilité · 2 exercices