|
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.
|