Etude d’un algorithme en binôme

Les algorithmes sont le plus souvent abordés hors contexte bien qu’ils soient présents dans n’importe quelle application smartphone.

Mise en scène

Le jeu Pokémon Go est sorti début 2016. Les détails de l’implémentation en sont pas connus mais cela n’empêche pas d’y réfléchir.

Les élèves seront groupés par deux, un élève plutôt débutant, un autre plutôt pas, ils tirent un algorithme ou une structure de données au hasard et doivent déterminer où il intervient dans les petites histoires décrites au paragraphe suivant. Les élèves devront ensuite l’implémenter, cela ne devrait pas dépasser 20 lignes.

5 points seront attribués à cet exercice pour cinq tâches :

  1. Associer l’algorithme à la bonne étape de l’histoire.
  2. Implémentation en Python.
  3. Résultats sur un exemple fabriqué.
  4. Impact économique si l’algorithme est deux fois plus rapide.
  5. Une piste d’amélioration pour l’application considérée.

Scénarios

Une personne sort son téléphone. Il ouvre l’application Trésor Caché. L’écran lui montre ce qui l’a devant lui comme s’il allait prendre une photo. Ces histoires sont fictives.

histoire 0

  1. L’utilisateur s’authentifie.

histoire 1

  1. Il balaye devant lui (il agite son téléphone portable).
  2. L’application cherche si un trésor est virtuellement caché devant lui.
  3. La position d’un des trésors correspond. L’application affiche ses caractéristiques.
  4. L’utilisateur swipe et stocke le trésor dans son coffre fort virtuel.
  5. L’application envoie l’information aux ordinateurs des créateurs de l’application. Elle envoie également l’image du paysage où le trésor a été attrapé.
  6. Ces ordinateurs déterminent si le joueur a gagné. Mais il n’a pas gagné.

histoire 2

  1. Le trésor a volontairement été placé par les concepteurs de l’application en hauteur au niveau de la pancarte du nom de la rue.
  2. Les ordinateurs distants extraient la zone de l’image correspondant à cette pancarte.
  3. Ils lancent une reconnaissance OCR pour lire le nom écrit sur cette pancarte.
  4. Ils comparent à une liste de noms rues mais il ne s’y trouve pas.
  5. Le moteur de reconnaissance de l’écriture fait parfois des erreurs, Ils lancent alors un moteur qui corrige les fautes d’orthographes automatiquement. Une seconde recherche est lancée. La rue est trouvée, elle n’a a priori pas changé de nom.
  6. Une dernière validation est effectuée. Une distance est calculée entre le nom de rue reconnu et le nom de rue corrigé. La distance n’est pas trop grande. Aucune vérification manuelle n’est requise.

histoire 3

  1. Le joueur est impatient, il demande une suggestion pour le prochain trésor.
  2. L’application récupère l’information stockée pendant que le joueur joue. Il envoie cette information au serveur des concepteurs.
  3. Ceux-ci déterminent trois trésors proches et non découverts.
  4. Ils sélectionnent trois magasins autour des trésors.
  5. Ils mettent aux enchères le profil de l’utilisateur.
  6. 5 magasins font une offre. Le meilleur est choisi.
  7. L’utilisateur reçoit le message qu’un indice se trouve dans ce magasin.
  8. L’application lui indique le chemin le plus court jusqu’au magasin.

histoire 4

Le jeu marche très bien mais finit par provoquer une certaine lassitude. Les concepteurs du jeu ont quelques idées. L’une d’elles est d’associer une récompense à chaque trésor comme des bons de réductions.

  1. Sans le savoir certains utilisateurs bénéficient de cette option, d’autres pas.
  2. On compare ces deux populations sur un mois en mesurant le temps de jeu moyen par joueur.
  3. L’idée est finalement validée.

Machine learning

Ces modèles sont utilisés dans l’une des histoires mais il n’est pas demandé de les implémenter.