« Informatique Tronc Commun — CPGE scientifiques 1re et 2e années »

Manuel de cours (602 pages) conforme au nouveau programme d’informatique des CPGE scientifiques (2021-2022). Thierry Audibert, ancien professeur en CPGE, et Amar Oussalah, maître de conférences, proposent une progression rigoureuse sur trois semestres, avec pour chaque chapitre cours, preuves, analyse de complexité et exercices corrigés. Le langage utilisé est Python.

Idée centrale : concevoir des algorithmes corrects et efficaces, en articulant systématiquement compréhension, preuve de correction et analyse de complexité.

Partie I — Premier semestre (les fondations)

• Ch. 1 — Programmer avec Python : bases du langage, types, structures de contrôle, fonctions, numpy, matplotlib.
• Ch. 2 — Algorithmes itératifs fondamentaux : arithmétique, recherche séquentielle et dichotomique, boucles imbriquées.
• Ch. 3 — Récursivité : pensée récursive, terminaison, correction.
• Ch. 4 — Les tris : insertion, rapide, fusion, dichotomique ; complexité comparée.
• Ch. 5 — Algorithmes gloutons : stratégie gloutonne, rendu de monnaie, sac à dos.
• Ch. 6 — Traitement de l’image : tableaux numpy, transformations géométriques, filtres par convolution.

Partie II — Deuxième semestre (fondements théoriques et structures avancées)

• Ch. 7 — Calcul numérique : représentation binaire, flottants IEEE 754, erreurs d’arrondi.
• Ch. 8 — Preuves et complexité : spécification, invariants, notations O, récurrences.
• Ch. 9 — Graphes : représentations, parcours, composantes connexes, Dijkstra.
• Ch. 10 — Programmation objet : classes, méthodes, encapsulation, application aux graphes.

Partie III — Troisième semestre (domaines spécialisés)

• Ch. 11 — Bases de données / SQL : modèle relationnel, algèbre relationnelle, requêtes SQL.
• Ch. 12 — Dictionnaires : tables de hachage, compression LZ78.
• Ch. 13 — Programmation dynamique : mémoïsation, distance d’édition, Roy-Floyd-Warshall.
• Ch. 14 — Algorithmes pour les jeux : jeux sur graphes, minimax, attracteurs.
• Ch. 15 — Étiquetage et classification : k-plus proches voisins, k-moyennes, scikit-learn.

Annexes : glossaire, bibliographie, index.

Ce livre s’adresse aux étudiants de CPGE scientifiques (MPSI, PCSI, PTSI, BCPST…) et à tout autodidacte souhaitant acquérir des bases solides en algorithmique Python, de l’initiation jusqu’aux algorithmes avancés.