Bac NSI cheat sheet

Pascal (1642) : machine arithmétique à roues dentées pour l'addition ; Leibniz (1673) étend aux quatre opérations.

Babbage (1837) : machine analytique avec unité de calcul et mémoire ; Ada Lovelace écrit le premier algorithme destiné à cette machine.

Hollerith (1890) : cartes perforées pour le recensement américain ; sa société devient IBM en 1924.

Turing (1936) : machine de Turing, modèle abstrait du calcul ; thèse de Church-Turing : tout calcul effectif est simulable par cette machine.

Von Neumann (1945) : architecture à programme enregistré en mémoire, partagée avec les données ; base des ordinateurs modernes.

1945 ENIAC (tubes à vide), 1947 invention du transistor (Bardeen, Brattain, Shockley), 1958 circuit intégré (Kilby, Noyce).

1969 : premier message ARPANET ; 1983 : adoption du protocole TCP/IP ; 1991 : Tim Berners-Lee met en ligne le premier site Web.

Loi de Moore (1965, révisée 1975) : le nombre de transistors par puce double environ tous les deux ans.

Repères logiciels : Fortran 1957 (scientifique), Lisp 1958, C 1972 (Ritchie), puis logiciel libre (GNU 1983, noyau Linux 1991).

Binaire : n bits codent 2^n valeurs, de 0 à 2^n − 1 ; pour 8 bits, 0 à 255.

Conversion décimal → binaire : divisions successives par 2, les restes lus à l'envers ; binaire → décimal : somme des 2^position.

Hexadécimal : 1 chiffre hexa = 4 bits ; octet = 2 chiffres hexa (ex. 1010 1111 = AF).

Entiers signés en complément à deux sur n bits : intervalle [−2^(n−1), 2^(n−1) − 1] ; pour 8 bits, −128 à 127. Opposé de x : inverser les bits puis ajouter 1.

Flottants IEEE 754 simple précision : 1 bit signe, 8 bits exposant (biais 127), 23 bits mantisse ; perte de précision car les décimaux ne sont pas tous représentables en base 2.

Texte : ASCII sur 7 bits (128 caractères) ; Latin-1 sur 8 bits ; Unicode associe un point de code (U+0000 à U+10FFFF) ; UTF-8 encode sur 1 à 4 octets, compatible ASCII.

Caractères de contrôle ASCII : LF = 10, CR = 13, NUL = 0 ; 'A' = 65, 'a' = 97, '0' = 48.

Booléen : deux valeurs ; opérateurs AND, OR, NOT, XOR ; tables de vérité et lois de De Morgan : NOT(a AND b) = (NOT a) OR (NOT b).

Toute donnée numérique stockée est finie : un entier sur n bits subit un dépassement (overflow) silencieux, un flottant une erreur d'arrondi.

En Python, une liste est mutable et indexée de 0 à len(liste) − 1 ; un tuple est immuable et se crée avec des parenthèses.

Index négatif : liste[-1] désigne le dernier élément ; liste[-k] le k-ième depuis la fin.

Copie de liste : b = a crée un alias ; b = a[:] ou list(a) crée une copie superficielle ; copy.deepcopy pour les structures imbriquées.

Dictionnaire : association clé → valeur, clés immuables et uniques ; accès par d[clé], ajout par d[clé] = valeur, test par clé in d.

Parcours de dictionnaire : for k in d parcourt les clés ; d.keys(), d.values(), d.items() renvoient des vues.

Matrice : liste de listes (lignes) ; accès M[i][j] ; une matrice n×m se crée avec une compréhension [[0]*m for _ in range(n)] et non [[0]*m]*n qui partage les lignes.

Pile (LIFO) : empiler avec append, dépiler avec pop() ; file (FIFO) : enfiler avec append, défiler avec pop(0) ou collections.deque.popleft().

Compréhension de liste : [f(x) for x in t if cond(x)] ; équivalent à une boucle avec accumulateur.

Tuple comme enregistrement : retourner plusieurs valeurs (min, max) et les déballer a, b = fonction().

Table = ensemble de lignes (enregistrements) décrites par des colonnes (attributs) ; chaque ligne a une clé identifiante unique.

CSV : valeurs séparées par un séparateur (souvent la virgule), première ligne = en-tête ; lecture en Python avec csv.reader ou csv.DictReader.

Import CSV : open(chemin, encoding="utf-8", newline="") puis csv.reader ; toutes les valeurs lues sont des chaînes, à convertir avec int() ou float().

Filtrage : sélectionner les lignes vérifiant un prédicat ; projection : ne garder que certaines colonnes.

Tri : sorted(table, key=lambda ligne: ligne[col]) ; tri stable, complexité O(n log n).

Jointure : fusionner deux tables sur un attribut commun ; en Python, construire un dictionnaire index sur la clé de la première table puis parcourir la seconde.

Agrégation : regrouper par valeur d'attribut et calculer somme, moyenne ou effectif (ex. avec un dictionnaire accumulateur).

Recherche dichotomique dans une table triée : complexité O(log n) contre O(n) pour une recherche linéaire.

