Révision Bac NSI Terminale

1.1 — Listes chaînées

class Noeud:
    def __init__(self, val, suivant=None):
        self.val = val
        self.suivant = suivant

class ListeChainee:
    def __init__(self):
        self.tete = None

    def inserer_debut(self, val):
        self.tete = Noeud(val, self.tete)

    def supprimer_debut(self):
        if self.tete is not None:
            self.tete = self.tete.suivant

1.2 — Piles (Stack)

class Pile:
    def __init__(self):
        self._data = []

    def empiler(self, val):
        self._data.append(val)          # O(1)

    def depiler(self):
        if not self.est_vide():
            return self._data.pop()   # O(1)

    def sommet(self):
        return self._data[-1]

    def est_vide(self):
        return len(self._data) == 0

1.3 — Files (Queue)

from collections import deque

class File:
    def __init__(self):
        self._data = deque()

    def enfiler(self, val):
        self._data.appendleft(val)       # O(1)

    def defiler(self):
        if not self.est_vide():
            return self._data.pop()   # O(1)

    def est_vide(self):
        return len(self._data) == 0

1.4 — Arbres binaires

Vocabulaire essentiel :

class Noeud:
    def __init__(self, val, gauche=None, droit=None):
        self.val = val
        self.gauche = gauche
        self.droit = droit

def hauteur(arbre):
    if arbre is None:
        return -1           # arbre vide : hauteur -1 (ou 0 selon convention)
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

def taille(arbre):
    if arbre is None:
        return 0
    return 1 + taille(arbre.gauche) + taille(arbre.droit)

Parcours d'arbres binaires

# Préfixe (racine, G, D)
def prefixe(a):
    if a is None: return
    print(a.val)
    prefixe(a.gauche)
    prefixe(a.droit)

# Infixe (G, racine, D)
def infixe(a):
    if a is None: return
    infixe(a.gauche)
    print(a.val)
    infixe(a.droit)

# Suffixe / postfixe (G, D, racine)
def suffixe(a):
    if a is None: return
    suffixe(a.gauche)
    suffixe(a.droit)
    print(a.val)

# Largeur (BFS avec file)
from collections import deque
def largeur(a):
    q = deque([a])
    while q:
        n = q.popleft()
        if n: print(n.val)
        if n.gauche: q.append(n.gauche)
        if n.droit: q.append(n.droit)

1.5 — Arbres Binaires de Recherche (ABR)

def rechercher(arbre, val):
    if arbre is None:
        return False
    if val == arbre.val:
        return True
    elif val < arbre.val:
        return rechercher(arbre.gauche, val)
    else:
        return rechercher(arbre.droit, val)

def inserer(arbre, val):
    if arbre is None:
        return Noeud(val)
    if val < arbre.val:
        arbre.gauche = inserer(arbre.gauche, val)
    elif val > arbre.val:
        arbre.droit = inserer(arbre.droit, val)
    return arbre

1.6 — Graphes

Deux représentations principales :

# M[i][j] = 1 si arête i→j
M = [
  [0, 1, 1, 0],  # 0→1, 0→2
  [0, 0, 1, 0],  # 1→2
  [0, 0, 0, 1],  # 2→3
  [0, 0, 0, 0],
]

# adj[sommet] = liste voisins
adj = {
    0: [1, 2],
    1: [2],
    2: [3],
    3: [],
}

1.7 — Dictionnaires & Tables de hachage

# En Python, dict est une table de hachage
d = {}
d["Alice"] = 25      # insertion O(1) moyen
d["Bob"] = 30
print(d["Alice"])    # accès O(1) moyen
"Alice" in d         # test appartenance O(1) moyen

2.1 — Modèle relationnel

Contraintes d'intégrité

2.2 — SQL : DDL (Définition)

-- Création de table
CREATE TABLE Eleve (
    id      INTEGER     PRIMARY KEY,
    nom     TEXT        NOT NULL,
    age     INTEGER     CHECK(age >= 0),
    classe  TEXT
);

CREATE TABLE Note (
    id       INTEGER PRIMARY KEY,
    eleve_id INTEGER NOT NULL,
    matiere  TEXT,
    note     REAL,
    FOREIGN KEY (eleve_id) REFERENCES Eleve(id)
);

