Retour à l'index de l'IGM

École Jeunes Chercheurs
en Algorithmique et Calcul Formel

Site du CNRS


À Marne-la-Vallée du 31 mars au 4 avril 2003

Accueil
Participants
Frais d'inscription
Inscription
Historique
Programme
Hébergement
Accès

Résumés des exposés courts


Anne-Elisabeth Baert : Création de composantes complexes dans les graphes aléatoires

Nous étudierons dans cet exposé, les propriétés des composantes connexes d'un certain modèle de graphes aléatoires, le modèle $G(n,t)$ (modèle dit à temps continu), pour observer un phénomène connu sous le nom de «naissance de la composante géante». Pour obtenir les résultats présentés ici, les méthodes du modèle probabiliste $G(n,t)$, sont combinées avec des méthodes d'énumérations asymptotiques. Nous considèrerons, les $(l+1)$-composantes d'un graphe aléatoire, définies comme étant les composantes connexes ayant $l+1$ arêtes de plus que de sommets, et nous étudierons, pendant l'évolution du graphe, le nombre de créations de $(l+1)$-composantes. Nous montrerons, en particulier, que la variable aléatoire définie par le nombre de créations de $(l+1)$-composantes est concentrée autour de sa moyenne.


Abdolali Basiri : An application of LLL algorithmes in Gröbner basis

Nous présentons un algorithme transformant une base de Gröbner d'un idéal pour un ordre donné en une base de Gröbner pour un autre ordre. Cet algorithme est basé sur une version modifiée de l'algorithme LLL. La complexité théorique, dans le pire des cas, n'est pas meilleure que la complexité de l'algorithme FGLM mais on peut exprimer cette complexité en fonction de paramètres dépendant de la taille de la sortie. Ainsi lorsque les degrés de la base de Gröbner finale sont petits l'algorithme devient plus efficace. Nous présentons une première implémentation en Maple de l'algorithme. L'algorithme est restreint au cas de deux variables mais est valide aussi en dimension positive.


Heikel Batnini : Analyse par intervalles et résolution de systèmes d'équations de distance

La plupart des outils pour la résolution de CSP continus s'appuient sur des consistances locales qui encadrent l'espace solution. Lorsque celui-ci est fractionné, cela conduit à conserver des valeurs incohérentes dans l'ensemble du système. De ce fait, les techniques de filtrage local sont utilisées en combinaison avec des méthodes d'énumération, comme la bissection, afin d'isoler les sous-espaces qui contiennent potentiellement une solution. Nous proposons une nouvelle technique, nommée LDF(Local Decomposition Filtering), basée sur un couplage entre une décomposition des domaines utilisant la sémantique des contraintes et une consistance locale. LDF décompose le CSP initial en un ensemble de CSP dont les domaines sont inclus dans les domaines initiaux et permettant d'orienter la recherche de solutions. La réduction globale des domaines est au moins égale à celle de la 2B-consistance. Nous illustrons l'apport de cette technique sur différents CSP constitués d'équations de distance.


Nadia Ben Atti : Réduction des matrices de Henkel utilisant les matrices de Toeplitz

Le travail porte sur les matrices de Hankel et la généralisation des divers algorithmes concernant ces dernières. Dans une première partie l'étude est axée sur la réduction automatique des matrices de Hankel à la forme « diagonale par blocs de Hankel inférieures », ce qui donne comme corollaire une preuve simple et purement algébrique du théorème de Frobenius. La deuxième partie consiste à améliorer l'algorithme de Berlekamp- Massey, afin d'économiser le temps de calcul.


Julien Bernat : Beta-numération et fractions continues

Il s'agit de présenter une généralisation des notions d'entiers, de fractions et de fractions continues, et d'utiliser ces outils pour obtenir, via l'utilisation de pavage, un résultat qui généralise le résultat classique sur les développements en fractions continues finis.


Simon Bliudze : Evaluation de performances dans les réseaux de télécommunications sous l'angle combinatoire

