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/