Comment retenir toutes les complexités algorithmiques ?

Ne les apprends pas bêtement ! Associe chaque complexité à un algorithme type (ex: O(n log n) -> tri fusion). Comprends POURQUOI elle est celle-là (à cause d'une boucle dans une boucle ? d'une division par 2 ?). Fais des tableaux comparatifs et entraîne-toi à les justifier sur des sujets d'annales.

Est-ce que je dois savoir coder tous les algorithmes (Dijkstra, tri fusion...) par cœur ?

Non, l'objectif n'est pas la récitation. Tu dois comprendre leur principe, leur déroulement sur un exemple et être capable de les adapter. Par contre, savoir écrire une recherche dichotomique, un parcours d'arbre ou un tri simple est souvent attendu. Concentre-toi sur la logique plus que sur la syntaxe parfaite.

Quelle est la partie la plus importante pour le BAC ?

Toutes les parties sont importantes car l'épreuve est transversale. Cependant, l'algorithmique (structures de données, complexité) et la programmation en Python sont le fil rouge de nombreux exercices. Les bases de données (SQL) et les réseaux (TCP/IP, HTTP) font aussi presque toujours l'objet de questions spécifiques. Ne fais pas d'impasse !

Fiche de revision NSI terminale : tout le programme en 10 pages

1. Structures de Données Avancées

En Terminale, tu vas manipuler des structures de données plus complexes qui permettent d'organiser l'information de manière efficace. La compréhension de leurs propriétés est cruciale pour choisir la bonne structure en fonction du problème.

Les Arbres et les Graphes

Les arbres sont des structures hiérarchiques non linéaires. Tu dois maîtriser :

Arbres binaires : Chaque nœud a au plus deux enfants.
Arbres binaires de recherche (ABR) : Pour tout nœud, les valeurs du sous-arbre gauche sont inférieures, et celles du droit sont supérieures. Permet une recherche, insertion et suppression efficaces (en O(log n) en moyenne).
Parcours d'arbres : En profondeur (infixe, préfixe, suffixe) et en largeur.

Les graphes modélisent des relations quelconques entre objets. Retiens :

Vocabulaire : sommets (ou nœuds), arêtes (non orientées) ou arcs (orientés), poids.
Représentations : matrice d'adjacence (efficace pour les graphes denses) et liste d'adjacence (efficace pour les graphes creux).
Algorithmes de parcours : Parcours en profondeur (DFS) et Parcours en largeur (BFS).
Algorithmes de plus court chemin : Dijkstra (avec des arêtes à poids positifs) et Bellman-Ford (gère les poids négatifs).

Les Tables de Hachage

Une table de hachage permet un accès extrêmement rapide (O(1) en moyenne) à des données via une clé. Le principe :

