Exercices de Coût des algorithmes, tris et recherche · Bac Asie

4 exercices de Coût des algorithmes, tris et recherche tombés au Bac de Numérique et Sciences Informatiques (Asie) (2022-2026). Avec corrigé détaillé.

Exercice 1 - Algorithmes et complexité · 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 algorithme de tri vu en cours et donner l'ordre de grandeur de son coût en temps d'exécution en fonction de la taille n de la liste à trier.

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 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 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, preuve de terminaison par variant de boucle et proposition d'une version améliorée palindrome2 pour éviter les tours de boucle inutiles.

Autres thèmes : Numérique et Sciences Informatiques

Structures de données

• Structures de données abstraites : listes, piles, files, dictionnaires · 8 exercices · 60 % de chances de tomber
• Programmation orientée objet : classes, attributs, méthodes · 6 exercices · 50 % de chances de tomber
• Arbres : vocabulaire, mesures et algorithmique · 3 exercices · 30 % de chances de tomber
• Graphes : modélisation, implémentations et parcours · 3 exercices · 40 % de chances de tomber

Bases de données

• Bases de données relationnelles, SGBD et langage SQL · 10 exercices · 70 % de chances de tomber

Architectures, systèmes et réseaux

• Binaire, entiers et opérateurs booléens · 3 exercices · 30 % de chances de tomber
• Architectures matérielles et systèmes d'exploitation · 3 exercices · 25 % de chances de tomber
• Réseaux : adressage IP et sous-réseaux · 3 exercices · 35 % de chances de tomber
• Protocoles de routage : RIP et OSPF · 4 exercices · 45 % de chances de tomber

Langages et programmation

• Récursivité · 4 exercices · 40 % de chances de tomber
• Mise au point des programmes : bugs, assertions et tests · 2 exercices · 25 % de chances de tomber
• Programme comme donnée, calculabilité et décidabilité · 1 exercice · 25 % de chances de tomber

Algorithmique

• Diviser pour régner · 1 exercice · 20 % de chances de tomber
• Recherche textuelle et algorithme de Boyer-Moore · 1 exercice · 25 % de chances de tomber