Accueil Publimath  Aide à la recherche   Recherche Avancée   Imprimer la fiche   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional
Auteur(s) : Connan Guillaume

Titre : Mathématice. N° 45. La complexité c'est simple comme la dichotomie.

Editeur : Sésamath Erôme, 2015

Type : article de périodique ou revue Langue : Français Support : internet

Public visé : enseignant, formateur Niveau Niveau scolaire visé par l'article : lycée professionnel, lycée, 1ère, terminale, licence Age : 16, 17, 18, 19, 20

Classification : A34Revues, article de revue, article sur un site internet
Lycée
 A35Revues, article de revue, article sur un site internet
Enseignement supérieur
 A37Revues, article de revue, article sur un site internet
Enseignement professionnel
 A39Revues, article de revue, article sur un site internet
Formation à l'enseignement, initiale et continue.
 C74Pour la classe de mathématiques : fabrication de séquences d'enseignement, préparation des cours, activités pour la classe et organisation de la classe. Méthodes d'enseignement. Processus didactique.
Lycée
 C75Pour la classe de mathématiques : fabrication de séquences d'enseignement, préparation des cours, activités pour la classe et organisation de la classe. Méthodes d'enseignement. Processus didactique.
Enseignement supérieur
 C77Pour la classe de mathématiques : fabrication de séquences d'enseignement, préparation des cours, activités pour la classe et organisation de la classe. Méthodes d'enseignement. Processus didactique.
Enseignement professionnel
 C79Pour la classe de mathématiques : fabrication de séquences d'enseignement, préparation des cours, activités pour la classe et organisation de la classe. Méthodes d'enseignement. Processus didactique.
Formation à l'enseignement, initiale et continue.
 P44Langages de programmation (classification des langages, éléments et caractéristiques des langages, processeurs)
Lycée
 P45Langages de programmation (classification des langages, éléments et caractéristiques des langages, processeurs)
Enseignement supérieur
 P47Langages de programmation (classification des langages, éléments et caractéristiques des langages, processeurs)
Enseignement professionnel
 P49Langages de programmation (classification des langages, éléments et caractéristiques des langages, processeurs)
Formation à l'enseignement, initiale et continue.
 

Résumé :

On pourrait sous-titrer cet article « Pour en finir avec la binarité de la dichotomie ». L'auteur fait sortir cette méthode classique de résolution de problèmes au lycée des sentiers battus, la frottant à la notion de complexité algorithmique pour mieux mettre en avant sa richesse souvent ignorée.
Tout commence par des déménageurs qui jettent des pianos par les fenêtres d'un immeuble. Et qui veulent, en minimisant les essais, déterminer à partir de quel étage la méthode aboutit à la destruction de l'instrument.
La démarche débute par un petit algorithme de recherche dichotomique de l'étage fatal, celui-ci est testé. Se termine-t-il ? Juste ? Et à quelle vitesse ? Les réponses sont oui, oui et, pour un immeuble de 1024 étages, à peu près cent fois plus vite que des essais en remontant !
L'auteur nous informe alors d'un petit bug de Java, qui recelait une erreur dans le code d'une bibliothèque utilisée pour la recherche dichotomique et nous invite à rectifier notre algorithme en conséquence. Pour prendre en compte la spécificité du codage des entiers sur 64 bits et pour le cas où l'immeuble aurait plus de 263 − 1 étages (on a pris comme hypothèse de départ que le nombre d'étages est une puissance de 2), ce qui sera courant dans un futur proche…
Pour conclure cette première partie le lecteur est invité à réfléchir sur quelques questions annexes comme le risque de pénurie de pianos pour les tests… Tout va bien, l'algorithme reste performant.
C'est le moment choisi par l'auteur pour nous ramener à notre réalité, un peu plus scolaire dirons-nous et surtout de laquelle (pour la plupart) les pianos sont absents.
Pour commencer la dichotomie ne permet pas de tout améliorer, un exemple utilisant la multiplication de deux entiers le prouve ; couper les nombres en deux n'accélère pas le calcul !
Et quel rapport avec la recherche des solutions d'une équation réelle ? Si l'on cherche notre solution dans un intervalle, que l'on fixe la précision désirée, notre solution sera l'étage parmi le nombre d'étages de possibilités. Passer du piano cassé à un test de valeur ne pose aucune difficulté.
On arrive alors au cœur de l'article, l'étude de la complexité sur machine. C'est à dire le calcul du temps de résolution d'un problème par une machine, ou plutôt du temps d'exécution des instructions qui aboutissent à cette résolution.
A partir d'un petit problème très simple, l'auteur commence tout d'abord par une partie expérimentale. La résolution du problème est codée en Python puis en C. Le temps de calcul est relevé en fonction de la taille de l'échantillon de départ, une formule est établie pour les deux langages qui est fonction du cube de cette taille multiplié par une certaine constante… C l'emporte grâce à sa constante, il est environ 400 fois plus rapide que Python ! Le but est d'optimiser le code, hélas même en C bien des choses restent cachées.
Nous passons alors à l'approche plus théorique avec l'analyse mathématique, le but étant d'optimiser le code, en Python comme en C. Et la conséquence est finalement assez simple.
Pour conclure l'article, l'auteur nous emmène du côté de l'algorithme d'Héron, avec quelques exemples de code pour déterminer une approximation de la racine carrée d'un entier positif. Cet algorithme donne une très bonne précision très rapidement.
Pour terminer l'auteur nous indique la bibliographie de l'article ; elle est très conséquente et permettra à ceux qui le désirent d'approfondir le sujet.

Notes :
Il est possible de lire et répondre à cet article : http://revue.sesamath.net/spip.php?article719
Cet article est également paru dans Repères-IREM n° 102. Ressource en ligne
MathémaTICE est une revue collaborative libre portant sur l'utilisation des TICE en classe de Mathématiques.
Une liste de thèmes est proposée en page d'accueil. A chaque requête thématique, MathémaTICE propose un dossier virtuel d'articles et de brèves correspondant à ce thème.

Cet article est en libre accès sur le site MathémaTICE

Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 07/05/2022
Accueil Publimath  Aide à la recherche   Recherche Avancée   Imprimer la fiche   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional