#Slides — Pensée computationnelle

Support de révision : chaque point peut servir de titre de diapositive. Le module complet couvre décomposition, abstraction, algorithmes, complexité et les animations.

#Ouverture

La pensée computationnelle : formuler un problème pour qu'une machine puisse le résoudre.
Quatre piliers : décomposer, abstraire, algorithmiser, évaluer.

Diviser un problème complexe en sous-problèmes plus simples et indépendants.
Étapes : identifier, diviser, définir les interfaces, résoudre, intégrer.
Chaque brique a un contrat : entrée, sortie, garantie.
Avantages : simplicité, réutilisabilité, testabilité, collaboration.
Exemple fil rouge : fréquences de mots. Nettoyer, découper, compter, trier.
Invariants de boucle : la propriété vraie à chaque itération, outil de preuve.
Définition inductive : une base finie, des règles de construction, et le plus petit ensemble clos. Non ambiguë = chaque élément a une seule construction.
Une décomposition ambiguë fait compter faux (exemple des additions booléennes).
La décomposition choisie détermine la récurrence : mots sans 00 → Fibonacci.

Séparer le « quoi » (spécification) du « comment » (implémentation).
Trois niveaux : données (types), procédures (contrats de fonctions), contrôle (parcours, transformations).
ADT : opérations et propriétés sans imposer l'implémentation.
Contrats : préconditions, postconditions, invariants.
Encapsulation : changer l'intérieur sans casser les appelants.
Domaine de définition = précondition ; fonction partielle = précondition non vide.
Curryfication : $f(a,b) = \mathrm{Curry}(f)(a)(b)$ ; ramène une interface à l'arité attendue.

Définition : séquence finie, précise, avec entrées et sorties.
Cinq propriétés : finitude, précision, entrées, sorties, faisabilité.
Correction = terminaison + validation partielle.
Terminaison récursive : mesure strictement décroissante dans un ordre bien fondé.
Induction structurelle : borner un arbre à $n$ nœuds donne $h \ge \log_2(n+1)$ .
Recherche linéaire : O(n), aucune hypothèse sur les données.
Recherche dichotomique : O(log n), exige un tableau trié ; espace divisé par 2 à chaque tour.
Tri à bulles : O(n²) ; O(n) sur entrée déjà triée avec détection d'échange.
Tri rapide : partition autour d'un pivot puis récursion ; O(n log n) moyen, O(n²) pire cas.

Grand-O : taux de croissance du coût, constantes et termes dominés ignorés.
Ordres : O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
n = 1 000 : 1, 10, 1 000, 10 000, 1 000 000, un nombre à 302 chiffres, un nombre à 2 568 chiffres.
$2^{n}$ opérations à 1 µs : 1 s pour n = 20, 12,7 jours pour n = 40, 366 siècles pour n = 60.
Voyageur de commerce par force brute : $(n-1)!$ parcours ; 12 villes ≈ 40 s, 20 villes ≈ 3 900 ans.
Temps contre espace : la mémoïsation échange de la mémoire contre du temps.
Pire cas, cas moyen, meilleur cas : annoncer lequel on communique.
Amorti : coût lissé d'opérations ponctuellement chères (ajout de liste).
Récurrence de coût : $T(n) = T(n-1) + n$ → quadratique ; $T(n) = 2T(n-1) + 1$ → $2^{n}-1$ ; $T(n) = 1 + T(n/2)$ → $1 + \log_2 n$ .
Tri rapide au pire cas : $c(n) = c(n-1) + n + 1$ → $(n^2+3n-4)/2$ , soit $\Theta(n^2)$ .

Un seul geste : penser en contrats (entrées, sorties, garanties) avant de penser en code.
Trois verbes pour les fondements : prouver (induction bien fondée), compter (avant d'énumérer), résoudre (la récurrence de coût).
Pour s'entraîner : les annales corrigées couvrent l'induction, le dénombrement et les récurrences sur douze exercices corrigés.
Pour manipuler les structures : animations interactives.