Uma revisão dos algoritmos e conjuntos de instâncias presentes na literatura do Problema da Mochila com Repetições (PMR) é apresentada nessa dissertação de mestrado. Os algoritmos e conjuntos de instâncias usados são brevemente descritos nesse trabalho, afim de que o leitor tenha base para entender as discussões. Algumas propriedades bem conhecidas e específicas do PMR, como a dominância e a periodicidade, são explicadas com detalhes. O PMR é também superficialmente estudado no contexto de problemas de avaliação gerados pela abordagem de geração de colunas aplicada na relaxação contínua do Bin Packing Problem (BPP) e o Cutting Stock Problem (CSP). Múltiplos experimentos computacionais e comparações são realizadas. Para os conjuntos de instâncias artificiais mais recentes da literatura, um simples algoritmo de programação dinâmica, e uma variante do mesmo, parecem superar o desempenho do resto dos algoritmos, incluindo aquele que era estado-da-arte. O modo que relações de dominância é aplicado por esses algoritmos de programação dinâmica têm algumas implicações para as relações de dominância previamente estudadas na literatura. O autor dessa dissertação defende a tese de que a escolha dos conjuntos de instâncias artificiais definiu o que foi considerado o melhor algoritmo nos trabalhos anteriores. O autor dessa dissertação disponibilizou publicamente todos os códigos e conjuntos de instâncias referenciados nesse trabalho. / A review of the algorithms and datasets in the literature of the Unbounded Knapsack Problem (UKP) is presented in this master's thesis. The algorithms and datasets used are brie y described in this work to provide the reader with basis for understanding the discussions. Some well-known UKP-speci c properties, such as dominance and periodicity, are described. The UKP is also super cially studied in the context of pricing problems generated by the column generation approach applied to the continuous relaxation of the Bin Packing Problem (BPP) and Cutting Stock Problem (CSP). Multiple computational experiments and comparisons are performed. For the most recent arti cial datasets in the literature, a simple dynamic programming algorithm, and its variant, seems to outperform the remaining algorithms, including the previous state-of-the-art algorithm. The way dominance is applied by these dynamic programming algorithms has some implications for the dominance relations previously studied in the literature. In this master's thesis we defend that choosing sets of arti cial instances has de ned what was considered the best algorithm in previous works. We made available all codes and datasets referenced in this master's thesis.

Neste trabalho, apresenta-se o resultado da existência de soluções fracas em domínios não-limitados para as equações de Navier-Stokes, desde que a fronteira satisfaça uma certa condição de regularidade que é necessária para a obtenção de estimativas em domínios não-limitados semelhantes à desigualdade de Poincaré em domínios limitados. Apresenta-se o desenvolvimento detalhado do método de Galerkin para as equações de Navier-Stokes em domínios não-limitados com cálculo explícito de várias constantes e com forças externas não nulas. Apresenta-se dois teoremas fundamentais: um fornecendo condições para existência de soluções do problema estacionário e o outro fornecendo condições para existência de soluções do problema não-estacionário. / In the work it is presented results of existence of weak solutions in unbounded doroains for the Navier-Stokes equations. The roain condition to obtain similar results as those for bounded doroains; for e."'Carople the Poincaré inequality; is a certain condition of regularity at the boundary of the doroain. It is presented the detailed developroent of the Galerkin roethod for the t.he Navier-Stokes equations in unbounded doroains ~vith the explicit calculat ions of many constants and ''rith non null externai forces. It is presented two basic theorern: one presenting condition for the existence of solutions for the stationary problem and the other presenting conditions for existence of solution for the non stationary problem.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / O Teorema Espectral à um dos teoremas mais famosos da Analise Funcional, principalmente pelo grande nÃmero de versÃes dadas ao mesmo. Existem versÃes para operadores limitados, ilimitados, autoadjuntos, compactos, em espacos de dimensÃo finita ou infinita. A versÃo geral do teorema foi provada independentemente por Stone e Neumann no perÃodo de 1929-1932, mas outras provas surgiram ao longo dos anos. A prova contida neste trabalho à de Edward Brian Davies(1994), o qual conseguiu, na prova da versÃo do teorema para cÃlculos funcionais, explicitar uma fÃrmula para f(H) (onde H à um operador nÃo-limitado e autoadjunto) para uma grande classe de funÃÃes e nÃo apenas mostrar a existÃncia do mesmo. A principal idÃia foi originalmente dada por Heler e Strojand(1989) e utiliza em sua prova teoremas conhecidos como a FÃrmula Integral de Cauchy Generalizada, Teorema da DivergÃncia, Stone Weierstrass, Teorema de Liouville, alÃm de fatos conhecidos da teoria dos operadores lineares em espacos de Hilbert. / The Spectral Theorem is one of the most famous theorems in Functional Analysis,particularly because of the large number of proofs given to it. There are versions for bounded operators, unbounded operators, self-adjoints operators, compacts, on finite-dimensional spaces, on finnite-dimensional spaces. The general version was proved by Stone and Weierstrass during the period 1929-1932, but another proofs emerged over the years. The proof in this monography was given by Edward Brian Davies(1994), which gives an explicity formula for the functional calculus f(H) (where H is an self-adjoint operator) and not only proof its existence. The main idea was originally given by Heler and Strojand(1989) and in its proofs it used well-knows theorems like Stokes' Theorem,Cauchy's Integral Formula Generalized, Stone-Weierstrass, Liouville's Theorem, besides facts of the theory of linear operators on Hilbert spaces.

