⌨ 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

programme source (texte)compilateurprogramme machinele programme source est une DONNÉE du compilateurimpératif : instructionsfonctionnel : fonctionsobjet : classestrois paradigmes, un même problème
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.

⚠️ Une erreur dans ce cours ? Signalez-la

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.

4

Paradoxe

★★★

On suppose qu'il existe une fonction arret(prog, x) qui renvoie True si le programme prog s'arrête sur l'entrée x, False sinon, et l'on écrit la fonction ci-dessous. Expliquer la contradiction obtenue avec paradoxe(paradoxe).

def paradoxe(p):
    if arret(p, p):
        while True:
            pass
    return 0
🔒 Correction réservée aux membres Créer un compte gratuit →
17

Bug célèbre

★★☆

En 1996, la fusée Ariane 5 a explosé à cause d'un bug : la conversion d'un flottant en entier sur $16$ bits a débordé. De quel type d'erreur s'agit-il ?

🔒 Correction réservée aux membres Créer un compte gratuit →

Vérifier

Avez-vous bien compris ?

Répondez au quiz : la correction s'affiche immédiatement.