Matinées
sur les
Interactions
Mathématiques & Informatique
à Montpellier
Ces matinées ont pour but de faire se rencontrer les mathématiciens et informaticiens montpellierains
autour de thèmatiques d'interaction.
Elles ont lieu de façon occasionnelle
au gré des envies et propositions de chacun,
autour de deux exposés à but pédagogique (donc très accessible par tous),
faits par des orateurs locaux ou extérieurs invités,
avec du temps prévu pour des questions et échanges d'idées.
Pour proposer un exposé, un orateur, un sujet à lancer, une question à débattre, une mise à jour...
contacter Emeric Gioan.
Vous pouvez également vous adresser en maths à Jorge Ramirez-Alfonsin.
Thématiques locales recensées
(date de janvier 2008, n'hésitez pas à signaler les mises à jour)
Prochaine séance
Sujets locaux précedemment exposés par des orateurs locaux
Exposés passés par des orateurs invités
en attente de suggestions et propositions...
Sujets locaux précedemment exposés par des orateurs locaux :
-
Richard G. Terrat.
(réseaux de Pétri/algèbre linéaire - 01/2008)
Une question d'algèbre linéaire dans les entiers liée aux réseaux de Pétri.
Cela fait quelques années que je bute sur un problème sans doute tout bête d'algèbre linéaire dans les entiers.
Grosso modo, il s'agit de trouver une base du noyau dans N d'une application linéaire de N dans Z
Application : recherche des semi-flots dans les Réseaux de Petri.
On trouve sans difficulté dans la littérature un algorithme attribué à Farkas, mais sans explication, sans justification, sans propriétés !
Voilà donc un sujet qui me démange.
Transparents d'exposé (4 juin 2008)
Accueil
-
Hédy Attouch.
(théorie des jeux/intelligence artificielle - 06/2008)
Apprentissage d'equilibres de Nash, de comportements cooperatifs, aspects inertiels, et algorithmes de calcul parallele.
Nous presentons quelques algorithmes, resultats de travaux recents menes dans le cadre du programme ANR "decisionprox" reunissant des chercheurs de l'equipe ACSIOM de Montpellier 2 et de l'equipe Combinatoire et Optimisation de Paris 6,
specialiste en theorie des jeux repetes.
La modelisation mathematique de processus de decision prenant en compte la complexite du probleme et de l'environnement, son caractere souvent inconnu et changeant, aussi bien que les aspects strategiques, conduit a une approche dynamique: etape par etape, les agents cherchent a ameliorer leurs performances tout en prenant en compte les difficultes liees a ces transitions.
Ceci conduit a introduire des couts au changement qui donnent a ces dynamiques un caractere plus realiste au niveau de la modelisation (routines, aspects inertiels, reactivite, apprentissage), avec de nombreuses applications, par exemple en theorie des jeux ou en economie, et calcul parallele. La prise en compte d'aspects multi-echelles en temps, permet, suivant la rapidite d'apprentissage des aspects cooperatifs, d'atteindre asymptotiquement toute une palette d'equilibres allant de Nash a Pareto.
Les caracteres decentralises, locaux, avec rationalite limitee ou procedurale, des mechanismes mis en jeux laissent entrevoir des liens avec l'Intelligence Artificielle.
Transparents d'exposé (4 juin 2008)
Accueil
-
Stéphan Thomassé.
(théorie des graphes/topologie - 06/2008)
Théorème de Brouwer et recherche de stable transversal dans un graphe.
Le but est la recherche d'un ensemble stable S (i.e. ne contenant aucune arête) dans un graphe G. Une contrainte
supplémentaire étant que l'ensemble des sommets V de G est partitionné en sous-ensembles V1,...,Vk et
que le stable S considéré doit intersecter chaque Vi en exactement un point.
On dit alors que S est un /stable transversal/ de G partitionné en V1,...,Vk.
Ce problème est sans grande surprise NP-complet. En effet, il est aisé d'exprimer des problèmes classiques
tels que 3-SAT (les partitions sont les clauses, et les arêtes relient chaque littéral à sa négation), ou encore la
coloration de graphes, etc
Le but est de trouver des outils qui permettent d'obtenir des conditions suffisantes à l'existence d'un stable transversal.
Ces outils sont actuellement de deux types:
- Certains, les plus puissants, de nature topologique s'expriment de la façon suivante : si pour tout choix d'un
sous-ensemble de k parties Vi, la valeur d'un certain invariant eta, restreint au graphe induit par cette union
de Vi est au moins k, alors un stable transversal existe. La fonction eta s'exprime en terme de connexité du
complexe des stables de G. Le lemme de Sperner (i.e. version discrete de Brouwer) donne l'existence du stable.
- D'autres, de nature combinatoire, s'expriment en termes de domination de graphes. Par exemple
si la restriction de G à l'union de k sous-ensembles Vi a pour nombre de domination totale au moins 2k,
alors un stable transversal existe.
Les principales publications concernant la recherche de stables tranversaux sont dues à Ron Aharoni,
Eli Berger, Penny Haxell, et Roy Meshulam.
Workshop sur ce thème au LIRMM en octobre 2008.
Accueil
Exposés passés par des orateurs invités :
20 janvier 2010
Nicolas Brisebarre
(LIP, École Normale Supérieure de Lyon)
Une application de l'algorithmique des réseaux euclidiens à l'arithmétique des ordinateurs : approximants polynomiaux
efficaces en machine
Quand on implante des fonctions en machine, on utilise presque
toujours des approximations polynomiales. Dans la plupart des cas,
le polynôme qui approche le mieux (pour une norme et un intervalle
donnés) une fonction a des coefficients qui ne sont pas exactement
représentables sur un nombre fini de bits. Or, les polynômes
que nous devons utiliser doivent satisfaire des contraintes du type :
si n désigne le degré maximal des polynômes considérés,
le i-ème coefficient, pour i = 0, ..., n, de l'approximant
doit être un nombre rationnel de dénominateur 2^{m_i},
où (m_i)_{i = 0, ..., n} est une suite d'entiers donnée ou à déterminer, suivant
l'application considérée. Nous présenterons une méthode heuristique
utilisant l'algorithmique des réseaux euclidiens et notamment
l'algorithme LLL qui permet de produire une très bonne (voire la
meilleure) approximation polynomiale sous ce type de contraintes
quand la norme considérée est la norme sup.
Des techniques similaires fonctionnent pour la norme L2.
[Travaux de B., Chevillard, Hanrot, Muller, Tisserand et Torres]
Transparents de l'exposé
Accueil
20 janvier 2010
Boris
Adamczewski
(Institut Camille Jordan, Université Lyon 1)
Numération et théorie des nombres.
Les systèmes de numération tels que les développements
binaires, décimaux, ou le développement en fraction continue permettent
de représenter les éléments d’un ensemble donné (entiers naturels,
nombres réels, nombres complexes, nombres p-adiques, séries formelles)
de façon unifiée sous une forme combinatoire : leur suite de chiffres.
Le but principal de cet exposé est de montrer comment certains concepts
naturels en combinatoire des mots ou en informatique théorique peuvent
être utilisés, via les systèmes de numération, pour étudier plusieurs
problèmes classiques de théorie des nombres.
Transparents de l'exposé
Accueil
4 juin 2008
Sophie Schbath
(Statistics for Systems Biology, INRA - Jouy, France)
Analyse statistique de réseaux biologiques.
Statistical analysis of biological networks: models and exceptional network motifs.
Getting and analyzing biological interaction networks is at the core of systems biology. To help understanding these complex networks, many recent works have suggested focusing on motifs which occur more frequently than expected in random (Milo et al., 2002; Shen-Orr et al., 2002; Prill et al., 2005). Such motifs seem indeed to reflect functional or computational units which combine to regulate the cellular behavior as a whole. The common method that has been used for now to detect significantly over-represented motifs is based on heavy simulations: random graphs are first generated, then the p-value is derived either from the empirical distribution of the count or via a Gaussian approximation of the z-score calculated thanks to the empirical mean and variance of the count.
To identify exceptional motifs in a given network, we propose a statistical and analytical method which does not require any simulation (Picard et al., 2008). For this, we first provide an analytical expression of the mean and variance of the count under any stationary random graph model. Then we approximate the motif count distribution by a compound Poisson distribution whose parameters are derived from the mean and variance of the count. Thanks to simulations, we show that the quality of our compound Poisson distribution is very good and highly better than a Gaussian or a Poisson one. The compound Poisson distribution can then be used to get an approximate p-value and to decide if an observed count is significantly high or not.
Beyond the p-value calculation, the assessment of the motif exceptionality in a given network relies on the choice of a suitable random graph model. This model should indeed fit some relevant characteristics of the observed network. The sequence degree is usually an important feature to take into account. Unfortunately the well known and well studied Erdös-Rényi model does not fit correctly biological networks, in particular it does not consider heterogeneities. We then emphasize the recent and promising mixture model for random graphs proposed by Daudin et al. (2008). This model assumes that nodes are spread into several classes of connectivity and that the probability for two nodes to be connected depends on their classes. The goodness-of-fit of this model on real biological networks is very satisfactory.
References
Daudin, J.-J., Picard, F. and Robin, S. (2008). A mixture model for random graphs. Stat. Comput., 18 173-183.
Picard, F., Daudin, J.-J., Koskas, M., Schbath, S. and Robin, S. (2008).
Assessing the exceptionality of network motifs. J. Comp. Biol., 15:1 1-20.
Prill, R.J., Iglesias, P.A. and Levchenko, A. (2005) Dynamic properties of network motifs contribute to biological network organization. PloS Biology, 3:11 2005
Milo, R., Shen-Orr, S., Itzkovitz, S., Newman, M.E.J and Alon, U. (2002) Networks motifs: simple building block of complex networks. Science, 298 824-827
Shen-Orr, S.S., Milo, S., Mangan, S. and Alon, U. (2002) Networks motifs in the transcriptional regulation network of Escherichia coli. Nature Genetics, 31 64-68
Transparents de l'exposé
Accueil
23 janvier 2008
Simon Plouffe
Les décimales du nombre Pi.
Récemment (1995-1996), j'ai trouvé une formule et un
algorithme qui permettent de calculer le
n'ième bit ou décimale du nombre Pi sans
avoir à calculer les précédentes et qui de
plus utilise très peu de mémoire. Pour le
calcul en binaire l'algorithme est ultra-rapide :
de l'ordre de n*log(n), considéré comme très
rapide. En 2001, la position 1015 du nombre
pi a été calculée grâce à cet algorithme.
Je présenterai également ce qui peut être
fait pour rendre l'algorithme encore
plus rapide.
Transparents de l'exposé
Accueil
|