Sujet de DEA

Bonjour, mon cher coloc illingus m'as filé le sujet d'un probleme informatique de mecs à jussieu :
A vous de vous amuesr si vous avez une 40 aine d'heures devant vous et que vous avez rien d'autre a foutre :

Dans le but d’étudier une population de pingouins, on veut déterminer si au moins trois pingouins ont une température supérieure à une certaine valeur. Pour cela chaque pingouin est équipé d’un capteur qui permet de savoir si le pingouin lui-même a atteint cette température. De plus quand deux pingouins se rencontrent leurs capteurs peuvent échanger des informations. En supposant que deux pingouins quelconques finissent toujours par se rencontrer, il est relativement facile de réaliser un protocole (et les capteurs correspondant) qui assure que si au moins trois pingouins ont dépassé le seuil alors tous les capteurs atteindront dans un état particulier d’alerte.

D’un point de vue plus abstrait on considère un réseau de capteur tel que (1) chaque capteur a une mémoire finie, (2) les capteurs sont anonymes, (3) deux capteurs peuvent communiquer deux à deux, (4) on suppose des propriétés sur le schéma de communication (par exemple chaque capteur communique infiniment souvent avec chaque autre capteur).

Dans l’exemple précédent le protocole est correct signifie que tous les capteurs arrivent ultimement dans un état d’alerte si et seulement si au moins trois pingouins ont une température supérieure au seuil. Plus généralement on peut modéliser de façon formelle ce type de systèmes et de déterminer quels genres de propriétés peuvent ainsi être calculées dans ce genre de modèle et comparer avec les classes plus classiques de calculabilité.

Plusieurs extensions sont possibles :

• En restreignant le graphe de communication on peut dans une certaine mesure restreindre le caractère anonyme des capteurs.
• Définition d’un calcul avec une certaine probabilité
• Tolérance aux pannes : si certains capteurs sont défaillants quelles problèmes peuvent être résolus.