L’objectif de ce cours est de présenter des aspects fondamentaux de l’algorithmique distribuée. Les systèmes distribués sont très variés et il existe de nombreux modèles de calcul pour modéliser de tels systèmes. Ce cours sera composé de deux parties présentant des  aspects différents de l’algorithmique distribuée actuelle. Dans les deux cas, on présentera ces modèles au travers de l’étude de problèmes fondamentaux du modèle ; on présentera des algorithmes ainsi que des résultats d’impossibilité.

1. Tolérance aux défaillances

 Dans un système distribué, la présence d’asynchronisme et de défaillances crée de l’incertitude. Celle-ci ne se situe pas à un niveau global, mais au niveau de chaque participant, qui ne peut pas connaître l’état exact des autres. Cette incertitude est à la base d’une distinction fondamentale entre les systèmes distribués et les systèmes séquentiels.
Dans cette partie du cours, nous verrons comment résoudre certains problèmes distribués en présence de défaillances, et donc comment surmonter cette incertitude. Nous aborderons également d’autres problèmes impossibles à résoudre, non pas à cause du manque de puissance de calcul des participants considérés individuellement, mais à cause de leurs protocoles de communication et de synchronisation.

    2 . Systèmes à agents mobiles  
Dans un système à  agents  mobiles, un  ou plusieurs agents mobiles se déplaçant sur le réseau exécutent chacun le même algorithme afin de résoudre une tâche distribuée. En général, les agents ne connaissent pas le réseau dans lequel ils évoluent. Dans ce cours, on s’intéressera aux problèmes de l’exploration (visiter tous les nœuds du réseau), de la cartographie  (reconstruire  une  carte  du  réseau)  et  du  rendez-vous (regrouper des agents initialement dispersés dans le réseau).
À la fin du cours, on présentera le logiciel de simulation Davis développé au LIS par E. Godard.

Courses

Les posets (ensembles partiellement ordonnés) sont des structures utiles pour la modélisation de divers problèmes (scheduling, sous-groupes d’un groupe), mais ils sont aussi la base d’une théorie combinatoire très riche. Nous discuterons des paramètres de posets comme la largeur, la dimension et les partitions en chaînes. À partir de là on fera un lien avec les polynômes en introduisant et étudiant le polynôme d’ordre — un polynôme associé à tout poset. Nous développerons ensuite un lien avec les polytopes (objets de la géométrie discrète). Un sous-ensemble de ℝⁿ est un polytope s’il peut être écrit comme le plus petit convexe contenant un ensemble de points V fini donné. Nous discuterons des polytopes entiers (c’est à dire V⊂ℤⁿ) et le polynôme d’Ehrhart qui est un polynôme associé à tout polytope entier. Le polytope d’ordre est un polytope associé à un poset. Nous montrerons que le polynôme d’Ehrhart du polytope d’ordre P est le polynôme d’ordre de P.

Après une introduction générale présentant les principaux modèles et problèmes étudiés, nous étudierons plus précisément trois sujets qui permettront d’illustrer des propriétés algorithmiques, des aspects algébriques et logiques de cette théorie :
*   caractérisation, décision et minimisation des transducteurs séquentiels ;
*   équivalence et fonctionnalité de transducteurs : de l’indécidabilité à la décidabilité ;

• présentation logique des transducteurs, et clôture par composition.

Nous donnerons un aperçu de deux familles classiques de mots infinis, traditionnellement utilisées comme source d’exemples de mots infinis avec des propriétés extrémales ou requises.

Les mots sturmiens sont des mots apériodiques avec seulement n + 1 facteurs différents d’une longueur donnée n, qui est la valeur minimale possible. Nous discuterons leurs définitions équivalentes et plusieurs méthodes habituelles de leur traitement, y compris la dualité de Berstel et Pocchiola et le lien avec les systèmes de numération d’Ostrowski.
 
Les mots morphiques, à leur tour, sont une source traditionnelle et très puissante d’exemples de mots infinis évitant certains motifs. Nous discuterons l’évolution des exemples de ce genre, du mot de Thue- Morse sur  l’alphabet binaire qui évitent les cubes,  jusqu’aux  nombreux exemples modernes construits par la recherche informatique sophistiquée. Nous discuterons également des démonstrations automatisées sur certains mots morphiques et le logiciel Walnut développé pour cela.

Les formes géométriques, qu’elles proviennent du monde naturel ou du monde manufacturé par l’Homme, ont tendance à être de plus en plus numérisées, cela, entre autres, à des fins de visualisation ou de mesure. Ce processus produit en général des maillages 3D, composés d’une multitude de polygones plans. Ces maillages sont la représentation discrète la plus commune pour caractériser la surface d’une forme virtuelle. Ces représentations surfaciques 3D sont traitées le plus souvent de manière automatique, parfois interactive, afin que leur structure globale ou certains détails soient analysés ou calculés. Cela peut être fait en extrayant des caractéristiques géométriques ou topologiques pertinentes. De telles caractéristiques de forme peuvent simplifier la façon dont l’objet est considéré, elles peuvent aider à la reconnaissance, et elles peuvent le décrire et le classifier selon des critères spécifiques. Ce cours traitera de la définition et du calcul de caractéristiques sur un maillage surfacique 3D, et de leur utilisation pour l’analyse de forme. Des méthodes récentes seront décrites pour extraire des caractéristiques ayant une signification liée non seulement à la géométrie mais aussi à la topologie. Plusieurs applications seront développées au cours des travaux pratiques.

Courses part 1    –   Courses part 2