Les différentes parties de mes travaux de thèse en géométrie discrète et géométrie algorithmique seront présentées durant cet exposé.
Partie 1 : Nous considérons tout d’abord le problème de l’approximation d’un nombre réel par un nombre rationnel de dénominateur borné. Soit a un nombre réel, soit b et b’ deux nombres entiers tels que b<b’, nous souhaitons déterminer le nombre rationnel r=p/q qui approxime au mieux a, tel que b <= q <= b’. La principale approche numérique connue utilise le développement en fraction continue du réel a. Géométriquement, ce problème revient à déterminer le point de la grille le plus proche de la droite d’équation y=ax compris dans un domaine vertical défini par {(x,y) | b <= x <= b’}. Nous proposons de calculer l’enveloppe convexe des points de la grille situés au dessus (resp. en dessous) de la droite et compris dans le domaine vertical. Notre algorithme atteint une complexité logarithmique en la largeur du domaine vertical. De plus, il est adaptatif puisque le nombre d’itérations en temps constant effectuées par notre algorithme est exactement égal au nombre de sommets des deux enveloppes convexes calculées.
Partie 2 : Par la suite, nous présenterons notre algorithme de reconnaissance de plans discrets. Nous rappelons qu’un ensemble de points S de Z^3 est appelé morceau de plan discret s’il est contenu dans la discrétisation d’un plan euclidien. Un tel algorithme est utilisé pour décider si un sous-ensemble de points d’un objet discret peut être remplacé par une facette dans une représentation polyédrique de l’objet. La méthode proposée décide si un sous-ensemble de points de Z^3 correspond à un morceau de plan discret en résolvant un problème de réalisabilité sur une fonction convexe en dimension 2, dite fonction épaisseur. Ainsi, notre méthode ne prend en compte que deux paramètres et elle utilise des techniques géométriques planaires pour déterminer si l’espace des solutions est vide. Notre algorithme s’exécute en O(n log D) dans le pire cas ou n correspond au nombre de points de l’ensemble S et D représente la taille d’une boite englobant S. Notre méthode s’avère également efficace en pratique et reconnaît un ensemble de 10^6 points en environ 10 itérations linéaires.
Partie 3 : Si le temps nous le permet, nous aborderons enfin une problématique un peu à part : calculer l’épaisseur d’un ensemble de points de Z^d dans le réseau entier de même dimension (épaisseur latticielle). L’épaisseur d’un ensemble de points K suivant une direction c de Z^d correspond à la quantité max{c.x | x \in K} - min{c.x | x \in K}. L’épaisseur latticielle de l’ensemble de points K correspond à l’épaisseur minimum pour toutes les directions du réseau. D’après une idée originale de Fabien FESCHET, nous avons mis en place un algorithme valable en toute dimension pour déterminer cette épaisseur. Cette méthode s’avère optimale puisque linéaire en temps dans le cas planaire. En dimensions supérieures, nous passons par une approche gloutonne qui s’avère efficace en pratique.
TBA
L'exposé sera pour un public de non spécialistes. J'essaierai de raconter ce qu'est un bon langage de programmation (selon moi) et donc ce qu'est PML. J'essaierai notamment d'expliquer les points suivants:
We consider the problem of approximating low eigenvalues of the Laplace operator on bounded domains in n dimensional Euclidean space with Dirichlet boundary conditions. The general purpose is to be able to understand better the relationships between the geometry of the domain and low eigenvalues, and we divide our approach into (roughly) three parts as follows: 1) asymptotic expansions 2) bounds depending on geometric quantities 3) more complex conjectured bounds supported by extensive numerical computations
Je ferai un premier exposé de complexité de communication, et un deuxième sur nos résultats sur les applications entre cette théorie et les automates cellulaires. Il y aura un peu de machines de Turing, pas mal d'automates cellulaires, beaucoup de complexité de communication, et aussi des circuits logiques. La complexité de communication est une théorie très générale, et il y a plein d'applications en complexité (parallèle et séquentielle), mais aussi des choses plus appliquées comme le design de processeurs, des problèmes de graphes, etc. En plus, c'est un modèle de calcul qui n'a pas besoin de la thèse de Church.
Dans cet exposé, je présenterai une famille de polyominos appelés doubles carrés, ayant la propriété de paver le plan par translation de deux façons distinctes. Rappelons qu'un polyomino est un sous-ensemble de la grille discrète qui est 4-connexe (connecté verticalement et horizontalement) et sans trou (c'est-à-dire que son complément est également 4-connexe). Nous pouvons en particulier coder son contour par un mot sur un alphabet à quatre lettres {h, b, g, d} codant les déplacements 'haut', 'bas', 'gauche' et 'droite'. J'introduirai d'abord les définitions de la combinatoire des mots nécessaires à cet exposé ainsi que les notions de polyominos et de pavages. Ensuite, je survolerai rapidement les résultats connus et certaines conjectures intéressantes. J'enchaînerai en présentant quelques propriétés sur les chemins liées à une généralisation de la notion de palindrome et je terminerai en présentant une famille de tuiles liées à la suite de Fibonacci. L'exposé se déroulera en québécois...
We obtain several averaging lemmas for transport operator with a force term. These lemmas improve the regularity yet known by not considering the force term as part of an arbitrary right-hand side. We compare the obtained regularities according to the space and velocity variables.
Nous présentons une approche (1D) d'écoulement mixte en conduite fermée à section non uniforme. Le modèle est dérivé à partir des équations d' Euler compressible et incompressible. Par le choix de variables dites équivalentes et d'une pression adéquate, on réécrit le modèle sous une seule formulation. Ce modèle fait intervenir des termes sources complexes que l'on propose de décentrer dans le cadre d'un schéma cinétique: les termes en question sont les termes sources de pression, les termes de géométrie et la friction. La difficulté du décentrement réside en la nature de chacun des ces termes : produits conservatifs, non-conservatifs ou d'aucun de ces deux types. On termine par quelques tests numériques où l'on compare les résultats obtenus avec une méthode type VFROE. Notamment, notre approche conserve la symétrie de certains écoulements contrairement à une approche explicite classique.
We apply the semigroup setting of Desch and Miller to a class of stochastic integral eqations of Volterra type with completely monotone kernels with a mutiplicative noise term. The corresponding equation is an infinite dimensional stochastic equation with unbounded diffusion operator that we solve with the semi group approach of Da Prato and Zabezyk. As a motivation of our results, we study an optimal control problem when the control enters the system together with the noise.
Nous considérons un écoulement de deux fluides newtoniens, imcompressibles et immiscibles dans un domaine mince. Nous supposons que l'écoulement est gouverné par les équations de Navier-Stokes. Dans un premier temps nous considérons que les deux fluides n'ont pas la même vitesse et nous ne tenons pas compte de la variation de la hauteur totale des fluides. Ainsi nous dérivons un modèle de Saint-Venant bicouche à toit rigide. Nous montrons la stabilité de solutions faibles du modèle. Dans un second temps nous supposons que la surface est libre mais que les deux fluides ont la même vitesse. Nous finissons par une étude numérique du modèle 1D.
Les équations différentielles stochastiques rétrogrades ont été introduites par Pardoux et Peng en 1990. La motivation initiale était de généraliser à des problèmes non-linéaires la formule de Feynman-Kac (représentation probabiliste d'EDP du second ordre). J'essaierai dans un premier temps d'expliquer les liens entre ce type d'équations stochastiques et la théorie des EDP puis dans un second temps je donnerai d'autres applications par exemple à la finance et/ou à la théorie des martingales.
Des entreprises comme Amazon, Google et Yahoo rendent maintenant disponibles une partie de leurs fonctionnalités sous la forme de services web; une application tierce peut communiquer avec ces services via Internet en échangeant des messages dont la structure et le contenu sont publics et formellement définis. Cependant, la documentation précise également une foule d'autres détails sur la manière dont ces services doivent être consommés, exprimés en langue naturelle et échappant à toute formalisation. Ce contexte nous a amené à développer LTL-FO+, une extension de la logique temporelle LTL incluant 1) une forme particulière de quantification du premier ordre; 2) une sémantique à 2, 3 ou 4 valeurs de vérité, selon le contexte. On verra que, contrairement à LTL, elle est appropriée pour exprimer des contraintes sur les séquences de messages propres aux applications web. On s'intéressera par la suite à son runtime monitoring; pour ce faire, nous présenterons BeepBeep, un outil permettant la vérification et l'application de formules LTL-FO+ en temps réel sur de vraies applications web. Finalement, on verra au moyen d'un exemple concret (si la connexion Internet le permet) comment BeepBeep: 1) empêche une application web mal programmée de commettre des erreurs; et 2) nous permet de découvrir que les services web d'Amazon ne respectent pas certains détails de leur propre documentation.
Cet exposé est basé sur le modèle de Canh-Hilliard qui permet de décrire l'évolution du mélange de plusieurs espèces. Il est décomposé en trois parties, une première partie qui concerne la biologie du cancer, la deuxième partie parle d'un modèle mathématique mis en place par Preziosi sur le cancer et enfin on essaie de voir le cancer comme un mélange d'espèces (cellules normales, cellules malades, matrice extracellulaires, ...)
Une justification mathématique de la condition d'adhérence imposée classiquement dans de nombreux modèles (notamment les modèles de mouvement de fluides visqueux) consiste à remplacer la paroi lisse, idéale, par une paroi rugueuse. L'idée est d'imposer uniquement une condition de non pénétration sur la paroi rugueuse, et de montrer que la condition d'adhérence s'obtient dans le modèle limite quand la taille des aspérités tend vers 0. Après avoir discuté du sens à donner à ce passage à la limite, nous montrerons sous quelles conditions une paroi périodique ou cristalline donne lieu à un effet de rugosité uniforme, sur des champs de vecteurs H^1 vérifiant une condition de glissement parfait sur la paroi rugueuse. En particulier cet effet de rugosité est indépendant d'une éventuelle équation satisfaite par les champs de vecteurs sur lesquels on l'applique.
The influence of wall roughness on the slip behavior of a viscous fluid has been discussed in several recent papers. We study the asymptotic behavior of a viscous fluid near a periodic oscillating wall with period epsilon and amplitude depending on the period. We assume the fluid to satisfy the so-called Navier’s boundary conditions. When the period and the amplitude have the same order, it is known that in the limit this boundary condition provides the adherence (or no-slip) condition. This gives a mathematical justification of why adherence conditions are usually imposed for viscous fluids, they are due to the microscopic asperities. In our work we consider the case where the amplitude is much smaller than the period. We show the existence of a boundary layer and, depending on if its value is zero, a positive number or infinite, we get different boundary conditions in the limit. As particular case, we can recover the adherence condition. The proof of our results is based on an original adaptation of the unfolding method, which is closely related to the two-scale convergence method.
Beaucoup de matériaux ont un comportement intermédiaire entre les solides élastiques et les fluides newtoniens. La rhéologie est l'étude de ces matériaux et de leurs conditions d'écoulement. Parmi ces matériaux nous présenterons brièvement la classe des matériaux vitreux/pâteux qui présente plusieurs propriétés caractéristiques des fluides complexes: ce sont des fluides élastoviscoplastiques. Après avoir rappelé ce que sont ces propriétés, nous présenterons un modèle multi-échelle conçu pour décrire le comportement des fluides vitreux. Nous étudierons ensuite les courbes de flots attachées à ce modèle pour montrer que leurs comportement à faible cisaillement subit une transition lorsque l'un des paramètres du modèle passe par une valeur critique.
On donnera la définition des objets en questions avec quelques motivations et des exemples simples. Ensuite, on interprètera ces objets comme un lien entre la géométrie complexe et la géométrie tropicale. Enfin on verra une ou deux applications à certains problèmes de la géométrie algébrique classique, par exemple une condition nécessaire sur les coefficients d'un polynôme réel à deux variables pour que ses zéros réels définissent une courbes de Harnack.
One of the purposes of quantum programming languages is to express quantum programs, however a possibly more important reason is to provide a framework for reasoning about the programs expressing quantum algorithms -- and hence about quantum computation in general.
Indeed, in classical computer science it is frequent to express the reasoning behind a program via several formally-defined logics. These logics provide important frameworks in which to reason and prove properties about the computational processes. Often they arise via the study of type systems for the language. Related to our motivation there is already a quantum logic, which was developed before quantum computing, and which is not known to have a clear relation to quantum programs and algorithms.
The Linear-Algebraic Lambda-Calculus extends the Lambda-Calculus with the possibility to make arbitrary linear combinations of terms a.t+b.u. We want to set up a type system for it which is capable of such handling vectorial notions, i.e. were types themselves form a vector space. This is needed at a practical level for instance in order to prove normalization and unitarity properties of terms. There is also the intriguing question as to what logical meaning we can give these `superposition types'.
Joint work with Pablo Arrighi.