• 15 hours
  • Easy

Free online content available in this course.

course.header.alt.is_video

course.header.alt.is_certifying

Got it!

Last updated on 12/13/19

Quiz 4

Log in or subscribe for free to enjoy all this course has to offer!

Evaluated skills

  • Se familiariser avec des algorithmes complexes
  • Question 1

    Vrai ou faux ? Deux programmes réalisant la même tâche sont deux programmes équivalents.

    • Vrai

    • Faux

  • Question 2

    Pour lire un prénom dans ma liste de prénoms, cela prend une opération, quel que soit le numéro de la case. Autrement dit, lire le prénom inscrit dans la case n° 1, ou bien dans la case n° 145 ou bien dans la case n° 3000000, se fera toujours en une seule opération et donc coûtera le même temps, quelle que soit la case lue. Avec l’algorithme de la dichotomie et une liste de 128 prénoms (triés par ordre alphabétique), combien d’opérations faut-il, dans le pire des cas, pour affirmer qu’un prénom est dans la liste ou affirmer qu’il n’y est pas :

    • 2 opérations

    • 7 opérations

    • 64 opérations

    • 256 opérations

  • Question 3

    Il existe une activité sympa à faire avec des enfants, qu’on pourrait appeler “le nombre cible”. Il s’agit d’écrire un nombre entre 1 et 100, caché quelque part (derrière le tableau, sur une feuille repliée…) Ensuite, on leur demande de deviner le nombre par essais successifs. Dans un premier temps, sauf coup de bol, on va droit à l’ennui global (après quelques essais cela devient rasoir). On peut ensuite ajouter des éléments pour rendre le jeu plus intéressant. Est-il possible, pour cela, d’utiliser la dichotomie ?

    • Non, c’est impossible car la dichotomie ne fonctionne que sur des mots (comme les prénoms).

    • Oui, ça marche mais seulement avec des mots et des nombres.

    • Oui, ça marche sur n’importe quel type d’objet que l'on peut ranger dans un ordre croissant (des mots, des nombres, des dates de naissance, des références de vols des compagnies aériennes, etc.)