Quels algorithmes faut-il connaître en NSI pour le bac
Le programme de NSI impose la maîtrise de plusieurs algorithmes fondamentaux. En première : la recherche séquentielle (parcourir une liste élément par élément), la recherche dichotomique (diviser pour régner sur une liste triée, complexité O(log n)), le tri par sélection (trouver le minimum et le placer en début) et le tri par insertion (insérer chaque élément à sa place). En terminale : les algorithmes sur les arbres (parcours en profondeur préfixe, infixe, suffixe, et parcours en largeur), les algorithmes sur les graphes (parcours en profondeur DFS et en largeur BFS, plus court chemin avec Dijkstra), la programmation dynamique (mémoïsation, problème du rendu de monnaie) et les algorithmes gloutons. Pour chaque algorithme, vous devez savoir l'expliquer, l'écrire en Python, donner sa complexité temporelle et spatiale, et identifier ses cas d'utilisation. Sur NSI-Lycée, chaque algorithme est présenté avec une animation visuelle, le pseudocode, l'implémentation Python et des exercices d'application. Nous proposons des comparaisons interactives entre algorithmes (par exemple tri par sélection vs tri par insertion). Pour les bases mathématiques de la complexité algorithmique, consultez revisemaths.fr et calculemoi.fr.
