Retour NSI
Algorithmes
Maîtriser les fondamentaux de l'algorithmique en NSI
Complexités à connaître
O(1)
Constant
Accès à un tableau par indice
O(log n)
Logarithmique
Recherche dichotomique
O(n)
Linéaire
Recherche séquentielle
O(n log n)
Quasi-linéaire
Tri fusion, tri rapide
O(n²)
Quadratique
Tri par insertion (pire cas)
O(2ⁿ)
Exponentiel
Fibonacci naïf
Chapitres
Algorithmes de tri
1èreOrganiser des données efficacement
- Tri par insertion
- Tri par sélection
- Tri fusion
- Tri rapide (Term)
Algorithmes de recherche
1èreTrouver un élément dans une collection
- Recherche séquentielle O(n)
- Recherche dichotomique O(log n)
- Recherche dans un arbre
Récursivité
1ère-TermFonctions qui s'appellent elles-mêmes
- Cas de base
- Appel récursif
- Pile d'appels
- Récursivité terminale
Complexité algorithmique
1ère-TermMesurer l'efficacité d'un algorithme
- O(1) constant
- O(n) linéaire
- O(n²) quadratique
- O(log n) logarithmique
Programmation dynamique
TermOptimisation par mémorisation
- Mémorisation
- Sous-problèmes
- Fibonacci optimisé
- Rendu de monnaie
Algorithmes sur les graphes
TermParcours et plus courts chemins
- Parcours en largeur (BFS)
- Parcours en profondeur (DFS)
- Dijkstra
- Cycle
Exemples de code Python
Recherche dichotomique
def recherche_dicho(tab, x):
g, d = 0, len(tab) - 1
while g <= d:
m = (g + d) // 2
if tab[m] == x:
return m
elif tab[m] < x:
g = m + 1
else:
d = m - 1
return -1Tri par insertion
def tri_insertion(tab):
for i in range(1, len(tab)):
cle = tab[i]
j = i - 1
while j >= 0 and tab[j] > cle:
tab[j + 1] = tab[j]
j -= 1
tab[j + 1] = cleProgramme par niveau
Première
- Tris simples
- Recherche
- Récursivité de base
- Complexité
Terminale
- Tris avancés
- Graphes
- Prog. dynamique
- Optimisation
Algorithmes au Bac NSI
Les algorithmes représentent une grande partie de l'épreuve écrite et pratique.
Conseils pour réussir
Pratiquer en Python
Code tous les algorithmes toi-même, teste-les avec différentes entrées
Justifier la complexité
Sache expliquer pourquoi un algorithme est en O(n), O(n²), etc.
