L'hypothèse qu'un grand nombre de problèmes n'admettent pas d'algorithme (exact et déterministe) polynomial date de l'avènement de la théorie de la NP-complétude dans les années 70. Depuis, de nombreuses théories et techniques algorithmiques se sont développées pour résoudre ces problèmes difficiles le plus efficacement possible. Dans cette thèse, nous nous intéressons aux algorithmes exacts faiblement exponentiels. L'objectif est d'obtenir des algorithmes de complexité 0* (c^n) où n est la taille de la donnée et c une Constante la plus faible possible / The assumption that many problems do not admit algorithm (exact and deterministic) polynomial ate of the advent of the theory of NP-completeness in the 70s. Since many theories and algorithmic techniques have been developed to solve these problems difficult as efficiently as possible. In this thesis, we focus on exact algorithms weakly exponential. The objective is to obtain algorithms complexity 0 * (c ^ n) where n is the size of the data and one constant c as small as possible

Cette thèse se situe dans le cadre de l'analyse théorique et numérique de modèles en séparation de phase qui tiennent compte d'effets d'anisotropie. Ceci est pertinent, par exemple, pour l'évolution de cristaux dans leur matrice liquide pour lesquels ces effets d'anisotropie sont très forts. On étudie l'existence, l'unicité et la régularité de la solution des équations de Cahn-Hilliard et d'Allen-Cahn ainsi que son comportement asymptotique en terme d'existence d'un attracteur global de dimension fractale finie. La première partie de la thèse concerne certains modèles de séparation de phase qui, en particulier, décrivent la formation de motifs dendritiques. D'abord, on étudie les équations de Cahn-Hilliard et d'Allen-Cahn qui prennent en compte les effets d'anisotropie forts en dimension un avec des conditions de type Neumann sur le bord et une non linéarité régulière de type polynomial. En particulier, ces modèles contiennent un terme supplémentaire appelé régularisation de Willmore. Ensuite, on étudie ces modèles avec des conditions de type périodique (respectivement, Dirichlet) sur le bord pour l'équation de Cahn-Hilliard (respectivement, d'Allen-Cahn) mais en dimension spatiales plus élevées. Finalement, on étudie la dynamique des équations de Cahn-Hilliard et d'Allen-Cahn visqueux avec des conditions de type Neumann et Dirichlet respectivement sur le bord et une non linéarité régulière et en plus, la présence de simulations numériques qui montrent les effets du terme de viscosité sur l'anisotropie et l'isotropie dans l'équation de Cahn-Hilliard. Dans le dernier chapitre, on étudie le comportement en temps long en termes d'attracteurs de dimension finie, d'une classe d'équations doublement non linéaires de type Allen-Cahn avec des conditions de type Dirichlet sur le bord et une non linéarité singulière. / This thesis is situated in the context of the theoretical and numerical analysis of models in phase separation which take into account the anisotropic effects. This is relevant, for example, for the development of crystals in their liquid matrix for which the effects of anisotropy are very strong. We study the existence, uniqueness and the regularity of the solution of Cahn-Hilliard and Alen-Cahn equations and the asymptotic behavior in terms of the existence of a global attractor with finite fractal dimension. The first part of the thesis concerns some models in phase separation which, in particular, describe the formation of dendritic patterns. We start by study- ing the anisotropic Cahn-Hilliard and Allen-Cahn equations in one space dimension both associated with Neumann boundary conditions and a regular nonlinearity. In particular, these two models contain an additional term called Willmore regularization. Furthermore, we study these two models with Periodic (respectively, Dirichlet) boundary conditions for the Cahn-Hilliard (respectively, Allen-Cahn) equation but in higher space dimensions. Finally, we study the dynamics of the viscous Cahn-Hilliard and Allen-Cahn equations with Neumann and Dirichlet boundary conditions respectively and a regular nonlinearity in the presence of the Willmore regularization term and we also give some numerical simulations which show the effects of the viscosity term on the anisotropic and isotropic Cahn-Hilliard equations. In the last chapter, we study the long time behavior, in terms of finite dimensional attractors, of a class of doubly nonlinear Allen-Cahn equations with Dirichlet boundary conditions and singular potentials.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Pour réaliser des simulations précises aux temps longs pour des vagues non linéaires, il faut faire appel à des algorithmes d'évolution temporelle précis. En particulier, la combinaison d'un pas de temps adaptatif avec un facteur intégrant est connue pour être très efficace. Nous proposons une modification de cette technique. Le principe consiste à soustraire un certain polynôme à une EDP. Puis, comme pour le facteur intégrant, nous faisons un changement de variable pour retirer la partie linéaire. Mais nous espérons retirer quelque chose de plus afin de rendre l'EDP moins raide pour les calculs numériques. Le polynôme choisi est une expansion de Taylor autour du temps initial de la solution. Afin de calculer les différentes dérivées nécessaires, nous utilisons le Dense Output qui donne la possibilité d'approximer les dérivées de la solution à tout temps. Une fois le facteur intégrant modifié appliqué, nous faisons appel à une avance temporelle classique afin de résoudre l'équation d'évolution. Il a été considéré plusieurs schémas de Runge-Kutta avec pas de temps adaptatif. Nous avons tiré avantage des méthodes emboîtées, afin de ne pas calculer de nouvelles fonctions et perdre du temps de calcul, en utilisant uniquement des données déjà calculées durant l'évolution temporelle. Les résultats numériques montrent que l'efficacité de notre méthode varie selon les cas. Par exemple, nous avons vérifié que plus le profil de l'onde est pentue, plus notre méthode est efficace. Pour le modèle de vagues non linéaires le plus compliqué à notre disposition, le modèle HOS, nous avons pu réduire le nombre de pas de temps de calcul jusqu'à près de 30 % avec un schéma de Runge-Kutta de Dormand-Prince et jusqu'à plus de 99 % pour un schéma de Bogacki-Shampine.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Dans cette thèse, on étudie l'existence, l'unicité et la régularité des solutionsd'équation de type Cahn-Hilliard ainsi que son comportement asymptotiqueen termes d'existence de l'attracteur global et d'un attracteur exponentiel. Cetteéquation est considérée dans un domaine borné et régulier pour différents types denonlinéarités et de conditions au bord.D'abord, on étudie l'équation avec des conditions de type Dirichlet sur le bord etune nonlinéarité régulière. Après, on considère une perturbation du problème et ondémontre l'existence d'une famille robuste d'attracteurs exponentiels lorsque ε tendvers 0.Ensuite, on étudie l'équation avec des conditions dynamiques sur le bord. On considèretout d'abord une nonlinéarité régulière et on donne une étude théorique etnumérique. Après, on illustre ces résultats par des simulations numériques en dimensiondeux d'espace qui permettent d'étudier l'influence des différents paramètres.On termine par une étude du modèle considéré avec une nonlinéarité singulière quel'on approche par des fonctions régulières et on introduit une notion de solutionappropriée. / This thesis is devoted to the study of the existence, uniqueness andregularity of solutions for a Cahn-Hilliard type equation, as well as the asymptoticbehavior in terms of existence of the global attractor and of an exponential attractor.This equation is considered in a bounded and smooth domain under variousassumptions on the nonlinear terms and with different boundary conditions.We start by studying the equation with Dirichlet boundary conditions and a regularnonlinearity. Then, we consider a perturbation of the problem and we prove theexistence of a robust family of exponential attractors as ε tends to 0.For the equation endowed with dynamic boundary conditions, we first consider aregular nonlinearity and we treat the theoretical and numerical analysis. Then, weillustrate the results by numerical simulations in two space dimension which allow usto study the influence of different parameters. Finally, we treat the problem consideredwith a singular nonlinearity which is approximated by regular functions andwe give a suitable notion of solutions.

Si µ est une mesure de probabilité à support compact dans uns espace vectoriel ou affine de dimension finie, le barycentre (ou centre de gravité) de µ est un point bien défini de l’espace. Mais des difficultés surgissent lorsque l’espace est remplacé par une variété riemannienne M ; dans ce cas, même en se restreignant aux variétés convexes (c’est-à-dire deux dont points quelconques sont toujours joints par une géodésique et une seule) et aux mesures à support fini, il est en général impossible d'assigner à chaque probabilité un barycentre de façon que, d'une part,pour tous λϵ [0; 1] et x et y dans M, le barycentre de µ = (1- λ ) δˣ+ λ δy soit toujours le point γ(λ), sur la géodésique telle que γ (0) = x et γ (1) = y, et que, d'autre part, soit préservée la propriété d'associativité (pour faire une moyenne, on peut commencer par faire des moyennes partielles). Dés que la mesure µ est portée par au moins trois points non tous situées sur une même géodésique, il y a de multiples façons différentes de définir son barycentre comme barycentre de barycentres partiels de barycentres partiels etc., chaque opération élémentaire ne faisant intervenir que deux points. On obtient ainsi tout un ensemble de points de M, les barycentres itérés de µ . Pour des probabilités plus générales, on appelle barycentre convexe de µ l'ensemble b(µ) des points x de M qui sont limites d'une suite (xn), ou chaque xn est un barycentre itéré d'une probabilité µn à support fini, les mesures µn tendant vers µ. / If μ is a probability measure carried on a small in a finite-dimension vectorial or affine space, the μ- barycenter (center of gravity) is a well-defined point in space. Nevertheless, difficulties arise when space is changed by Riemannian manifold M. In this case, even if we limit to convex manifolds (i.e : when any two points are joined by one geodesic and just one) and to finite-support measures, it’s, in general impossible to attribute a barycenter to each probability, in such a way, on one hand, whetever λϵ [0; 1] and x and y in M, the barycenter of µ = (1- λ ) δˣ+ λ δy will be always the point γ(λ) of the geodesic such that γ (0) = x et γ (1) =y, and on another hand, the associative property will be maintained (to make a mean, we can begin by doing partial means). Once the measure μ is carried by at least three points which are not all localed on the same geodesic, there are different manners to define its barycenter as one of partial barycenters of partial barycenters and so on, in which each elementary operation includes only two points. Thus, we get a whole set of set of points of M, the iterated barycenters of μ. For more general probabilities μ, we call convex barycenter of μ, the set b(μ) of points x of M which are limit of sequence (xn), in which each xn is an iterated barycenter of a finite support probability μn, the measure μn tending to μ.

No description available.

Soit P(z):=\sum_{\nu=0}^na_\nu z^{\nu}$ un polynôme de degré n et M:=\sup_{|z|=1}|P(z)|.$ Sans aucne restriction suplémentaire, on sait que $|P'(z)|\leq Mn$ pour $|z|\leq 1$ (inégalité de Bernstein). Si nous supposons maintenant que les zéros du polynôme $P$ sont à l'extérieur du cercle $|z|=k,$ quelle amélioration peut-on apporter à l'inégalité de Bernstein? Il est déjà connu [{\bf \ref{Mal1}}] que dans le cas où $k\geq 1$ on a $$(*) \qquad |P'(z)|\leq \frac{n}{1+k}M \qquad (|z|\leq 1),$$ qu'en est-il pour le cas où $k < 1$? Quelle est l'inégalité analogue à $(*)$ pour une fonction entière de type exponentiel $\tau ?$ D'autre part, si on suppose que $P$ a tous ses zéros dans $|z|\geq k \, \, (k\geq 1),$ quelle est l'estimation de $|P'(z)|$ sur le cercle unité, en terme des quatre premiers termes de son développement en série entière autour de l'origine. Cette thèse constitue une contribution à la théorie analytique des polynômes à la lumière de ces questions. / Let P(z):=\sum_{\nu=0}^na_\nu z^{\nu}$ a polynomial of degree n and M:=\sup_{|z|=1}|P(z)|$. Without any additional restriction, we know that $|P '(z) | \leq Mn$ for $| z | \leq 1$ (Bernstein's inequality). Now if we assume that the zeros of the polynomial $P$ are outside the circle $| z | = k$, which improvement could be made to the Bernstein inequality? It is already known [{\bf \ref{Mal1}}] that in the case where $k \geq 1$, one has$$ (*) \qquad | P '(z) | \leq \frac{n}{1 + k} M \qquad (| z | \leq 1),$$ what would it be in the case where $k < 1$? What is the analogous inequality for an entire function of exponential type $\tau$? On the other hand, if we assume that $P$ has all its zeros in $| z | \geq k \, \, (k \geq 1),$ which is the estimate of $| P '(z) |$ on the unit circle, in terms of the first four terms of its Maclaurin series expansion. This thesis comprises a contribution to the analytic theory of polynomials in the light of these problems.

