En 1962, Cohen a résolu le premier problème de Hilbert en montrant que l'hypothèse du continu est indécidable dans la théorie des ensembles de Zermelo-Fraenkel. La technique qu'il a introduite pour établir ce résultat non trivial - le forcing - est devenue aujourd'hui un outil standard en théorie des modèles. Cette technique a permis d'établir de nombreux autres résultats de cohérence relative (ou d'indépendance), comme par exemple la cohérence de l'axiome de Solovay: « toute partie de R est mesurable au sens de Lebesgue » dans une théorie des ensembles sans axiome du choix (mais avec choix dépendant).
Dans cet exposé introductif au forcing, je me propose de présenter la théorie des modèles booléens, une variante du forcing (introduite par Scott, Solovay et Vopenska dans les années 1960) qui permet de faire essentiellement les mêmes constructions que Cohen, mais dans un cadre qui est plus facile à saisir au premier abord. J'introduirai les notions de base (algèbres de Boole, ultrafiltres, modèles booléens, quotient, produit, ultraproduit et ultrapuissance) tout en illustrant mon propos par quelques exemples de constructions, notamment en lien avec l'« analyse non standard ».
La preuve de l'indépendance de l'hypothèse du continu à l'aide de ces outils fera l'objet de l'exposé suivant.
On considère la classe des systèmes de Timoshenko. L’objectif est de démontrer la stabilité à l’infini (l’énergie décroit vers zéro quand le temps converge vers l’infini) et obtenir une estimation sur le taux de décroissance. Pour cela, on distingue deux cas. 1. Les deux équations ont la meme vitesse de propagation : pour toute solution faible, on montre une estimation générale et explicite sur l’énergie ce qui donne une idée précise sur l’influence de chaque controle sur la stabilité du système. On donne quelques exemples pour illustrer notre estimation. 2. Les deux équations n’ont pas la meme vitesse de propagation : sous des hypothèses plus fortes et pour des solutions plus régulières, on montre une estimation de stabilité plus faible. L’idée de la démonstration est basée sur la méthode des multiplicateurs et quelques inégalités intégrales. Ses résultats ont été obtenus en collaboration avec S. Messaoudi (KFUPM, Dhahran, Arabie Saoudite) dont une partie va apparaitre dans Mathematical Methods in the Applied Sciences.
In 2003, Hofmann and Jost introduced a type system that uses a potential-based amortized analysis to infer bounds on the resource consumption of (first-order) functional programs. This analysis has been successfully applied to many standard algorithms but is limited to bounds that are linear in the length of the input.
Here we extend this system to polynomial resource bounds. An automatic amortized analysis is used to infer these bounds for functional programs without further annotations if a maximal degree for the bounding polynomials is given. The analysis is generic in the resource and can obtain good bounds on heap-space, stack-space and time usage. Furthermore, the analysis can be used to infer polynomial relations between the input and the output sizes of a function in the sense of sized types.
Travail en collaboration avec Jan Hoffmann.
The wire calculus is a process algebra for modelling truly concurrent systems with explicit network topologies. It benefits from using categorical operators for coordination of processes: the tensor product and sequential composition of monoidal categories. The dynamics are handled by operators inspired by Milner's CCS and Hoare's CSP: unary prefix operation, binary choice and a standard recursion construct. The operational semantics is a labelled transition systems derived using SOS rules. After presenting the formal definition of the calculus I will discuss some basic results and give several examples.
On s’intéresse aux structures R_f = (R,+,*,<,f) engendrées par une fonction C^\infty f restreinte à un compact. L’objet de cet exposé est de montrer que pour une fonction f générique, la structure R_f est o-minimale. On exibera en effet une condition explicite sur les développements de Taylor de f qui implique la o-minimalité de R_f et est générique au sens de Whitney. L’essentiel de la preuve consiste a établir la quasi-analyticité de certaines algèbres differentielles engendrées par f. Ce résultat permet d’obtenir très simplement les corollaires suivants (les deux premiers étant déjà connus) : 1. Il existe des structures o-minimales n’admettant pas la propriété de décomposition analytique. 2. Il existe des structures o-minimales incompatibles (au sens où elles ne sont pas des restrictions d’une même structure o-minimale) 3. Il existe des structures o-minimales incompatibles avec les sous-analytiques.
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.