Prêt à booster tes révisions ?
Essayer maintenantSans carte bancaire - Rejoins +40 000 étudiants
Fiches de révision NSI Terminale : structures de données, bases de données, algorithmique, POO, réseaux. Exemples Python. Bac 2026.
La spécialité Numérique et Sciences Informatiques (NSI) en Terminale prépare aux deux épreuves du baccalauréat : une épreuve écrite (3h30, coefficient 16) portant sur l’ensemble du programme et une épreuve pratique (1h, coefficient inclus) de programmation en Python. Le programme s’articule autour de cinq grandes thématiques : structures de données, bases de données, architectures matérielles et réseaux, langages et programmation, algorithmique. Cette fiche couvre l’intégralité du programme officiel 2025-2026 avec des exemples de code Python.
Les structures de données permettent d’organiser et de stocker efficacement les informations. Choisir la bonne structure est essentiel pour écrire des algorithmes performants.
Une liste chaînée est une structure de données où chaque élément (appelé nœud ou maillon) contient une valeur et une référence (ou pointeur) vers l’élément suivant. Le dernier élément pointe vers None.
À la différence des tableaux (listes Python), les listes chaînées ne permettent pas un accès direct par indice en O(1). L’accès à un élément nécessite de parcourir la liste depuis le début, soit O(n). En revanche, l’insertion et la suppression en tête sont en O(1).
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.tete = None
def inserer_en_tete(self, valeur):
nouveau = Maillon(valeur, self.tete)
self.tete = nouveau
def afficher(self):
courant = self.tete
while courant is not None:
print(courant.valeur, end=" -> ")
courant = courant.suivant
print("None")
Une pile (stack) fonctionne selon le principe LIFO (Last In, First Out) : le dernier élément empilé est le premier dépilé. Opérations fondamentales : empiler (push), dépiler (pop), sommet (top), est_vide.
Applications courantes : gestion de la pile d’appels en récursivité, vérification du parenthésage, évaluation d’expressions postfixées, fonction « Annuler » (Ctrl+Z).
class Pile:
def __init__(self):
self.elements = []
def empiler(self, valeur):
self.elements.append(valeur)
def depiler(self):
if self.est_vide():
raise IndexError("Pile vide")
return self.elements.pop()
def sommet(self):
if self.est_vide():
raise IndexError("Pile vide")
return self.elements[-1]
def est_vide(self):
return len(self.elements) == 0
Une file (queue) fonctionne selon le principe FIFO (First In, First Out) : le premier élément entré est le premier sorti. Opérations : enfiler (enqueue), défiler (dequeue), est_vide.
Applications : file d’attente d’impression, gestion des processus dans un OS, parcours en largeur (BFS) d’un graphe.
from collections import deque
class File:
def __init__(self):
self.elements = deque()
def enfiler(self, valeur):
self.elements.append(valeur)
def defiler(self):
if self.est_vide():
raise IndexError("File vide")
return self.elements.popleft()
def est_vide(self):
return len(self.elements) == 0
Un arbre binaire est une structure hiérarchique où chaque nœud possède au plus deux fils : un fils gauche et un fils droit. Le nœud au sommet est la racine. Un nœud sans fils est une feuille. La hauteur d’un arbre est le nombre d’arêtes sur le plus long chemin de la racine à une feuille. La taille est le nombre total de nœuds.
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def taille(arbre):
if arbre is None:
return 0
return 1 + taille(arbre.gauche) + taille(arbre.droit)
def hauteur(arbre):
if arbre is None:
return -1
return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))
Trois parcours fondamentaux (tous récursifs) :
def parcours_prefixe(arbre):
if arbre is None:
return []
return [arbre.valeur] + parcours_prefixe(arbre.gauche) + parcours_prefixe(arbre.droit)
def parcours_infixe(arbre):
if arbre is None:
return []
return parcours_infixe(arbre.gauche) + [arbre.valeur] + parcours_infixe(arbre.droit)
def parcours_suffixe(arbre):
if arbre is None:
return []
return parcours_suffixe(arbre.gauche) + parcours_suffixe(arbre.droit) + [arbre.valeur]
Un arbre binaire de recherche est un arbre binaire où pour tout nœud : toutes les valeurs du sous-arbre gauche sont inférieures et toutes les valeurs du sous-arbre droit sont supérieures. Cette propriété permet une recherche efficace en O(log n) dans le cas équilibré (O(n) dans le pire cas d’un arbre dégénéré).
Le parcours infixe d’un ABR donne les valeurs dans l’ordre croissant.
def rechercher(arbre, valeur):
if arbre is None:
return False
if valeur == arbre.valeur:
return True
elif valeur < arbre.valeur:
return rechercher(arbre.gauche, valeur)
else:
return rechercher(arbre.droit, valeur)
def inserer(arbre, valeur):
if arbre is None:
return Noeud(valeur)
if valeur < arbre.valeur:
arbre.gauche = inserer(arbre.gauche, valeur)
elif valeur > arbre.valeur:
arbre.droit = inserer(arbre.droit, valeur)
return arbre
Un graphe est constitué de sommets (ou nœuds) et d’arêtes (ou arcs dans un graphe orienté) qui relient ces sommets. Un graphe peut être orienté (les arcs ont un sens) ou non orienté. Un graphe peut être pondéré (chaque arête a un poids).
Deux représentations classiques :
# Matrice d'adjacence
matrice = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0],
]
# Liste d'adjacence
graphe = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"],
}
Le modèle relationnel (Edgar F. Codd, 1970) organise les données en tables (ou relations). Chaque table a un schéma qui définit ses attributs (colonnes) et leurs types. Chaque ligne est un enregistrement (ou n-uplet).
SQL (Structured Query Language) est le langage standard pour interagir avec les bases de données relationnelles.
Requêtes de sélection :
-- Sélectionner tous les élèves de Terminale
SELECT nom, prenom, classe
FROM eleves
WHERE classe = 'Terminale'
ORDER BY nom ASC;
-- Compter le nombre d'élèves par classe
SELECT classe, COUNT(*) AS nombre_eleves
FROM eleves
GROUP BY classe;
-- Jointure : afficher les notes avec le nom de l'élève
SELECT e.nom, e.prenom, n.matiere, n.note
FROM eleves e
JOIN notes n ON e.id = n.id_eleve
WHERE n.note >= 10
ORDER BY n.note DESC;
Requêtes de modification :
-- Insérer un nouvel élève
INSERT INTO eleves (nom, prenom, classe) VALUES ('Dupont', 'Marie', 'Terminale');
-- Mettre à jour une note
UPDATE notes SET note = 15 WHERE id_eleve = 42 AND matiere = 'NSI';
-- Supprimer un enregistrement
DELETE FROM notes WHERE id_eleve = 42 AND matiere = 'NSI';
La normalisation réduit la redondance des données et garantit la cohérence. La première forme normale (1NF) impose que chaque attribut soit atomique (pas de valeurs multiples). La deuxième forme normale (2NF) impose que tout attribut non clé dépende de la totalité de la clé primaire. La troisième forme normale (3NF) impose l’absence de dépendance transitive.
Un ordinateur repose sur l’architecture de von Neumann (1945) : un processeur (CPU) exécute les instructions, la mémoire (RAM) stocke temporairement les données et programmes, et le bus assure la communication entre composants. Le processeur contient une unité arithmétique et logique (UAL) pour les calculs, une unité de commande pour le séquençage des instructions, et des registres pour le stockage rapide.
Les mémoires forment une hiérarchie : registres (très rapides, très petits) → cache → RAM → stockage secondaire (SSD/HDD, lent, grande capacité).
Le système d’exploitation (OS) gère les ressources matérielles et logicielles. Un processus est un programme en cours d’exécution. Chaque processus a un état (prêt, en exécution, en attente, terminé). L’ordonnanceur (scheduler) décide quel processus s’exécute à un instant donné. Algorithmes d’ordonnancement : tourniquet (Round Robin), priorité, premier arrivé premier servi (FCFS). L’interblocage (deadlock) survient quand deux processus s’attendent mutuellement.
Le modèle TCP/IP organise les communications en quatre couches : accès réseau, Internet (IP), transport (TCP/UDP), application (HTTP, HTTPS, DNS).
Le routage détermine le chemin emprunté par les paquets dans un réseau. Chaque routeur possède une table de routage. Le protocole RIP (Routing Information Protocol) utilise le nombre de sauts. Le protocole OSPF (Open Shortest Path First) utilise le coût des liens (débit) et l’algorithme de Dijkstra pour trouver le plus court chemin.
La récursivité est une technique où une fonction s’appelle elle-même. Toute fonction récursive doit avoir un cas de base (condition d’arrêt) et un appel récursif qui converge vers ce cas de base.
Chaque appel récursif empile un nouveau contexte d’exécution sur la pile d’appels. Un nombre excessif d’appels provoque un dépassement de pile (RecursionError en Python, limite par défaut : 1000).
# Factorielle
def factorielle(n):
if n == 0: # Cas de base
return 1
return n * factorielle(n - 1) # Appel récursif
# Suite de Fibonacci (version naïve, O(2^n))
def fibonacci(n):
if n <= 1: # Cas de base
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# Fibonacci avec mémoïsation (O(n))
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
La programmation orientée objet organise le code autour d’objets qui encapsulent des données (attributs) et des comportements (méthodes). Une classe est un modèle (ou plan) à partir duquel on crée des objets (instances).
Concepts clés :
class Animal:
def __init__(self, nom, age):
self.nom = nom
self.age = age
def se_presenter(self):
return f"Je suis {self.nom}, j'ai {self.age} ans."
class Chien(Animal): # Héritage
def __init__(self, nom, age, race):
super().__init__(nom, age) # Appel au constructeur parent
self.race = race
def aboyer(self):
return "Ouaf !"
rex = Chien("Rex", 5, "Berger allemand")
print(rex.se_presenter()) # "Je suis Rex, j'ai 5 ans."
print(rex.aboyer()) # "Ouaf !"
La modularité consiste à découper un programme en modules (fichiers) indépendants et réutilisables. En Python, chaque fichier .py est un module. On importe un module avec import ou from ... import .... Cela facilite la maintenance, les tests et la collaboration.
Tri par insertion : on insère chaque élément à sa bonne place dans la partie déjà triée. Complexité : O(n²) en moyenne et au pire, O(n) au meilleur cas (liste déjà triée). Tri en place et stable.
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] = cle
return tab
Tri fusion (merge sort) : algorithme diviser pour régner. On divise le tableau en deux moitiés, on trie récursivement chaque moitié, puis on fusionne. Complexité : O(n log n) dans tous les cas. Tri stable mais pas en place (nécessite de la mémoire supplémentaire).
def tri_fusion(tab):
if len(tab) <= 1:
return tab
milieu = len(tab) // 2
gauche = tri_fusion(tab[:milieu])
droite = tri_fusion(tab[milieu:])
return fusionner(gauche, droite)
def fusionner(g, d):
resultat = []
i, j = 0, 0
while i < len(g) and j < len(d):
if g[i] <= d[j]:
resultat.append(g[i])
i += 1
else:
resultat.append(d[j])
j += 1
resultat.extend(g[i:])
resultat.extend(d[j:])
return resultat
Tri rapide (quicksort) : on choisit un pivot, on place les éléments inférieurs à gauche et les supérieurs à droite, puis on trie récursivement les deux parties. Complexité : O(n log n) en moyenne, O(n²) dans le pire cas (pivot mal choisi). Tri en place mais instable.
def tri_rapide(tab):
if len(tab) <= 1:
return tab
pivot = tab[len(tab) // 2]
gauche = [x for x in tab if x < pivot]
milieu = [x for x in tab if x == pivot]
droite = [x for x in tab if x > pivot]
return tri_rapide(gauche) + milieu + tri_rapide(droite)
La recherche dichotomique (binary search) fonctionne sur un tableau trié. On compare l’élément recherché avec le milieu du tableau : si c’est égal, on a trouvé ; si c’est inférieur, on cherche dans la moitié gauche ; si c’est supérieur, dans la moitié droite. Complexité : O(log n).
def recherche_dichotomique(tab, valeur):
gauche, droite = 0, len(tab) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if tab[milieu] == valeur:
return milieu
elif tab[milieu] < valeur:
gauche = milieu + 1
else:
droite = milieu - 1
return -1 # Non trouvé
Parcours en largeur (BFS — Breadth-First Search) : on explore les sommets par niveaux de distance croissante depuis le sommet de départ, en utilisant une file. Utile pour trouver le plus court chemin en nombre d’arêtes dans un graphe non pondéré.
from collections import deque
def bfs(graphe, depart):
visite = set()
file = deque([depart])
visite.add(depart)
ordre = []
while file:
sommet = file.popleft()
ordre.append(sommet)
for voisin in graphe[sommet]:
if voisin not in visite:
visite.add(voisin)
file.append(voisin)
return ordre
Parcours en profondeur (DFS — Depth-First Search) : on explore le plus loin possible dans chaque branche avant de revenir en arrière, en utilisant une pile (ou la récursivité). Utile pour détecter des cycles, topological sort.
def dfs(graphe, depart, visite=None):
if visite is None:
visite = set()
visite.add(depart)
ordre = [depart]
for voisin in graphe[depart]:
if voisin not in visite:
ordre.extend(dfs(graphe, voisin, visite))
return ordre
L’algorithme de Dijkstra (1959) trouve le plus court chemin depuis un sommet source vers tous les autres dans un graphe pondéré à poids positifs. Il utilise une file de priorité et un tableau de distances.
Principe : initialiser toutes les distances à l’infini sauf la source (à 0). À chaque itération, sélectionner le sommet non visité de distance minimale, puis mettre à jour les distances de ses voisins (relaxation).
import heapq
def dijkstra(graphe, depart):
distances = {sommet: float("inf") for sommet in graphe}
distances[depart] = 0
file_priorite = [(0, depart)]
while file_priorite:
dist_actuelle, sommet = heapq.heappop(file_priorite)
if dist_actuelle > distances[sommet]:
continue
for voisin, poids in graphe[sommet]:
nouvelle_dist = dist_actuelle + poids
if nouvelle_dist < distances[voisin]:
distances[voisin] = nouvelle_dist
heapq.heappush(file_priorite, (nouvelle_dist, voisin))
return distances
# Exemple d'utilisation
graphe_pondere = {
"A": [("B", 4), ("C", 2)],
"B": [("D", 3), ("C", 1)],
"C": [("B", 1), ("D", 5)],
"D": [],
}
print(dijkstra(graphe_pondere, "A"))
# {'A': 0, 'B': 3, 'C': 2, 'D': 6}
La complexité mesure l’efficacité d’un algorithme en fonction de la taille de l’entrée (notée n). On utilise la notation O (grand O) pour exprimer le comportement asymptotique dans le pire cas.
| Complexité | Exemple | Description |
|---|---|---|
| O(1) | Accès à un élément d’un tableau | Constante |
| O(log n) | Recherche dichotomique | Logarithmique |
| O(n) | Parcours d’un tableau | Linéaire |
| O(n log n) | Tri fusion, tri rapide (moy.) | Quasi-linéaire |
| O(n²) | Tri par insertion (pire cas) | Quadratique |
| O(2ⁿ) | Fibonacci naïve | Exponentielle |