Panorama de l'année#
Les quatorze chapitres de l’année ne sont pas indépendants : les mêmes outils (la récursivité, la pile, la file…) reviennent d’un chapitre à l’autre, et une même question — « combien ça coûte ? » — traverse toute l’année. Ces pages donnent une vue d’ensemble, à relire à chaque nouveau chapitre : elles aident à prendre du recul pour l’écrit comme pour le Grand Oral.
Le plan de l’année en quatre blocs#
Le programme se partage en quatre grands blocs. Dans chaque bande, on lit les chapitres du bloc ; leur numéro indique l’ordre dans lequel on les étudie au fil de l’année.
L’année ne parcourt pas les blocs l’un après l’autre : elle alterne. Après les outils de base (chapitres 1 à 3), on découvre la machine dès l’automne (processus), puis de nouvelles structures et méthodes ; viennent ensuite le réseau et sa sécurité, juste après les graphes dont ils ont besoin, de nouveaux algorithmes au printemps, et l’on termine par les limites de l’informatique et les systèmes sur puce.
Le fil rouge : le coût d’un algorithme#
Depuis la Première, on ne se demande pas seulement « est-ce que ça marche ? » mais aussi « combien d’opérations cela demande-t-il quand les données sont nombreuses ? ». On range les algorithmes sur une échelle de coût (\(n\) désigne la taille des données) :
Toute l’année, on cherche à descendre cette échelle, ou à contourner le problème quand c’est impossible. Chaque grande méthode correspond à une stratégie :
| Stratégie | L’idée | Chapitre |
|---|---|---|
| Bien ranger les données | Avec des données organisées (triées, ou dans un arbre binaire de recherche), on élimine la moitié des candidats à chaque étape : on passe de n à log2n. | 5 Arbres (dichotomie : 1re) |
| Diviser pour régner | Couper le problème en deux, résoudre chaque moitié, recombiner : le tri fusion passe de n2 à nlog2n. | 7 Diviser pour régner |
| Ne jamais recalculer | Mémoriser les résultats des sous-problèmes : on échange du temps contre de la mémoire. | 11 Programmation dynamique |
| Renoncer à l’optimum | Quand la solution exacte est hors de portée (voyageur de commerce : essayer tous les trajets), un algorithme glouton donne vite une solution, pas toujours la meilleure. | glouton : 1re (comparé en 11) |
| Faire du coût un bouclier | Le chiffrement RSA est sûr parce que factoriser un très grand nombre coûte trop cher avec les méthodes connues. | 10 Cryptographie |
Remarque
Le \(\log_2 n\) n’est qu’un outil de comptage : c’est le nombre de fois où l’on peut couper \(n\) en deux avant d’arriver à \(1\) (à peu près le nombre de bits de \(n\), vu en Première). Pour un million de données, \(\log_2 n \approx 20\).
Chapitre par chapitre#
Pour chaque chapitre : ce qu’il réutilise, et où il resservira. Les notions de Première sont signalées par « 1re ».
| Chapitre | S’appuie sur… | Resservira dans… |
|---|---|---|
| 1 Récursivité | fonctions (1re) | arbres, diviser pour régner, parcours en profondeur, programmation dynamique |
| 2 Programmation objet | types construits (1re) | toutes les structures : classes Pile, File, Arbre, Graphe |
| 3 Piles, files, listes chaînées | programmation objet, récursivité | parcours d’arbres et de graphes ; file des processus prêts |
| 4 Processus | files ; arborescence de fichiers, modèle de von Neumann (1re) | arbres (l’arbre des processus) ; graphes (le cycle d’un interblocage) ; systèmes sur puce |
| 5 Arbres | récursivité, programmation objet, piles et files ; dichotomie (1re) | index des bases de données ; graphes (un arbre est un graphe particulier) |
| 6 Bases de données, SQL | données en table (1re) ; arbres (les index) | projets (site web adossé à une base) ; Grand Oral (données, vie privée) |
| 7 Diviser pour régner | récursivité ; dichotomie, tris (1re) | programmation dynamique (même découpage, sans recalcul) |
| 8 Graphes | piles et files, récursivité, programmation objet, arbres ; graphe d’attente (processus) | routage (réseaux) ; GPS |
| 9 Réseaux | graphes pondérés (Dijkstra) ; Internet, paquets (1re) | cryptographie (sécuriser ce qui circule) |
| 10 Cryptographie | réseaux ; coût (factorisation) | HTTPS, signature, sécurité des échanges |
| 11 Programmation dynamique | récursivité, diviser pour régner ; glouton (1re) | problèmes d’optimisation (rendu de monnaie, sac à dos) |
| 12 Recherche textuelle | chaînes, boucles, coût (1re) | moteurs de recherche, traitement de texte, ADN |
| 13 Calculabilité | un programme est une donnée (1re) | limites de tout programme (un antivirus parfait est impossible) |
| 14 Systèmes sur puce | modèle de von Neumann (1re) ; processus | synthèse : le téléphone, un ordinateur complet sur une puce |
Remarque
Pour le Grand Oral, ces liens sont précieux : une bonne question en croise souvent deux (« Comment un message trouve-t-il son chemin sur Internet ? » \(=\) graphes, pour le plus court chemin, \(+\) réseaux, pour le routage). Voir les pages Préparer les épreuves, en fin de livre.
Une histoire de l’informatique en quelques dates#
Chaque date de cette frise correspond à une notion que l’on étudie cette année, dans le chapitre indiqué à droite. Certaines sont bien plus anciennes que les ordinateurs (les graphes, les tours de Hanoï) ; la plupart sont nées entre 1936 et 1980.
mainmattertrue