LIPN: Séminaire OCAD

Permutation tableaux are relatively new combinatorial objects that are in bijections with permutations. They have ben introduced in the context of algebraic combinatorics and subsequently found applications in combinatorial aspects of some particle models (like PASEP). Permutation tableaux have been studied mostly by bijective methods. In this talk, I will describe a direct, elementary approach based on probabilistic interpretation of a basic construction. This talk is partially based on results obtained jointly with Sylvie Corteel.

The InteGrade project is multi-university initiative aimed at building a novel object-oriented Grid middleware that focuses on leveraging the idle computing power of commodity workstations such as PCs in shared laboratories, corporate employee workstations, and household PCs. Our goal is to allow organizations to use their existing computing infrastructure to perform useful computation, without requiring the purchase of additional hardware. Moreover, users who share the idle portion of their resources should have their quality of service preserved by the InteGrade middleware. InteGrade provides support for highly-coupled parallel applications, checkpointing, security, and an integrated development environment.

In this presentation I will quickly present the main features of InteGrade, and then present some combinatorial problems related to the project.

Dans les réseaux Internet, la façon dont le trafic est routé dépend du protocole de routage utilisé.

Les protocoles de routage « classiques » routent le trafic sur des plus court chemins. Le méta-protocole MPLS (Multi-Protocole Label Switching) offre plus de flexibilité pour router le trafic.

Le Traffic Engineering (TE) consiste à chercher la meilleure façon d'utiliser les ressources d'un réseau donné pour satisfaire un ensemble de demandes. Dans cet exposé, plusieurs problèmes d'optimisation issus du TE seront présentés, ainsi que des modèles et/ou des techniques utilisés pour les résoudre.

Le modèle de Tetris sera le fil rouge de l'exposé. Il constitue un paradigme pour différents modèles de Systèmes a Evènements Discrets, qui peuvent se voir comme des spécialisations, variations ou extensions de Tetris. Tetris constitue également le point de rencontre de deux classes de modèles mathématiquement intéressantes : les systèmes itérés d'applications topicales (max-plus dans le cas de Tetris) et les marches aléatoires sur les groupes ou monoïdes discrets (traces dans le cas de Tetris). Par ailleurs, le modèle de Tetris est intéressant en lui-même et sera étudié en tant que tel. On s'intéresse aux aspects énumératifs (combien d'empilements différents ?), à l'optimisation (à quoi ressemblent les empilements les plus denses ?) et à l'évaluation de performances (à quelle vitesse se constituent les empilements aléatoires ?).

Une lecture de la métrologie de l'internet et de sa modélisation statistique vue depuis le traitement du signal a été présentée à AlgoTel 2007 et sera adapté pour le séminaire OCAD. On y parlera de réseaux, de mesures, de trafic agrégé, de distributions ou de dépendance à temps long), d'invariance d'échelle ou de dépendance à temps long et d'applications récentes de ces notions à la détection d'anomalies dans le trafic internet.

New uniform asymptotic approximations with error bounds are derived for a generalized total variation distance of Poisson approximation to the Poisson-binomial distribution (covering binomial distribution as special case). The method of proof is also applicable to other Poisson approximation problems, and therefore to a lot of data structures and algorithms.

François Baccelli, Georges Gonthier, Gilles Schaeffer, Patrice Abry, Laurent Massoulié, Frédéric Cazals et Sylvain Soliman présentent des résultats récents à l'Académie des Sciences. Nous invitons doctorants (et permanents!) à se rendre à Paris (23, Quai de Conti) pour assister à ces conférences de prestige.

Calculer de bonnes bornes pour des programmes en nombres entiers non linéaires est difficile, d'autant plus que la relaxation lagrangienne classique nécessite la résolution de sous-problèmes entiers non linéaires, qui ne sont pas en général plus faciles à résoudre que le problème initial. Pour des problèmes à fonction économique convexe et contraintes linéaires, nous proposons une relaxation primale, qui peut etre résolue par la méthode des multiplicateurs combinée à la décomposition simpliciale limitée. Nous montrons sur des instances de problèmes d'implantation non linéaire avec contraintes de capacité, que cette borne peut etre calculée de façon efficace, et que pour des problèmes linéaires la méthode est en fait plus stable qu'une méthode de sous-gradient.

Broadcast is an efficient and scalable way of transmitting data to an unlimited number of clients that are listening to a channel. Cyclically broadcasting data over the channel is a basic scheduling technique, which is known as flat scheduling. When multiple channels are available, a data allocation technique is needed to assign data to channels. Partitioning data among channels in an unbalanced way, depending on data popularities, is an allocation technique known as skewed allocation. In this talk, the problem of data broadcasting over multiple channels is considered assuming skewed data allocation to channels and flat data scheduling per channel, with the objective of minimizing the average waiting time of the clients. First, several algorithms, based on dynamic programming, are presented which provide optimal solutions for N data items and K channels.
Moreover,for data items with non-uniform lengths, it is shown that the problem is NP-hard when K=2, and strong NP-hard for arbitrary K. For larger instances, a new heuristic is devised which is experimentally tested on some benchmarks whose popularities are characterized by Zipf distributions. Such experimental tests reveal that the new heuristic proposed here always outperforms the best previously known heuristic in terms of solution quality.

http://www-anp.lip6.fr/~bonami/
En 2003, Balas et Perregaard ont proposé un nouvel algorithme de séparation des coupes de lift-and-project basé sur une correspondance exacte entre les coupes de Gomory et les coupes de lift-and-project. Bien que cet algorithme soit nettement plus efficace que les algorithmes précédents il n'existe pas d'implémentation publiquement disponible àce jour.
Dans ces travaux nous proposons 3 variantes de ce nouvel algorithme de lift-and-project. Les 3 variantes ont été implémentées dans un code open-source publiquement disponible sur le site de COIN-OR.
Après avoir brièvement présenté les coupes de lift-and-project et les éléments théoriques permettant de les séparer efficacement, nous décrivons les trois variantes et présentons des résultats de calcul obtenus avec le code publiquement disponible.

On envisage le problème qui consiste a minimiser le coût d'affectation des tâches avec des dates de disponibilité et des deadlines à des machines hétérogènes. Pour le résoudre efficacement, on sépare les composants d'optimalité et de faisabilité du problème. Dans notre cas, les méthodes de la Programmation Linéaire en Nombres Entiers sont "responsables" de l'optimisation et des algorithmes spéciaux combinatoires assurent la faisabilité à l'aide des coûts.
En utilisant cette idée, nous avons proposé des algorithmes de types "branch-and-cut" et génération de colonnes pour résoudre le problème. La recherche expérimentale a montré que ces algorithmes sont meilleurs que les algorithmes existants dans la littérature.