Neste trabalho, apresenta-se o resultado da existência de soluções fracas em domínios não-limitados para as equações de Navier-Stokes, desde que a fronteira satisfaça uma certa condição de regularidade que é necessária para a obtenção de estimativas em domínios não-limitados semelhantes à desigualdade de Poincaré em domínios limitados. Apresenta-se o desenvolvimento detalhado do método de Galerkin para as equações de Navier-Stokes em domínios não-limitados com cálculo explícito de várias constantes e com forças externas não nulas. Apresenta-se dois teoremas fundamentais: um fornecendo condições para existência de soluções do problema estacionário e o outro fornecendo condições para existência de soluções do problema não-estacionário. / In the work it is presented results of existence of weak solutions in unbounded doroains for the Navier-Stokes equations. The roain condition to obtain similar results as those for bounded doroains; for e."'Carople the Poincaré inequality; is a certain condition of regularity at the boundary of the doroain. It is presented the detailed developroent of the Galerkin roethod for the t.he Navier-Stokes equations in unbounded doroains ~vith the explicit calculat ions of many constants and ''rith non null externai forces. It is presented two basic theorern: one presenting condition for the existence of solutions for the stationary problem and the other presenting conditions for existence of solution for the non stationary problem.

O objetivo central desta tese é demonstrar a existência de uma estrutura regenerativa visível para cadeias de alcance variável não limitadas. Também apresentamos um algoritmo de identificação de seqüências de instantes de regeneração que converge quase certamente quando o tamanho da amostra diverge. / Our main aim is prove the existence of a regeneration scheme in unbounded variable length chains. We present an algorithm to identify sequences of regeneration times which converges almost surely as the sample length.

The aim of this work is to provide an introduction into the theory of infinite dimensional stochastic processes. The thesis contains the paper A class of infinite dimensional stochastic processes with unbounded diffusion written at Linköping University during 2012. The aim of that paper is to take results from the finite dimensional theory into the infinite dimensional case. This is done via the means of a coordinate representation. It is shown that for a certain kind of Dirichlet form with unbounded diffusion, we have properties such as closability, quasi-regularity, and existence of local first and second moment of the associated process. The starting chapters of this thesis contain the prerequisite theory for understanding the paper. It is my hope that any reader unfamiliar with the subject will find this thesis useful, as an introduction to the field of infinite dimensional processes.

