Récréations algorithmiques
Atelier d'initiation aux problèmes d'optimisation combinatoire et aux algorithmes de résolution, avec exemples concrets.
Considérons les deux problèmes suivants : 'Étant donnée une carte routière, quel est le plus court chemin entre deux villes (disons, Paris et Toulouse) ?', 'Un voyageur de commerce doit visiter une et une seule fois certaines villes fixées, puis revenir à son point de départ. Quel est l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ?'
Ces deux problèmes sont des problèmes d'optimisation combinatoire : il s'agit de trouver le meilleur chemin (ou tour) étant donné un nombre fini (mais très grand) de chemins (ou de tours). Cependant, il existe un algorithme efficace qui résout le premier problème (ce problème est dit facile), alors que l'on ne sait pas résoudre efficacement le deuxième problème (ce problème fait partie de la classe des problèmes difficiles).
Le but de cet atelier est de présenter, par des exemples, des problèmes d'optimisation combinatoire (faciles et difficiles), et de montrer pour certains de ces problèmes les algorithmes (méthodes de résolution automatique) les résolvant.
Dévorer les frontières
Pause cerveau : l’assiette sous influence
Créer le cristal, Voyage entre art et science
Atelier créatif : crée un « zine » pour parler du changement climatique !
Décryptez, détournez, réinventez les images de films !
Écoulement d'eau souterraine, comment ça marche ? - Le cycle de l'eau
Plancton, y es-tu ? Découvrons l'incroyable biodiversité du plancton
L’environnement a-t-il vocation à rester toujours une variable d’ajustement ?
Le plastique, un poison si pratique ?
Fabriquez vos billes de bubble tea avec la chimie !
Sciences sans frontières
