Questions « flash »
Envoyées par votre boomer adoré rencontré le 10 mars, exemples de ce qu’il y aurait en fin d’année pour celles et ceux qui arrêteraient…
Correction des codes proposés pour aujourd’hui
Question sur le cours de lundi ?
Une synthèse des éléments essentiels est dans les deux dernières questions du quizz recopiées ci-dessous, avec commentaires audio extraits du salon de discussion discord.
On considère la fonction Python suivante, qui prend en argument une liste L et renvoie le maximum des éléments de la liste :
la taille de la liste.
Quelle est la complexité en nombre d’opérations de l’algorithme ?
def rechercheMaximum(L):
max = L[0]
for i in range(len(L)):
if L[i] > max:
max = L[i]
return max
On note la taille de la liste.
Quelle est la complexité en nombre d’opérations de l’algorithme ?linéaire, c’est-à-dire de l’ordre de
constante, c’est-à-dire ne dépend pas de
quadratique, c’est-à-dire de l’ordre de 
cubique, c’est-à-dire de l’ordre de 
Pour trier par sélection une liste de 2500 entiers, le nombre de comparaisons nécessaires à l’algorithme est
de l’ordre de 
de l’ordre de 
de l’ordre de 
de l’ordre de 
Dichotomie – le sujet du jour
- Un petit jeu par oral sur discord « trouve le nombre »
- Une animation : ici. (Celle qui a permis la vidéo ci-dessus, merci !)
- Un document institutionnel.
- Des prises de notes d’élèves (merci) :
- Pour appliquer la dichotomie la liste doit être triée
- À chaque puissance de 2 supplémentaire il y a un coup supplémentaire (ex 15 cartes : 4 coups au max, 16 cartes : 5 au max)
- Le nombre de possibilités correspond (à un près) au nombre de bits nécessaires en binaire.
- Cela s’appelle en gros le logarithme en base 2 :
- Exemple
c’est 2, mais avec 4 valeurs on a
soit 3 coups max
en gros c’est le nombre de bits qu’il faut pour écrire
- L’algorithme de dichotomie a une complexité au pire de l’ordre de
est la complexité au pire
- L’algorithme naïf est de complexité de
car on prend nombre par nombre.
- Un algorithme de dichotomie s’arrête de deux manières :
- soit si on trouve le bon nombre et on renvoie l’indice (donc milieu),
- soit on s’arrête car droite<gauche ou gauche>droite (c’est pareil) et on renvoie
.
- On code ça avec while droite >= gauche
Pourquoi ce décalage de 1 entre le log en base 2 et le nombre max de coups dont on n’a pas vraiment parlé pendant le cours ?
Travail d’ici lundi (rien à rendre) :
- Travailler et comprendre le document institutionnel jusqu’au mileu de la troisième page.
- Programmer la dichotomie en commençant par compléter le pseudo-code ci-dessous (le code étant déjà dans le document en lien) :
- en entrée une liste t et une valeur à chercher val
- on initialise
- gauche à …
- droite à …
- tant que gauche … droite :
- milieu =
- si t[milieu] … val
- alors renvoyer …
- sinon si t[milieu] … val
- alors droite = milieu … 1
- sinon :
- alors gauche = milieu … 1
- renvoyer …
- QCM (27 questions = une bonne heure max) :
« Des maths & de l'info chez Marcel & Louis » 
Bonjour, je ne comprend pas que ce que la méthode par dichotomie renvoi quand elle est implémentée dans une fonction (dans la fonction proposer dans le lien « document institutionnel » la fonction « recherche_dichotomique » la variable « milieu » retourne quoi, l’indice dans la liste? Combien de fois la chiffre est présent dans la liste? Si vous pouvez m’expliquer (en plus j’ai un truc à rendre Lundi si vous pouvez me dépanner)
Merci à vous.
Bonjour,
La fonction renvoie bien un indice, si elle trouve val, ou -1 si elle ne le trouve pas.
La recherche dichotomique ne cherche pas combien de fois on aurait val dans la liste tab, mais si il est dans la liste … ou pas.
Si on le trouve, c’est à l’indice « milieu » et la valeur cherchée « val » est dans le tableau tab à cet endroit là, c’est à dire que si on le trouve, tab[milieu] vaut val. Ok ?
Si on ne le trouve pas, la fonction renvoie -1, et val n’est PAS dans tab.
Bon courage et bonne année !