We shall consider the physical layer of mobile communications, i.e. one link between a Base Station (in GSM, Node-B in UMTS) and a mobile station (User Equipment (UE) in UMTS). An important measure for the analysis of this link's performance is the probability that a bit is decoded incorrectly at reception, otherwise called Bit Error Rate (BER).

A classical formula due to Barret ('87) giving a closed form of this probability is computationaly unstable in some cases that reflect some real-life situations. Rewriting it in a such a way that it becomes stable, one obtains an expression containing certain symmetric functions.

Their decomposition in the base of Schur functions gives rise to a set of interesting combinatorial objects (combinations of Young tableaux). Those in turn can be bijectively mapped to sets of 0-1matrices that yield easier to analysis and allow to obtain stable closed form expressions for the probability in question in several cases where Barret's formula fails to do so.


Alin Bostan : Autour du principe de transposition

Le principe de transposition de Tellegen est un ensemble de règles de transformation pour des programmes "linéaires". Cependant, quoique bien connu, ce principe n'est pas employé systématiquement en pratique, peu d'implantations étant fondées dessus. Dans cet exposé, nous proposons des versions transposées explicites de la multiplication et la division des polynômes, ainsi que de nouveaux algorithmes pour l'évaluation multipoint et l'interpolation et leur transposés, améliorant d'un facteur constant la complexité des algorithmes connus. C'est un travail en collaboration avec G. Lecerf et É. Schost.


Philippe Chapdelaine : Difficulté de la recherche locale pour les CSP booléens

Pour la résolution des problèmes d'optimisation NP-difficiles, les méthodes de recherche locale, qui consistent à chercher des optima locaux, se sont révélées très efficaces et sont largement utilisées en pratique. La classe PLS regroupe les problèmes d'optimisation pour lesquels un optimum local peut être vérifié en temps polynomial. De nombreux résultats de classification existent pour des problèmes précis.

Nous nous plaçons dans le cadre du problème de satisfaisabilité générale SAT($F$), où $F$ est une famille finie de contraintes booléennes. Nous savons qu'il existe de nombreux résultats de classifications complètes de complexité pour les CSP booléens, que ce soit pour les problèmes de décision, d'optimisation ou de comptage. Nous présentons une classification similaire pour les problèmes de recherche locale.


Arnaud Dartois : Le modèle du tas de sable

Marianne Durand : Un algorithme de comptage probabiliste

On présente ici un algorithme qui permet d'évaluer le nombre d'éléments distincts d'un grand ensemble de données, en utilisant un espace mémoire très faible, et en ne lisant qu'une seule fois les données. Ce type d'algorithmes a des applications en data-mining et permet d'évaluer qualitativement des flots de données, par exemple sur des routeurs internet.


Loubna Echabbi : Protocole distribué pour commutation de circuits virtuels pour les réseaux de télécommunications avec tarification par les enchères

Le progrès dans les technologies de réseaux permet de plus en plus le partage des ressources disponibles. De plus, l'utilisation des nouveaux services diversifiés implique une croissance exponentielle en matière de demande en débit et d'exigences de qualités de service. Un des objectifs actuels est de pouvoir satisfaire les qualités de service requises par des services spécifiques. La méthode visée par notre travail est l'allocation de ressources (en terme de bande passante) pour la réservation distribuée de circuits virtuels.

Une des méthodes de résolution de collisions entre demandes de connexion en chaque noeud du réseau est l'utilisation d'enchères. Nous considérons dans un premier lieu le cas déterministe où pour chaque destination il n'y a qu'un lien de sortie possible déterminé par la fonction de routage. De fait, les enchères sur les différents liens sont indépendants et n'ont pas d'influence les uns sur les autres. Plusieurs type d'enchères peuvent être envisagés. D'une part, ils peuvent être fait sur une unité de ressource. Le prix unitaire sur un lien donné est fixé au départ à 0. Ensuite ce prix est augmenté d'une unité tant que la demande des requêtes ayant un prix unitaire plus important excède la capacité disponible sur ce lien. Les enchères sont réitèrées à chaque fois qu'il réside de la capacité non attribué sur le lien. On prouve que ce type d'enchères est à chaque étape implémentable de façon polynomial et que le résultat final des enchères peut aussi être trouvé directement de façon polynomial.

Nous confrontons aussi ce modèle à d'autres types d'enchères possibles, notamment celui où chaque requête fixe son offre et le routeur choisit celles qui seront acceptées selon des critères différents (minimiser la capacité non utilisé, maximiser le bénéfice, satisfaire une certaine équité entre les requêtes...). Les requêtes non acceptées à chaque étape augmentent leur offre jusqu'au moment où aucune requête non acceptée ne peut augmenter son offre. Nous démontrons que ce problème est par contre NP-complet à chaque étape et nous essayons de caractériser le résultat final de ces enchères.

On essaie ensuite de présenter le problème général où pour une destination donnée, plusieurs liens de sorties sont possibles à chaque routeur. Nous démontrons que dans ce cas, l'implémentation de la méthode d'enchères que l'on a proposé devient NP- complet et on essaie de caractériser aussi le résultat de ces enchères et d'implémenter une heuristique pour l'approcher.


Taoufik Faik : Sur les b-colorations d'un graphe
Contrairement à d'autres colorations (A-chromatique et Grundy coloring), un graphe peut avoir une {\em $b$-coloration} avec $p$ couleurs et une {$b$-coloration} avec $q$ couleurs, $p < q$, alors qu'il n'existe pas de {\em $b$-coloration} intermédiaire, dans le cas contraire on dit que le graphe est {\em $b$-continu}, on donne des exemples, et on montre les arbres et sont {\em $b$-continus}. On donne aussi d'autre résultats sur cet aspect de continuité.

Nazim Fatès : Que peut nous apprendre la modélisation par automates cellulaires ?

Les automates cellulaires (AC) sont souvent présentés comme des paradigmes pour l'étude de "systèmes complexes". Mais que signifie cette expression ? Nous présenterons des résultats récents relatifs à la classification des AC en montrant que le problème de classification concerne trois facettes des AC : modèles de calcul parallèle, systèmes dynamiques discrets et outil de modélisation.


Aline Gouget : Sur le critère de propagation des fonctions booléennes

Le critère de propagation est un des critères cryptographiques connus des fonctions booléennes utilisées dans les systèmes de chiffrement par blocs. Après avoir introduit ce critère, nous présenterons des constructions de fonctions booléennes vérifiant un haut degré de propagation ainsi qu'un (relativement) haut degré algébrique. Ces constructions reposent sur les propriétés des codes linéaires. Enfin, nous étudierons ce critère sur des fonctions booléennes particulières, les fonctions symétriques.


Adel Guerziz : Mots et morphismes à effacements sturmiens

Un mot infini est dit sturmien si pour tout entier naturel n, le nombre de facteurs de longueur n est égal à n+1. Un morphisme est dit sturmien s'il préserve l'ensemble des mots sturmiens. Nous proposons quelques définitions et une généralisation possible, aussi bien pour les mots que pour les morphismes sturmiens, sur un alphabet à trois lettres. Nous verrons par la suite que les mots à effacements sturmiens, qui peuvent être construits par morphisme, ont une complexité structurellement semblable à celle des mots sturmiens (de la forme n+k à partir d'un certain rang). Nous verrons aussi que les morphismes laissant stables les mots à effacements sturmiens envoient nécessairement une lettre de l'alphabet sur le mot vide. L'ensemble de ces morphismes ne peut être engendré par une famille finie de morphismes contrairement à l'ensemble des morphismes sturmiens qui est engendré par une famille de trois morphismes.


Jean-Loup Guillaume : Modélisation de graphes petit-monde

La majorité des graphes rencontrés en pratique possèdent des propriétés communes qui ont peu à peu reçu la dénomination de "petit-monde". Ces similitudes ainsi que la diversité de ces graphes ont amené un grand nombre de travaux dans divers domaines (sciences humaines, physique, informatique...) portant notamment sur la modélisation de ces graphes. L'exposé passera en revue quelques modèles introduits ces dernières années pour tenter de capturer ces propriétés et les résultats qu'on a pu en tirer.


Nicolas Gurel : Algorithme de Kedlaya : une introduction

Nous allons introduire les outils de cohomologie $p$-adique utilisés par Kedlaya dans son algorithme pour calculer le nombre de points d'une courbe hyperelliptique sur un corps fini de petite caractéristique.


Emmanuelle Lebahr : Les graphes et modules sandwich

Un graphe sandwich est un graphe compris entre deux graphes ayant le même ensemble de sommets, l'un étant un sous-graphe de l'autre. Cette notion introduite par Golumbic, Kaplan et Shamir en 1995 permet de définir les problèmes sandwich pour une propriété de graphe $\Pi$, un problème entre reconnaissance et complétion: il s'agit de décider de l'existence d'un graphe sandwich vérifiant la propriété $\Pi$. Nous verrons que des situations réelles se traduisent en problèmes sandwich, par exemple dans le domaine du séquençage de l'ADN ou de l'ordonnancement, de façon générale ce sont les situations où l'on trouve des contraintes obligatoires et d'autres optionnelles. Un module dans un graphe est un ensemble de sommet ayant chacun le même voisinage à l'extérieur de l'ensemble, c'est une notion très utile à la décomposition de graphe, nous aborderons le problème énumératif travers les modules sandwich. Enfin, nous verrons que l'on peut élargir les problèmes sandwich aux ordres en étudiant les graphes orientés transitivement.


Clémence Magnien : Modèle du tas de sable abélien : configurations récurrentes

Le modèle du tas de sable abélien a été introduit en physique par Bak, Tang et Wiesenfeld comme un modèle type du phénomène d'auto-organisation critique (self-organized criticality). Plusieurs modèles proches ont ensuite été introduits et étudiés dans plusieurs disciplines, notamment en physique, en sciences sociales et en informatique. Un ensemble de configurations particulières de ce modèle, appelées récurrentes, a la propriété de former un groupe pour l'addition. Nous présenterons certaines configurations remarquables, et nous présenterons des axes d'étude qui permettent de comprendre ces configurations.


Cyrille Martig : Autour de la réecriture d'une série rationnelle en plusieurs variables sous forme du quotient de 2 polynômes

Nous donnons d'abord un algorithme permettant de réécrire une série rationnelle en plusieurs variables non commutatives sous forme d'une expression rationnelle. Il s'appuie sur la représentation de la série par un automate fini pondéré, à partir de sa matrice de Hankel. En l'adaptant, cet algorithme permet de réécrire une série reconnaissable en plusieurs variables commutatives sous forme du quotient de 2 polynômes. Puis nous proposons des voies pour traiter certaines séries rationnelles non reconnaissables, grâce à la série échangeable non commutative associée, ou à partir des relations de dépendances linéaire existant entre les lignes (resp. les colonnes) de leur matrice de Hankel.


Ludovic Meunier : Encyclopédie Automatique des Fonctions Spéciales

Le manuel {\em Handbook of Mathematical Functions}, par M.Abramowitz et I.Stegun (1964), liste de nombreuses propriétés mathématiques et identités pour une centaine de fonctions. Toutes les formules de ce manuel, mais aussi de toutes les références actuelles sur les fonctions spéciales (comme, par exemple, le projet DLMF du NIST), ont été 1) calculées, 2) vérifiées et 3) écrites à la main.

