Les routes de Monsieur Fermat

Une application de l’inégalité triangulaire
mardi 26 octobre 2010
par  Nathalie CARRIÉ

Comme cette année la valeur absolue est une nouveauté dans le programme de première S et comme elle n’est pas encore traitée dans les manuels, la conception de ce chapitre pour mes élèves m’a menée à une réflexion sur distance et algorithmes, pour finalement leur proposer le problème des autoroutes de Fermat que j’avais lu dans le manuel ISTRA de l’IREM de Strasbourg [1].

Voici le plan du cours que j’ai proposé à mes élèves. Le cours manuscrit en classe à l’aide du logiciel Xournal se trouve dans le portfolio ci-dessous. [2]

  • Définition
    définition algorithmique de la valeur absolue et définition mathématique
  • Distance
    • distance sur une droite
      résolution d’équations et d’inéquations simples avec la valeur absolue
    • Distance dans le plan
      calcul avec algorithme et programme TI82
    • Equations de cercles
  • Inégalité triangulaire
    • avec des nombres réels
    • avec des points
  • Application : le problème de Fermat.

Le problème de Fermat

Pïerre De Fermat
Enoncé du problème posé par FERMAT :

Étant donné 3 villes A, B, C au sommet d’un triangle, il s’agit de construire une route de longueur minimale reliant les 3 villes 2 à 2.

- Lemme préliminaire

Triangle PQR {PNG} PQR est un triangle.
Pour tout point N intérieur au triangle, on a : NQ+NR < PQ+QR

indication : introduire Q’ intersection de (QN) et de (PR).

- Résolution pour un triangle ABC où les angles sont inférieurs à 120°.

Étant donné un point M du plan, le problème est de minimiser la distance MA+MB+MC. D’où l’idée de travailler sur la fonction
f : P \rightarrow R, M \mapsto MA+MB+MC.

7zones {PNG}Le triangle des 3 villes délimite 7 zones du plan.
Montrer que :
- si M en 2, f(M) a un minimum atteint en A
- si M en 3, f(M) a un minimum atteint en I où  \{ I \}=(MC) \cap (AB)
- Régions 4, 5, 6, 7 ?
- si M en 1, Toricelli a démontré en 1659 qu’il existe un point T intérieur au triangle qui rend f(M) minimum.

AutoroutesDeFermat {PNG}

La figure CarMetal qui suit permet de rechercher le ou les minimums éventuels de MA+MB+MC.

<carmetals|doc=4424|largeur=800|hauteur=600>

Il faut d’abord initialiser le point Min en bougeant le point initMin, puis en déplaçant le point M, la distance s’affiche et le point Min se déplace. On peut ainsi chercher de proche en proche la position du point M qui rend cette distance minimale.

Le bouton « Solution » vous affichera la solution géométrique et le calcul associé. La construction du point solution, appelé point de Fermat, ou point de Toricelli, est celle donnée dans Wikipédia sur cette page.
AutoroutesDeFermatAvecSolution {PNG}

Recherche de la distance minimum MA+MB+MC : le point de vue analytique (algébrique ?)

La fonction f : P \mapsto R qui à M associe le réel positif MA+MB+MC donne dans un repère du plan une fonction où interviennent deux variables : l’abscisse et l’ordonnée du point M. La recherche du minimum de f revient donc à une recherche de minimum pour une fonction de 2 variables, et ça, nous ne savons pas le faire en première S.

Par contre, ce problème peut se ramener à une recherche algorithmique de minimum puisque la fenêtre de CarMetal est un rectangle de l’écran contenant un certain nombre de pixels en abscisse et en ordonnée. En balayant de manière systématique la fenêtre de tracé de CarMetal pour le point M, on peut calculer la distance MA+MB+MC pour tous les points de l’écran et en chercher le minimum.

Le code qui permet de calculer f(M) dans le repère de CarMetal est :

xM=X("M"); yM=Y("M"); // on récupère les coordonnées des points dont nous avons besoin
xA=X("A"); yA=Y("A");
xB=X("B"); yB=Y("B");
xC=X("C"); yC=Y("C");

distance=Math.sqrt((xM-xA)*(xM-xA)+(yM-yA)*(yM-yA))+Math.sqrt((xM-xB)*(xM-xB)+(yM-yB)*(yM-yB))+Math.sqrt((xM-xC)*(xM-xC)+(yM-yC)*(yM-yC)); // calcul de f(M)
Println("MA+MB+MC = "+distance); // affichage de f(M)

Dans le repère orthonormé R de CarMetal (O, \vec{i}, \vec{j}), la fenêtre de géométrie a les caractéristiques suivantes, en unités CarMetal données par le repère R :
- sa demi-largeur : windoww
- sa longueur : windowh
- les coordonnées de son centre C : C(windowcx, windowcy)
- le nombre de pixels compris dans une unité du repère est pixel.

Les coordonnées en pixels de la fenêtre sont donc données par le schéma suivant :

LaFenetreDeCarMetal {PNG}

En créant des expressions qui contiennent ces valeurs, nous pouvons les transmettre au carscript : ExpressionsAutoroutesDeFermat {PNG}

