Moteurs de recherche sur internet

En collaboration avec le Professeur P. Van Dooren

Les méthodes de recherche sur internet permettent de retrouver de l'information dans des bases de données immenses. Plusieurs méthodes novatrices pour conduire de telles recherches ont été proposées récemment. Ces méthodes exploitent la structure de graphe du réseau internet pour identifier les sites les plus pertinents. Ce mémoire analysera certaines de ces méthodes et développera des variantes. Le mémoire fait suite à celui réalisé en 2000-2001 par Maureen Heymans.

Référence:

Authoritative Sources in a Hyperlinked Environment, Jon Kleinberg, 1997.

Complexité de Kolmogorov

La complexité algorithmique d'un problème donne une estimation asymptotique du temps calcul nécessaire pour résoudre le problème au moyen d'un algorithme. La complexité « à la Kolmogorov » est, elle, une complexité descriptionnelle ou informationnelle. La complexité de Kolmogorov d'un objet est donnée par la longueur du plus petit énoncé qui permet de décrire l'objet; c'est une mesure de la quantité d'information inhérente à l'objet. Ainsi, par exemple, une séquence aléatoire est de complexité maximale puisque réductible à aucune autre description qu'elle-même.

Dans le cadre de ce mémoire on décrira les bases fondamentales de la théorie de la complexité de Kolmogorov.

Graphe de connexion d'un réseau de téléphone

En collaboration avec Mobistar (Bruxelles)

Un grand nombre d'entreprises s'aperçoivent aujourd'hui que les données qu'elles ont enregistrées dans leur secteur d'activité sont d'une telle ampleur qu'elles ne permettent plus de dégager l'information pertinente pour la prise de décision et la gestion stratégique. Le volume submerge la qualité autrefois apparente.

De nouvelles méthodes sont actuellement mises au point pour faciliter l'extraction d'information au départ de grandes bases de données. Ces méthodes font appel à des techniques de reconnaissance de formes, de classification, d'apprentissage, d'agrégation, etc.

Dans le cadre de ce mémoire, on s'intéressera à l'extraction d'information d'un graphe d'un réseau de téléphonie. Chaque numéro de téléphone est représenté par un sommet du graphe et deux sommets sont liés entre eux par une arête s'il y a eu par le passé une communication entre les numéros correspondants. On appliquera à ce graphe des méthodes récentes d'extraction d'information.

Le mémoire sera réalisé sur des données du réseau Mobistar en Belgique. Il sera réalisé en partie au sein de l'entreprise Mobistar à Bruxelles.

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écéssaires. Généralement, les dynamiques continues correspondant aux différents modes peuvent êre 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écement, 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 rapidemment 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.
Perturbed Turing Machines and Hybrid Systems.
Preprint, 2001.

[Fr] M. Franzle.
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.

[GHJ] V. Gupta, T.A. Henzinger, and R. Jagadeesan.
Robust timed automata
HART 97: Hybrid and Real-time Systems, LNCS 1201, Springer-Verlag, 331--345, 1997.

[HKPV] T.A. Henzinger, P.W. Kopke, A. Puri, and P. Varaiya.
What's decidable about hybrid automata?
27th Annual Symposium on Theory of Computing, ACM Press, 373--382, 1995.

[Pu] A. Puri.
Dynamical properties of timed automata, Discrete Systems: Theory and Applications, 2000.

[H] T.A. Henzinger.
The theory of hybrid automata.
Proceedings of the 11th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, 278--292, 1996.

[HR] T.A. Henzinger and J.-F. Raskin.
Robust Undecidability of Timed and Hybrid Systems
Proceedings of HSCC'00, LNCS 1790, 145--159, 2000.

Stratégies automates pour le dilemme itéré du prisonnier

En collaboration avec le Professeur J. 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.

Dans un premier temps, on analysera la démonstration de NP-complétude du problème suivant: Pour une stratégie automate et un entier k donnés, on cherche la stratégie automate de taille bornée par k qui fournit le meilleur gain asymptotique.

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

Indécidabilité pour des systèmes dynamiques simples

On prend un entier positif quelconque. S'il est pair on le divise par deux, s'il est impair on le multiplie par trois et on ajoute 1, et on recommence. Par exemple, au départ de l'entier 13 on obtient: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,... D'après la conjecture de Collatz (connue aussi sous le nom de "conjecture 3n+1"), quel que soit le nombre de départ on fini toujours par tomber sur le cycle 2, 1, 4, 2, 1, .... Cette conjecture est indémontrée depuis un demi siècle. Cet example illustre la complexité potentielle de systèmes dynamiques simples.

En liaison avec la conjecture de Collatz, John H.Conway a montré qu'une classe particulière de fonctions qui englobe la fonction de Collatz possède la puissance d'expressivité des machines de Turing. Pour cette classe de fonctions, le problème de déterminer si les itérées successives d'un point initial x(0) par une fonction de la classe tombe sur un cycle est indécidable. Il n'existe pas d'algorithme qui permet de répondre à toutes les instances de ce problème.

Dans ce mémoire, on analysera la complexité algorithmique (décidabilité ou NP-complétude) d'un problème relatif aux systèmes dynamiques.

Référence:

A survey of computational complexity results in systems and control, Vincent D. Blondel and John N. Tsitsiklis, Automatica, 36:9, pp. 1249-1274, 2000.

Théorie de l'apprentissage

L. Valiant a jeté en 1984 les premières bases d'une théorie mathématique de l'apprentissage. La théorie permet de décrire avec précision les concepts qui peuvent être appris au moyen d'un algorithme. L'article initial a donné lieu depuis lors à de nombreux développements. Dans ce mémoire on s'attachera à une description des bases de cette théorie.

Références:

A theory of the learnable, Valiant, 1984.

Computational Learning Theory, M. Anthony and N. Biggs, 1992.

Décidabilité de problèmes matriciels

En collaboration avec le Professeur C. Choffrut (Laboratoire d'Informatique, Université Paris 6).

Soient A_0 et A_1 deux matrices carrées avec des entrées entières. On considère l'ensemble P des matrices obtenues en effectuant des produits de A_0 et de A_1. Certains problèmes liés à la famille P sont décidables tandis que d'autres ne le sont pas. Ainsi la question ``P est fini?'' est décidable tandis que ``0 appartient à P?" ne l'est pas. Dans ce mémoire, on s'attachera à la description de l'algorithme qui permet de décider ``P est fini?'' et on analysera des résultas récent de décidabilité pour des matrices de petites dimensions.

Références:

La finitude des repr\'esentations lin\'eaires des semi-groupes est d\'ecidable, G. Jacob, Journal of Algebra, 1978.

Unsolvability in $3 \times 3$ matrices, M. Paterson, Studies in Applied Math., 1970.

When is a pair of matrices mortal?, V. Blondel, J. Tsitsiklis, Information Processing Letters, 1997.

Some open problems in combinatorics of words and related areas, J. Karhumäki, TUCS Technical report, 2000.