Les récents progrès du Calcul Formel permettent d'{\em automatiser} complétement 1) le calcul et 2) la vérification de la plupart de ces formules. De cette constatation est né notre projet de créer une encyclopédie {\em automatique} des fonctions spéciales.

Dans cet exposé, nous présenterons l'état d'avancement de notre encyclopédie.


Antoine Meyer : Traces contextuelles de graphes infinis

L'une des caractéristiques importantes pour l'étude d'un graphe est le langage des mots, appelés traces, étiquetant les chemins de ce graphe. On peut donc se poser la question suivante : "étant donné une famille de langages F, quelle est la famille de graphes dont les traces sont exactement les langages de F", ou sa réciproque, "étant donné une famille de graphes G, quelle est la famille de langages formée par les traces des graphes de G".

Dans cette présentation, nous nous intéresserons plus particulièrement à des familles de graphes infinis dont les traces sont les langages de Chomsky de type 1, ou langages contextuels. Nous présenterons succinctement la famille des graphes rationnels, puis énoncerons quelques résultats concernant les graphes de transition des machines de Turing linéairement bornées.


Laurent Noé : Recherche heuristique de similitudes dans les séquences d'ADN

Je présenterai brièvement un certain nombre de méthodes heuristiques pour l'alignement local de sequences d'ADN, en m'interessant plus particulièrement à celles utilisant des k-mots (répétitions exactes de taille k).


