Les algorithmes classiques

🔴 Expert

Les énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres suivent l'accès à la famille « Algorithmique et Python ».

1
Démontre que le nombre d'étapes d'une recherche dichotomique dans une liste de n éléments est de l'ordre du logarithme de n en base 2.
Voir le corrigéoffert
À chaque étape, le nombre d'éléments encore candidats est divisé par 2, à une unité près.
Après $k$ étapes, il reste donc environ $\dfrac{n}{2^{k}}$ éléments, et l'on s'arrête lorsque ce nombre descend à 1.
Cela donne $2^{k} \approx n$ , c'est-à-dire $k \approx \log_{2}(n)$ .
Concrètement, doubler la taille de la liste n'ajoute qu'une seule étape : c'est ce qui rend la méthode utilisable sur des milliards d'éléments, là où un parcours complet serait impensable.
2
Compare l'ordre de grandeur du nombre de comparaisons du tri par sélection et des tris les plus rapides, puis conclus sur leur usage.
Voir le corrigéoffert
Le tri par sélection effectue $\dfrac{n(n-1)}{2}$ comparaisons, soit de l'ordre de $n^{2}$ .
Les tris les plus efficaces, comme le tri fusion, effectuent de l'ordre de $n\log_{2}(n)$ comparaisons.
Pour $n = 1000$ , cela fait environ 500 000 d'un côté contre 10 000 de l'autre, soit un rapport de 50 ; pour un million d'éléments, le rapport dépasse 50 000.
Le tri par sélection reste donc acceptable sur quelques dizaines d'éléments, et devient inutilisable au-delà. C'est pourquoi on l'étudie pour comprendre, et qu'on utilise en pratique le tri fourni par le langage.
3
Explique la méthode générale permettant de démontrer qu'une boucle « tant que » se termine, et applique-la à l'algorithme d'Euclide par divisions.
🔒 Corrigé réservé aux abonnésS'abonner →
4
Explique pourquoi un algorithme peut donner un résultat exact et pourtant être inutilisable, et donne un exemple.
🔒 Corrigé réservé aux abonnésS'abonner →
5
Explique pourquoi tester un algorithme sur des exemples ne suffit pas à démontrer qu'il est correct.
🔒 Corrigé réservé aux abonnésS'abonner →
6
On applique l'algorithme d'Euclide par soustractions à deux termes consécutifs de la suite de Fibonacci. Explique pourquoi ce cas est le plus défavorable.
🔒 Corrigé réservé aux abonnésS'abonner →
7
Décris un algorithme qui détermine si une liste est triée dans l'ordre croissant, et donne le nombre de comparaisons effectuées au mieux et au pire.
🔒 Corrigé réservé aux abonnésS'abonner →
8
Explique comment choisir entre une recherche séquentielle et une recherche dichotomique, en tenant compte du coût du tri.
🔒 Corrigé réservé aux abonnésS'abonner →
9
Démontre, à l'aide d'un invariant, que l'algorithme de recherche du maximum d'une liste renvoie bien le plus grand élément.
🔒 Corrigé réservé aux abonnésS'abonner →
10
Explique pourquoi la méthode de dichotomie appliquée à une équation exige que la fonction change de signe sur l'intervalle de départ, et ce qui se passe sinon.
🔒 Corrigé réservé aux abonnésS'abonner →

Comment ça s'est passé ?

Retrouve tout dans Mon suivi.

← Changer de niveau