Fiche de révision : Numérique et sciences informatiques (spécialité)

Les notions de cette fiche

• Objets connectés : capteurs, actionneurs et IHM — Un système informatique embarqué reçoit des informations de capteurs (mesures physiques) et d'une interface homme-machine, et agit sur le monde physique par des actionneurs (moteur, lampe, haut-parleur) ; identifier l'algorithme de contrôle d'un objet courant ; écrire des programmes simples d'acquisition de données ou de commande d'un actionneur ; contraintes de temps réel, de consommation, de sûreté et de sécurité.
• Écriture d'un entier positif en base 2, 10 et 16 — Écriture positionnelle d'un entier naturel dans une base b : valeur de chaque chiffre selon son rang (puissances de b) ; passage de la base 10 à la base 2 par divisions successives et inversement ; base 16 (chiffres 0 à 9 et A à F) et regroupement des bits par paquets de quatre ; bit et octet.
• Booléens, opérateurs et tables de vérité — Valeurs booléennes (vrai, faux ; 1, 0) ; opérateurs and, or, not et ou exclusif (xor) ; table de vérité d'une expression booléenne ; évaluation séquentielle de and et or en Python (le second opérande n'est évalué que si nécessaire) ; addition binaire comme application (somme = xor, retenue = and).
• Nombre de bits d'un entier, d'une somme, d'un produit — Nombre de bits nécessaires pour écrire un entier naturel n en base 2 (le plus petit k tel que n < 2^k) ; plus grand entier représentable sur k bits (2^k − 1) ; une somme de deux entiers de k bits tient sur k + 1 bits, un produit sur 2k bits ; tailles courantes des entiers (8, 16, 32 ou 64 bits) ; entiers de taille arbitraire de Python.
• Dictionnaires par clés et valeurs — Un dictionnaire associe des valeurs à des clés uniques : lecture d'une valeur par sa clé, ajout ou modification d'une entrée, test d'appartenance d'une clé ; itération sur les clés, les valeurs ou les couples avec keys(), values() et items().
• Représentation d'un texte : ASCII, ISO-8859-1, Unicode — Un texte est une suite de caractères, chacun codé par un nombre : ASCII code 128 caractères sur 7 bits, sans lettres accentuées ; ISO-8859-1 (Latin-1) étend à 256 caractères sur un octet ; Unicode attribue un numéro (point de code) à chaque caractère de toutes les écritures, et UTF-8 l'écrit sur 1 à 4 octets en restant compatible avec ASCII ; un fichier lu avec un autre encodage que celui de son écriture affiche des caractères erronés.
• Interactions entre l'homme et la machine sur le Web — Composants graphiques d'une page (boutons, champs de formulaire) décrits en HTML, et comportement programmé (en JavaScript) en réaction à des événements comme un clic ; distinguer ce qui est exécuté sur le client et sur le serveur, et dans quel ordre ; ce qui est mémorisé par le client et retransmis au serveur (cookies) ; formulaire et passage de paramètres par les requêtes GET (dans l'URL) ou POST (dans le corps de la requête) ; quand et pourquoi la transmission est chiffrée.
• p-uplets et p-uplets nommés — Un p-uplet (tuple en Python) regroupe un nombre fixé de valeurs, éventuellement de types différents, accessibles par leur indice et non modifiables ; une fonction peut renvoyer plusieurs valeurs sous forme d'un p-uplet et l'appelant les récupère par affectation multiple ; un p-uplet nommé associe un nom à chaque champ (en Python, on l'implémente par un dictionnaire).
• Parcours séquentiel d'un tableau — Parcourir un tableau élément par élément pour rechercher une occurrence, un extremum (maximum, minimum) ou calculer une moyenne ; le coût est linéaire : le nombre d'opérations est proportionnel à la longueur du tableau, et une recherche d'occurrence examine tout le tableau dans le pire cas.
• Repères de l'histoire de l'informatique — Situer dans le temps les principaux événements de l'histoire de l'informatique et leurs protagonistes : algorithmes présents dès l'Antiquité, machines à calculer à partir du XVIIe siècle, concept de machine universelle capable d'exécuter tous les algorithmes en 1936 (Alan Turing), premiers ordinateurs en 1948, réseau Internet développé depuis 1969 ; évolution des rôles relatifs des logiciels et des matériels.
• Spécification, assertions et jeux de tests — Prototyper une fonction (nom, paramètres, type du résultat) et la documenter ; décrire des préconditions sur les arguments et des postconditions sur le résultat ; les vérifier par des assertions (assert) ; construire un jeu de tests couvrant les cas ordinaires et les cas limites ; un jeu de tests réussi ne prouve pas la correction d'un programme ; diversité des langages et constructions élémentaires communes.
• Systèmes d'exploitation et ligne de commande — Fonctions d'un système d'exploitation : lancer et gérer les programmes, gérer la mémoire, les fichiers, les périphériques et les utilisateurs ; systèmes libres et propriétaires ; commandes de base en ligne de commande (se déplacer dans l'arborescence, lister, créer, copier, déplacer, supprimer des fichiers) ; droits et permissions d'accès aux fichiers (lecture, écriture, exécution, pour le propriétaire, le groupe et les autres).
• Tableaux indexés et tableaux de tableaux — Tableau (list en Python) dont les éléments sont de même type : lecture et modification d'un élément par son indice, de 0 à len(t) − 1 ; parcours par indice ou par élément ; construction par compréhension ; tableau de tableaux pour représenter une matrice, élément a[i][j] à la ligne i et à la colonne j.
• Algorithmes gloutons — Un algorithme glouton construit une solution pas à pas en faisant à chaque étape le choix qui paraît le meilleur sur le moment, sans revenir en arrière ; rendu de monnaie (rendre la plus grande pièce possible), problème du sac à dos ; la solution obtenue n'est pas toujours optimale : elle l'est pour le rendu de monnaie avec les pièces et billets en euros, pas avec un système comme (1, 3, 4).
• Algorithme des k plus proches voisins — Exemple d'algorithme d'apprentissage : pour prédire la classe d'un nouvel élément, on calcule sa distance à chaque élément d'un jeu de données déjà classé, on retient les k plus proches et on attribue la classe majoritaire parmi eux ; influence du choix de k et de la distance ; un k impair évite les égalités entre deux classes.
• Entiers relatifs en complément à deux — Représentation d'un entier relatif sur n bits par le complément à deux : le bit de poids fort a le poids −2^(n−1) ; intervalle représentable de −2^(n−1) à 2^(n−1) − 1 ; codage de −x en inversant les bits de x puis en ajoutant 1 ; l'addition binaire ordinaire reste valable, la retenue sortante étant ignorée ; dépassement de capacité.
• Coût d'un algorithme : ordre de grandeur du nombre d'opérations — Estimer comment le nombre d'opérations d'un algorithme varie avec la taille n des données : coût constant, logarithmique (la donnée est divisée par deux à chaque étape), linéaire (une boucle sur les n éléments), quadratique (deux boucles imbriquées) ; quand n double, un coût linéaire double, un coût quadratique est multiplié par quatre, un coût logarithmique augmente d'une étape ; intérêt de passer d'un coût quadratique en n² à n log₂ n, ou de n à log₂ n, sur des données nombreuses.
• Transmission de données dans un réseau — Intérêt du découpage des données en paquets et de leur encapsulation (chaque couche de protocole ajoute son en-tête) ; dérouler un protocole simple de récupération de perte de paquets, le protocole du bit alterné (chaque message porte un bit 0 ou 1 alternativement, l'accusé de réception renvoie ce bit, et l'émetteur réémet après un délai sans accusé) ; rôle des constituants d'un réseau local ; simuler un réseau.
• Traitement de données en tables — Une table est une liste de p-uplets nommés (ou un tableau doublement indexé) partageant les mêmes descripteurs : importer une table depuis un fichier CSV ; rechercher les lignes vérifiant un critère écrit en logique propositionnelle ; trier une table selon une colonne ; construire une table en fusionnant deux tables sur un descripteur commun ; repérer doublons et incohérences.
• Nombres flottants : une représentation approchée des réels — Un nombre flottant est représenté en base 2 avec un nombre fini de chiffres significatifs : seuls certains décimaux sont exacts (ceux qui s'écrivent avec un dénominateur puissance de 2, comme 0,25 ou 0,5) ; 0,1 et 1/3 n'ont pas d'écriture binaire finie ; en Python, 0.1 + 0.2 == 0.3 vaut False ; il faut éviter de tester l'égalité de deux flottants et comparer plutôt leur écart à une tolérance.
• Modèle d'architecture de von Neumann — Constituants d'une machine : unité arithmétique et logique, unité de commande, mémoire contenant à la fois le programme et les données, dispositifs d'entrée-sortie, reliés par des bus ; architectures monoprocesseur et multiprocesseur ; dérouler l'exécution d'une séquence d'instructions simples de type langage machine (lecture, calcul, écriture, saut) ; les circuits combinatoires réalisent des fonctions booléennes.
• Recherche dichotomique dans un tableau trié — Dans un tableau TRIÉ, on compare la valeur cherchée à l'élément du milieu et on poursuit dans la moitié qui peut la contenir ; la largeur de l'intervalle de recherche (variant de boucle) diminue strictement à chaque tour, ce qui prouve la terminaison ; le nombre de tours est au plus ⌊log₂ n⌋ + 1, soit un coût logarithmique, contre un coût linéaire pour le parcours séquentiel.
• Tris par sélection et par insertion — Tri par sélection : à l'étape i, on cherche le minimum de la partie non triée et on l'échange avec l'élément d'indice i ; il effectue toujours n(n − 1)/2 comparaisons. Tri par insertion : on insère chaque élément à sa place dans la partie déjà triée, en décalant les plus grands ; de n − 1 comparaisons (tableau déjà trié) à n(n − 1)/2 (tableau trié à l'envers). Invariant de boucle (« après l'étape i, les i + 1 premiers éléments sont triés »), terminaison, coût quadratique dans le pire cas.

À maîtriser avant de commencer

Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.

• Instructions conditionnelles — Instruction if, avec elif et else : une seule branche est exécutée, la première dont la condition est vraie ; conditions écrites avec les comparaisons (==, !=, <, <=, >, >=) et les opérateurs booléens ; le bloc d'une branche est délimité par l'indentation.
• Boucles bornées et non bornées — Boucle bornée for, en particulier for i in range(a, b) qui fait prendre à i les valeurs a, a + 1, …, b − 1 ; boucle non bornée while, répétée tant que sa condition est vraie ; dérouler une boucle à la main dans un tableau de suivi des variables (traçage) ; accumulateur (somme, compteur) ; choix entre les deux boucles.
• Le Web : HTML, CSS, URL, HTTP et modèle client-serveur — Le Web est un système de pages reliées par des liens hypertextes et accessibles par Internet ; une page est écrite en HTML (contenu et structure, balises) et mise en forme par CSS (style) ; chaque page a une adresse unique, l'URL, qui se décompose en protocole, nom de domaine et chemin ; le navigateur (client) envoie des requêtes HTTP au serveur, qui renvoie des pages stockées ou fabriquées à la demande ; HTTPS chiffre les échanges ; repères historiques (naissance du Web au CERN en 1989) ; notions juridiques (licence, droit d'auteur, droit d'usage) ; réglages de sécurité et de confidentialité du navigateur (cookies).
• Définition et appel de fonctions — Définir une fonction avec def, ses paramètres et l'instruction return qui renvoie un résultat et termine l'exécution de la fonction ; appeler une fonction avec des arguments ; variables locales ; différence entre renvoyer une valeur (return) et l'afficher (print).
• Internet : protocole TCP/IP, paquets et routage — Les informations circulent sur Internet découpées en paquets contenant les données et les adresses de l'émetteur et du destinataire ; le protocole IP identifie les machines et achemine chaque paquet de routeur en routeur, chacun choisissant le suivant d'après sa table ; le protocole TCP fiabilise la communication (accusés de réception, réémission des paquets perdus, remise dans l'ordre) mais ne garantit aucun délai d'arrivée ; un paquet est détruit au-delà d'un nombre maximal de routeurs traversés ; Internet est indépendant du réseau physique (fibre, Wi-Fi, 4G, Ethernet…).
• Données structurées, descripteurs et métadonnées — Une donnée est une valeur décrivant un objet ; un descripteur nomme la caractéristique décrite (nom, date…) ; une collection d'objets partageant les mêmes descripteurs se présente en table (objets en ligne, descripteurs en colonne) ; le format CSV enregistre une table en texte avec des séparateurs ; les métadonnées décrivent un fichier ; une donnée personnelle se rapporte à une personne identifiable ; stockage dans le nuage et consommation énergétique des centres de données.

S’entraîner sur ces notions

• S’entraîner : Capteurs, traitement et actionneurs
• S’entraîner : Bases 2, 10 et 16 : un même nombre, plusieurs écritures
• S’entraîner : Booléens : vrai, faux, et les opérateurs and, or, not
• S’entraîner : Combien de bits pour écrire un entier ?
• S’entraîner : Dictionnaires : associer une clé à une valeur
• S’entraîner : Encoder un texte : ASCII, Latin-1 et UTF-8
• S’entraîner : Événements et état d’une interface web
• S’entraîner : p-uplets : regrouper plusieurs valeurs
• S’entraîner : Parcours séquentiel d'un tableau
• S’entraîner : Situer les grandes étapes sans confondre matériel, réseau et Web
• S’entraîner : Spécifier une fonction et choisir ses tests
• S’entraîner : Système d'exploitation, commandes et permissions
• S’entraîner : Tableaux indexés et tableaux de tableaux
• S’entraîner : Algorithmes gloutons : le meilleur choix immédiat
• S’entraîner : Classer par les k plus proches voisins
• S’entraîner : Complément à deux : écrire les entiers négatifs en binaire
• S’entraîner : Coût d'un algorithme : compter les opérations
• S’entraîner : Distinguer transmission et propagation d’un paquet
• S’entraîner : Filtrer, sélectionner et agréger une table
• S’entraîner : Nombres flottants : pourquoi 0,1 + 0,2 ne fait pas 0,3
• S’entraîner : Programme et données dans une architecture de von Neumann
• S’entraîner : Recherche dichotomique : couper en deux à chaque étape
• S’entraîner : Trier un tableau : sélection et insertion

Pour aller plus loin

• Toutes les fiches de révision