💻 NSI au bac : Coefficient 16 (Terminale). Épreuve écrite 3h30 + épreuve pratique 1h (notée sur 8). Pratique Python quotidienne indispensable — l'algo ne s'apprend pas en lisant, il s'apprend en codant.
Programme NSI Terminale
| Thème | Contenus | Langages / Outils |
|---|---|---|
| Structures de données | Listes chaînées, piles, files, arbres binaires, graphes, tables de hachage | Python (classes) |
| Bases de données | Modèle relationnel, algèbre relationnelle, SQL (SELECT, JOIN, sous-requêtes) | SQL, SQLite |
| Architectures & réseaux | Protocoles TCP/IP, routage, DNS, HTTP/HTTPS, cybersécurité | Wireshark (TP) |
| Langages & programmation | Paradigmes (impératif, fonctionnel, objet), récursivité, lambda, calculabilité | Python, Scheme |
| Algorithmique | Diviser pour régner, prog. dynamique, algorithmes sur graphes (Dijkstra) | Python |
| Histoire de l'informatique | Machine de Turing, circuits logiques, encodage, histoire des langages | Culture générale |
Structures de données — Les essentielles
Pile (Stack) — LIFO
pile = []
pile.append(x) # push
pile.pop() # pop (dernier entré)
Usages : gestion des appels récursifs, évaluation d'expressions, annulation (Ctrl+Z)
File (Queue) — FIFO
from collections import deque
file = deque()
file.append(x) # enqueue
file.popleft() # dequeue
Usages : BFS (parcours en largeur), file d'attente, planification
Arbre binaire
class Noeud:
def __init__(self, val):
self.val = val
self.gauche = None
self.droit = None
Parcours : préfixe (R-G-D), infixe (G-R-D), postfixe (G-D-R), largeur (BFS)
Graphe — Représentation
g = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}
Listes d'adjacence pour graphes épars. Matrice d'adjacence pour graphes denses.
Algorithmique — Diviser pour régner
Tri fusion (Merge Sort) — O(n log n)
def tri_fusion(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
g = tri_fusion(lst[:mid])
d = tri_fusion(lst[mid:])
return fusion(g, d)
def fusion(g, d):
res, i, j = [], 0, 0
while i < len(g) and j < len(d):
if g[i] <= d[j]:
res.append(g[i]); i += 1
else:
res.append(d[j]); j += 1
return res + g[i:] + d[j:]
Algorithme de Dijkstra (plus court chemin)
Principe : à chaque étape, choisir le nœud non visité de distance minimale. Utilise une file de priorité (tas min). Complexité : O((V + E) log V) avec un tas.
SQL — Requêtes essentielles
-- Sélection avec filtre
SELECT nom, age FROM eleves WHERE age > 17 ORDER BY nom;
-- Jointure
SELECT e.nom, c.matiere
FROM eleves e JOIN cours c ON e.id_cours = c.id;
-- Agrégation
SELECT matiere, AVG(note) as moyenne FROM notes GROUP BY matiere HAVING AVG(note) > 12;
-- Sous-requête
SELECT nom FROM eleves WHERE note = (SELECT MAX(note) FROM eleves);
Récursivité — Méthode
Toute fonction récursive doit avoir : 1) un cas de base (condition d'arrêt) et 2) un appel récursif qui se rapproche du cas de base.
def factorielle(n):
if n <= 1: # cas de base
return 1
return n * factorielle(n-1) # appel récursif
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2) # sans mémoïsation : O(2^n) !
⚠️ Piège NSI : fibonacci récursif naïf est exponentiel. Avec mémoïsation (@lru_cache) ou programmation dynamique (tableau), on obtient O(n). Savoir expliquer cette différence est souvent demandé.
Épreuve pratique — Conseils
- Testez votre code avec plusieurs valeurs (notamment cas limites : liste vide, n=0, graphe sans chemin)
- Écrivez des fonctions claires avec des noms explicites
- Commentez si le code n'est pas évident
- La banque nationale d'exercices est disponible sur le site Eduscol — entraînez-vous sur les 50 exercices types
Entraînez-vous sur BacIA
QCM algorithmique, exercices Python corrigés et explications IA pour décrocher votre bac NSI.
Pratiquer maintenant →