Evènement pour le groupe Algorithmique Distribuée


Date 2016-02-29  14:00-15:00
TitreLe point de vue  
RésuméDans un papier récent, Beauquier et al. décrivent des conditions sur l'ordonnancement d'un système distribué (totalement asynchrone), de type théorie de l'information et aléa algorithmique ("algorithmic randomness"), qui permettent d'assurer que tel ou tel problème peut être résolu pour *tout* ordonnancement respectant ces conditions. Les conditions sont du type "la séquence d'actions est T-aléatoire", ce qui signifie qu'un programme générant un n-préfixe de la séquence doit être de taille au moins T.n (le cas T=1 correspond à une séquence aléatoire au sens de Kolmogorov). En particulier, ils montrent que lorsque T=1 est suffisant pour résoudre un problème, il n'est jamais nécessaire - il existe toujours une constante T'<1 qui suffit. Je n'ai aucun résultat original sur le sujet; je me contenterai de présenter ce que j'en ai compris. 
Lieu178 
OrateurPhilippe Duchon 



Aucun document lié à cet événement.

Retour
Retour à l'index