Ch1 — Algorithmique et raisonnement logique · Exercices WIMS
Raisonnement logique
Implication : « Si P alors Q » est fausse seulement quand P est vraie et Q est fausse.
Réciproque : « Si Q alors P » (pas équivalente !).
Contraposée : « Si non-Q alors non-P » (équivalente).
Quantificateurs : \(\forall\) (pour tout), \(\exists\) (il existe).
Algorithmique
Variables, affectation, boucle for/while, conditionnelle if/else.
Complexité : nombre d’opérations en fonction de la taille de l’entrée.
Terminaison : la boucle s’arrête toujours.
Raisonnement par récurrence
Pour montrer \(P(n)\) pour tout \(n \geq n_0\) :
- Initialisation : vérifier \(P(n_0)\).
- Hérédité : supposer \(P(n)\) vraie, montrer \(P(n+1)\).
La récurrence forte suppose \(P(k)\) pour tout \(k \leq n\).