Établissement
Lycée Marguerite de Navarre (Bourges)
Année
2016-2017
Résumé
100 nombres sont écrits sur 100 cartes différentes, disposées en carré de 10x10, et retournées face cachée. Sur chaque ligne (de gauche à droite) du carré les cartes sont placées par ordre croissant. De même sur chaque colonne (de haut en bas).
1) Proposez un algorithme qui vous indique, étant donné un nombre, s’il est présent ou pas sur l’une des cartes, et si oui sur laquelle. Cet algorithme peut retourner toutes les cartes qu’il veut, l’objectif étant qu’il en retourne le moins possible. Pouvez-vous prouver que votre algorithme est optimal dans le pire des cas ?
2) Généralisez le problème à tout nombre de cartes N (dans l’exemple N=100) et à toute dimension de l’espace (dans l’exemple D=2).
1) Proposez un algorithme qui vous indique, étant donné un nombre, s’il est présent ou pas sur l’une des cartes, et si oui sur laquelle. Cet algorithme peut retourner toutes les cartes qu’il veut, l’objectif étant qu’il en retourne le moins possible. Pouvez-vous prouver que votre algorithme est optimal dans le pire des cas ?
2) Généralisez le problème à tout nombre de cartes N (dans l’exemple N=100) et à toute dimension de l’espace (dans l’exemple D=2).
Mots clés
Type de présentation au congrès
Exposé