This thesis is concerned with the numerical simulation of high Reynolds number, three-dimensional, incompressible flows in open domains. Many problems treated in Computational Fluid Dynamics (CFD) occur in free space: e.g., external aerodynamics past vehicles, bluff bodies or aircraft; shear flows such as shear layers or jets. In observing all these flows, we can remark that they are often unsteady, appear chaotic with the presence of a large range of eddies, and are mainly dominated by convection. For years, it was shown that Lagrangian Vortex Element Methods (VEM) are particularly well appropriate for simulating such flows. In VEM, two approaches are classically used for solving the Poisson equation. The first one is the Biot-Savart approach where the Poisson equation is solved using the Green's function approach. The unbounded domain is thus implicitly taken into account. In that case, Parallel Fast Multipole (PFM) solvers are usually used. The second approach is the Vortex-In-Cell (VIC) method where the Poisson equation is solved on a grid using fast grid solvers. This requires to impose boundary conditions or to assume periodicity. An important difference is that fast grid solvers are much faster than fast multipole solvers. We here combine these two approaches by taking the advantages of each one and, eventually, we obtain an efficient VIC-PFM method to solve incompressible flows in open domain. The major interest of this combination is its computational efficiency: compared to the PFM solver used alone, the VIC-PFM combination is 15 to 20 times faster. The second major advantage is the possibility to run Large Eddy Simulations (LES) at high Reynolds number. Indeed, as a part of the operations are done in an Eulerian way (i.e. on the VIC grid), all the existing subgrid scale (SGS) models used in classical Eulerian codes, including the recent "multiscale" models, can be easily implemented.

This thesis is concerned with the numerical simulation of high Reynolds number, three-dimensional, incompressible flows in open domains. Many problems treated in Computational Fluid Dynamics (CFD) occur in free space: e.g., external aerodynamics past vehicles, bluff bodies or aircraft; shear flows such as shear layers or jets. In observing all these flows, we can remark that they are often unsteady, appear chaotic with the presence of a large range of eddies, and are mainly dominated by convection. For years, it was shown that Lagrangian Vortex Element Methods (VEM) are particularly well appropriate for simulating such flows. In VEM, two approaches are classically used for solving the Poisson equation. The first one is the Biot-Savart approach where the Poisson equation is solved using the Green's function approach. The unbounded domain is thus implicitly taken into account. In that case, Parallel Fast Multipole (PFM) solvers are usually used. The second approach is the Vortex-In-Cell (VIC) method where the Poisson equation is solved on a grid using fast grid solvers. This requires to impose boundary conditions or to assume periodicity. An important difference is that fast grid solvers are much faster than fast multipole solvers. We here combine these two approaches by taking the advantages of each one and, eventually, we obtain an efficient VIC-PFM method to solve incompressible flows in open domain. The major interest of this combination is its computational efficiency: compared to the PFM solver used alone, the VIC-PFM combination is 15 to 20 times faster. The second major advantage is the possibility to run Large Eddy Simulations (LES) at high Reynolds number. Indeed, as a part of the operations are done in an Eulerian way (i.e. on the VIC grid), all the existing subgrid scale (SGS) models used in classical Eulerian codes, including the recent "multiscale" models, can be easily implemented.

