Correction et terminaison des programmes (MPSI)

Spécifier une fonction, la tester et prouver qu'elle termine et qu'elle est correcte, grâce aux variants et aux invariants de boucle.

MPSI · Séquence 4 sur 10 · Thèmes : Algorithmique et preuve de programmes

Notions abordées

• Spécification d'une fonction
• Jeux de tests
• Variant de boucle
• Invariant de boucle
• Correction des programmes récursifs

Ressources de la séquence

Ces ressources sont réservées aux élèves et professeurs inscrits :

• Un cours rédigéSe connecter pour ouvrir
• Une présentationSe connecter pour ouvrir
• Une série d'exercicesSe connecter pour ouvrir
• Un notebook Python à compléter, exécutable dans le navigateurSe connecter pour ouvrir

Dans le programme MPSI

• Séquence précédente : Récursivité
• Séquence suivante : Types de données composés
• Toutes les séquences de MPSI

Thèmes liés dans l'autre année

• MP · Séquence 1

  Complexité algorithmique

  Mesurer l'efficacité d'un algorithme : compter les opérations, utiliser la notation asymptotique et calculer la complexité de programmes itératifs et récursifs.

• MP · Séquence 2

  Algorithmes de tri

  Comprendre, programmer et comparer les principaux algorithmes de tri, des tris simples au tri rapide et au tri fusion.

• MP · Séquence 3

  Arbres binaires

  Représenter, parcourir et exploiter les arbres binaires, les arbres binaires de recherche et les tas.