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) : Chrétien Stéphane

Titre : Repères-IREM, N°61. p. 91-103. Physique statistique et optimisation combinatoire.
English title: Statistical physics and comtinatorial optimization. (ZDM/Mathdi)

Une version texte intégral est sur le site Bibliothèque numérique des IREM et de l'APMEP  Télécharger 

Editeur : TOPIQUES éditions Metz, 2005
Format : 16 cm x 23,7 cm, p. 91-103 Biliogr. p. 103-103
  ISSN : 1157-285X

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

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

Classification : A34Revues, article de revue, article sur un site internet
Lycée
 A35Revues, article de revue, article sur un site internet
Enseignement supérieur
 A39Revues, article de revue, article sur un site internet
Formation à l'enseignement, initiale et continue.
 K34Théorie des graphes
Lycée
 K35Théorie des graphes
Enseignement supérieur
 K39Théorie des graphes
Formation à l'enseignement, initiale et continue.
 M54Physique. Chimie. Astronomie. Technologie. Ingénierie.
Lycée
 M55Physique. Chimie. Astronomie. Technologie. Ingénierie.
Enseignement supérieur
 M59Physique. Chimie. Astronomie. Technologie. Ingénierie.
Formation à l'enseignement, initiale et continue.
 N64Optimisation, recherche opérationnelle, aide à la décision.
Lycée
 N65Optimisation, recherche opérationnelle, aide à la décision.
Enseignement supérieur
 N69Optimisation, recherche opérationnelle, aide à la décision.
Formation à l'enseignement, initiale et continue.
 

Résumé :

Les problèmes d'optimisation combinatoire sont étonnamment très présents dans notre univers quotidien. Comment remplir un camion lors d'un déménagement, faire un emploi du temps optimal pour un lycée ou une conférence, trouver le plus court chemin entre deux serveurs reliés par Internet, construire un réseau d'approvisionnement énergétique résistant à un nombre donné de pannes, affecter des fréquences pour les bornes de retransmission des téléphones portables... Or, si certains de ces problèmes semblent faciles à résoudre pour de petits exemples, la plupart sont insolubles lorsque le nombre d'objets à traiter devient grand. Pour essayer d'y voir plus clair, les mathématiciens ont mis au point une théorie dans laquelle sont classifiés les problèmes selon le temps que met le meilleur algorithme à donner une solution. On soupçonne que certains d'entre eux sont excessivement difficiles à résoudre. Par exemple, on ne connaît pas de méthode qui résolve le problème d'affectation de fréquence de façon optimale en un temps inférieur à l'âge de l'univers pour des cas de 100 bornes ! La physique statistique est alors d'un grand secours. On sait maintenant par exemple que les méthodes de simulations que les physiciens ont inventées pour simuler des matériaux ferromagnétiques ou des plasmas peuvent servir à approcher la solution des problèmes de combinatoire. La physique donne aussi des intuitions sur ce qui rend ces problèmes difficiles. Notamment, les phénomènes de transition de phase, comme le passage d'un état extrêmement ordonné à un état très peu structuré chez les matériaux ferromagnétiques sont extrêmement difficiles à obtenir par ces méthodes. Reprenant cette idée, les mathématiciens ont essayé de comprendre si les transitions de phase existent aussi en optimisation combinatoire et commencent maintenant à en trouver. Cette vision des choses pourrait bien être dans l'avenir la clé pour une meilleure classification des problèmes et ouvrent des voix prometteuses dans la compréhension de l'efficacité des algorithmes.

Notes :
Repères-IREM est la revue du réseau national des Instituts de Recherche sur l'Enseignement des Mathématiques (IREM), elle a été créée en octobre1990. De nombreux articles peuvent être utilisés en formation initiale des enseignants.
Tous les articles parus dans Repères-IREM sont consultables et téléchargeables librement en ligne sur le Portail des IREM, dès la parution du numéro, à partir de son sommaire : cliquez sur l'onglet "Repères IREM", puis sur "Consultation en ligne".
Vous pouvez aussi soumettre un article à la revue en l'adressant en document attaché au rédacteur en chef de la revue à l'adresse : reperes-irem@univ-irem.fr


Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 08/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