Christophe Papazian : Hiérarchie des classes de reconnaissances sur graphes

Je présenterai une hiérarchie dense de classes de complexité sur le problème de la reconnaissance de graphes par des automates dont on quantifie la taille mémoire par une fonction dépendant de la taille de l'entrée (le graphe). On met ainsi en évidence plusieurs phénomènes intéressants : la densité de la hiérarchie et le passage incomplet de la puissance de calcul du local au global qui sont les conséquences du lien entre puissance de calcul disponible et taille du support en entrée.


Hervé Perdry : Les nombres p-adiques

Gilles Radenne : Structures d'ordres et Algèbre de Hecke à $q=0$

L'algèbre de Hecke à $q=0$, très importante en combinatoire algébrique, et liée au tri à bulle et aux ordres. Nous présenterons ce lien, avant de montrer comment on peut en déduire des structures sur des ensembles d'objets combinatoires, en donnant l'exemple des tableaux de rubans. Nous montrerons entre autre que la structure de l'algèbre de Hecke permet de déduire des résultats intéressants sur la géométrie de ces tableaux de rubans.


Guénaël Renault : Calcul efficace d'un idéal des relations entre les racines d'un polynôme

Dans cet exposé nous montrerons comment deux algorithmes de calcul d'un idéal des relations peuvent être mixés pour en obtenir un nouveau plus efficace. Ce travail est issu d'une collaboration avec A. Valibouze et S. Orange.


