Algorithmique appliquée | BTS | Mathématiques
Dernière mise à jour : 15 juin 2026
1. Dans un tableau de 200 éléments, combien de comparaisons au pire pour une recherche séquentielle ? (2 pts)
2. Le tableau est trié et contient 256 éléments : combien au pire pour une recherche dichotomique ? (3 pts)
3. Pourquoi la dichotomie exige-t-elle un tableau trié ? (3 pts)
1. 200. 2. \(\log_2(256)=8\). 3. À chaque étape, on compare au milieu et on élimine la moitié où la valeur ne peut pas être ; cela n'a de sens que si le tableau est ordonné.
On définit \(s(0)=0\) et \(s(n)=n+s(n-1)\) (somme des entiers de 1 à \(n\)).
1. Calcule \(s(5)\) en déroulant. (3 pts)
2. Donne une formule directe de \(s(n)\). (3 pts)
1. \(s(5)=5+4+3+2+1+0=15\).
2. \(s(n)=\dfrac{n(n+1)}{2}\) (ex. \(\frac{5\times6}{2}=15\)).
1. Trie \([4,\ 1,\ 3,\ 2]\) par sélection (donne le tableau final). (3 pts)
2. Quelle est la complexité d'un tri par sélection sur \(n\) éléments ? (3 pts)
1. \([1,\ 2,\ 3,\ 4]\).
2. \(O(n^2)\) (deux boucles imbriquées : on cherche le minimum du reste à chaque position).