Quiz — Paradigme diviser pour régner

Question 1

Quelle est la complexité temporelle en $O(…)$ de l'algorithme de recherche dichotomique dans un tableau trié de taille $n$ ?

Accepted Answer

$O(\log n)$

Answer

$O(n)$

Answer

$O(n^2)$

Answer

$O(1)$

Question 2

Le rover Curiosity doit convertir le code hexadécimal `1A3` en décimal pour activer un protocole de communication. Quelle est la valeur décimale correcte de ce code ?

Accepted Answer

419

Answer

163

Answer

429

Answer

259

Question 3

Pour la mission Mars Sample Return, l'orbiteur doit effectuer une recherche dichotomique sur les coordonnées GPS des échantillons martiens stockés dans une base de données. Les coordonnées sont triées par ordre croissant. L'orbiteur interroge la base avec une requête SQL pour trouver l'échantillon le plus proche de la coordonnée 1500. Quelle est la complexité en $O(…)$ de cette recherche si la base contient $n$ échantillons ?

Accepted Answer

$O(\log n)$

Answer

$O(n)$

Answer

$O(n^2)$

Answer

$O(1)$

Question 4

Identifie la ligne incorrecte dans le code Python suivant, qui implémente la recherche dichotomique dans une liste triée : $$def\ recherche\ dichotomique(liste,\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
    element):$$ $$gauche,\\ droite = 0,\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
    len(liste)-1$$ $$while\ gauche <= droite:\$$ $$milieu = (gauche + droite)\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
    // 2$$ $$if\ liste[milieu] == element:\$$ $$return\ milieu$$ $$elif\ liste[milieu] < element:\$$ $$gauche = milieu$$ $$else:\$$ $$droite = milieu - 1$$ $$return\ -1$$

Accepted Answer

La ligne $gauche = milieu$

Answer

La ligne $milieu = (gauche + droite) // 2$

Answer

La ligne $droite = milieu - 1$

Answer

La ligne $while\ gauche <= droite:$

Question 5

Pour calculer la distance Terre-Lune en unités astronomiques (UA), l'ordinateur de bord utilise la formule $d = 2^{x}$, où $x$ est un entier. Quelle est la valeur de $x$ si la distance mesurée est de 32 UA ?

Accepted Answer

$x = 5$

Answer

$x = 4$

Answer

$x = 6$

Answer

$x = 32$

Paradigme diviser pour régner

Notions à maîtriser

Teste-toi sur ce chapitre

Diviser pour régner : la stratégie gagnante

Garder ta progression ?