Made available in DSpace on 2015-03-26T13:45:33Z (GMT). No. of bitstreams: 1 texto completo.pdf: 346839 bytes, checksum: cab5395001fcc113256f79ba4e365ce8 (MD5) Previous issue date: 2010-02-26 / In this work we study two class of elliptic problems modeled on unbounded domains. The study of these class of problems is relevant not only in applied mathematics, but also in nonlinear analysis. In the these problems, since the domain is unbounded, there is a lack of compactness of the Sobolev embedding, bringing some difficults to show the convergence of the Palais-Smale sequence. To solve this difficulty we work in a subspace of the usual Sobolev space where we can recover some compactness result. The solutions are obtained by Lagrange multiplier. We give another proof of results in [6] due to Wei-Yue Ding and Wei-Ming Ni, who used to solve The Mountain Pass Theorem and a priori estimates. The results of our study are due to Habao Su, Zhi-Qiang Wang and Michel Willem. / Neste trabalho, estudamos duas classes de problemas elípticos modeladas em domínios ilimitados. O estudo dessas classes de problemas e relevante não só no campo da matemática aplicada, mas também na área de análise não linear. Nesses problemas, como o domínio é ilimitado, há a perda de compacidade da “imersão" de Sobolev, dificultando a convergência da sequência de “soluções" (sequência de Palais Smale). Essa dificuldade é contornada trabalhando num subespaço do espaço de Sobolev usual onde se recupera a compacidade utilizando resultados de imersão. As soluções são obtidas via multiplicadores de Lagrange. Apresentamos uma outra maneira de resolver um problema em [6], devido a Wei-Yue Ding e Wei-Ming Ni, que utilizaram na solução o Teorema do Passo da Montanha e estimativas a priori. Os resultados de nosso estudo são devidos a Habao Su, Zhi-Qiang Wang e Michel Willem.

Nous nous intéressons dans ce mémoire à des équations d'évolution associées aux fonctionnelles de Ginzburg-Landau, de nature parabolique. Notre but est de décrire le comportement temporel de la limite des solutions quand un petit paramètre de pénalisation tend vers 0.Dans le premier chapitre, nous retraçons de manière synthétique l'étude remarquable due à Bethuel, Orlandi et Smets sur l'équation de Ginzburg-Landau parabolique en dimension 2 : l'évolution des points vortex est gouvernée par le flot gradient de la fonctionnelle de Kirchoff-Onsager modifié par un terme de drift; elle est régulière hors des temps de collision ou de séparation de vortex ;ces phénomènes sont soumis à la conservation du degré local et à la dissipation d'énergie.Dans le second chapitre, nous considérons le problème de Cauchy pour des systèmes d'équations paraboliques semi-linéaires. Motivés par l'exemple des vortex, nous construisons, pour des nonlinéarités défocalisantes, des solutions globales de l'équation intégrale associée ayant des données initiales non bornées en espace (croissant comme exp(x^2)). Dans le cas de nonlinéarités focalisantes, nous montrons un phénomène d'explosion instantanée.Dans le troisième chapitre, nous revenons à l'équation de Ginzburg-Landau parabolique en dimension quelconque. Nous remplaçons la borne sur l'énergie de Bethuel, Orlandi et Smets, par une borne locale en espace, qui permet de traiter des configurations générales de vortex sans avoir recours aux « vortex évanescents ». Nous étendons leur analyse, et montrons des résultats de décomposition de l'énergie renormalisée, et du mouvement par courbure moyenne de la mesure d'énergie concentrée. / We are interested in this thesis in evolution equations related to the Ginzburg-Landau functionals, of parabolic nature. Our goal is to describe the temporal behavior of limiting solutions as a small penalisation parameter tends to 0.In the first chapter, we retrace in a synthetic way the remarkable study by Bethuel, Orlandi and Smets on the parabolic Ginzburg-Landau equation in dimension 2 : the evolution of point vortices is governed by the gradient flow of the Kirchoff-Onsager functionnal modified by a drift term ; it is smooth away from the merging and splitting times ; these phenomenon are subject to conservation of the local degree and energy dissipation.In the second chapter, we consider the Cauchy problem for systems of semi-linear parabolic equations. Motivated by the example of the vortices, we construct, for defocusing nonlinearities, global solutions to the associated integral equation with intial data unbounded in space (allowed to grow like exp(x^2)). In the case of focusing nonlinearities, we show a phenomenon of instantaneous blow-up.In the third chapter, we go back to the parabolic Ginzburg-Landau equation. We replace the energy bound of Bethuel, Orlandi et Smets by a local-in-space bound on the energy. This allows to consider general configurations of vortices without the help of « vanishing vortices ». We extend their analysis, and show various results of decomposition of the renormalized energy, and that the concentrated energy moves according to the mean curvature flow.