Techniques de résolution basées sur la Programmation Linéaire pour l'ordonnancement de projetLe RCPSP (Resource-Constrained Project Scheduling Problem), connu pour être NP-difficile au sens fort, consiste à planifier dans le temps l'exécution des activités d'un projet, soumises à des contraintes de précédence et de ressources, dans le but de minimiser le temps total d'exécution. Ce problème suscite un intérêt important dans la communauté des chercheurs opérationnels parce qu'il sert de modèle pour de nombreux problèmes réels de gestion de projet et de planification.
Nous présentons une reformulation originale de ce problème, basée sur une relaxation linéaire continue, où chaque variable est associée à un ensemble d'activités pouvant être exécutées simultanément au cours de l'ordonnancement. La résolution de cette relaxation par l'algorithme du Simplexe fait appel à des techniques de génération de colonnes dont le problème de pricing correspond au problème de sac-à-dos / stable maximum. Nous adjoignons à chaque itération de la descente proposée par le Simplexe un test incrémental de respect, par la famille des variables en base, des propriétés identifiées à partir de notre reformulation pour que cette famille représente un ordonnancement réalisable. Un résultat théorique de connexité de l'espace de ces solutions réalisables, pour notre opérateur de voisinage, est fourni.
La qualité médiocre des premiers résultats de cette descente avec pivotage sélectif est dûe au nombre important de minima locaux. Elle incite à proposer des techniques de diversification dans l'espace de recherche. Deux algorithmes ont été développés dans ce sens, améliorant sensiblement les valeurs des solutions réalisables obtenues, l'optimum étant atteint relativement fréquemment sur les instances classiques de la librairie PSPLIB à 30 activités.
De plus, la version préemptive du RCPSP autorise l'interruption de l'exécution d'activités pour être reprise ultérieurement, sans pénalité. Les méthodes décrites ci-dessus traitent avec qualité ce cas particulier. Une méthode par Séparation/Evaluation, basée sur cette même relaxation linéaire, a été développée pour celui-ci. Le branchement correspond à des contraintes de non-circuit que l'on ajoute aux différents nœuds de l'arbre par le biais de mises à zéro de certaines variables. Trois variantes de branchement ont été conçues, et l'une d'elles fournit toutes les solutions optimales préemptives des instances mentionnées ci-dessus. Une formulation linéaire mixte a également été proposée pour ce problème, et donne lieu actuellement à l'implémentation de techniques de Branch and Cut and Price très prometteuses.

La coloration orientée est une façon possible de généraliser aux graphes orientés la coloration classique définie sur les graphes simples. Nous la présenterons au moyen du formalisme des homomorphismes de graphes, formalisme qui souligne sa similitude avec le cadre non-orienté.
Nous discuterons ensuite de la complexité de ce problème ainsi que l'approximation (différentielle) du problème d'optimisation associé. Enfin, nous adapterons la notion de polynôme chromatique pour la coloration orientée et discuterons de quelques propriétés en montrant les similitudes et différences avec le cadre non-orienté.
Au cours de ces discussions, nous verrons l'intérêt d'introduire ces notions dans le cadre plus large des graphes mixte, afin de faire le lien entre les cadres non-orienté et orienté.

Cet exposé se place dans le cadre de la conception de protocoles (ou algorithmes) devant interagir avec des utilisateurs indépendants et individualistes. Chaque utilisateur souhaite optimiser son propre critère, qui peut être très différent de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser cette fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste.
Je présenterai dans cet exposé plus particulièrement un problème d'ordonnancement dans lequel des utilisateurs individualistes sont en concurrence pour des ressources partagées : chaque utilisateur possède une tâche dont il souhaite qu'elle soit effectuée le plus rapidement possible.
Chaque utilisateur est le seul à connaître la longueur de sa tâche, qu'il déclare alors à l'algorithme qui ordonnance les différentes tâches. Les utilisateurs peuvent ainsi déclarer de fausses valeurs si cela peut permettre à leur tâche d'être exécutée plus tôt. Ces informations erronées peuvent induire de mauvaises performances globale de l'algorithme. Nous cherchons alors à concevoir des algorithmes tels que les utilisateurs n'aient pas d'intérêt à déclarer de fausses informations, et analysons la performance de tels algorithmes.

Dans cet exposé, nous nous intéressons à des problèmes de sécurisation et dimensionnement de réseaux de télécommunication multicouches.
Dans un premier temps, nous considérons un problème de sécurisation de réseaux IP-sur-optique. Nous présentons une approche polyédrale pour ce problème. En particulier, nous discutons de certaines familles de contraintes valides et de procédures de séparation. Nous introduisons des opérations de réduction de graphes qui sont très utiles pour la séparation des contraintes. Et en utilisant ces résultats, nous proposons un algorithme de coupes et branchement pour le problème et discutons de résultats expérimentaux effectués sur des instances réelles fournies par France Télécom.
Nous considérons par la suite une extension de ce problème dans laquelle on étudie le dimensionnement du réseau. Nous discutons de formulations en termes de programmes linéaires mixtes, et nous proposons un algorithme de coupes, génération de colonnes et branchement pour le problème. Nous présentons des résultats expérimentaux sur des instances réelles également fournies par France Télécom.

Nous considérons une application d'un problème de tournées de véhicules combinées à la gestion des stocks. Une flotte de véhicules est affectée à collecter un seul produit sur différents sites. Chaque site a son propre taux d'accumulation et sa capacité de stockage. À chaque visite, le stock est vidé. Dans la phase de planification tactique, nous cherchons une solution périodique qui est répétée dans le temps. L'objectif est de minimiser la taille de la flotte et les coûts de transport tout en donnant un découpage régionale de l'espace par une partition des sites entre les véhicules. Au terme d'une analyse comparative nous proposons une modélisation adéquate. La structure du problème est exploitée pour développer une approche de décomposition de Dantzig-Wolfe. Des plannings périodiques sont générés pour les véhicules en résolvant un problème de sac-à-dos à choix multiple. L'élaboration des plannings de collecte pour les sites est traitée dans le programme maître. Ce dernier est reformulé en terme de variables agrégées pour éviter la symétrie en temps. Les bornes duales sont calculées par une méthode tronquée de Branch-and-Price-and-Cut. Les bornes primales sont obtenues par des heuristiques d'arrondi et de recherche locale développées dans le contexte de la génération de colonnes. Des instances réelles sont résolues avec une déviation à l'optimalité raisonnable.

