Evaluation des algorithmes distribués
analyse, complexité, méthodes
Coll. Informatique

Ce livre propose un tour d'horizon de l'état de la complexité des algorithmes et de ses méthodes. Il présente l'analyse de la quasi-totalité des algorithmes fondamentaux du domaine. Les douze chapitres sont assortis de nombreux exercices corrigés et de notes bibliographiques.

Notations et définitions Partie 1. Concepts fondamentaux 1. Systèmes distribués et algorithmes distribués 2. Complexité des algorithmes distribués Partie 2. Les réseaux avec identités 3. L'élection sur les anneaux avec identités 4. L'élection dans les réseaux complets 5. Élection et arbres de recouvrement dans les réseaux quelconques 6. Analyse d'un algorithme distribué d'exclusion mutuelle 7. Graphes et algorithmes distribués sur les graphes 8. Algorithmes distribués de tri et de sélection Partie 3. Les réseaux anonymes 9. Introduction aux algorithmes probabilistes - application aux anneaux anonymes 10. L'élection sur les anneaux anonymes 11. Protocoles et élection dans les réseaux anonymes 12. Information et complexité distribuées Formulaire - Annexes I. Généralités sur les permutations II. Démonstrations de l'identité harmonique III. Nombre moyen de pics d'une permutation Correction des exercices Bibliographie

Cet ouvrage propose un tour d'horizon de l'état de la complexité des algorithmes et de ses méthodes. Il présente l'analyse de la quasi-totalité des algorithmes fondamentaux du domaine, assortie de nombreux exercices corrigés. Le prérequis mathématique est de niveau d'un Deug scientifique.