Dichotomie

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 :
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 : \log_2(n)
    • Exemple \log_2(4) c’est 2, mais avec 4 valeurs on a \log_2(4) + 1 soit 3 coups max
    • \log_2(n) en gros c’est le nombre de bits qu’il faut pour écrire n en binaire … moins un (correctif depuis le cours) si on l’arrondit par défaut … embrouille mais voir table ci-dessous.
    • L’algorithme de dichotomie a une complexité au pire de l’ordre de O\left(\log_2(n)\right)
    • O(\cdots) est la complexité au pire
    • L’algorithme naïf est de complexité de O(n) 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 -1.
    • 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 ?

cm 2020-03-25 log_2 et dichotomie

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) :

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.