Spécialité NSI — Terminale

Programme officiel — synthèse

Algorithmique et complexité

Tri par fusion (divide and conquer)

def fusion(a, b):
    i = j = 0
    c = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i]); i += 1
        else:
            c.append(b[j]); j += 1
    return c + a[i:] + b[j:]

def tri_fusion(t):
    if len(t) <= 1:
        return t
    m = len(t)//2
    return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))

Complexité moyenne et pire : O(n log n). Mémoire supplémentaire O(n).

Structures de données

Pile et file

class Pile:
    def __init__(self): self._d = []
    def empiler(self, x): self._d.append(x)
    def depiler(self): return self._d.pop()
    def vide(self): return len(self._d) == 0

from collections import deque
file = deque()
file.append(1); file.append(2)
file.popleft()  # 1

Parcours de graphe

from collections import deque
def bfs(graphe, source):
    vus, q = {source}, deque([source])
    ordre = []
    while q:
        u = q.popleft(); ordre.append(u)
        for v in graphe[u]:
            if v not in vus:
                vus.add(v); q.append(v)
    return ordre

Bases de données — SQL

Schéma exemple: Élève(id, nom), Note(id, eleve_id, matiere, valeur)

-- Moyenne par élève en mathématiques
SELECT e.nom, AVG(n.valeur) AS moyenne
FROM Eleve e
JOIN Note n ON n.eleve_id = e.id
WHERE n.matiere = 'Maths'
GROUP BY e.nom
ORDER BY moyenne DESC;

Clés: primaire (unicité), étrangères (références). Normalisation pour éviter les duplications.

Réseaux et Web

• DNS résout les noms de domaine en adresses IP.
• HTTP définit les méthodes (GET, POST...), les codes (200, 404...).
• JSON: format texte pour échanger des données.

// Requête GET avec fetch (JS)
fetch('https://api.exemple.com/users')
  .then(r => r.json())
  .then(data => console.log(data))
  .catch(console.error);

Raisonner sur la complexité

• Identifier la boucle la plus coûteuse (n, n², n log n...).
• Évaluer séparément les étapes majeures puis sommer.
• Comparer des approches (itérative vs récursive).

Écrire du code fiable

• Découper en fonctions pures testables.
• Nommer clairement, documenter l’API, typer si possible.
• Tester: cas nominal, bords, erreurs.

def somme(xs):
    assert all(isinstance(x, (int, float)) for x in xs)
    s = 0
    for x in xs: s += x
    return s

Méthode SQL

1. Lire le besoin et identifier les tables concernées.
2. Écrire le FROM/JOIN, puis filtrer (WHERE).
3. Aggréger (GROUP BY) et trier (ORDER BY) si nécessaire.

Exercices guidés

1. Implémenter une pile avec deux files (complexité amortie).
2. Écrire merge k listes triées (tas binaire recommandé).
3. Détecter un cycle dans un graphe (DFS avec couleurs).
4. Donner la complexité des fonctions fournies.
5. Modéliser puis écrire les requêtes SQL pour un cahier de notes.

🧪 Exercice pratique : Algorithme de recherche

Énoncé : Implémentez la recherche dichotomique et comparez sa complexité avec la recherche linéaire.

def recherche_dichotomique(tab, x):
    debut, fin = 0, len(tab) - 1
    comparaisons = 0

    while debut <= fin:
        comparaisons += 1
        milieu = (debut + fin) // 2
        if tab[milieu] == x:
            return milieu, comparaisons
        elif tab[milieu] < x:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return -1, comparaisons

💾 Exercice SQL interactif

Base de données Librairie :

Question : Écrivez une requête pour trouver tous les livres de plus de 15€.

Jeu de tests exemple

def test_tri_fusion():
    assert tri_fusion([]) == []
    assert tri_fusion([1]) == [1]
    assert tri_fusion([3,1,2]) == [1,2,3]

def test_recherche_dichotomique():
    assert recherche_dichotomique([1,3,5,7,9], 5)[0] == 2
    assert recherche_dichotomique([1,3,5,7,9], 10)[0] == -1

⚡ Simulateurs interactifs avancés

Explorez les concepts algorithmiques avec ces outils interactifs de nouvelle génération

🔍 Simulateur de tri interactif

🐍 Console Python interactive

🕸️ Visualiseur de graphes

🗄️ Constructeur de requêtes SQL

📈 Analyseur de complexité