Search

Si les références aux machines se multiplient au XVIe siècle pour décrire l’univers réglé par Dieu ou encore le corps humain (l’organique étant conçu comme une mécanique), elles se font plus rares lorsqu’il s’agit d’aborder la question politique. Revient cependant, pour désigner le commonwealth, l’image du corps humain dont l’harmonie entre les différents membres, au sein d’une stricte hiérarchie, est la condition sine qua non de la bonne marche du royaume. Mais là où les traités théoriques et les discours officiels (sermons, homélies, …) dessinent un idéal parfaitement ordonné, le théâtre historique de la fin du XVIe et du début du XVIIe siècles en propose une vision bien plus nuancée, faite de dérèglements et de machinations. En donnant notamment une place de plus en plus importante aux figures de conseillers, qui obligent le roi à partager la scène – du théâtre mais aussi du pouvoir –, ces pièces dévoilent les coulisses de la pratique politique à un public qui en est le plus souvent, et pour la plupart de ses membres, exclu. La politique y apparaît comme la sphère de l’imprévu et de l’incertitude, marquée par la possibilité de l’erreur – autant celle du roi que de ses conseillers – et donc par la délibération à plusieurs et pas uniquement par la décision ou l’action d’un seul homme. La politique commande alors de s’adapter à son temps, principe machiavélien par excellence, là où l’expertise est difficilement mesurable et la légitimité – pour les conseillers, du moins – souvent contestable. Il s’agit donc de s’interroger à la fois sur le politique comme machine potentiellement infernale et sur l’identité de ceux choisis – par le roi – pour la manipuler. À une époque où, suite aux progrès techniques et scientifiques, émerge une classe technocratique dans de nombreux domaines comme la navigation (le pilote cédant sa place à l’expert), la politique n’a pas encore le statut d’une science ni d’une technique.

National audience; Nous proposons un algorithme simple pour la mise à jour d'un arbre couvrant un groupe dont les membres peuvent arriver et/ou partir à chaque étape. L'objectif est alors de maintenir un arbre dont le diamètre est proche du diamètre minimum. La dynamicité des membres et le respect de la contrainte sur le diamètre peuvent nécessiter la reconstruction de l'arbre. Une étape de reconstruction étant coÛteuse, nous nous intéressons à la minimisation de ce nombre d'étapes. Si cette démarche a déjà été étudiée, les précédents travaux se sont restreints à l'étude du pire cas (algorithmes d'approximation ou étude du rapport de compétitivité dans le contexte online). Dans cet article, nous analysons le comportement de notre algorithme en moyenne. Pour cela, nous proposons quelques encadrements analytiques particuliers et un moyen algorithmique efficace pour calculer de manière exacte l'espérance du nombre de reconstructions (sous des hypothèses d'équiprobabilité). Nous donnons alors les grandes tendances de cette espérance.

National audience; Cet article est consacré au problème de l'interconnexion de plusieurs groupes dans un réseau. Nous cherchons ici á réserver des ressources (liens de communication) du réseau, afin d'établir des connexions efficaces entre les membres de chaque groupe. Ces connexions doivent fournir des garanties sur la latence maximum (ou temps de communication maximum) de chaque groupe dans la ou les structures formées par les ressources réservées. Nous allons montrer que les approches pour interconnecter des groupes qui conservent les diamètres donnent lieu á des problèmes algorithmiques difficiles. Ces résultats nous conduisent á proposer une autre approche consistant á construire un seul arbre pour interconnecter tous les groupes. Nous proposons ici le premier algorithme avec garantie de performance mettant en oeuvre cette approche.