DROP TABLE Eleve;          -- supprime la table
ALTER TABLE Eleve ADD COLUMN email TEXT;

2.3 — SQL : DML (Manipulation)

-- Insertion
INSERT INTO Eleve (id, nom, age, classe)
VALUES (1, 'Alice', 17, 'Tle A');

-- Mise à jour
UPDATE Eleve SET age = 18 WHERE id = 1;

-- Suppression
DELETE FROM Eleve WHERE age < 15;

2.4 — SQL : SELECT (Requêtes)

-- Structure générale
SELECT   attributs
FROM     table(s)
[WHERE   condition]
[GROUP BY attribut]
[HAVING  condition_agrégat]
[ORDER BY attribut [ASC|DESC]]
[LIMIT   n];

-- Exemples
SELECT * FROM Eleve;

SELECT nom, age FROM Eleve WHERE classe = 'Tle A';

SELECT nom FROM Eleve WHERE age >= 17 ORDER BY nom ASC;

-- Fonctions d'agrégat
SELECT COUNT(*) FROM Eleve;
SELECT AVG(note), MAX(note), MIN(note) FROM Note;

-- GROUP BY
SELECT classe, COUNT(*) AS effectif
FROM Eleve
GROUP BY classe
HAVING COUNT(*) > 10;

Jointures

-- INNER JOIN : tuples ayant correspondance des deux côtés
SELECT Eleve.nom, Note.matiere, Note.note
FROM Eleve
INNER JOIN Note ON Eleve.id = Note.eleve_id;

-- LEFT JOIN : tous les élèves, même sans notes
SELECT Eleve.nom, Note.note
FROM Eleve
LEFT JOIN Note ON Eleve.id = Note.eleve_id;

-- Jointure avec filtre
SELECT E.nom, AVG(N.note) AS moyenne
FROM Eleve E
JOIN Note N ON E.id = N.eleve_id
WHERE E.classe = 'Tle A'
GROUP BY E.nom
ORDER BY moyenne DESC;

2.5 — Algèbre relationnelle

3.1 — Modèle de Von Neumann

Cycle Fetch–Decode–Execute

3.2 — Hiérarchie mémoire

3.3 — Systèmes d'exploitation

Fonctions principales :

• Gestion des processus (création, ordonnancement, terminaison)
• Gestion de la mémoire (allocation, pagination, mémoire virtuelle)
• Gestion du système de fichiers
• Gestion des entrées/sorties (drivers)
• Sécurité et contrôle d'accès

Processus

Ordonnancement

Gestion des fichiers — commandes Unix

# Navigation
pwd                    # répertoire courant
ls -la                 # liste fichiers avec droits
cd /chemin/vers/dossier

# Manipulation
cp source dest         # copie
mv source dest         # déplace/renomme
rm fichier             # supprime fichier
mkdir dossier          # crée dossier
cat fichier            # affiche contenu
grep "motif" fichier   # recherche dans fichier

# Droits (rwx = lecture/écriture/exécution)
chmod 755 fichier      # rwxr-xr-x
chmod u+x fichier      # ajoute exécution pour propriétaire

# Processus
ps aux                 # liste processus
kill -9 PID            # termine processus
top                    # moniteur en temps réel

4.1 — Modèle OSI et TCP/IP

4.2 — Adressage IP

Adresses privées (RFC 1918) : 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16. Non routables sur Internet.

4.3 — TCP vs UDP

4.4 — Protocole HTTP/HTTPS

# Requête HTTP GET
GET /index.html HTTP/1.1
Host: example.com
User-Agent: Mozilla/5.0
Accept: text/html

# Réponse HTTP
HTTP/1.1 200 OK
Content-Type: text/html
Content-Length: 1234

<html>...</html>

Méthodes HTTP

4.5 — DNS et routage

5.1 — Complexité

5.2 — Algorithmes de tri

Tri par insertion — O(n²)

def tri_insertion(t):
    for i in range(1, len(t)):
        cle = t[i]
        j = i - 1
        while j >= 0 and t[j] > cle:
            t[j + 1] = t[j]
            j -= 1
        t[j + 1] = cle
    return t