Nous présentons dans cet exposé une étude du problème du multi-sac-à-dos quadratique en variables entières (QMKP) qui est un problème NP-difficile.
Il constitue un cas particulier de la programmation non linéaire en variables entières qui trouve de nombreuses applications dans les domaines de la recherche opérationnelle. Nous étudions, dans un premier temps, un cas particulier du problème (QMKP): le problème du multi-sac-à-dos quadratique en variables entières dont la fonction é conomique est concave et séparable. Dans ce contexte, nous élaborons une procédure de recherche arborescente par séparation et évaluation pour le résoudre. Cette dernière repose sur le calcul d'un majorant fin de la valeur optimale de (QMKP). Ce majorant provient d'une méthode basée sur une linéarisation et une relaxation agrégée du problème initial. Notre branch-and-bound incorpore également des procédures de pré-traitement en amont. Nous comparons les performances en terme de temps de calcul et de qualité de notre majorant avec trois méthodes exactes existantes: un algorithme de branch-and-bound développé par Djerdjour et al. (1988), une formulation linéarisée en variables 0-1 (initialement utilisée pour résoudre le sac-à-dos quadratique mono-contraint en variables entières que nous avons étendu au cas multi-contraint), un branch-and-bound classique (optimisation quadratique Cplex9.0). Notre branch-and-bound est clairement le plus performant nous permettant de résoudre des problèmes de grandes tailles (jusqu'à 2000 variables et contraintes) en 5 minutes en moyenne.
Dans un deuxième temps, nous étendons nos recherches au cas où la fonction économique du problème (QMKP) est concave et non séparable. Nous proposons alors une voie théorique de résolution de ce problème basée sur une transformation du problème non séparable en un problème séparable. Nous sommes alors en mesure de lui appliquer notre algorithme développé pour résoudre (QMKP) séparable et ainsi de fournir l'optimum entier de ce problème.

non communiqué

On sait que la génération de colonnes est équivalente à la relaxation lagrangienne, laquelle se ramène à l'optimisation d'une fonction convexe (la fonction duale). Dans les problèmes qui nous intéressent, l'oracle (i.e. le problème auxiliaire) est NP, par exemple un sac à dos. Par ailleurs, la condition habituelle que tous les coûts réduits soient positifs se traduit par une contrainte convexe dans l'espace dual. Enfin, des coûts primaux tous égaux à 1 donnent une forme bien particulière à cette contrainte : elle est positivement homogène.

Dans cet exposé, nous expliquons une méthode d'optimisation convexe (faisceaux) adaptée à ces divers cas, et nous l'illustrons sur le problème de la découpe industrielle.

L'analyse des interactions entre gènes ou protéines conduit à la recherche de sous-graphes ayant une morphologie donnée dans un graphe. Le graphe en question décrit par exemple les interactions entre gènes. La question à résoudre est la recherche de sous-graphe particulièrement présents (motifs) ou particulièrement absents (anti-motifs) par rapport à une présence "normale" dans un graphe aléatoire.

Ce travail est consacré d'une part au calcul de la loi de distribution du nombre de composantes connexes dans un modèle de graphe aléatoire particulier (les graphes d'Erdős) et d'autre part à la descritption d'un algorithme de recherche de sous-graphes à l'aide de tries.

Nous nous intéressons à des problèmes algorithmiques de type on-line (en ligne). Dans ce contexte, les données du problème à traiter ne sont pas connues dès le départ, mais révélées au fur et à mesure, sans aucune connaissance du futur. Nous proposons des algorithmes pour la construction en ligne d'un arbre couvrant un groupe dynamique dans un graphe, où les sommets à ajouter et/ou retirer du groupe sont révélés au fur et à mesure. L'arbre doit alors être mis à jour, et respecter à chaque étape une certaine qualité évaluée en termes de distance maximum et/ou moyenne entre membres du groupe dans l'arbre. Nous donnons des bornes analytiques (inférieures et supérieures) pour différentes variantes de ce problème, et proposons, lorsque cela se révèle nécessaire, un principe de remise en cause maîtrisée de la solution courante. Dans la grande majorité des cas étudiés, la qualité de nos algorithmes est optimale en ordre de grandeur. Une application possible de ces travaux est la construction en ligne de structures de communications pour des groupes d'utilisateurs dans les réseaux.

We consider probabilistic models for Steiner tree problem. Under these models, the problem is defined in a two-stage setting over a complete weighted graph whose vertices are associated with a probability of presence in the second stage. A first-stage feasible solution on the input graph might become infeasible in the second stage, when certain vertices of the graph fail (with the specified probability). Therefore, a well defined modification strategy is devised which transforms a partial solution to a feasible second-stage solution. The objective is to devise an algorithm for the first-stage solution (sometimes called the a priori or anticipatory solution) so that the expected second-stage solution cost is minimized. An important feature of this framework is that the modification strategy is essentially a part of the problem, while algorithmic treatment is required in the construction of the anticipatory solution. We essentially provide approximation results regarding two modification strategies. Furthermore, for the first of them we also formulate the associated objective function and prove complexity results for the computation of the anticipatory solution optimizing it.

Non disponible.

On attache à tout graphe G son polynôme chromatique X(G,c), qui dénombre ses colorations avec c couleurs.

Le polynôme chromatique demeure un objet mystérieux (certains espèrent toujours trouver une preuve analytique simple du théorème des 4 couleurs grâce à lui!), mais ayant de nombreuses propriétés magiques.

Par exemple, sa valeur en -1 donne le nombre d'orientations acycliques du graphe.

Nous montrerons comment généraliser ce résultat de Stanley, en obtenant in fine tous les coefficients de X(G,c) développé en puissances de c et surtout en puissances de (c-1).

L'utilisation systématique des fonctions génératrices des fonctions d'ensembles permet d'avoir des démonstrations très courtes et explicatives.

Ceci donne également un nouvel éclat aux résultats de Cartier, Foata, Viennot, Brenti, Gessel et Stanley, Gebhard et Sagan, Duchamp et Krob, Greene et Zaslavsky, et sur l'invariant β(G) de Crapo.

Les applications des fonctions d'ensembles à des questions d'optimisation combinatoire sont par ailleurs nombreuses.

Il s'agit de l'étude d'un problème de graphe sandwich.

1^ère partie : Ordonnancement multiprocesseurs

Les applications deviennent de plus en plus gourmandes en temps de calcul, notamment les applications temps réel et les programmes tels que la prédiction météorologique et la simulation numérique où les besoins de précision et de fiabilité sont toujours croissants. Le parallélisme a été une possibilité de répondre à cette demande de performances car le recours au parallélisme est motivé par le besoin de plus de rapidité. Cependant, son exploitation reste difficile et pose beaucoup de problèmes. Les difficultés se situent au niveau algorithmique, au niveau des langages de programmation parallèle pour exprimer le parallélisme de l'application, ainsi qu'au niveau de l'ordonnancement et le placement des tâches composant ces applications sur l'architecture matérielle (les processeurs).

La qualité d'un ordonnancement, voir sa validité, dépendent de nombreux paramètres : le temps total d'exécution de l'application (MakeSpan), l'efficacité, le nombre de processeurs utilisés, ainsi que la complexité du processus d'ordonnancement. La prise en compte de ces paramètres est capitale dans la recherche d'implantations parallèles efficaces.

Dans le cadre de cet exposé, je parlerai du problème d'ordonnancement des modèles de tâches plus réalistes (graphe de tâches de grande taille, les durées des tâches et des communications sont variables) sur des architectures à mémoires distribuées. Je présenterai quelques heuristiques :

1. Un algorithme DCPS basé sur la technique du chemin critique sur des architectures UNP.
2. Un algorithme CTS basé sur l'urgence des tâches sur des architectures BNP.
3. Un algorithme Bicritère (BSA) pour la minimisation simultanée du makespan et la probabilité de défaillance de l'application en présence de pannes matérielles.

2^e partie : Ordonnancement distribué temps réel