Une fonction de hachage transforme la clé en un indice (hash).
En cas de collision (deux clés donnent le même indice), il faut la gérer, souvent par chaînage (liste à l'indice) ou par adressage ouvert.

En Python, le type dict est l'implémentation par excellence d'une table de hachage.

2. Algorithmique Avancée et Complexité

Cette partie est le cœur de la réflexion informatique. Il s'agit de concevoir des stratégies efficaces pour résoudre des problèmes.

Diviser pour Régner et Récursivité

Le principe « Diviser pour Régner » consiste à :

Diviser le problème en sous-problèmes plus petits et indépendants.
Régner : Résoudre récursivement chaque sous-problème.
Combiner les solutions des sous-problèmes pour obtenir la solution du problème initial.

Exemples classiques : le tri fusion (merge sort) et la recherche dichotomique. Leur complexité est souvent meilleure (O(n log n) pour le tri fusion) que les approches naïves.

Programmation Dynamique

Contrairement à « Diviser pour Régner », la programmation dynamique évite de recalculer plusieurs fois les mêmes sous-problèmes. Elle est utilisée quand les sous-problèmes se chevauchent. La démarche :

Caractériser la structure d'une solution optimale.
Définir récursivement la valeur d'une solution optimale.
Calculer cette valeur de manière ascendante (ou mémoïsée) en stockant les résultats intermédiaires.

Un exemple incontournable : le calcul de la suite de Fibonacci sans récursivité naïve, ou le problème du sac à dos.

Notation Grand O et Complexité

Tu dois être capable de classer les complexités et de les justifier :

O(1) : Temps constant (accès à un tableau).
O(log n) : Logarithmique (recherche dichotomique).
O(n) : Linéaire (parcours de liste).
O(n log n) : « Quasi-linéaire » (bons algorithmes de tri).
O(n²), O(2^n) : De moins en moins efficaces.

Astuce BAC : On te demande souvent de comparer deux algorithmes. Pense toujours à justifier en parlant de la complexité dans le pire des cas et/ou en moyenne.

3. Bases de Données et Langage SQL

Les bases de données relationnelles permettent de stocker, organiser et interroger de grandes quantités de données de manière fiable.

Le Modèle Relationnel

Les données sont organisées en tables (ou relations). Chaque ligne est un enregistrement (ou tuple), chaque colonne un attribut. Une clé primaire identifie de manière unique un enregistrement. Une clé étrangère fait référence à une clé primaire dans une autre table, créant un lien.

Interrogation avec SQL

Le langage SQL (Structured Query Language) est indispensable. Maîtrise ces requêtes fondamentales :

SELECT ... FROM ... WHERE : Pour sélectionner des données avec conditions.
JOIN (INNER, LEFT, etc.) : Pour fusionner des données de plusieurs tables.
GROUP BY et fonctions d'agrégation (COUNT, SUM, AVG, MAX, MIN).
INSERT, UPDATE, DELETE : Pour modifier les données (à utiliser avec précaution !).

Exemple : SELECT nom, COUNT(*) FROM Eleves GROUP BY nom HAVING COUNT(*) > 1; trouve les noms en double.

4. Architectures Matérielles, Systèmes d'Exploitation et Réseaux

Comprendre comment fonctionne la machine et la communication entre machines.

De la Logique aux Processeurs

Rappelle-toi la construction en couches :

Portes logiques (ET, OU, NON) sont les briques de base.
Elles forment des circuits combinatoires (comme l'additionneur) puis séquentiels (comme la bascule, mémoire d'un bit).
Ces circuits constituent l'Unité Arithmétique et Logique (UAL) et les registres du processeur.
Le processeur exécute des instructions machine (langage binaire), gérées par le système d'exploitation.

Rôle du Système d'Exploitation

Le SE (comme Linux ou Windows) est le chef d'orchestre. Il gère :

Les processus et le multitâche (partage du temps processeur).
La mémoire vive (RAM) et la mémoire virtuelle.
Le système de fichiers (organisation des données sur le disque dur).
Les périphériques (pilotes).

Principes des Réseaux

Pour que ton site web s'affiche, des protocoles empilés travaillent :

Modèle TCP/IP : Couche Lien (Ethernet, WiFi), Internet (IP), Transport (TCP fiable / UDP rapide), Application (HTTP, HTTPS, DNS).
Adressage : Adresse IP (logique) et adresse MAC (physique).
Routage : Comment un paquet IP trouve son chemin à travers les routeurs.
Protocole HTTP/HTTPS : Le langage du web. HTTPS ajoute une couche de chiffrement (TLS/SSL) pour la sécurité.

5. Stratégie de Révision et Conseils pour l'Épreuve

Maintenant que tu as les connaissances, il faut les mobiliser le jour J.

Comment Utiliser Cette Fiche ?

Ne l'apprends pas par cœur ! Utilise-la comme :

Un guide de vérification : Est-ce que je connais chaque point ?
Un aide-mémoire : Pour retrouver rapidement une formule ou un concept.
Un support pour faire des exercices : Travaille sur des sujets types BAC en t'y référant.

Le Jour de l'Épreuve

Gère ton temps (4 heures) :

Lecture complète (15 min) : Identifie les exercices et leur difficulté.
Traitement des questions : Commence par ce qui te semble le plus simple pour gagner en confiance.
Rédaction soignée : Justifie tes réponses, commente ton code, sois clair. Un algorithme bien commenté peut rapporter des points même s'il a un petit bug.
Vérification (20-30 min) : Revois tes réponses, teste mentalement ton code avec des valeurs simples.

Bon courage pour tes révisions ! Avec une compréhension solide de ces 10 pages et un entraînement régulier, tu es paré pour réussir l'épreuve de NSI.