|
Aide à la recherche | Recherche Avancée | Imprimer la fiche | Aidez-nous à améliorer cette fiche |
|
|
|
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.
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. 
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 :
|
|