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

Les notions de cette fiche

• Systèmes sur puce — Un système sur puce regroupe dans un seul circuit des fonctions autrefois réparties sur une carte : microprocesseurs, mémoires, interfaces radio et filaires, gestion d'énergie, contrôleurs vidéo, accélérateur graphique ; avantages de cette intégration en vitesse et en consommation ; exemple du circuit d'un téléphone.
• 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.
• Services d'un système de gestion de bases de données — Un système de gestion de bases de données relationnelles (SGBD) assure la persistance des données, gère les accès concurrents de plusieurs utilisateurs ou programmes, traite les requêtes efficacement et sécurise les accès (droits des utilisateurs) ; ce que permet une base de données et que ne permet pas un simple fichier de table.
• Arbres binaires : vocabulaire et mesures — Structure hiérarchique : nœuds, racine, feuilles, sous-arbre gauche et sous-arbre droit ; taille (nombre de nœuds) et hauteur (avec une convention à préciser : un arbre réduit à sa racine a pour hauteur 1, l'arbre vide 0) ; encadrement h ⩽ n ⩽ 2^h − 1 entre la hauteur h et la taille n d'un arbre binaire non vide ; situations nécessitant une structure arborescente (arborescence de fichiers, expression arithmétique).
• Chiffrement symétrique et asymétrique — Chiffrement symétrique : la même clé, partagée, sert à chiffrer et à déchiffrer ; chiffrement asymétrique : une clé publique chiffre, seule la clé privée associée déchiffre ; en HTTPS, un protocole asymétrique sert à échanger une clé symétrique de session, puis les échanges sont chiffrés symétriquement (plus rapide) ; exemples de chiffrements simples (décalage, ou exclusif).
• Vocabulaire de la programmation objet — Une classe décrit un type d'objets ; un objet (instance) est créé en appelant la classe, ce qui exécute la méthode __init__ ; attributs (données propres à chaque objet) et méthodes (fonctions de la classe, dont le premier paramètre self désigne l'objet) ; accès par la notation pointée objet.attribut et objet.methode().
• Modèle relationnel — Une relation (table) est décrite par un schéma : son nom et ses attributs, chacun avec son domaine de valeurs ; une clé primaire identifie chaque enregistrement de façon unique ; une clé étrangère référence la clé primaire d'une autre relation ; contraintes d'intégrité de domaine, de relation et de référence ; distinguer la structure d'une base (ensemble des schémas) de son contenu ; repérer des anomalies (redondances, anomalies d'insertion, de suppression, de mise à jour).
• 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.
• Paradigmes de programmation et mise au point — Distinguer sur des exemples les paradigmes impératif, fonctionnel et objet, et les combiner dans un même programme ; reconnaître les causes typiques de bugs : problèmes de typage, effets de bord non désirés, débordement d'indice dans un tableau, instruction conditionnelle non exhaustive, mauvais choix d'inégalité, comparaison de flottants, mauvais nommage des variables ; utiliser spécification, assertions et tests pour les anticiper.
• Requêtes d'interrogation en SQL — Identifier les composants d'une requête ; construire des requêtes d'interrogation avec SELECT (colonnes, DISTINCT, fonctions d'agrégation COUNT, SUM, AVG, MIN, MAX), FROM, WHERE (conditions combinées par AND, OR, NOT), ORDER BY (ASC, DESC) et JOIN … ON pour relier deux tables par une clé étrangère.
• Requêtes de mise à jour en SQL — Construire des requêtes d'insertion (INSERT INTO … VALUES), de modification (UPDATE … SET … WHERE) et de suppression (DELETE FROM … WHERE) ; une requête de mise à jour doit respecter les contraintes d'intégrité (clé primaire unique, clé étrangère existante, domaine).
• Listes, piles et files — Structures linéaires caractérisées par leurs opérations : pile (empiler, dépiler, tester si vide ; mode LIFO, le dernier entré est le premier sorti) ; file (enfiler, défiler ; mode FIFO, le premier entré est le premier sorti) ; liste (tête et queue) ; dictionnaire (accès par clé) ; choisir la structure adaptée à une situation ; une recherche dans une liste est linéaire, un accès par clé dans un dictionnaire ne parcourt pas les éléments.
• Processus, ordonnancement et interblocage — Un processus est un programme en cours d'exécution, créé par le système d'exploitation ; états d'un processus (prêt, élu, bloqué) ; l'ordonnanceur partage le processeur entre plusieurs processus ; risque d'interblocage quand plusieurs processus attendent chacun une ressource détenue par un autre ; observer les processus actifs d'une machine.
• Programmes récursifs — Une fonction récursive s'appelle elle-même sur une donnée plus petite ; elle comporte au moins un cas de base, traité sans appel récursif, qui garantit l'arrêt ; analyser un appel par la pile des appels ou l'arbre des appels ; compter les appels effectués ; écrire une version récursive d'un calcul (factorielle, puissance, somme des chiffres).
• Protocoles de routage RIP et OSPF — Identifier la route empruntée par un paquet selon le protocole de routage : RIP choisit la route qui traverse le moins de routeurs (nombre de sauts) ; OSPF choisit la route de coût total minimal, le coût de chaque liaison dépendant de son débit ; lien avec la recherche d'un plus court chemin dans un graphe pondéré ; tables de routage données.
• Interface et implémentation d'une structure de données — Spécifier une structure de données par son interface (les opérations disponibles et leur effet) ; distinguer l'interface de l'implémentation (la façon de programmer ces opérations) ; écrire plusieurs implémentations d'une même structure, par exemple une file avec un tableau ou avec deux piles ; modularité et utilisation de bibliothèques.
• Graphes : vocabulaire et représentations — Structure relationnelle : sommets, arêtes (graphe non orienté) ou arcs (graphe orienté), voisins, degré, chemin ; modéliser une situation (réseau routier, réseau électrique, Internet, réseau social) par un graphe ; représenter un graphe par une matrice d'adjacence ou par des listes de successeurs (ou de prédécesseurs), passer d'une représentation à l'autre et choisir selon le traitement.
• Algorithmes sur les arbres binaires et les arbres binaires de recherche — Calculer récursivement la taille et la hauteur d'un arbre binaire ; parcours en profondeur dans les ordres préfixe (racine, gauche, droite), infixe (gauche, racine, droite) et suffixe (gauche, droite, racine), et parcours en largeur ; dans un arbre binaire de recherche, rechercher et insérer une clé en descendant à gauche ou à droite selon la comparaison ; coût proportionnel à la hauteur, logarithmique si l'arbre est équilibré ; le parcours infixe d'un arbre binaire de recherche donne les clés dans l'ordre croissant.
• Recherche textuelle : algorithme de Boyer-Moore — Rechercher un motif dans un texte : l'algorithme naïf compare le motif à chaque position ; l'algorithme de Boyer-Moore compare le motif de droite à gauche et, grâce à un prétraitement du motif (table de la dernière position de chaque caractère dans le motif), décale le motif de plusieurs positions en cas de non-correspondance.
• Diviser pour régner et tri fusion — Méthode « diviser pour régner » : découper le problème en sous-problèmes de même nature plus petits, les résoudre (souvent récursivement) puis combiner leurs solutions ; tri fusion : couper le tableau en deux moitiés, les trier, puis fusionner deux tableaux triés ; coût en n log₂ n dans tous les cas, contre n² pour les tris par sélection et par insertion dans le pire cas.
• Parcours de graphes — Parcours en profondeur d'abord (avec une pile ou par récursivité) et en largeur d'abord (avec une file) en marquant les sommets déjà visités ; chercher un chemin entre deux sommets ; repérer la présence d'un cycle ; le parcours en largeur d'un graphe non pondéré atteint chaque sommet par un chemin ayant le moins d'arêtes possible ; exemples du labyrinthe et du routage.
• Programmation dynamique — Résoudre un problème en combinant les solutions de sous-problèmes qui se chevauchent, chacune calculée une seule fois et mémorisée (de haut en bas avec mémoïsation, ou de bas en haut en remplissant un tableau) ; exemples du rendu de monnaie optimal (nombre minimal de pièces) et de l'alignement de séquences ; coût en mémoire de la table.
• Programme comme donnée, calculabilité et problème de l'arrêt — Tout programme est aussi une donnée, que peuvent lire ou produire d'autres programmes (interpréteur, compilateur, système d'exploitation, téléchargement) ; la calculabilité ne dépend pas du langage de programmation utilisé ; le problème de l'arrêt (décider, pour tout programme et toute entrée, si le programme s'arrête) est indécidable : aucun programme ne peut le résoudre dans tous les cas, ce que montre un raisonnement par l'absurde.

À maîtriser avant de commencer

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

• 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.
• 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).
• 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).
• 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.
• 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.
• 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.
• 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().
• 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).
• 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.
• 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.
• Graphe d'un réseau social : rayon, diamètre et centre — Un réseau social se représente par un graphe (sommets = personnes, arêtes = relations) ; distance entre deux sommets = nombre minimal d'arêtes d'un chemin qui les relie ; écartement d'un sommet = sa plus grande distance aux autres ; diamètre = plus grand écartement ; rayon = plus petit écartement ; centre = sommet(s) d'écartement égal au rayon ; notion de « petit monde » et expérience de Milgram (1967).
• 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.
• 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.
• 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).

S’entraîner sur ces notions

• S’entraîner : Comprendre un système sur puce et son budget mémoire
• S’entraîner : Situer les grandes étapes sans confondre matériel, réseau et Web
• S’entraîner : Transactions et services d’un SGBD
• S’entraîner : Arbres binaires : vocabulaire et mesures
• S’entraîner : Chiffrement symétrique et asymétrique
• S’entraîner : Classes, instances et attributs propres à chaque objet
• S’entraîner : Clés et cardinalité d’une jointure relationnelle
• S’entraîner : Coût d'un algorithme : compter les opérations
• S’entraîner : Déboguer les références et les mutations partagées
• S’entraîner : Interroger une base de données avec SQL
• S’entraîner : Modifier une base de données avec SQL
• S’entraîner : Piles, files et listes
• S’entraîner : Processus et ordonnancement par tourniquet
• S’entraîner : Récursivité : une fonction qui s'appelle elle-même
• S’entraîner : Routage : RIP compte les sauts, OSPF additionne les coûts
• S’entraîner : Séparer l’interface d’une pile de son implémentation
• S’entraîner : Sommets, arêtes et parcours dans un graphe
• S’entraîner : Arbres binaires : taille, hauteur et parcours
• S’entraîner : Comprendre le décalage du mauvais caractère
• S’entraîner : Diviser pour régner : le tri fusion
• S’entraîner : Parcourir un graphe en largeur et en profondeur
• S’entraîner : Programmation dynamique : mémoriser pour ne pas recalculer
• S’entraîner : Prouver une terminaison sans prétendre résoudre tous les programmes

Pour aller plus loin

• Toutes les fiches de révision