Figure: Internet Mapping Project (Lucent/Bell Labs).
Moteurs de recherche sur internet
En collaboration avec le Professeur Paul Van Dooren
Les méthodes de recherche sur internet permettent de retrouver de l'information dans des bases de données immenses (le web actuel compte plus d'un milliard de pages). Plusieurs méthodes novatrices pour conduire de telles recherches ont été proposées récemment. Ces méthodes exploitent la structure de graphe du web pour identifier les sites les plus pertinents. Nous proposons plusieurs thèmes de mémoire dans cette thématique.
Graphes et identification de communautés SMS
En collaboration avec le Professeur Paul Van Dooren et l'opérateur de mobilophonie Mobistar (Bruxelles).
L'opérateur de mobilophonie Mobistar envisage l'introduction prochaine du successeur du SMS: le MMS (Multimedia Message System) qui permettra la transmission de texte mais aussi d'images et de son. Dans ce contexte, la société souhaite dégager une meilleure compréhension de la structure actuelle des échanges de SMS.
Dans ce mémoire, on s'intéressera à l'extraction d'information du graphe SMS. Dans le graphe SMS chaque numéro de téléphone est représenté par un sommet (pour Mobistar il y en a de l'ordre de 2 millions) et deux sommets sont liés entre eux par une arête s'il y a eu par le passé un échange de SMS entre les numéros correspondants. Chaque numéro actif envoie en moyenne 50 SMS par mois. Nous souhaitons identifier dans ce graphe des communautés de sommets fortement connectés entre eux. Pour ce faire nous appliquerons une méthode d'extraction d'information que nous avons introduite récemment et qui démontré son efficacité pour l'extraction automatique de synonymes dans un dictionnaire. Le mémoire sera réalisé sur des données du réseau Mobistar en Belgique.
Référence: Vincent D. Blondel, Pierre P. Sennelart, Automatic extraction of synonyms in a dictionary. To appear in the Proceedings of the SIAM Workshop on Text Mining, Arlington (Texas, USA), 2002. Cet article peut-Ítre obtenu au départ http://www.inma.ucl.ac.be/~blondel/publications/
Visualisation de grands graphes
La visualisation de grand graphes tels que celui du web (de l'ordre d'un milliard de sommets) pose des problèmes
théoriques et d'implémentation nouveaux. Dans le cadre de ce mémoire on analysera certaines
méthodes de visualisation, on en proposera d'éventuelles extensions et on mettra en oeuvre un algorithme de
visualisation. L'algorithme choisi sera utilisé pour visualiser le graphe du réseau de
téléphone du l'UCL (de l'ordre de quatre milles sommets).
Figure: Internet Mapping Project (Lucent/Bell Labs).
Référence: Giuseppe Di Battista, Peter Eades Roberto Tamassia, Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 2001.
Graphes petit monde et fouille de textes
Comme le monde est petit!
Dans le graphe des relations personnelles, chaque personne est représentée par un sommet et deux
personnes sont liées par une arÍte si elle se connaissent personnellement. Des expériences sociologiques
menées dans les années 1960 aux Etats-Unis ont montré que deux personnes prises
au hasard ne sont jamais très éloignées l'une de l'autre. Il ne faut souvent pas plus de 4
intermédiaires pour passer de l'une à l'autre; on dit que le graphe est un graphe ``petit monde". Une
observation analogue peut Ítre faite pour le graphe de Hollywood (deux acteurs sont connectés par une arÍte s'ils ont
joués dans un mÍme film) ou pour le graphe du web (deux pages sont connectées par une arÍte si elles sont
liées par un hyperlien). Dans le graphe du web on estime que le nombre maximum de clics nécessaires pour
passer d'une page quelconque à une autre est d'au plus une petite vingtaine.
Un graphe petit monde possède un faible diamètre, il est peu dense globalement mais fort dense localement. Des quantités caractéristiques des graphes ont été proposées pour décrire dans quelle mesure un graphe s'approche du modèle de graphe petit monde. Nous nous intéresserons dans ce travail au calcul de ces quantités caractéristiques pour des graphes construits au départ de textes de littérature. En particulier, nous tenterons de dégager si certaines de ces quantités restent constantes pour un auteur donné.
Automates quantiques
Le calcul par des systèmes mettant en oeuvre des processus physiques quantiques font l'objet d'une recherche intensive depuis quelques
années. Cet intérêt provient en partie de la découverte récente d'algorithmes quantiques de
factorisation qui tournent en temps polynomial.
Stratégies automates pour le dilemme itéré du
prisonnier
En collaboration avec le Professeur Jean
Mairesse (Laboratoire d'Informatique, Université Paris 6).
Le
dilemme du prisonnier est un paradoxe bien connu en théorie des jeux.
Deux suspects sont arrêtés. Ils sont interrogés séparément et ne
peuvent pas communiquer entre eux. Les règles sont les suivantes. Si
l'un avoue et pas l'autre, celui qui avoue est libéré et l'autre est
condamné à 5 ans de prison; si aucun n'avoue, il sont condamnés tous
les deux à 2 ans de prison; si les deux avouent, ils sont condamnés
tous les deux à 4 ans de prison. On constate facilement qu'un suspect a
toujours avantage à avouer. Quel que soit le choix de l'autre suspect,
cette solution génère pour lui une peine inférieure à celle obtenue
en
n'avouant pas. Pourtant, si les deux suspects avouent tous les deux,
ils sont condamnés à 4 ans alors qu'ils peuvent n'obtenir que 2 ans
s'ils se taisent.
Les comportements optimaux sont potentiellement plus complexes lorsque
le "jeux" est itéré avec les mêmes partenaires. Cette situation se
présente par exemple lorsque deux joueurs doivent chaque jour choisir
de partager ou de se disputer des ressources limitées. Dans une telle
situation, les joueurs peuvent, par le choix d'une stratégie de jeux,
adapter leur comportement en fonction du comportement passé de l'autre
joueur. Dans le cadre de ce travail, on considèrera des aspects de
complexité algorithmique liés à des jeux itérés dont les stratégies
sont modélisées au moyen d'automates finis.
Dans un premier temps, on montrera que
si un des joueurs a une stratégie automate de taille k connue, alors
la stratégie optimale de l'autre joueur est encore une stratégie automate
de taille bornée par k, calculable
en temps polynomial. Pour cela, on construira un automate à multiplicités
sur le semi-anneau max-plus et on utilisera la théorie spectrale dans ce semi-anneau.
Ensuite on étudiera l'article [2] où est démontré
la NP-complétude du problème suivant.
Si le premier joueur a une stratégie automate de taille k connue,
déterminer pour le second joueur la stratégie automate de taille bornée par k optimale.
Dans un deuxième temps, on s'intéressera au dilemme itéré du prisonnier
dans le plan. Dans cette version du dilemme itéré, les joueurs sont
répartis dans le plan et jouent avec leurs voisins respectifs. A chaque
itération, les joueurs adoptent la stratégie de leur voisin si elle se
présente comme localement supérieure. On cherchera à montrer que, dans cette
situation, la question de déterminer si pour un champ de stratégies
initiales données une stratégie est finalement dominante est un
problème indécidable.
[1] E. Ben-Porath. The complexity of computing a best response automaton in repeated
games with mixed strategies. Games Econ. Behav., 2(1):1--12, 1990.
[2] C. Papadimitriou. On players with a bounded number of states. Games Econ. Behav., 4(1):122--131, 1992.
[3] A. Rubinstein. Finite automata play the repeated prisoner's dilemma. Journal of Economic Theory, 39:83--96, 1986.
Systèmes hybrides perturbés
En collaboration avec le Professeur J.-F.
Raskin (ULB)
Un système hybride est un système qui combine des dynamiques
continues avec une dynamique globale discrète. Les dynamiques continues
correspondent aux différents modes de fonctionnement du système
et la dynamique discrète détermine les changements discrets
entre ces différentes dynamiques. De tels systèmes
sont largement utilisés pour le contrôle de processus industriels
comme par exemple le monitoring de centrales nucléaires, le contrôle
de systèmes de transport comme par exemple les métros automatisés,
l'aide au pilotage d'avions, etc.
Vu la complexité intrinsèque de tels systèmes,
des outils de modélisation mathématiques sont nécessaires.
Généralement, les dynamiques continues correspondant aux
différents modes peuvent être modélisées à
l'aide de systèmes linéaires. Par contre, les dynamiques
discrètes sont naturellement modélisées à l'aide
d'automates finis. Récemment, la classe des automates hybrides a
été proposée comme un formalisme qui permet de combiner
les deux aspects : les dynamiques continues et l'évolution discrète
entre celles-ci. Chaque location d'un automate hybride contient la
description d'une dynamique linéaire (aspect continu) et les passages
d'un mode à un autre dans le système sont modélisés
par les transitions que l'automate peut effectuer entre ses différentes
locations.
Les systèmes hybrides sont souvent utilisés dans des situations
critiques (monitoring d'une centrale nucléaire ou contrôle
de systèmes de transport par exemple). Les erreurs de conception
de tels systèmes ne sont donc pas acceptables. C'est pourquoi des
méthodes d'analyses automatiques des modèles de systèmes
hybrides ont été étudiées. Malheureusement,
il est rapidement apparu [HKPV] qu'un grand nombre de questions naturelles
relatives aux automates hybrides (telle que par exemple la question de
savoir si le système évite un ensemble d'états prohibés
donnés) sont indécidables (il n'existe pas d'algorithme qui
permet de répondre à toutes les instances de ce problème).
Ces résultats d'indécidabilité réduisent l'intérêt
pratique de ces modèles.
En pratique cependant la dynamique d'un système n'est jamais
donné de manière exacte [GHJ]. Plusieurs chercheurs ont récemment
tenté d'analyser si le caractère indécidable des dynamiques
est préservé lorsque le système est soumis à
des perturbations. Des résultats obtenus tout récemment semblent
apporter une réponse nuancée. En particulier, dans
[AB] sont présentés des arguments en faveur d'un basculement
vers la décidabilité lorsque le système est soumis
à perturbation, par contre dans [HR] des arguments sont présentés
dans le sens inverse. Les deux articles introduisent deux formalisations
différentes de la notion de perturbation.
Dans ce mémoire on étudiera dans un premier temps les
deux articles [AB] et [HR] en détail. Les deux formalisations de
la notion de perturbation seront comparées. Dans un deuxième
temps, on tentera de dégager les propriétés qui distinguent
les modèles de perturbations qui mènent à la décidabilité,
des propriétés des modèles qui maintiennent l'indécidabilité.
Outre les deux articles mentionnés ci-dessus, on étudiera
également les deux articles suivants: [Fr] et [Pu].
Références:
[AB] A. Bouajjani and E. Asarin.
[Fr] M. Franzle.
[GHJ] V. Gupta, T.A. Henzinger, and R. Jagadeesan.
[HKPV] T.A. Henzinger, P.W. Kopke, A. Puri, and P. Varaiya.
[Pu] A. Puri.
[H] T.A. Henzinger.
[HR] T.A. Henzinger and J.-F. Raskin.
Cadre du mémoire: UCL ou université de Paris 6 (Pierre et Marie Curie).
Perturbed Turing Machines and Hybrid Systems.
Preprint, 2001.
Analysis of Hybrid Systems: An ounce of realism can save an infinity
of states
CSL'99: Computer Science Logic, LNCS 1683, Springer Verlag, 126--140,
1999.
Robust timed automata
HART 97: Hybrid and Real-time Systems, LNCS 1201, Springer-Verlag,
331--345, 1997.
What's decidable about hybrid automata?
27th Annual Symposium on Theory of Computing, ACM Press, 373--382,
1995.
Dynamical properties of timed automata, Discrete Systems: Theory and
Applications, 2000.
The theory of hybrid automata.
Proceedings of the 11th Annual Symposium on Logic in Computer Science,
IEEE Computer Society Press, 278--292, 1996.
Robust Undecidability of Timed and Hybrid Systems
Proceedings of HSCC'00, LNCS 1790, 145--159, 2000.