Les expressions associées sont indiquées sur le schéma de la fenêtre CarMetal et le code qui en résulte est celui-ci :

windoww=GetExpressionValue("E24");
windowh=GetExpressionValue("E25");
windowcx=GetExpressionValue("E26");
windowcy=GetExpressionValue("E27");
pixel=GetExpressionValue("E28");

Pour balayer la fenêtre et parcourir tous les points M de cette fenêtre, il nous faut une double boucle for : une première boucle balaye les abscisses en pixels de wlDebut à wlFin avec :

wlDebut=(windowcx-windoww)*pixel;
wlFin=(windowcx+windoww)*pixel;

et une seconde balaye les ordonnées en pixels de whDebut à whFin avec :

whDebut=(windowcy-windowh/2)*pixel;
whFin=(windowcy+windowh/2)*pixel;

La double boucle se code alors ainsi :

min=1000; //on initialise le minimum à une valeur assez grande

for (wl=wlDebut; wl<wlFin; wl=wl+1){
        for (wh=whDebut; wh<whFin; wh=wh+1){
                xM=wl/pixel; //wl et wh étant en pixels, on revient aux unités du repère de CarMetal
                yM=wh/pixel;
                distance=Math.sqrt((xM-xA)*(xM-xA)+(yM-yA)*(yM-yA))+Math.sqrt((xM-xB)*(xM-xB)+(yM-yB)*(yM-yB))+Math.sqrt((xM-xC)*(xM-xC)+(yM-yC)*(yM-yC));
                if (distance<min){
                        min=distance;
                        xMFermat=xM; // on stocke les coordonnées du point qui réalise le minimum
                        yMFermat=yM;
                }
        }
}

Il ne reste plus qu’à afficher, à la sortie de la double boucle, les valeurs contenues dans les variables min, xMFermat et yMFermat. Il en résulte le carscript suivant : Script de recherche de la distance minimale {PNG}

Comme c’est magique, l’exécution du carscript nous fournit une valeur approchée de la distance minimale à 10^{-5} près.

Si l est l’indice qui va balayer la largeur de la fenêtre et h est celui qui va balayer la hauteur de la fenêtre, l’algorithme utilisé se résume à :

Entrer x_A, y_A, x_B, y_B, x_C, y_C
Entrer lDebut, lFin, hDebut, hFin
 min \leftarrow 1000
 x_M \leftarrow 0
 y_M \leftarrow 0
 x_{Fermat} \leftarrow 0
 y_{Fermat} \leftarrow 0
Pour l allant de lDebut à lFin
Pour h allant de hDebut à hFin
 x_M \leftarrow \frac{ l}{ pixel }
 y_M \leftarrow \frac{ h}{ pixel }
 f(M) \leftarrow \sqrt{(x_M-x_A)^2 + (y_M-y_A)^2} + \sqrt{(x_M-x_B)^2 + (y_M-y_B)^2} + \sqrt{(x_M-x_C)^2 + (y_M-y_C)^2}
Si  f(M) < min Alors
 min \leftarrow f(M)
 x_{Fermat}  \leftarrow  x_M
 y_{Fermat}  \leftarrow  y_M
FinSi
FinPour
FinPour
Afficher min, x_{Fermat}, y_{Fermat}

Exercice : En téléchargeant le fichier AutoroutesDeFermat.zirs, seule la première figure contient le carscript décrit ici, je vous propose de transporter ce script dans la 2e figure.

Recherche de la distance minimum MA+MB+MC : c’est possible aussi à la calculatrice TI-82 !

La fenêtre de la TI-82 a pour dimensions 96 pixels de large et 64 pixels de haut. En laissant 1 pixel pour le cadre de chaque côté, la largeur va donc compter 94 pixels à balayer et la hauteur 62 pixels, comme le montre le schéma suivant :

Les pixels de la TI-82 {PNG}

La fenêtre graphique paramétrée dans « Window » (ou « fenêtre ») a des variables dont nous avons besoin : Xmin, Xmax, Ymin, Ymax. Xmax-Xmin représente les abscisses parcourues pour 94 pixels de large, et Ymax-Ymin, les ordonnées parcourues pour 62 pixels de haut.

L’algorithme à implémenter sur la TI-82 devient alors :

Entrer x_A, y_A, x_B, y_B, x_C, y_C
 min \leftarrow 1000
Pour l allant de 0 à 94
Pour h allant de 0 à 62
 x_M \leftarrow Xmin + l*\frac{Xmax-Xmin}{ 94 }
 y_M \leftarrow Ymax - h*\frac{Ymax-Ymin}{ 62 }
 f(M) \leftarrow \sqrt{(x_M-x_A)^2 + (y_M-y_A)^2} + \sqrt{(x_M-x_B)^2 + (y_M-y_B)^2} + \sqrt{(x_M-x_C)^2 + (y_M-y_C)^2}
Si  f(M) < min Alors
 min \leftarrow f(M)
 x_{Fermat}  \leftarrow  x_M
 y_{Fermat}  \leftarrow  y_M