Chloé Rispal : Mots indexés par des ordres linéaires

Récemment, Bruyère et Carton ont défini des expressions rationnelles et des automates reconnaissant des mots indexés par des ordres linéaires. Ces mots généralisent les mots finis, infinis, bi-infinis et les mots indexés par des ordinaux. Le théorème de Kleene établissant l'équivalence entre rationnalité et reconnaissabilité a été étendu à ces ensembles de mots. On s'intéresse au problème de la complémentation d'ensembles rationnels de mots sur les ordinaux.


Olivier Ruatta : Sur une généralisation de l'interpolation de Newton

Dans cette exposé nous nous intéressons à l'interpolation algébrique multivarié. Nous commençons par donner une généralisation de l'interpolation de Lagrange. Puis nous proposons une généralisation du schéma d'interpolation de Newton dans le cadre algébrique multivarié. Nous donnons explicitement une base d'interpolation dont la spécialisation dans le univarié donne les polynômes de Newton classiques. En nous servant de l'interpolation de Lagrange, nous donnons un algorithme pour le calcul des coefficients d'un polynôme dans la base de Newton. Nous terminerons sur un problème sur les fonctions qui donnent ces coefficients.


Olivier Serre : Jeux sur des graphes finis et infinis
Dans cet exposé j'introduirai la notion de jeu à deux joueurs sur un graphe. Dans le cas des jeux sur des graphes finis munis d'une condition de Büchi, je donnerai des méthodes pour déterminer le gagnant et la stratégie. J'introduirai également la notion de condition de parité et de Muller. Enfin, j'aborderai le problème des jeux sur des graphes infinis en évoquant les problèmes algorithmiques qu'ils soulèvent.

Hervé Sibert : Entity Authentication Schemes Using Braid Word Reduction

Artin's braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced. A variety of key agreement protocols based on braids have been described, put few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements.

Pour toute information, contacter ejc2003@univ-mlv.fr.


Institut d'électronique et d'informatique Gaspard-Monge
77454 Marne-la-Vallée Cedex 2 - Tél : +33.1.60.95.75.65


http://www-igm.univ-mlv.fr/~ejc2003
ejc2003@univ-mlv.fr