Pour le problème de l'ordonnancement distribué temps réel : Dans un réseau quelconque et totalement distribué, des groupes de tâches sporadiques avec dépendances, caractérisés par leurs échéances temporelles (deadlines) peuvent apparaître sur n'importe quel site et à n'importe quel moment. Nous parlerons d'un mécanisme original RTDS (Real Time Distributed Scheduling) basé sur le concept de calcul des sphères (Cet algorithme est le fruit d'un travail mené avec Lucian FINTA.) pour déterminer les voisins potentiels qui peuvent participer à l'exécution du groupe de tâches. L'approche étudiée se décompose de deux parties :

• l'ordonnancement local (boîte noire): un algorithme capable de décider en ligne s'il peut garantir l'exécution d'un groupe de tâches avant sa deadline.
• l'ordonnancement réparti : dans le cas d'un rejet local du groupe de tâches, une coopération entre les différents sites appartenant à la même sphère est invoquée pour permettre une exécution distribué du groupe de tâches.

Les travaux présentés dans cet exposé portent sur la résolution approchée de problèmes d'optimisation combinatoire. Il s'agit, pour les problèmes NP-difficiles, de proposer des méthodes de résolution garantissant l'obtention de solutions proches de la solution optimale. Différents aspects liés à cette problématique seront abordés :

• la classification des problèmes selon leur difficulté de résolution (classe d'approximation, réductions, complétude)
• les liens avec la logique (expression logique des problèmes combinatoires, problèmes de satisfiabilité,...)
• l'extension à des situations où l'instance du problème n'est pas fixe (car inconnue, dynamique,...), comme le cadre on-line, l'optimisation combinatoire probabiliste,...

Attention, ce séminaire est à 14h00 précises !

L'objectif de la stéganographie est d'échanger des messages confidentiels sans dévoiler l'existence d'une communication secrète. Pour cela, la stéganographie cherche à insérer de l'information secrète au sein d'un document anodin, sans modifier de manière notable ce dernier (on pense essentiellement à des images ou de la vidéo). Le document anodin est ensuite transmis au destinataire des données confidentielles. Sous le camouflage d'une communication anodine, on échange ainsi des informations secrètes. La furtivité de l'insertion est bien entendu cruciale pour la confidentialité. Toutefois, d'autres applications comme le marquage de documents numériques tolèrent une furtivité moindre pour une certaine robustesse de l'insertion.

Je présenterai les liens entre cette problématique et celle de la correction d'erreurs. Ces liens conduisent à des algorithmes stéganographiques que l'on peut prouver optimaux dans certains cas en étudiant les objets combinatoires sous-jacent : les codes de recouvrement. Je montrerai ensuite comment l'ajout de la robustesse conduit aux codes centrés, généralisation des codes correcteurs classiques, et ce qu'apporte ces codes à la problématique du marquage ou de la stéganographie robuste.

Attention, le séminaire débutera à 12h30 précises !

Les travaux que je présente dans cet exposé ont pour objet les algorithmes de chiffrement symétrique, dit encore à clé secrète. Bien que ces systèmes nécessitent l'échange, préalable à toute communication, d'un secret commun -- contrairement à leurs homologues asymétriques -- ils sont les seuls à répondre de manière satisfaisante à des exigences de débit élevé ou d'encombrement faible qui les rendent utilisables pour le chiffrement d'importants flux de données. L'évaluation de leur sécurité est donc primordiale.
La sécurité de tout algorithme de chiffrement peut être vue sous deux aspects complémentaires. Le cryptanalyste, d'une part, analyse --- éventuellement << casse >> le système --- soulignant ainsi ses faiblesses. Le cryptographe a alors pour charge de prendre en compte ces faiblesses et de les formaliser de manière à pouvoir proposer des critères pour concevoir de nouveaux systèmes sûrs... jusqu'à une nouvelle attaque.
J'ai abordé le premier de ces aspects par le biais d'une attaque différentielle d'ordre supérieur (de Tanaka et al. 1999) sur le chiffrement itératif par blocs MISTY1, variante de l'algorithme KASUMI utilisé dans la norme UMTS. J'ai pu expliquer l'origine de cette attaque par les propriétés de composition des fonctions de non-linéarité maximale utilisées comme fonctions de tour dans l'algorithme. Ces fonctions, aux propriétés algébriques fortes, ont paradoxalement été choisies car elles assurent une résistance maximale aux deux principales attaques génériques connues alors, les cryptanalyses linéaire et différentielle. J'ai ainsi pu concevoir une attaque différentielle d'ordre supérieur qui s'applique à la plupart des chiffrements de Feistel à 5 tours utilisant de telles fonctions.
Je me suis intéressée à l'aspect relatif à la conception de systèmes de chiffrement sûrs au travers de l'étude des propriétés cryptographiques des fonctions booléennes symétriques. Ces fonctions qui sont caractérisées par le fait que leur valeur est invariante par permutation des variables d'entrée, sont les seules pour lesquelles on connaisse une implémentation en un nombre de portes logiques qui dépendent de manière linéaire du nombre de variables d'entrée. Elles pourraient donc recéler de bonnes candidates pour être des fonctions de filtrage pour des chiffrements à flot visant un encombrement mémoire (logiciel ou matériel) faible. Les propriétés cryptographiques que j'ai étudiées sont le degré algébrique, l'équilibre, la résilience, la non-linéarité -- l'étude de l'immunité algébrique est en cours. Bien que fort peu de fonctions dans cette famille semblent atteindre des valeurs satisfaisantes pour les paramètres cryptographiques, la mise en évidence d'une propriété de périodicité pour un vecteur de représentation de ces fonctions a permis d'améliorer substantiellement les résultats existants. Liés aux deux aspects précédents, je présenterai également les pistes que j'envisage d'explorer pour améliorer la formalisation de la sécurité des systèmes de chiffrement symétrique.

Several important tree models, e.g., recursive trees, plane-oriented recursive trees and binary increasing trees are members of the family of increasing trees. These tree models turned out to be appropriate in order to describe the behaviour of a lot of quantities in various applications, e.g., they are used to describe the spread of epidemics, for pyramid schemes, and they are used as a simplified growth model of the world wide web, since plane-oriented recursive trees are a special instance of the so called Albert-Barabasi model for scale-free networks.
Increasing trees can be considered as labelled trees, where the nodes of a tree of size n are labelled by distinct integers of the set {1, ..., n} in such a way that each sequence of labels along any path starting at the root is increasing. However, it is more common to describe certain members of increasing tree families via a tree evolution process and studying tree parameters by applying probabilitsitc techniques, like using Polya-Eggenberger urn models or by translating results from continuous time branching processes.
However, by means of these probabilistic methods there are obtained relatively few results that give insight into the behaviour of the node j (= the j-th individual) during the growth process in a tree of size n, in particular if the label j = j(n) is growing with n. Here we use a combinatorial description of increasing tree families, which in particular turned out to be suitable for a distributional analysis of such labe l-dependent parameters as the degree of node j, the depth of node j, the size of the subtree of node j, the distance between two nodes j_{1} and j_{2}, etc., dependent on the growth of j=j(n).
The results presented are based on common work with Markus Kuba (TU Wien).

Etant donné l'écart de performance évident et continuellement croissant qui existe entre les sous systèmes de stockage et l'unité centrale, le choix d'une bonne architecture de stockage et d'une stratégie optimale d'accès à cette dernière est essentielle. Les systèmes d'exploitation procurent aux développeurs plusieurs méthodes d'accès aux fichiers via des primitives système (open, read, write, close) sous Unix/Linux ou API (CreateFile, ReadFile, WriteFile, CloseHandle) sous Windows. Ces fonctions permettent l'utilisation d'un nombre de drapeaux spécifiant certaines options d'accès (e.g. O_SYNC pour open(), FILE_FLAG_NOBUFFERING pour CreateFile) qui peuvent aider le système à optimiser les accès. Nous avons observé en effectuant quelques mesures de performance, que pour un même flux de données les performances pouvait varier d'un facteur 10 dans certains cas (pour un disque pouvant soutenir 40MO/sec, nous avons obtenu 4MO/ sec sur un _fichier séquentiel_) et plus souvent d'un facteur 2 voire 3. Quelles sont *les causes* de ces variations de performances ? Comment les *comprendre* ? Comment les *prédire* ? Et comment faire pour *identifier *la stratégie d'accès la plus optimale pour une charge de travail et/ou une architecture donnée(s) ?. C'est à ces questions que je tenterai de répondre lors de ma présentation.

Mots-clés : /Système d'exploitation, disque, cache du système de fichiers, cache disque, politique de préchargement , mesures de performances, simulation, entrées / sorties, mode d'accès, stockage.

Les travaux présentés dans cet exposé se situeront au carrefour de la géométrie discrète et de la combinatoire des mots. Je m'intéresserai en particulier aux relations entre ces disciplines et montrerai, comment obtenir de nombreuses propriétés (propriétés structurelles, statistiques...) des plans et surfaces discrets (analogues discrets des plans et des surfaces usuels) à partir d'un codage des ces objets par des mots bidimensionnels indexés par ℤ². Je terminerai mon exposé par l'énoncé de quelques perspectives de recherches ainsi que quelques questions ouvertes auxquelles je m'intéresse actuellement.

On s'intéresse à des problèmes d'optimisation où les solutions sont évaluées à l'aide plusieurs critères conflictuels. Ils permettent de modéliser des situations n'admettant pas d'optimum global clairement établi mais où un ensemble de solutions de compromis, dominant toutes les autres, existe. Cet ensemble, appelé courbe de Pareto, est difficile à déterminer et nous cherchons à l'approcher avec une garantie de performance sur chacun des critères. Les problèmes étudiés sont : la coupe maximale bicritère et une version restreinte du problème du voyageur de commerce multicritère.

We consider the following general edge-removal procedure for labelled rooted trees. Select i∈ℕ nodes (v_λ1, v_λ2, ..., v_λi) labelled 1≤λ₁<λ₂<...<λ_i≤|T| of a given tree T. It is assumed that the tree T is labelled by |T| (size of T) distinct integers 1, 2,... , |T|.

Pick at random one of the edges of T and remove it. This separates the tree into a pair of rooted trees; the tree containing the root of the original tree retains its root while the tree not containing the root of the original tree is rooted at the vertex adjacent to the edge that was cut. Now continue this procedure in one or both of the arising subtrees until the nodes (v_λ1, v_λ2, ..., v_λi) are isolated. The random variable X counts the number of random cuts until (v_λ1, v_λ2, ..., v_λi) are isolated. We study this procedure for recursive trees and several choices of (v_λ1, v_λ2, ..., v_λi). We can give some limit distribution results for normalized versions of |X|.

A special case of this procedure is the so-called destruction of trees (cutting down) procedure (λ=1, v₁ is the root of T), which is also applicable for unlabelled rooted trees. We consider a modified version of the destruction of tree procedure, which isolates a leaf of the given tree. Again we offer limit distribution results.

Keywords: recursive trees, destruction of trees, cutting down procedure, random cutting.

We give two different bilinear mixed-integer programming formulations for the problem of scheduling dependent tasks onto an arbitrary architecture of homogeneous processors. If two dependent tasks are scheduled to different processors, a communication delay occurs, which depends on the quantity of data they have to exchange as well as the processor distance in the architecture. We carry out computational comparison using two different linearizations of the two formulations.

In this talk, I will consider the computational complexity of approximating the b-chromatic number of a graph. Let G=(V,E) be a simple finite undirected graph. A coloring (i.e. proper coloring}) of G is an assignment of colors to the vertices of G, such that any two adjacent vertices have different colors. A coloring is called a b-coloring, if for each color class i there exists a vertex x_i adjacent to a vertex in color class j, for all j \neq i. The b-chromatic number phi(G) of a graph G is the largest number k such that G has a b-coloring with k colors. The b-chromatic number of a graph was introduced by Irving and Manlove (1999). I will show that there is no constant epsilon > 0 for which this problem can be approximated within a factor of \appval - epsilon in polynomial time, unless P = NP. This is the first hardness result for approximating the b-chromatic number. Joint work with Sylvie Corteel and Juan Vera.

A radio network is a distributed system consisting of a large number of tiny sensors with low-power transceivers and no central controller. One of the most important problems in such networks is to minimize the energy consumption, and maximize the network lifetime. In the initialization problem (also known as naming) each of the n indistinguishable (anonymous) nodes in a given network is assigned a unique identifier, ranging from 1 to n. We consider a network where $n$ nodes (processors) are randomly deployed in a square (resp. a cube) X. The network is assumed to be synchronous and the time to be slotted. Two nodes can communicate only if they are at a distance of at most r from each other (r is the transmitting/receiving range). Moreover, if two or more neighbors of a processor u are transmitting concurrently at the same time slot, u cannot receive either of their messages (collision). We suppose also $n$ and |X| represent the only topological knowledge in each node. To solve the initialization problem, we propose an energy-efficient randomized algorithm running in at most O(n^¾log(n)^¼) time slots, with no station being awake for more than O(n^¼log(n)^¾) time slots.

We consider uniform distribution of sensors, where each sensor sends equal number of reports toward the closest sink. We assume an energy consumption model governed by the relation E=d^α+c where d is the transmission distance, α≥2 is the attenuation power, and c is a system-dependent positive constant. This paper investigates theoretical aspects of the uneven energy depletion phenomenon recently noticed in sink-based wireless sensor networks. Our results are multifold. First, we show that all sensors whose distance to the sink is at most (2c/(α-2))^1/α should report directly to the sink. Interestingly, this limit does not depend on the size of the network (the furthest distance R from sink to a sensor). Next, we prove that, in order to minimize the total amount of energy spent on routing along a path originating at a sensor in a corona and ending at the sink, all the coronas must have the same width, and that width is equal to the above expression for optimal size of the first corona. This choice, however, leads to uneven energy depletion phenomenon and creation of energy holes. We show that for α>2 the uneven depletion can be prevented by judicious system design. In such a system, the energy expenditure is balanced across the network. We describe an iterative process for determining the sizes of other coronas. Their optimal sizes (and corresponding transmission radii) and the number of coronas depends on R. The width of coronas in energy balanced sensor network increases. Finally, we show that for α=2, the uneven energy depletion phenomenon is intrinsic to the system and no routing strategy can avoid the creation of an energy hole around the sink.

Dans cet exposé, nous considérons le problème du sous-graphe biparti induit de poids maximum. Nous étudions le polyèdre associé à ce problème. Nous décrivons plusieurs classes de contraintes valides et nous donnons des conditions nécessaires et suffisantes pour que ces contraintes définissent des facettes du polytope. Nous discutons également d'algorithmes de séparation et nous montrons que certaines de ces classes peuvent être séparées en temps polynomial. Nous développons aussi un algorithme de coupes et branchements basé sur ces résultats pour le problème du sous-graphe biparti induit.

Nous proposons ensuite deux applications de ce problème. La première concerne la conception de circuits intégrés de grandes dimensions (VLSI). Plus particulièrement, nous montrons comment le problème de Via Minimization contraint peut se ramener à rechercher un plus grand sous-graphe biparti induit dans un graphe particulier.

Enfin, nous nous intéressons au problème d'assemblage SNP d'haplotypes qui constitue une étape du séquençage du génome pour les organismes diploïdes. Sous certains critères, nous montrons que ce problème se ramène également au problème du sous-graphe biparti induit. Enfin, nous appliquons notre algorithme de coupes et branchements pour résoudre des instances issues de ces deux applications.

Plusieurs approches ont été proposée dans l'étude des algorithmes répartis tolérant aux pannes, parmi lesquelles l'auto-stabilisation (le système rétablit de lui-même un fonctionnement correct au bout d'un temps fini) et le confinement de fautes (on limite la propagation d'une faute singulière). Nos travaux visent à étendre les champs d'application de ces deux approches.

Concernant l'approche auto-stabilisante, nous proposons un algorithme d'ordonnancement des déplacements dans un système de robots mobiles communiquant sur des points de rendez-vous fixés. Cet algorithme garantit que, après la phase de stabilisation, chaque visite à un point de rendez-vous aboutit à une communication. Nous présentons ensuite un algorithme auto-stabilisant pour engendrer et maintenir les tables de routage des robots.

Pour pallier aux limites de l'auto-stabilisation, des approches ont été développées pour un traitement plus local et plus rapide des fautes singulières, consistant à les circonscrire à une zone proche des processeurs corrompus et à contraindre le temps de stabilisation. L'une de ces approches, le confinement de fautes, fait l'objet de la deuxième partie de cet exposé. Nous avons introduire cette notion dans un algorithme de construction d'arbre couvrant dans un système asynchrone et non uniforme.

Les problèmes de satisfaction de contraintes (CSP) fournissent un formalisme permettant de modéliser de nombreux problèmes, dans des domaines très variés comme l'intelligence artificielle ou les bases de données. Une instance d'un CSP consiste en un ensemble de variables sur un domaine D et un ensemble de contraintes, c'est-à-dire de relations sur ces variables restreignant les valeurs qu'elles sont autorisées à prendre, le but étant généralement de vérifier que l'on peut trouver un assignement sur les variables tel qu'aucune relation n'est enfreinte. Dans le cas où l'ensemble des relations permettant de construire les contraintes est restreint, on peut parfois obtenir une classification de la complexité. Ainsi, si les seules relations pouvant être utilisées sont booléennes, sur le domaine {0,1}, on sait par le théorème de Schaefer que ce problème est soit polynomial, soit NP-complet. Ce résultat de classification est fortement lié au pouvoir d'expression des relations, c'est-à-dire à l'ensemble des relations dont elles peuvent simuler le comportement.

Nous verrons deux approches différentes permettant de mesurer ce pouvoir d'expression. La première est liée aux propriétés de clôture des ensembles de relations et à la correspondance de Galois entre les ensembles clos de relations sur un domaine D et les ensemble clos de fonctions sur D. Dans le cas booléen, cette correspondance permet d'obtenir aisément une classification de la complexité pour certains problèmes. Pour d'autres problèmes, en revanche, une approche constructive plus classique se révèle nécessaire pour obtenir de telles classifications. Nous montrerons des classifications, pour les problèmes du comptage et de la recherche locale, obtenues par ces deux méthodes.

La théorie des réseaux est née à la fin du 19ème siècle, suite aux travaux de Minkowski introduisant la « théorie des nombres », travaux qui déplaçaient des questions sur les formes quadratiques vers un contexte propice à l'intuition. Les contributions de cette théorie sont abondantes en mathématiques, mais aussi en informatique, particulièrement depuis le début des années 80. En effet, en 1982, Lenstra, Lenstra et Lovasz proposèrent un algorithme (LLL) dont l'emploi fut très fructueux dans des domaines aussi bien théoriques que pratiques (programmation linéaire en nombres entiers, cryptanalyse). Il est remarquable que cet algorithme, très utilisé en pratique, est assez mal compris : les méthodes classiques d'analyse d'algorithmes se heurtent à sa structure trop complexe.

Par exemple, sa complexité dans le pire des cas en dimension 3 n'est pas connue avec précision. Après une présentation assez générale du domaine, j'évoquerai plusieurs notions de réduction dans les réseaux, puis je détaillerai l'analyse du pire cas de LLL en dimension 2.

Dans leur longue série d'articles sur les mineurs de graphes, Robertson et Seymour on défini une nouvelle classe de décompositions des graphes -- les décompositions en branches – pour obtenir une obstruction aux décompositions arborescente. Cette obstruction a permis à Seymour et Thomas, en calculant exactement la largeur de branches des graphes planaires, de donner la meilleure approximation de la largeur arborescente des graphes planaires.

Je montrerai comment unifier ces deux types de décompositions à l'aide d'un nouvel objet combinatoire: les matriochkas. Ces matriochkas permettent de mieux comprendre les liens mais aussi les différences entre les décompositions arborescentes et les décompositions en branches. En les utilisant, il est aussi possible de transférer des résultats d'une des décompositions à l'autre. Je présenterai une nouvelle démonstration du fait que la largeur arborescente d'un graphe planaire et celle de son dual diffèrent au plus d'un, démonstration que j'ai obtenue de cette façon.

Le but de ces séances est de présenter une sélection de questions relatives aux fonctions ou aux formules booléennes aléatoires: énumération de classes de fonctions booléennes, avec les outils pour les résoudre (dûs à Drmota), différentes manières de définir une loi de probabilité sur l'ensemble des fonctions booléennes, notion de complexité d'une fonction booléenne, liée à sa représentation, et lien avec sa probabilité.

En cherchant à implanter les automates cellulaires dans le plan hyperbolique, l'auteur a mis au point une méthode d'étude des pavages de cet espace permettant d'y parvenir. Un intérêt de cette méthode est qu'elle met en relation des notions de géométrie élémentaire, de théorie élémentaire des nombres et de théorie des langages.

Après un bref rappel sur la notion de pavage, on étudiera tout d'abord la « pentagrille », c'est-à-dire le pavage engendré par le pentagone rectangle régulier. On en profitera pour présenter la méthode du découpage et les avantages que l'on peut en tirer. On montrera ensuite que cela s'étend à d'autres pavages du plan hyperbolique (il y en a une infinité), ainsi qu'au pavage de l'espace hyperbolique de dimension 3 par le dodécaèdre rectangle régulier et au pavage de l'espace hyperbolique de dimension 4 par le polytope régulier rectangle à 120 facettes.

La « promenade » se terminera par une visite des automates cellulaires du plan hyperbolique qui résolvent SAT en temps polynomial et par une visite de deux automates cellulaires universels, un dans la pentagrille du plan hyperbolique, l'autre dans le pavage dodécaédral de l'espace hyperbolique de dimension 3.

Christophe Cérin, nouveau professeur au LIPN, nous présentera ses thématiques de recherche en deux exposés.

Le problème de couplage est un problème d'optimisation difficile. Nous faisons une analyse de la performance en moyenne de l'algorithme glouton qui présente l'avantage de donner rapidement un couplage maximal (généralement non maximum): pour ce faire nous utilisons une fonction génératrice bivariée utilisée par Martin Dyer, Alan Frieze et Boris Pittel pour déterminer la moyenne et la variance de la variable aléatoire définie par le nombre d'arête du couplage si le graphe est un arbre. Dans notre cas nous déterminons la moyenne et la variance du variable aléatoire lorsque l'entrée de l'algorithme est choisie uniformément parmi les composantes-(n,n+L).

Le problème consiste à affecter plusieurs types de locomotives en considérant les besoins de puissance des trains, la maintenance des locomotives, la compatibilité des locomotives entre elles et avec les voies. La méthode de résolution utilise la génération de colonnes, la programmation dynamique, des plans de coupes, un branch and bound...

Soutenance à mi-parcours de sa thèse effectuée au sein de la DR&T - SNCF (dans le cadre d'une bourse CIFRE)

Les extraits de sa thèse présentés parlent de la convergence : cette propriété assure que, quel que soit l'état de départ et quel que soit l'enchaînement des actions, le système atteindra toujours (avec probabilité 1) un ensemble donné d'états d'arrivée en un nombre fini d'actions (auto-stabilisation).

En approximation polynomiale au pire des cas, on cherche des algorithmes rapides (de complexité polynomiale) et efficaces, c'est-à-dire que la solution fournie doit assurer un rapport constant à l'optimum (ex. pour un problème de maximisation, la valeur approchée vaut au moins 10%, 60% ou encore 90% de la valeur optimale, quelle que soit l'instance traitée). Dans cet exposé, on ouvre l'évaluation des algorithmes au rapport différentiel, mesure d'évaluation qui ne cherche plus à situer la solution approchée par rapport à la seule valeur optimale, mais sur l'intervalle [valeur d'une pire solution, valeur optimale] : en différentiel, on dira par exemple qu'une solution est à mi-chemin entre les valeurs d'une pire et d'une meilleure solution.

Dans un premier temps, on s'intéressera à des formes de solution particulières : plus précisément, on se restreindra aux optima locaux, pour une structure de voisinage donnée, se posant alors la question : quels sont les problèmes dont tous les optima locaux constituent de bonnes solutions au regard de l'approximation au pire des cas ?

Ensuite, c'est au contraire le problème que l'on figera, en proposant un algorithme dédié au problème du voyageur de commerce bivalué : on présentera un algorithme qui offre une approximation différentielle à 3/4.

La technologie du code mobile est prometteuse dans de nombreux domaines d'applications, en particulier dans le domaine de l'informatique nomade. La mobilité et le nouveau mode de communication utilisé dans les réseaux mobiles ad hoc engendrent des problèmes propres à l'environnement mobile. Cet exposé traite des possibilités d'utilisation du code mobile dans un controle centralisé des réseaux ad hoc.

I present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. This framework is a simplification of the the ``Generalized Rush Hour Logic'' developed by Flake and Baum.

I use this model of computation to show the PSPACE-hardness of several puzzles and motion-planning problems, including sliding-block puzzles, sliding-coin puzzles, plank puzzles, hinged polygon dissections, Sokoban (strengthening an earlier result), and Rush Hour (simplifying an earlier result).

I show where these problems fit in the complexity hierarchy of puzzles and games, and outline how variants of nondeterministic constraint logic could potentially be used to address harder problems, such as go with superko.

Jean-Frédéric Myoupo est candidat professeur au LIPN cette année.

Je présenterai mes travaux effectués jusqu'à présent, qui se constituent de deux axes principaux, à savoir: attribution de codes pour des réseaux mobiles ad-hoc sans-fil, dans le cadre du protocole CDMA (Code Division Multiple Access) et engendrement de nombres premiers de façon distribuée.

Le CDMA est un protocole qui donne l'accès simultané a tout le spectrum de fréquence sans occasioner pour cela des collisions. Notre travail consiste à minimiser le nombre de codes attribués à toutes les stations (processeur, nœuds) du réseaux mobile ad-hoc sans-fil, ainsi permettant un meilleur profit du spectre de fréquence.

Le crible de la roue est un algorithme d'engendrement de nombres premiers pour un intervalle allant de 2 à N, nous avons distribué cet algorithme obtenant un facteur d'accéleration de 2 par rapport aux simulations séquentielles. Autrement une nouvelle proposition de cette distribution sera abordé.

Finalement un nouveau algorithme distribué d'engendrement de nombres premiers sera exposé, cet algorithme est basé sur une technique d'ordonnancement par multiples réversions d'arêtes (acronyme anglais: SMER), qui est une généralisation de l'ordonnancement par réversions d'arêtes (connu en anglais par SER). Ces techniques, comme leurs noms l'indiquent, sont applicables, par exemple, pour la gestion de resources partagées entre plusieurs processus, ces processus étant représentés par les nœuds d'un graphe acyclique.

Cet exposé se place dans l'étude des modèles du calcul continus. Nous y montrons que la géométrie plane permet de calculer. Nous définissons un calcul géométrique et utilisons la continuité de l'espace et du temps pour stocker de l'information au point de provoquer des accumulations et atteindre une autre puissance de calcul.

Dans le monde des automates cellulaires, on parle souvent de particules ou de signaux (qui forment des lignes discrètes sur les diagrammes espace-temps) tant, pour analyser une dynamique que, pour concevoir des automates cellulaires particuliers. Le point de départ de nos travaux est d'envisager des versions continues de ces signaux. Nous définissons un modèle de calcul continu, les machines à signaux, qui engendre des figures géométriques suivant des règles strictes. Ce modèle peut se comprendre comme une extension continue des automates cellulaires.

L'exposé commence par une présentation des automates cellulaires et la mise en avant d'exemples de particules/signaux tirés de la littérature. De là, nous abstrayons le modèle, les machines à signaux.

Dans un premier temps, nous montrons comment tout calcul au sens de Turing (par la simulation de tout automate à deux compteurs) peut y être mené. Nous montrons également comment modifier une machine de manière à réaliser des transformations géométriques (translations, homothéties) sur les diagrammes engendrés. Nous construisons également les itérations automatiques de ces constructions de manière à contracter le calcul à une bande (espace borné) puis, à un triangle (temps également borné).

Dans un second temps, nous nous intéressons aux points d'accumulation. Nous montrons que la prévision de l'apparition d'une accumulation est indécidable. Ce problème est même Σ_2,0-complet (hiérarchie arithmétique), en construisant pour tout automate à deux compteurs une machine à signaux et une configuration initiale simulant l'automate pour toutes les valeurs possibles.

Avec quelques exemples, nous montrons l'existence d'accumulations, non pas en un point, mais sur un segment ou un Cantor.

Nous introduisons alors une restriction sur les règles assurant qu'il ne peut y avoir que des accumulations sur des points isolés. Il est toujours possible de mener tout calcul malgré cette contrainte. Par ailleurs, les accumulations sont « propres », ce qui permet d'avoir une capacité de calcul semblables à celles sur les ordinaux ou de l'utilisation d'un « trou noir » (infinité d'itérations pendant une durée finie bornée).

L'exposé se conclut par la présentation de perspectives de recherches.

Cet exposé fait un tour d'horizon de quelques problèmes de localicsation et placement sur lesquels j'ai travaillé.

Certains de ces problèmes se posent naturellement comme des programmes quadratiques en variables 0-1, d'autres comme des programmes linéaires mixtes.

Je présenterai les différentes approches que nous avons appliquées pour améliorer la formulation ou la résolution de ces problèmes, ainsi qu'un certain nombre de perspectives.

We consider a model of particles jumping on a row of cells, called in physics the one dimensional totally asymmetric exclusion process with open boundaries (TASEP). From the point of view of combinatorics a remarkable feature of this Markov chain is that Catalan numbers are involved in several entries of its stationary distribution. We give a combinatorial interpretation and a simple proof of these observations in the simplest case where the particles enter, jump and exit with the same rate. Then we extend our approach to general rates.

This is a joint work with Gilles Schaeffer, École polytechnique

Sous-titre: « Du rififi chez les philosophes. »

Cet exposé présentera le travail effectué au cours de ma thèse, dans le cadre de la vérification de systèmes distribués en anneaux de taille paramétrée. Je me suis plus précisément intéressée à des méthodes de preuve de convergence, d'une part dans le cas où le système effectue des actions déterministes (avec une méthode automatisée), et d'autre part dans le cas où les actions sont probabilistes. Pour le cas probabiliste, je m'arrêterai plus longuement sur l'algorithme du dîner des philosophes probabiliste, dont nous avons prouvé la convergence sans hypothèse d'équité sur les philosophes, et donné une borne inférieure du temps moyen de convergence.

Un système informatique de contrôle temps-reel est chargé de l'acquisition de mesures, le calcul et l'émission de commandes ainsi que de la gestion des événements d'alarme. On parle d'informatique temps-reel lorsque ces activités appelés tâches sont contraintes a s'exécuter dans un laps de temps limité. L'ordonnancement de ces tâches constitue un problème complexe. Pour modéliser les contraintes de temps, une date critique (deadline) est associée a chaque tâche. Si cela est possible, l'exécutif doit achever l'exécution de chaque tache avant sa date critique ; sinon, il doit minimiser l'impact du dépassement sur le système contrôlé. Nous présentons une solution à l'ordonnancement de tâches aléatoires (apériodiques : qui peuvent apparaître sur n'importe quel site et à n'importe quel moment) dans un système reparti, un système constitué de plusieurs sites éloignés, relies entre eux par un réseau de communication avec couplage lâche. L'approche proposée se décompose en deux étapes:

1. l'ordonnancement local: un algorithme d'ordonnancement monoprocesseur capable de décider en ligne s'il peut garantir l'exécution d'une tâche avant sa deadline.
2. l'ordonnancement reparti: dans le cas d'un rejet d'une tâche, une coopération entre les différents sites du système est invoquée pour permettre l'exécution des taches écartées.

Le choix d'un site d'exécution pour une tâche non garantie localement est basé sur les surplus échangés entres les sites plus les distances les plus courtes en terme de temps.

On part d'un ensemble de structures finies de taille n (nombre d'éléments du domaine). Soit P une propriété sur ces structures. On effectue un tirage uniforme d'une structure et on calcule la probabilité qu'elle vérifie P. Quand cette probabilité admet une limite quand n tend vers l'infini, celle-ci est appelée probabilité asymptotique de P. Une logique L admet une loi 0-1 quand toute propriété P exprimable dans L a une probabilité asymptotique égale à 0 ou 1.

Glebskii, Kogan, Liogonki et Talanov en 1969 et indépendamment Fagin en 1976 ont montré que la logique du premier ordre admet une loi 0-1.

En revanche, il est facile de vérifier que la logique du second ordre n'admet pas de loi 0-1 car elle permet d'exprimer des propriétés telles que PARITÉ, le nombre d'éléments du domaine est pair, qui fournissent des contre-exemples de loi 0-1. Il est cependant possible de déterminer des lois 0-1 pour des fragments de cette logique qui demeurent assez expressifs (capturant des propriétés NP-complètes).

Kolaitis et Vardi ont entamé en 1987 une classification des fragments de la logique du second ordre selon les lois 0-1.

Dans cette exposé nous verrons les différentes propriétés qui ont été proposées comme contre-exemples de loi 0-1. Nous nous intéresserons en particulier à la propriété de noyau qui a, d'une part, permis d'achever cette classification et, d'autre part, donné une caractérisation unique des fragments du second ordre sans loi 0-1.

Je montrerai une version distribuée du crible de la roue, ainsi que des mesures expérimentales du temps d'exécution. Je montrerai aussi une nouvelle méthode pour générer des nombres premiers en distribué utilisant une technique dénommée « Scheduling Multiple Edge Reverse ».

Soit G = (V,E) un graphe non orienté avec une capacité (ou poids) positive et entière u_e sur chaque arête e de E et soit une liste de K paires de sommets {s_k,t_k}, k = 1,...,K. On note n = |V| et m = |E|. On associe un flot à chaque paire de sommets {s_k, t_k}. Le problème du multiflot maximal en nombres entiers consiste à maximiser la somme des valeurs des flots entiers F_k routés de s_k à t_k, en respectant les contraintes de capacité et de conservation de flot. Le problème de la s_k-t_k multicoupe minimale consiste à trouver un ensemble d'arêtes de poids minimal dont le retrait coupe chaque chaîne menant de s_k à t_k, k = 1,...,K. Ces deux problèmes sont connus pour être NP-difficiles et Max SNP-difficiles pour K>=3 dans des graphes quelconques.

Nous nous intéressons à la résolution de ces deux problèmes dans des structures particulières, que sont les arbres et les anneaux. Dans les arbres, nous montrons notamment que ces deux problèmes sont polynomiaux si l'arbre est orienté. Nous proposons également un algorithme polynomial en O(n2) avec capacité uniforme. Nous proposons également un algorithme polynomial en O(min(K*n2, n3)) permettant de résoudre le problème de multicoupes minimales dans les anneaux. Ces algorithmes s'appliquent dans des anneaux sur lesquels nous avons effectué plusieurs règles de réduction. Ces règles permettent de transformer l'anneau d'origine en un anneau orienté comportant une source et/ou un puits en chaque sommet.

Ce travail était en collaboration avec Siqun Wang

In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(|V|) time complexity and O(|V|.|E|) message complexity.