Description de l'activité

 : Informatique et technologie

L'atelier sera divisé en 2 séances de 30 minutes (chacune pour 15 élèves) avec un échange des groupes à la mi-temps. 

Séance 1 : Récréations algorithmiques

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ésoud 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.

Séance 2 : Initiation à la programmation avec le jeu SPY

SPY est un jeu vidéo conçu pour apprendre les bases de la programmation informatique. Plusieurs scénarios de jeu à la difficulté progressive permettent de se perfectionner. Il propose un langage à base de blocs facile à utiliser pour programmer les actions de robots. SPY est un jeu gratuit, libre d'utilisation et personnalisable avec ses éditeurs de scénarios et de missions inclus.

Nombre maximal d'élèves par créneau