⌨ Spécialité NSI · Numérique et sciences informatiques Terminale Générale · Chapitre 9

Calculabilité, modularité et paradigmes de programmation

Programme en tant que donnée, notion de calculabilité et indécidabilité du problème de l'arrêt, modularité (modules, API, interfaces), paradigmes impératif, fonctionnel et objet, et gestion des bugs.

1. Programme en tant que donnée

Un programme peut être la donnée d'un autre programme ; plusieurs paradigmes permettent d'écrire un même algorithme.

Définition

Un programme est lui-même une donnée : un compilateur prend un programme en entrée et produit un autre programme ; un interpréteur l'exécute ; un système d'exploitation charge des programmes en mémoire. Cette idée remonte à Alan Turing (1936) et sa machine universelle.

2. Calculabilité et problème de l'arrêt

Propriété · Indécidabilité

Une fonction est calculable s'il existe un algorithme qui la calcule. Turing a démontré qu'il n'existe aucun programme arret(prog, x) capable de dire, pour tout programme et toute entrée, si le programme s'arrête : le problème de l'arrêt est indécidable.

Exemple · Idée de la preuve

def paradoxe(p):
    if arret(p, p):
        while True:
            pass
    return 0

Si paradoxe(paradoxe) s'arrête, alors arret répond vrai et le programme boucle ; s'il boucle, arret répond faux et il s'arrête : contradiction. Donc arret ne peut pas exister.

3. Modularité

Définition

Un logiciel est découpé en modules qui proposent une interface (ou API) documentée : on peut les utiliser sans connaître leur implémentation, les tester et les remplacer séparément. En Python, un fichier outils.py s'importe avec import outils.

4. Paradigmes

Propriété · Trois styles

Impératif : suite d'instructions qui modifient l'état (variables, boucles). Fonctionnel : composition de fonctions sans effet de bord, sans modifier les données (fonctions pures, récursivité, map, filter, fonctions passées en argument). Objet : objets regroupant données et méthodes. Python permet les trois ; d'autres langages en privilégient un (Haskell : fonctionnel ; Java : objet ; C : impératif).

Exemple · Même calcul, deux paradigmes

# impératif
s = 0
for x in t:
    if x > 0:
        s = s + x * x
# fonctionnel
s = sum(map(lambda x: x * x, filter(lambda x: x > 0, t)))

Activité · Créer un module

MatérielPython, deux fichiers dans le même dossier.

ConsigneÉcrire geometrie.py contenant aire_disque(r) et perimetre_disque(r) documentées, puis les utiliser depuis main.py.

Résultatimport geometrie ; geometrie.aire_disque(2) ; help(geometrie) affiche la documentation.

BilanLa documentation du module est son contrat avec les programmes qui l'utilisent.

Attention · Bugs

Erreurs fréquentes : dépassement de capacité, erreurs d'arrondi des flottants, effets de bord inattendus, accès hors limites, mauvaise gestion des cas limites. Les tests, les assertions et la relecture du code limitent leur nombre.

S'entraîner

Exercices corrigés

🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.

Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.

Créer un compte gratuit Se connecter