La théorie des pavages par tuiles de Wang a été inventée par (surprise) Hao Wang afin de proposer un problème combinatoire concret correspondant au pouvoir d'expressivité d'un fragment de la logique du premier ordre. La théorie des pavages s'est en fait révélée comme une théorie élégante s'exprimant facilement logiquement, et a ainsi apporté de nombreux résultats en logique mathématique.
Il s'agit dans cet exposé de proposer une présentation des liens entre pavages et logique. On analysera en particulier comment deux des théorèmes fondamentaux sur les pavages se traduisent :
- Par l'existence d'une théorie complète finiment axiomatisable et superstable [Makowsky, Poizat]
- Par le fait que le fragment AEA de la logique du premier ordre forme une classe de réduction conservative [Büchi, Kahr-Moore-Wang]
tout en expliquant bien entendu ce que signifient les nombreux mots potentiellement obscurs des phrases précédentes.
Aucune connaissance sur les pavages n'est nécessaire. Une connaissance rudimentaire de la logique du premier ordre sera appréciée.
Les exceptions sont généralement vues comme un mécanisme modifiant le flot de contrôle d'un programme. Cette vision cantonne les exceptions aux langages pour lesquels la notion de flot de contrôle est bien définie, ce qui n'est généralement pas le cas pour les langages de la théorie des types. Nous présenterons un mécanisme où les exceptions sont attachées aux valeurs plutôt qu'au flot de contrôle, ainsi qu'un système de types pour ces exceptions basé sur la notion de corruption. Nous montrerons que cette notion, utilisée à travers une relation de sous-typage, permet la détection statique d'exceptions non rattrapées, et ce sans compromettre la propagation automatique des exceptions. Nous illustrerons ce système d'exceptions dans le cadre d'une extension du Système F, utilisé ici comme une première étape vers des systèmes de types plus riches (avec pour horizon le calcul des constructions). Enfin, nous présenterons un modèle de réalisabilité pour justifier et expliquer la notion de corruption dans notre calcul.
La représentation des images par des descripteurs géométriques locaux s'est imposée dans nombre d'applications comme la détection d'objets, l'identification de scène, la reconstruction 3D, la création de panorama, etc. Ces descripteurs sont généralement construits autour de points d'intérêt, par exemple sous la forme d'histogrammes locaux d'orientation du gradient de l'image (cas des descripteurs SIFT proposés par D. Lowe), ce qui leur permet d'être invariants ou robustes à de nombreuses transformations et altérations de l'image. Dans cet exposé, on s'intéresse à l'appariement de tels descripteurs. Pour chaque descripteur d'un ensemble de requêtes, on souhaite décider s'il ressemble ou non à certains descripteurs d'une base de données. Dans la littérature, cette étape se résume souvent au choix d'un seuil sur la distance euclidienne au plus proche voisin. La procédure de mise en correspondance que nous proposons utilise d'une part une distance de transport entre descripteurs et d'autre part une approche a contrario qui permet de valider ou pas les mises en correspondance. Cette approche fournit des seuils de validation qui s'adaptent automatiquement à la complexité de chaque descripteur requête et à la diversité de la base de données. Elle permet à la fois de détecter plusieurs occurences d'une même requête et de gérer correctement les cas où aucune de ces requêtes n'est présente dans la base de données. Aux appariements ainsi validés correspondent des transformations dans le plan des images. La détection de groupes spatialement cohérents dans l'espace de ces transformations permet in fine de reconnaître des ``formes globales'' entre les images considérées.
Current continuation methods for finding all solutions to systems of polynomial equations first compute all complex solutions, and then sieve them to find the real solutions. This method is not optimal in that number of paths to be followed may not reflect the actual number of real solutions. This problem is particularly acute for fewnomial systems, a class of systems whose number of real solutions is typically much smaller than their number of complex solutions. Recent work has established a new bound for the number of real solutions to a system of fewnomials, by transforming the system of polynomials into an equivalent system of master functions on a hyperplane complement, called the gale dual system. Sturmfels observed that the method used to establish those bounds, the Khovanskii-Rolle Theorem, could be the basis of a continuation algorithm to compute all real solutions, which has the additional feature that the path continuation only follows real solutions. In this talk, I will sketch the main ideas in this new algorithm. This will also include a sketch of the proof of these new fewnomial bounds, and some of the continuation issues which arisen in an implementation of the algorithm. We remark that the complexity of this algorithm depends on the ambient (real dimension) and the fewnomial bound, and not on the number of complex solutions. The implementation of the algorithm is joint work with Daniel J. Bates, while the fewnomial bounds and reduction to Gale systems is work with Frédéric Bihan and Bates.
Dans cette exposé nous étudions le problème d'évolution associé à l'équation de Monge-Kantorovich pour le transport optimale de masse. Il est aussi appelé le modèle de Prigozhin pour le tas de sable. Nous démontrons les résultats d'existence et d'unicité de solution dans le cas où les données sont des mesures et nous montrons comment appliquer des méthodes de dualités pour la résolution numérique. Enfin nous présentons quelques résultats de simulations numérique.
The purpose of this communication is to discuss the simulation of a free surface compressible flow between two fluids, typically air and water. We use a two fluid model with the same velocity, pressure and temperature for both phases. In such a model, the free surface becomes a thin three dimensional zone. The present model has at least three advantages: (i) the free-surface treatment is completely implicit; (ii) it can naturally handle wave breaking and other topological changes in the flow; (iii) one can easily vary the Equation of States (EOS) of each fluid (in principle, one can even consider tabulated EOS). Moreover, our model is unconditionally hyperbolic for reasonable EOS. First, we present the physical context of our study. Then, we introduce the governing equations and we give some rationales on the limit of this model to the classical free surface model. Finally, we present our numerical method based on a flux scheme which is, in particular, constructed to model accurately impacts of waves on walls. Since our code is designed for unstructured meshes, it can easily treat complex geometries (for example, liquified natural gas carrier tank). This communication will conclude with the presentation of different simulation results on the sloshing of a liquid in a closed container.
Cf le site idoine: http://choco.pps.jussieu.fr/events.
Le vitrier ou le carreleur exploite un phénomène que nous nous proposons d'analyser : une petite incision dans un matériau cassant permet de générer des concentrations de contraintes localisées. En termes mathématiques, nous considèrerons une perturbation singulière de la géométrie d'un domaine et présenterons l'analyse asymptotique de la solution de l'équation de Laplace dans ce domaine perturbé. Nous montrerons comment utiliser cette analyse pour le calcul numérique et le cas de plusieurs perturbations. Ces travaux sont réalisés dans le cadre de l'ANR Macadam.
Comme le montrent les publicités dans les magazines (multi-coeur par-ci, hyperthread par-là), la tendance des architectures des ordinateurs est à la parallélisation, et l'on commence donc dans le grand public à parler de programmation avec des threads. Du côté des machines de calcul scientifique, on mélange en fait allègrement ces technologies de manière hiérarchique pour aboutir à de véritables cathédrales, sur lesquelles on exécute une armée de threads. Cependant, pour obtenir une exécution efficace (et donc économiser du temps, des machines ou de l'énergie), il est indispensable de distribuer de manière raisonnée ces threads sur ces machines. La tâche est d'autant plus ardue que les threads peuvent en créer d'autres, éventuellement de manière irrégulière. Durant ma thèse, j'ai proposé la notion de /bulles/, qui regroupent de manière récursive les threads et apportent ainsi une certaine structure aux applications de calcul scientifique. En modélisant par ailleurs les machines de calcul sous forme d'un arbre, on ramène ainsi notre problème à la mobilité des bulles et threads sur cet arbre. Une boîte à outil permet alors d'implémenter des algorithmes de placement/redistribution pour les appliquer à des applications bien concrètes. On peut alors observer des gains de performances de l'ordre de 20 à 40% par rapport à un ordonnancement classique ! Je débuterai mon exposé en expliquant quelques détails architecturaux importants par rapport à l'efficacité de l'exécution des threads d'une application. J'introduirai alors ce que j'entends par ordonnancement'',placement'' et ``migration'' des threads et bulles. Je présenterai ensuite la boîte à outils au travers de quelques exemples, et l'on pourra discuter notamment de la ressemblance intriguante avec des ambients.
On considère un type de métriques riemanniennes singulières qui apparait naturellement en théorie du contrôle : soient X et Y deux champs de vecteurs sur une variété M de dimension 2. Si X et Y forment partout une famille libre, ils définissent naturellement sur M une métrique riemannienne dont ils forment un champ de bases orthonormées. Quand X et Y ne sont plus partout linéairement indépendants, sous certaines conditions génériques de non intégrabilité de la distribution qu'ils engendrent, ils définissent sur M une métrique sous-riemannienne sur une distribution de rang non constant, qu'on peut voir comme une métrique riemannienne singulière. Ces structures font apparaître des phénomènes intéressants, en particulier pour ce qui concerne les liens entre courbure, lieu conjugué et topologie de la variété. Je présenterai, lors de cet exposé, un résultat du type ``formule de Gauss-Bonnet'' démontré par Agrachev, Boscain et Sigalotti et expliquerai les difficultés liées à sa démonstration dans le cas ou la métrique présente des singularités de type Martinet.
Cet exposé, est une partie d’un article en cours, en collaboration avec {\it Latifa Faouzi} (Fes et Casablanca) et se compose de deux parties indépendantes.
PARTIE I: $k$-algèbre libre sur un monoïde.
On considère un corps commutatif $k$ et un monoïde (= demi-groupe commutatif et unitaire) $M$. On désigne par $k[M]$ la $k$-algèbre sur le monoïde $M$, i.e. l’espace vectoriel sur $k$ ayant $M$ comme base, c’est alors aussi un anneau puisque $M$ est stable par produit. L’exemple type étant l’algèbre des polynômes sur $k$. Le corps $k$ étant fixé, on montre plusieurs propriétés de la classe des algèbres sur un monoïde. Par exemple $k[X] x k[Y]$ est une $k$-algèbre libre sur un monoïde. On développe aussi une classe plus large où le produit de deux élements de $M$ est soit $0$, soit un élement de $M$.
PARTIE II: Demi-treillis compact. Dans cette partie, les monoïdes ne sont pas unitaires. On considère un triplet $(L,O,.)$ où $(L,O)$ est un espace compact séparé, $(L,.)$ est un monoïde idempotent (mais sans unité). On suppose que l’application $(x,y) -> x. y$ est continue. En interprétant $x . y$ comme l’infimum de $x$ et de $y$, $(L,.)$ est un (inf-)demi-treillis et $.$ est continue. Noter que $L$ est alors un ensemble ordonné en posant $x \leq y$ ssi $x . y = x$. On montre quelques propriété de cette classe de structures. Par exemple, une telle structure possède un plus petit élément $0$ et toute partie non vide et filtrante supérieurement possède un supremum. La topologie est alors déterminée par l’ordre: une sous-base de la topologie est formée d’élements de la forme $U_x := { y \in L : y \geq x }$ et $L \setminus U_x$ où $x$ est un élément “compact” de $L$. Ces notions de demi-treillis compacts apparaissent lors de l’étude des domaines et des treillis algébriques.
PARTIE III: Le lien. Si on considère le corps $k = {0,1}$ ayant deux éléments et le monoïde $M$ idempotent, alors $k[M]$ est une algèbre de Boole, dont l’espace des ultrafiltres (ou des idéaux maximaux) est un demi-treillis compact et “réciproquement”.
Bibliographie:
[1] Bourbaki N.: Eléments de mathématiques, Algèbre, Chapitres 1--3, Hermann, 1970.
[2] Lang S.: Algebra, Addision-Wiesley Pub, 1970.
[3] Gierz, G., Hofmann K. H., Keimel K., Lawson J. D., Mislove M. and Scott D. S.: Continuous lattices and domains, Encyclopedia of Mathematics and its Applications, 93. Cambridge University Press, Cambridge, 2003, 591 pp.
L'objectif de cet exposé est de présenter le contexte et les motivations ayant conduit à mon sujet de thèse : Géométrie multirésolution des objets discrets bruités. On commencera par présenter quelques outils classiques autour des droites discrètes et leurs applications à l'estimation de quantités géométriques sur des formes discrètes. L'extension de ces outils aux formes discrètes bruitées sera ensuite abordée. On en déduira les quelques axes de recherche qui seront explorés dans ma thèse.
On présente un ensemble d'études traitant de la modélisation numérique d'écoulements à surface libre. Les équations considérées peuvent être des équations de Navier-Stokes surface libre (résolues par des schémas éléments finis en formulation ALE - caractéristiques) ou encore leurs dérivées asymptotiques type ``shallow'' (non visqueux, schémas volumes finis). La première partie traite de la modélisation des plaines d'inondations et porte tout particulièrement sur les aspects inverses tels que la calibration des modèles, leur couplage faible simultané, l'identification de paramètres et l'assimilation de données. Ces approches sont basées sur les méthodes de contrôle optimal et des équations adjointes. La seconde partie traite d'une modélisation de la dynamique de la ligne triple en microfluidique (modèle de Shikhmurzaev). On y présente aussi bien des aspects analyse mathématique qu'élaboration d'algorithmes et illustration avec l'étalement d'une gouttelette sur un substrat solide. La troisième partie, dont les travaux viennent seulement de commencer, traite d'écoulements glaciaires multi-échelles. On y retrouve alors un ensemble d'ingrédients mathématiques, numériques et logiciels abordés dans les deux applications précédentes.
Cet exposé fera un survol du domaine de la topologie des images, ou digital topology'', ainsi que quelques-unes de ses applications. L'espace image est vu comme un sous-ensemble de Z^n, une forme dans une image est un sous-ensemble de Z^n. Nous présenterons ainsi les approches graphes, cellulaires et intermédiaires. On verra qu'une des difficultés est de définir ce qu'est une surface (discrète'' donc) dans ces espaces, afin de retrouver les propriétés classiques de l'espace euclidien. Ensuite, nous montrerons quelques algorithmes effectifs d'extraction de surfaces, avec quelques applications. Si le temps le permet, nous nous intéresserons au calcul effectif de l'homologie, afin d'obtenir des invariants topologiques sur les formes discrètes.
Ce séminaire donnera les liens entre un problème de recouvrement des entiers et la combinatoire des mots afin d'étudier la conjecture de Fraenkel. Cette conjecture a été formulée dans le cadre de la théorie des nombres il y a maintenant plus de 30 ans. Elle prétend que pour k > 2 entier fixé, il y a une unique façon de recouvrir les entiers par $k$ suites de Beatty avec des fréquences deux à deux distinctes. Ce problème peut être exprimé en termes de combinatoire des mots de la façon suivante: pour un alphabet à k lettres, il existe une unique suite équilibrée avec des fréquences de lettres deux à deux distinctes qui est exactement la suite de Fraenkel notée $(F r_k )^{omega}$ où F r_k = F r_{k-1} k F r_{k-1}, avec F r_3 = 1213121. Cette conjecture est prouvée pour k = 3, 4, 5, 6 d'après les travaux de Altman, Gaujal, Hordijk et Tijdeman ainsi que dans d'autres cas particuliers. Dans ce séminaire, nous présenterons donc une synthèse sur ce sujet et la résolution de la conjecture dans un cas particulier.