# Stable | En place | Pire: O(n²) | Meilleur: O(n)

Tri fusion (Merge Sort) — O(n log n)

def fusionner(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:]

def tri_fusion(t):
    if len(t) <= 1:
        return t
    m = len(t) // 2
    return fusionner(tri_fusion(t[:m]), tri_fusion(t[m:]))
# Stable | NON en place | Toujours O(n log n)

Tri rapide (Quick Sort) — O(n log n) moy.

def tri_rapide(t):
    if len(t) <= 1:
        return t
    pivot = t[len(t) // 2]
    gauche  = [x for x in t if x < pivot]
    milieu  = [x for x in t if x == pivot]
    droite  = [x for x in t if x > pivot]
    return tri_rapide(gauche) + milieu + tri_rapide(droite)
# Non stable | Pire cas O(n²) si pivot mal choisi

5.3 — Recherche dichotomique

def dichotomie(t, cible):
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == cible:
            return m          # trouvé à l'indice m
        elif t[m] < cible:
            g = m + 1          # chercher à droite
        else:
            d = m - 1          # chercher à gauche
    return -1               # non trouvé

5.4 — Parcours de graphes

DFS — Parcours en Profondeur (Depth-First Search)

def dfs(graphe, debut):
    visites = set()
    pile = [debut]
    while pile:
        sommet = pile.pop()
        if sommet not in visites:
            visites.add(sommet)
            print(sommet)
            for voisin in graphe[sommet]:
                if voisin not in visites:
                    pile.append(voisin)
    return visites   # O(|S| + |A|)

BFS — Parcours en Largeur (Breadth-First Search)

from collections import deque

def bfs(graphe, debut):
    visites = {debut}
    file = deque([debut])
    while file:
        sommet = file.popleft()
        print(sommet)
        for voisin in graphe[sommet]:
            if voisin not in visites:
                visites.add(voisin)
                file.append(voisin)
    return visites   # O(|S| + |A|)

5.5 — Algorithme de Dijkstra

import heapq

def dijkstra(graphe, source):
    # graphe[s] = [(voisin, poids), ...]
    dist = {s: float('inf') for s in graphe}
    dist[source] = 0
    tas = [(0, source)]   # (distance, sommet)

    while tas:
        d, u = heapq.heappop(tas)
        if d > dist[u]:
            continue    # sommet déjà traité avec meilleure dist
        for v, poids in graphe[u]:
            if dist[u] + poids < dist[v]:
                dist[v] = dist[u] + poids
                heapq.heappush(tas, (dist[v], v))
    return dist   # O((|S|+|A|) log |S|)

5.6 — Programmation dynamique

# Naïf : O(2^n)
def fib_naif(n):
    if n <= 1: return n
    return fib_naif(n-1) + fib_naif(n-2)

# Mémoïsation top-down : O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)

# Bottom-up : O(n) temps, O(1) espace
def fib_dp(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

5.7 — Diviser pour régner

6.1 — Paradigmes de programmation

Programmation fonctionnelle en Python

# Fonctions de première classe
def appliquer(f, x):
    return f(x)

# Lambda
carre = lambda x: x ** 2

# map, filter, reduce
carres = list(map(lambda x: x**2, [1,2,3,4]))   # [1,4,9,16]
pairs  = list(filter(lambda x: x%2==0, [1,2,3,4])) # [2,4]

from functools import reduce
somme = reduce(lambda a,b: a+b, [1,2,3,4])    # 10

6.2 — Programmation orientée objet

class Animal:
    # Attribut de classe (partagé)
    categorie = "Vertébré"

    def __init__(self, nom, age):
        # Attributs d'instance
        self.nom = nom
        self.age = age

    def parler(self):
        raise NotImplementedError

    def __str__(self):
        return f"{self.nom} ({self.age} ans)"


class Chien(Animal):             # Héritage
    def parler(self):
        return "Woof!"

    def __init__(self, nom, age, race):
        super().__init__(nom, age)  # appel constructeur parent
        self.race = race


rex = Chien("Rex", 3, "Labrador")
print(rex)          # Rex (3 ans)
print(rex.parler()) # Woof!
isinstance(rex, Animal)  # True

6.3 — Mise au point, tests, assertions

# Assertions
def division(a, b):
    assert b != 0, "Division par zéro !"
    return a / b

# Tests unitaires avec unittest
import unittest

class TestDivision(unittest.TestCase):
    def test_normale(self):
        self.assertEqual(division(10, 2), 5)

    def test_zero(self):
        with self.assertRaises(AssertionError):
            division(1, 0)

if __name__ == '__main__':
    unittest.main()

6.4 — Types construits Python

# Tuple (immuable, ordonné)
point = (3, 4)
x, y = point           # déstructuration

# Liste (mutable, ordonnée)
t = [1, 2, 3]
t.append(4)
t.sort()
[x**2 for x in t if x > 1]  # compréhension de liste

# Dictionnaire (mutable, clé→valeur)
d = {"a": 1, "b": 2}
d["c"] = 3
d.get("z", 0)           # valeur par défaut si absent
d.items()               # paires (clé, valeur)

# Ensemble (mutable, non ordonné, sans doublon)
s = {1, 2, 3}
s.add(4)
s1 & s2   # intersection
s1 | s2   # union
s1 - s2   # différence

7.1 — Principes généraux

7.2 — Chiffrement symétrique

def chiffrer_xor(message, cle):
    # Répéter la clé si plus courte que le message
    return bytes(m ^ cle[i % len(cle)]
                  for i, m in enumerate(message.encode()))

message = "NSI"
cle = b'\x42'   # clé d'un octet
chiffre = chiffrer_xor(message, cle)
dechiffre = chiffrer_xor(chiffre.decode('latin1'), cle)
# XOR est son propre inverse : chiffrer deux fois = original

7.3 — Chiffrement asymétrique (RSA)

7.4 — Fonctions de hachage

import hashlib

h = hashlib.sha256("mot de passe".encode())
print(h.hexdigest())
# a665a45920422f9d417e4867efdc4fb8a04a1f3fff1fa07e998e86f7f7a27ae3

# Vérification d'intégrité
def verifier(fichier, hash_attendu):
    with open(fichier, "rb") as f:
        h = hashlib.sha256(f.read()).hexdigest()
    return h == hash_attendu

7.5 — HTTPS et TLS

8.1 — Principe

# Factorielle
def fact(n):
    if n == 0:              # cas de base
        return 1
    return n * fact(n - 1)  # cas récursif

# Pile d'appels pour fact(3) :
# fact(3) → 3 * fact(2)
#              → 2 * fact(1)
#                   → 1 * fact(0)
#                        → 1

8.2 — Exemples classiques

# Somme d'une liste
def somme(t):
    if t == []: return 0
    return t[0] + somme(t[1:])

# Exponentiation rapide O(log n)
def puissance(x, n):
    if n == 0: return 1
    if n % 2 == 0:
        moitie = puissance(x, n // 2)
        return moitie * moitie
    return x * puissance(x, n - 1)

# Miroir d'une chaîne
def miroir(s):
    if len(s) <= 1: return s
    return miroir(s[1:]) + s[0]

# Hanoi (n disques : 2^n - 1 mouvements)
def hanoi(n, source, cible, intermediaire):
    if n == 1:
        print(f"Déplacer disque 1 de {source} vers {cible}")
        return
    hanoi(n-1, source, intermediaire, cible)
    print(f"Déplacer disque {n} de {source} vers {cible}")
    hanoi(n-1, intermediaire, cible, source)

8.3 — Récursion sur les structures

# Aplatir une liste de listes
def aplatir(lst):
    if not isinstance(lst, list):
        return [lst]
    if lst == []: return []
    return aplatir(lst[0]) + aplatir(lst[1:])

# Parcours infixe ABR récursif
def infixe(arbre):
    if arbre is None: return []
    return (infixe(arbre.gauche)
            + [arbre.val]
            + infixe(arbre.droit))

# DFS récursif sur graphe
def dfs_rec(graphe, sommet, visites=None):
    if visites is None: visites = set()
    visites.add(sommet)
    for voisin in graphe[sommet]:
        if voisin not in visites:
            dfs_rec(graphe, voisin, visites)
    return visites

8.4 — Preuve de terminaison et correction