Dans cette thèse, nous avons présenté trois méthodes différentes pour l’énumération de sousréseauxparticuliers d’un réseau métabolique: les histoires métaboliques, les ensembles minimaux deprécurseurs et les organisations chimiques. Pour chacune de ces trois méthodes, nous avons présentédes résultats théoriques, et pour les deux premières, nous avons en outre fourni une illustration surcomment les appliquer afin d’étudier le comportement métabolique des organismes vivants. Les histoiresmétaboliques sont définies comme des graphes acycliques dirigés maximaux dont les ensemblesde sources et de cibles sont limités à un sous-ensemble des noeuds. La motivation initiale de cette définitionétait d’analyser des données expérimentales de métabolomique, mais la méthode a égalementété explorée dans un contexte différent. Les ensembles de précurseurs métaboliques sont des ensemblesminimaux de nutriments qui permettent de produire des métabolites d’intérêt. Nous présentons troisméthodes différentes pour l’énumération de tels ensembles minimaux de précurseurs, et nous illustronsleur application dans une étude des échanges métaboliques dans un système symbiotique. Les organisationschimiques sont des ensembles de métabolites qui à la fois sont fermés et s’auto-maintiennent,ce qui reflète des caractéristiques de stabilité dans le sens où aucun nouveau métabolite ne peut êtreproduit et qu’aucun des métabolites déjà présents dans le système ne peut disparaître. / In this thesis, we presented three different methods for enumerating special subnetworks containedin a metabolic network: metabolic stories, minimal precursor sets and chemical organisations. Foreach of the three methods, we gave theoretical results, and for the two first ones, we further providedan illustration on how to apply them in order to study the metabolic behaviour of living organisms.Metabolic stories are defined as maximal directed acyclic graphs whose sets of sources and targets arerestricted to a subset of the nodes. The initial motivation of this definition was to analyse metabolomicsexperimental data, but the method was also explored in a different context. Metabolic precursor setsare minimal sets of nutrients that are able to produce metabolites of interest. We present threedifferent methods for enumerating minimal precursor sets and we illustrate the application in a studyof the metabolic exchanges in a symbiotic system. Chemical organisations are sets of metabolites thatare simultaneously closed and self-maintaining, which captures some stability feature in the