Un algorithme décrit une suite finie d'étapes pour résoudre un problème. Le cours utilise le Pascal, langage mentionné dans la maquette du document. Les exercices se travaillent sur papier ; les ateliers interactifs de l'application restent consacrés à Python et SQL.
Définition 1 (Structures de contrôle en Pascal). Une condition s'écrit if condition then instruction else instruction. Une boucle bornée s'écrit for i := 1 to n do instruction. Une boucle conditionnelle s'écrit while condition do instruction. Plusieurs instructions se regroupent entre begin et end. On utilise := pour affecter et = pour comparer.
Exercice 2 (Sommer les entiers de 1 à n). On suppose $n\geq0$. Étudier l'algorithme Pascal s := 0; for i := 1 to n do s := s + i;. Donner les valeurs successives de $s$ pour $n=4$, justifier le résultat général et traiter $n=0$.
Indice
Après l'itération $i$, quelle somme la variable $s$ contient-elle ?
Solution
Pour $n=4$, les valeurs de $s$ sont successivement $0,1,3,6,10$. L'invariant est : après l'itération $i$, $s=1+\cdots+i=i(i+1)/2$. Il est vrai au départ avec la somme vide ; ajouter $i$ conserve la propriété. À la fin, $s=n(n+1)/2$. Pour $n=0$, la boucle ne s'exécute pas et $s=0$. Le programme effectue $n$ additions, avec un type entier assez grand pour éviter un dépassement.
Tableaux et invariants
Définition 3 (Invariant de boucle). Un invariant est une propriété vraie avant une boucle, conservée par chaque itération, et qui aide à conclure à la sortie. Une preuve complète établit aussi la terminaison, par exemple grâce à un compteur borné ou à un entier positif qui décroît.
Exercice 4 (Rechercher le maximum d’un tableau). Un tableau $A[1..n]$ contient $n\geq1$ entiers. Proposer un algorithme Pascal pour trouver son maximum et expliquer pourquoi initialiser le maximum à $0$ serait incorrect en général.
Indice
Le maximum provisoire doit être une valeur du tableau, même si toutes les valeurs sont négatives.
Solution
On initialise m := A[1]. Puis for i := 2 to n do if A[i] > m then m := A[i]. Après chaque étape, $m$ est le maximum des éléments déjà examinés. À la fin, tous les éléments ont été vus, donc $m$ est le maximum du tableau. Si $n=1$, aucune comparaison n'est nécessaire. Initialiser à $0$ échoue pour $[-5,-2,-9]$ : le programme rendrait $0$, qui n'appartient même pas au tableau. La méthode utilise $n-1$ comparaisons.
Exercice 5 (L’algorithme d’Euclide). Pour deux entiers strictement positifs $a,b$, on répète r := a mod b; a := b; b := r tant que $b\ne0$. Exécuter cet algorithme pour $(84,30)$ et justifier le résultat.
Indice
Utilise $\gcd(a,b)=\gcd(b,a\bmod b)$. Le reste est strictement plus petit que le diviseur.
Solution
Les couples successifs sont $(84,30)$, $(30,24)$, $(24,6)$, puis $(6,0)$. Le résultat est donc $a=6$. À chaque étape, $a=qb+r$ implique qu'un entier divise $a$ et $b$ si et seulement s'il divise $b$ et $r$ : le PGCD est conservé. Les valeurs positives de $b$ décroissent strictement, donc la boucle termine. À la sortie, $\gcd(a,0)=a=6$.
Vérifie ta compréhension. Dans une boucle while, quel argument prouve la terminaison ?
Une propriété simplement conservée
Un entier naturel qui décroît strictement à chaque itération
La présence d’une affectation
Réponse
Bonne réponse : B.
Un entier naturel ne peut pas décroître strictement indéfiniment. Un invariant seul explique la correction du résultat, mais ne garantit pas l’arrêt.
Remarque 6 (Repères du parcours L1). Les modules transversaux regroupent plusieurs UE ; les durées proposées sont des repères de travail personnel.
Exercices corrigés
Chaque exercice propose un indice et une solution détaillée : essaie d'abord, puis compare.
Tome I · Amateur
Découvrir les méthodes et appliquer les définitions et les résultats du cours.
Exercice 1 (Pair ou impair). Expliquer l'instruction Pascal if n mod 2 = 0 then writeln('pair') else writeln('impair') et donner l'affichage pour $n=7$ et pour $n=-4$.
Indice
n mod 2 donne le reste de la division de $n$ par $2$.
Solution
Si le reste vaut $0$, $n$ est pair, sinon il est impair. Pour $n=7$, le reste vaut $1$ : affichage « impair ». Pour $n=-4$, le reste vaut $0$ : affichage « pair ». Pour un $n$ négatif impair, le reste vaut $1$ ou $-1$ selon le compilateur ; dans les deux cas il n'est pas nul, et le test reste correct.
Exercice 2 (Compter les chiffres). On veut compter les chiffres d'un entier $n\ge0$. Comparer c := 0; while n > 0 do begin n := n div 10; c := c + 1 end et c := 0; repeat n := n div 10; c := c + 1 until n = 0. Exécuter les deux pour $n=4096$, puis pour $n=0$.
Indice
Une boucle while peut ne jamais s'exécuter ; une boucle repeat s'exécute au moins une fois.
Solution
Pour $4096$, les deux boucles divisent successivement en $409$, $40$, $4$, $0$ et donnent $c=4$. Pour $n=0$, la boucle while ne s'exécute pas et renvoie $0$ chiffre, alors que $0$ s'écrit avec un chiffre ; la boucle repeat donne bien $1$. Il faut toujours tester les cas limites.
Exercice 3 (Le maximum de trois nombres). Écrire une fonction Pascal max2(a, b: integer): integer qui renvoie le plus grand de deux entiers, puis l'utiliser pour calculer le maximum de trois entiers $a$, $b$ et $c$.
Indice
Dans une fonction Pascal, on affecte le résultat au nom de la fonction.
Solution
function max2(a, b: integer): integer; begin if a >= b then max2 := a else max2 := b end; Le maximum de trois entiers s'obtient par m := max2(max2(a, b), c). Décomposer un problème en petites fonctions testées séparément rend le programme plus fiable.
Tome II · Entraînement
Combiner plusieurs notions et rédiger une démarche complète.
Exercice 1 (La somme des chiffres et son invariant). Étudier s := 0; while n > 0 do begin s := s + n mod 10; n := n div 10 end pour $n=2026$. Proposer un invariant de boucle qui prouve que $s$ contient la somme des chiffres de l'entier initial $n_0$ en fin de boucle.
Indice
À chaque tour, le dernier chiffre de $n$ passe dans $s$.
Solution
Les valeurs successives de $(s,n)$ sont $(0,2026)$, $(6,202)$, $(8,20)$, $(8,2)$, $(10,0)$ : la somme vaut $10$. Invariant : « $s$ + somme des chiffres de $n$ = somme des chiffres de $n_0$ ». Il est vrai au départ et conservé par chaque tour. À la sortie, $n=0$, donc $s$ est la somme cherchée. La boucle termine car $n$ décroît strictement.
Exercice 2 (Rechercher une valeur). On cherche si $x$ apparaît dans un tableau $A[1..n]$ avec trouve := false; i := 0; while (i < n) and not trouve do begin i := i + 1; if A[i] = x then trouve := true end. Combien de comparaisons avec $x$ fait-on dans le pire cas ? Que vaut $i$ à la sortie si $x$ est présent ?
Indice
Le pire cas se produit quand $x$ est absent ou en dernière position.
Solution
Dans le pire cas, on compare $x$ aux $n$ cases : $n$ comparaisons. Si $x$ est présent, la boucle s'arrête à sa première occurrence et $i$ en est la position. Le booléen évite de lire $A[n+1]$, qui n'existe pas, sans dépendre de l'ordre d'évaluation des conditions.
Exercice 3 (Compter les diviseurs). L'algorithme c := 0; for i := 1 to n do if n mod i = 0 then c := c + 1 compte les diviseurs de $n$. Que donne-t-il pour $n=36$ ? Comment réduire le nombre de tours à environ $\sqrt n$ ?
Indice
Les diviseurs vont par paires $(d,n/d)$ avec $d\le\sqrt n\le n/d$.
Solution
Les diviseurs de $36$ sont $1,2,3,4,6,9,12,18,36$ : $c=9$. On peut faire varier $i$ seulement tant que $i\times i\le n$, et compter $2$ pour chaque diviseur $i<\sqrt n$ et $1$ si $i=\sqrt n$. Pour $36$, les paires $(1,36)$, $(2,18)$, $(3,12)$, $(4,9)$ donnent $8$, plus $1$ pour $6$ : on retrouve $9$, avec $6$ tours au lieu de $36$.
Tome III · Perfectionnement
Approfondir le cours avec des problèmes de synthèse et des justifications complètes.
Exercice 1 (La recherche dichotomique). Dans un tableau trié $A[1..n]$, on cherche $x$ en comparant à l'élément du milieu, puis en ne gardant que la moitié utile. Écrire l'invariant de la méthode. Combien de tours faut-il au plus pour $n=1\,000$ ?
Indice
À chaque tour, la zone de recherche $[g,d]$ est au moins divisée par $2$.
Solution
Invariant : « si $x$ est dans le tableau, il est dans $A[g..d]$ ». On calcule m := (g + d) div 2, puis on remplace $d$ par $m-1$ ou $g$ par $m+1$ selon la comparaison, jusqu'à trouver $x$ ou obtenir $g>d$. La taille passe de $1\,000$ à au plus $500$, $250$, $125$, $62$, $31$, $15$, $7$, $3$, $1$ : au plus $10$ tours, contre $1\,000$ comparaisons pour une recherche séquentielle.
Exercice 2 (Le tri par sélection). Le tri par sélection place à chaque étape le plus petit élément restant à sa position définitive. Dérouler le tri sur $[5,2,4,1]$, puis compter les comparaisons effectuées pour un tableau de $n$ éléments, et pour $n=100$.
Indice
À l'étape $i$, on cherche le minimum parmi $n-i+1$ éléments, ce qui demande $n-i$ comparaisons.
Solution
Étape $1$ : le minimum $1$ est échangé avec $5$, d'où $[1,2,4,5]$. Les étapes $2$ et $3$ ne changent rien. Le nombre de comparaisons vaut $(n-1)+(n-2)+\cdots+1=\dfrac{n(n-1)}{2}$, soit $4\,950$ pour $n=100$, quel que soit l'ordre initial.
Exercice 3 (L’exponentiation rapide). Pour calculer $a^n$, on utilise $a^n=(a^{n/2})^2$ si $n$ est pair et $a^n=a\cdot a^{n-1}$ si $n$ est impair. Combien de multiplications cette méthode demande-t-elle pour $a^{13}$ ? Comparer avec la méthode naïve et donner l'ordre de grandeur en fonction de $n$.
On calcule $a^2$, $a^3$, $a^6$, $a^{12}$, $a^{13}$ : $5$ multiplications, contre $12$ pour la méthode naïve. Chaque élévation au carré divise l'exposant par $2$ : le nombre de multiplications est au plus $2\log_2n$. Pour $n=10^6$, environ $40$ multiplications suffisent au lieu d'un million.
Continue avec ton tuteur
Dans Mathventure, tu rédiges tes réponses et le tuteur les corrige en t'expliquant tes erreurs. Les exercices suivants s'adaptent à ton niveau.
Mathventure