Resource reservation in a communication network is a research area leading to many algorithmic problems. A network can be seen as a graph, in order to easily design algorithms for resource reservation. The purpose is to manage as well as possible the resonrces for members who want to communicate using the network. For resource reservation in a single link, we use scheduling algorithms. In these problems, we can not always know al1 the informations about the problem since the beginning. To consider this lack of information, we consider the on-line setting. The informations are revealed one by one, without any knowledge of the future. For each problem we treat, we propose algorithms with an analytical evaluation, considering one (resp. several) performance criterion (resp. criteria).; La réservation de ressources dans un réseau de communication est un domaine d'application très vaste, qui implique des problèmes algorithmiques nombreux et variés. La modélisation d'un réseau sous la forme d'un graphe permet, indépendamment de sa nature physique, de développer des algorithmes pour déterminer quels sont les noeuds et/ou les liens du réseau qui doivent être réservés. Il s'agit de gérer au mieux l'attribution de ces ressources pour les membres qui inter-agissent via le réseau. Pour la résolution de problèmes liés à la réservation de ressources au niveau d'un lien particulier, c'est la modélisation sous la forme d'un ordonnancement qui est alors particulièrement adaptée. Dans ce type de problèmes, il n'est pas toujours possible de connaître à l'avance toutes les données à traiter. En effet, les demandes de membres amenés à communiquer via le réseau ainsi que les demandes de réservation au niveau des liens arrivent en pratique au fils de l'eau. Pour prendre en compte cette difficulté, nous nous plaçons dans le contexte de l'algorithmique on-line (en ligne). Les données du problème à traiter ne sont donc pas connues dès le départ, mais révélées au fur et à mesure, sans aucune connaissance du futur. Pour chacun des problèmes on-lines traités, nous proposons des algorithmes que nous évaluons analytiquement, en fonction d'un (ou parfois plusieurs) critère(s) de performance.

National audience; Cet article est consacré au problème suivant : étant donné un ensemble de membres dans un réseau, construire une structure permettant de les connecter tout en minimisant le poids de la structure, ainsi que la distance moyenne et maximale entre membres. Nous traitons ici plus spécifiquement l'aspect dynamique du problème lié au fait que de nouveaux membres peuvent intégrer la structure et d'autres la quitter. Nous prenons en compte le fait que les membres à connecter et les membres à déconnecter ne sont pas connus dès le début, mais dévoilés au fur et à mesure. Après avoir modélisé cette situation sous forme de problème de graphe, nous faisons une synthèse de nos travaux concernant différentes méthodes (de type online) qui seront classées en deux grandes catégories : les méthodes sans reconstruction (un ajout se fait par incrémentation et un retrait par décrémentation de la structure courante) et les méthodes avec reconstructions (on s'autorise à casser des liens internes de la structure courante pour traiter un ajout ou un retrait).

National audience

Resource reservation in a communication network is a research area leading to many algorithmic problems. A network can be seen as a graph, in order to easily design algorithms for resource reservation. The purpose is to manage as well as possible the resonrces for members who want to communicate using the network. For resource reservation in a single link, we use scheduling algorithms. In these problems, we can not always know al1 the informations about the problem since the beginning. To consider this lack of information, we consider the on-line setting. The informations are revealed one by one, without any knowledge of the future. For each problem we treat, we propose algorithms with an analytical evaluation, considering one (resp. several) performance criterion (resp. criteria)., La réservation de ressources dans un réseau de communication est un domaine d'application très vaste, qui implique des problèmes algorithmiques nombreux et variés. La modélisation d'un réseau sous la forme d'un graphe permet, indépendamment de sa nature physique, de développer des algorithmes pour déterminer quels sont les noeuds et/ou les liens du réseau qui doivent être réservés. Il s'agit de gérer au mieux l'attribution de ces ressources pour les membres qui inter-agissent via le réseau. Pour la résolution de problèmes liés à la réservation de ressources au niveau d'un lien particulier, c'est la modélisation sous la forme d'un ordonnancement qui est alors particulièrement adaptée. Dans ce type de problèmes, il n'est pas toujours possible de connaître à l'avance toutes les données à traiter. En effet, les demandes de membres amenés à communiquer via le réseau ainsi que les demandes de réservation au niveau des liens arrivent en pratique au fils de l'eau. Pour prendre en compte cette difficulté, nous nous plaçons dans le contexte de l'algorithmique on-line (en ligne). Les données du problème à traiter ne sont donc pas connues dès le départ, mais révélées au fur et à mesure, sans aucune connaissance du futur. Pour chacun des problèmes on-lines traités, nous proposons des algorithmes que nous évaluons analytiquement, en fonction d'un (ou parfois plusieurs) critère(s) de performance.

National audience; Nous proposons dans cet article des algorithmes d'ordonnancement permettant à un opérateur d'un lien haut-débit de gérer des demandes de réservations provenant de ses clients. Nos propositions ont les avantages suivants : (1) elles permettent de gérer les demandes à la volée, dès qu'elles arrivent à l'opérateur ; (2) nous prouvons qu'elles permettent d'approcher à de faibles facteurs multiplicatifs près, le profit maximum atteignable et, simultanément, le nombre maximum de clients pouvant être servis ; (3) ces facteurs sont ajustables et permettent à l'opérateur de donner plus d'importance relative à l'un ou l'autre des critères.