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)

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
Enseignement secondaire, lycée
 A35Revues, article de revue
Enseignement supérieur, Post-Bac
 A39Revues, article de revue
Formation à l'enseignement, initiale et continue.
 K34Théorie des graphes
Enseignement secondaire, lycée
 K35Théorie des graphes
Enseignement supérieur, Post-Bac
 K39Théorie des graphes
Formation à l'enseignement, initiale et continue.
 M54Physique. Astronomie. Technologie. Engineering. Informatique. Sciences de la terre.
Enseignement secondaire, lycée
 M55Physique. Astronomie. Technologie. Engineering. Informatique. Sciences de la terre.
Enseignement supérieur, Post-Bac
 M59Physique. Astronomie. Technologie. Engineering. Informatique. Sciences de la terre.
Formation à l'enseignement, initiale et continue.
 N64Optimisation. Programmation mathématique
Enseignement secondaire, lycée
 N65Optimisation. Programmation mathématique
Enseignement supérieur, Post-Bac
 N69Optimisation. Programmation mathématique
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 des Instituts de Recherche sur l'Enseignement des Mathématiques (IREM), elle a été créée en 1990. Un grand nombre de ces articles peuvent être utilisés en formation initiale ESPE (ex IUFM).
Vous pouvez consulter les éditoriaux et les articles un an après leur parution, à partir du sommaire de chaque numéro de Repères-IREM disponible sur le Portail des IREM : cliquez sur "Repères IREM", puis sur "Consultation en ligne". Dans chaque numéro plus récent, un des articles l'est également. Vous pouvez aussi soumettre un article à la revue en l'adressant au rédacteur en chef à l'adresse : reperes-irem@univ-irem.fr

Une version texte intégral est en téléchargement sur le site " Bibliothèque numérique des IREM et de l'APMEP"

Mots clés :


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