FinSi
FinPour
FinPour
Afficher min, x_{Fermat}, y_{Fermat}

Cet algorithme une fois implémenté sur la TI-82 donne, après avoir testé le source si vous le souhaitez, à l’aide du TI-Editor :
FermatTI82 {PNG}

FermatTI82Editor {PNG}

Si vous avez le câble de connexion TI-82, vous pouvez charger directement ce fichier binaire , sinon, voici le code source à copier-coller :

Prompt A,B,C,D,E,F
1000→M
For(L,0,94)
For(H,0,62)
Xmin+L*(Xmax-Xmin)/94→X
Ymax-H*(Ymax-Ymin)/62→Y
√((X-A)^2+(Y-B)^2)+√((X-C)^2+(Y-D)^2)+√((X-E)^2+(Y-F)^2)→Z
If Z<M
Then
Z→M
X→P
Y→Q
End
End
End
Disp M
Disp P,Q

L’exécution du programme donne finalement pour A(-3; 3) B(3; 3) et C(1; -1) les valeurs approchées suivantes :
 min = 9.25112
 x_{Fermat} = 0.7447
 y_{Fermat} = 1.2903
J’ai utilisé CarMetal et la macro-construction « Point de Fermat » pour voir que finalement, le calcul effectué avec la calculatrice est tout à fait acceptable :
FermatCarMetalTI82 {PNG}

Recherche de la distance minimum MA+MB+MC avec Scratch

- La fenêtre de Scratch
LaFenetreDeScratch {PNG}

Nous allons directement travailler avec des coordonnées en pixels. L’algorithme à implémenter sur Scratch devient alors :

Entrer x_A, y_A, x_B, y_B, x_C, y_C
 min \leftarrow 1000
Pour l allant de -240 à 240
Pour h allant de -180 à 180
 x_M \leftarrow l
 y_M \leftarrow h
 f(M) \leftarrow \sqrt{(x_M-x_A)^2 + (y_M-y_A)^2} + \sqrt{(x_M-x_B)^2 + (y_M-y_B)^2} + \sqrt{(x_M-x_C)^2 + (y_M-y_C)^2}
Si  f(M) < min Alors
 min \leftarrow f(M)
 x_{Fermat}  \leftarrow  x_M
 y_{Fermat}  \leftarrow  y_M
FinSi
FinPour
FinPour
Afficher min, x_{Fermat}, y_{Fermat}

L’exécution du programme donne finalement pour A(-120; 90) B(75; 100) et C(100; -100) les valeurs approchées suivantes (vous pouvez le lancer avant d’aller dormir... [3]) :
 min = 386.8
 x_{Fermat} = 42
 y_{Fermat} = 61

FermatSurScratchSolution {PNG}
FermatScratchSurCarMetal {PNG}

Ce qui est intéressant avec Scratch, c’est de voir l’abeille se déplacer à largeur en pixel fixe, le long de la hauteur de la fenêtre, et de regarder comment le calcul du minimum se fait.

On peut évidemment optimiser ce programme en ne retenant comme bornes des deux boucles que les extrêmes des coordonnées de A, B et C.

Les ressources suivantes sont fournies :

- Programme sur Scratch sans le graphique

- Programme sur Scratch avec affichage du triangle ABC

Le programme à télécharger

Vous pouvez si vous le souhaitez voir le programme s’exécuter en ligne à cette adresse.


[1Math Premières Scientifiques, IREM de Strasbourg, collection ISTRA, 1988

[2L’ensemble des pages manuscrites en classe devant les élèves se trouvent sur le site Maths en classe en images.

[3Il faut près d’une minute d’exécution par colonne (par valeur de l), ce qui fait plusieurs heures pour parcourir les 480 pixels de large !


Documents joints

Autoroutes de Fermat
Autoroutes de Fermat
4 figures CarMetal au format zirs
Autoroutes de Fermat ABC fixe
Autoroutes de Fermat ABC fixe
Autoroutes de Fermat avec ABC fixe
Autoroutes de Fermat avec ABC fixe
Fermat en fichier binaire TI82
Fermat en fichier binaire TI82
Macro Point de Fermat
Macro Point de Fermat
macro-construction CarMetal
Zip - 44 ko
Zip - 44 ko

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 13 septembre 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 4 octobre 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 11 octobre 2017, 14h-18h, campus du Tampon
- Mercredi 22 novembre 2017, 14h-18h, campus du Tampon
- Mercredi 7 février 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 7 mars 2018, 14h-18h, campus du Tampon
- Mercredi 4 avril 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 2 mai, 14h-18h, campus du Tampon
- Mardi 5 juin 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 6 juin, 14h-18h, campus du Tampon

Fête de la science

Du 13 au 18 novembre 2017.
Thème : « La recherche à l’heure du numérique »

Semaine des mathématiques

Du 26 au 31 mars 2018.
Thème : « Mathématiques et mouvement »


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

lundi 25 septembre 2017

Publication

766 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

319 aujourd'hui
1251 hier
2102814 depuis le début
41 visiteurs actuellement connectés