Algorithmique et logique

Fiches de cours et sous-notions liées à ce chapitre.

Pas assez de questions pour un entraînement ciblé sur cette notion.

Logique

Non commencé

Définitions

La logique mathématique formalise les assertions vraies ou fausses. La négation de « pour tout $x$ , $P(x)$ » est « il existe $x$ tel que non $P(x)$ ».

L'implication $P\Rightarrow Q$ a pour contraposée $\neg Q\Rightarrow\neg P$ (équivalente). La réciproque $Q\Rightarrow P$ n'est pas toujours vraie.

Pourquoi ça marche : la logique fixe le sens des quantificateurs et implications ; un algorithme décrit une procédure finie. La récurrence prouve une propriété pour tout entier en initialisant puis en héritant.

Formules

$\neg(\forall x,\ P(x)) \equiv \exists x,\ \neg P(x)$
$\neg(\exists x,\ P(x)) \equiv \forall x,\ \neg P(x)$
$(P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P)$
$\neg(P \land Q) \equiv \neg P \lor \neg Q$

Exemples

Exemple 1

La négation de « tout $x$ est positif » est…

Méthode

Étape 1 : repérer les données.

Étape 2 : Négation de $\forall$ : $\exists x$ non positif (négatif ou nul).

Étape 3 : conclure avec Il existe $x$ non positif.

Résultat

Il existe $x$ non positif

Exemple 2

Si $P\Rightarrow Q$ , quelle est la contraposée ?

Méthode

Étape 1 : repérer les données.

Étape 2 : Contraposée : $\neg Q\Rightarrow\neg P$ (équivalente à $P\Rightarrow Q$ ).

Étape 3 : conclure avec $\neg Q \Rightarrow \neg P$ .

Résultat

$\neg Q \Rightarrow \neg P$

À retenir

Algorithmique

Non commencé

Définitions

L'algorithmique décrit une méthode de résolution en étapes précises (pseudo-code). Structures de base : séquence, alternative (si…alors…sinon), boucle pour, boucle tant que.

En Seconde, on lit et écrit des algorithmes simples : entrées/sorties, tests, boucles. La notion de complexité ( $O(\log n)$ , algorithmes gloutons…) relève du programme NSI en Terminale, pas des maths de Seconde.

Pourquoi distinguer : le périmètre mesure le contour (unité de longueur), l’aire la surface (unité²), le volume l’espace (unité³). Les formules découlent du découpage ou du produit « base × hauteur » (avec les bons coefficients).

Formules

$\text{Tant que } C \text{ faire } \ldots$
$\text{Pour } i \text{ de } 1 \text{ à } n \text{ faire } \ldots$
$\text{Si } C \text{ alors } \ldots \text{ sinon } \ldots$

Exemples

Exemple 1

Quelle structure répète un bloc tant qu'une condition est vraie ?

Méthode

Étape 1 : repérer les données.

Étape 2 : La boucle conditionnelle « tant que » répète tant que la condition reste vraie.

Étape 3 : conclure avec Tant que.

Résultat

Tant que

Exemple 2

Quelle structure répète un bloc un nombre fixe de fois ?

Méthode

La boucle « pour » parcourt un compteur connu à l'avance ( $1$ à $n$ ). On vérifie ensuite que le résultat Pour est cohérent avec l’énoncé.

Résultat

Pour