Vincent BLONDEL
TFE pour 2004-2005

Cette page se trouve à l'adresse: http://www.inma.ucl.ac.be/~blondel/tfe2004.html


Graphes, systèmes dynamiques et mathématiques discrètes

Nous proposons plusieurs sujets de mémoire à l'interface entre la théorie des graphes, la théorie des systèmes dynamiques et les mathématiques discrètes. Pour plus d'informations, prendre contact directement.


Comment visualiser de très grands graphes?

La visualisation de très grand graphes et réseaux tels que ceux du web ou d'un réseau de mobilophonie (de l'ordre du million ou du 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 introduites récemment, on en proposera d'éventuelles extensions et on mettra en oeuvre un algorithme de visualisation. Les méthodes proposées pourraient être testées sur le graphe du réseau de mobilophonie belge Mobistar enregistré durant le mois de septembre 2003.

 


Codes, séquences binaires et rayon spectral conjoint

On s'intéressera dans ce mémoire à un problème en théorie des codes qui fait apparaitre la notion récemment introduite de rayon spectral conjoint d'un ensemble de matrices. Le problème est celui de la recherche du nombre maximum de séquences binaires de longueur donnée dont les différences évitent un ensemble de motifs interdits. C'est un problème simple de formulation, élégant et qui pourrait mener à des développement nouveaux intéressants.

La différence entre deux séquences binaires de longueur n est une séquence de n caractères pris dans {-1, 0, +1}. Etant donné un ensemble fini D de séquences interdites de {-1, 0, +1}, le plus grand nombre de séquences binaires de longueur n dont les différences n'incluent aucun élément de D est donné par d(n). Les auteurs de l'article [1] on démontré que la limite d(n)^(1/n) existe et peut être caractérisée au moyen du rayon spectral conjoint de matrices construites au départ de l'ensemble D.

Le rayon spectral conjoint de matrices est en général NP-difficile a calculer [2]. Les matrices construites dans [1] ont toutefois une structure particulière pour laquelle il n'est pas exclu de trouver des algorithmes polynomiaux. Dans le cadre de ce mémoire on analysera d'abord le degré de généralité de l'algorithme proposé dans [1] et on analysera ensuite plus finement la complexité algorithmique du problème proposé. On tentera en particulier de déterminer si le problème est ou n'est pas NP-difficile.

Références.
[1] B. Moision, A. Orlitsky, and P. Siegel, On codes that avoid specified differences, IEEE Transactions on Information Theory, 47:1, pp. 433-442. Disponible au départ de http://ece.ucsd.edu/~alon/pub.html
[2] J. Tsitsiklis, V. Blondel, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard -- when not impossible -- to compute and to approximate, Mathematics of Control, Signals, and Systems, 10, pp. 31-40, 1997. Disponible au départ de http://www.inma.ucl.ac.be/~blondel/publications/