Client-serveur : le navigateur envoie une requête HTTP, le serveur renvoie une réponse avec un code de statut (200 OK, 404 non trouvé, 500 erreur serveur).

URL : schéma://hôte[:port]/chemin?paramètres#ancre ; les paramètres de requête suivent ? et sont séparés par &.

Méthodes HTTP : GET pour lire (paramètres dans l'URL, visibles), POST pour envoyer des données dans le corps de la requête.

HTML décrit la structure (balises, attributs id, class, href, src) ; CSS décrit la présentation ; JavaScript ajoute le comportement côté client.

Formulaire :

avec ; chaque champ porte un attribut name qui devient le nom du paramètre.

Événements JavaScript : onclick, onsubmit, addEventListener ; on peut annuler l'envoi d'un formulaire avec event.preventDefault() pour valider côté client.

Validation côté client (JavaScript) améliore l'ergonomie mais ne remplace pas la validation côté serveur, indispensable à la sécurité.

Cookie : petit texte stocké par le navigateur et renvoyé au serveur à chaque requête du même domaine ; utilisé pour sessions et préférences.

HTTPS chiffre les échanges via TLS ; sans lui, mots de passe et cookies circulent en clair.

Architecture de von Neumann : processeur (UAL + unité de contrôle), mémoire, entrées-sorties, reliés par des bus ; programme et données dans la même mémoire.

Cycle d'exécution d'une instruction : fetch (charger), decode (décoder), execute (exécuter), puis écriture du résultat ; répété à la fréquence de l'horloge.

Mémoire hiérarchisée : registres (les plus rapides), caches L1/L2/L3, RAM volatile, stockage persistant (SSD, disque) ; le temps d'accès croît avec la capacité.

Rôle du système d'exploitation : gérer les processus, allouer la mémoire, organiser les fichiers, piloter les périphériques, gérer les utilisateurs et droits.

Ordonnanceur : partage le temps CPU entre processus (temps partagé) ; un processus peut être élu, préempté, bloqué en attente d'E/S.

Système de fichiers : arborescence depuis la racine / (Unix) ou C:\ (Windows) ; chemin absolu vs relatif ; permissions r, w, x.

Commande shell : ls (lister), cd (changer de répertoire), mkdir, cp, mv, rm, cat, grep ; le tube | enchaîne la sortie d'une commande vers l'entrée d'une autre.

Réseau : adresse IP identifie une machine, port identifie un service ; TCP garantit l'ordre et la retransmission, UDP ne le garantit pas.

Périphériques et capteurs : un objet connecté associe capteur (entrée), actionneur (sortie) et unité de traitement communicante.

Trois constructions de contrôle suffisent : séquence, alternative (if/elif/else), boucle (while, for).

Fonction : paramètres, valeur de retour (return) ; sans return, la fonction renvoie None en Python ; une fonction sans effet de bord est dite pure.

Portée des variables : une variable locale existe seulement dans la fonction ; global permet de modifier une variable globale (à éviter).

Spécification : décrire pour chaque fonction le type et le rôle des paramètres, la valeur de retour, et les préconditions ; documenter avec une docstring.

Mise au point : tests unitaires avec assert, jeu de tests couvrant cas normaux, cas limites (liste vide, zéro, négatif) ; débogage par affichage ou debugger.

Exceptions : try / except / finally ; lever une erreur avec raise ValueError("message").

Récursivité : une fonction s'appelle elle-même avec un cas de base ; risque de récursion infinie ou de dépassement de pile.

Programmation objet : classe = attributs et méthodes ; instance créée par le constructeur init ; self désigne l'objet courant.

Style : noms explicites, indentation cohérente (4 espaces en Python), éviter les variables globales et la duplication de code.

Recherche linéaire : parcourir les éléments un à un, complexité O(n) dans le pire cas ; fonctionne sur toute séquence.

Recherche dichotomique : sur une séquence triée, comparer au milieu et réduire de moitié ; complexité O(log n), environ 10 étapes pour 1 000 éléments.

Tri par insertion : O(n²) dans le pire cas, O(n) si déjà trié ; tri par sélection : O(n²) quel que soit l'entrée.

Tri par fusion (merge sort) : diviser, trier, fusionner ; complexité O(n log n) dans tous les cas, mais mémoire auxiliaire O(n).

Terminaison d'une boucle while : vérifier qu'une quantité entière décroît strictement et reste bornée ; un variant garantit la sortie.

Invariant de boucle : propriété vraie avant et après chaque itération ; sert à prouver la correction d'un algorithme.

Algorithmes sur les graphes : parcours en largeur (BFS, file, plus court chemin en nombre d'arêtes), parcours en profondeur (DFS, pile ou récursion).

Complexité : compter les opérations élémentaires en fonction de la taille n des données ; ignorer les constantes et ne garder que le terme dominant.

Algorithmique gloutonne : choisir localement le meilleur candidat ; correct seulement si le problème possède la propriété du choix glouton (ex. rendu de monnaie avec pièces adaptées).