背包問題是整數規劃中一個特殊的模式，雖然它可以運用一般整數規劃法則來處理， 但是由於它只含有一個限制，所以發展出更有效的法則也是可能的。在過去十幾年當 中，已發表出很多研究論文，這些研究結果已推動吾人對這問題作更進一步的探討， 並導出更有效的求解法則。 本文分六章共二十節，內容大致如下： （一）緒論。 （二）討論背包問題一些重要的求解法則及其性質與應用。 （三）討論陷縮背包問題（The collapsing knapsack problem ）之應用及求解法則 ，決定元由整數擴大為混合的情形（實數）。 （四）結論與建議。

On s'intéresse à la géométrie globale et asymptotique de certaines variétés riemanniennes non compactes. Dans une première partie, on étudie la topologie et la géométrie à l'infini des variétés riemanniennes à courbure (de Ricci) positive ayant un rapport asymptotique de courbure fini. On caractérise le cas non effondré via la notion de cône asymptotique et on donne des conditions suffisantes sur le groupe fondamental pour garantir un non effondrement. La seconde partie est dédiée à l'étude des solutions de Type III du flot de Ricci à courbure positive et aux solitons gradients de Ricci expansifs (points fixes de Type III) présentant une décroissance quadratique de la courbure. On montre l'existence et l'unicité des cônes asymptotiques de tels points fixes. On donne également des conditions suffisantes de nature algébrique et géométrique pour garantir une géométrie de révolution de tels solitons. Dans une troisième partie, on caractérise la géométrie des solitons gradients de Ricci stables à courbure positive et à croissance volumique linéaire. Puis, on s'intéresse au non effondrement des variétés riemanniennes de dimension trois à courbure de Ricci positive ayant un rapport asymptotique de courbure fini. / We study the global and asymptotic geometry of non-compact Riemannian manifolds. First, we study the topology and geometry at infinity of Riemannian manifolds with nonnegative (Ricci) curvature and finite asymptotic curvature ratio. We focus on the non-collapsed case with the help of asymptotic cones and we give sufficient conditions on the fundamental group to guarantee non-collapsing. The second part is dedicated to the study of (non-negatively curved) Type III Ricci flow solutions. We mainly analyze the asymptotic geometry of Type III self-similar solutions (expanding gradient Ricci soliton) with finite asymptotic curvature ratio. We prove the existence and uniqueness of their asymptotic cones. We also give algebraic and geometric sufficient conditions to guarantee rotational symmetry of such metrics. In the last part, we characterize the geometry of steady gradient Ricci solitons with nonnegative sectional curvature and linear volume growth. Finally, we study the non-collapsing of three dimensional Riemannian manifold with nonnegative Ricci curvature and finite asymptotic curvature ratio.

Among the wide range of remarkable experimentson dilute Bose-Einstein condensates has been the observed dynamics of attractive condensatesexhibiting collapse and subsequent explosion. For attractive condensates the collapse occurs when the number of atoms N becomes higher than a critical value Nc. After a collapse, the number of atoms N in the condensate is reduced so that for N below Nc A stable configuration is attained. By increasing the number of atoms in the condensate up to the point where N>Nc a further collapse is induced and so on, this process may be repeated and a series of collapses may be observed.In this work we investigate analytically the behavior of the collapsing condensate within the framework of a nonlinear Gross-Pitaevskii equation, suitable to describe the dynamics of the order parameter Ψ(r, t ) of a Bose-Einstein condensatemagnetically trapped in a harmonic three-dimensional potential.Two and three-body inelastic collisions which remove atoms from the condensate are included.By using a variational approach based on d’Alembert ́s principle and suitable for non-conservative systems wefindananalyticalsolutionforacollapsingBose-Einsteincondensate.We demonstrate that a Gaussianansatzcapturesremarkablywellthesequenceofimplosionand explosionobservedinattractivecondensates. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Entre o vasto leque de experiências notáveis em condensados de Bose-Einstein diluídos, foi observada a dinâmica de condensados atrativos exibindo colapso e subseqüente explosão. Para condensados atrativos, o colapso ocorre quando o número de átomos N torna-se maior que um valor crítico Nc'N>Nc. Após um colapso, o número de átomos no condensado é reduzido tal que, para N abaixo de Nc uma configuração estável é atingida. Aumentando o número de átomos no condensado até o ponto onde N>Nc outro colapso é induzido e, assim por diante, esse processo será repetido e uma série de colapsos pode ser observada. Neste trabalho, nós investigamos analiticamente o comportamento do condensado colapsante no âmbito de uma equação de Gross-Pitaevskii não-linear, apropriada para descrever a dinâmica do parâmetro de ordem Ψ(r, t ) de um condensado de Bose-Einstein magneticamente aprisionado em um potencial harmônico tridimensional. Colisões inelásticas de dois e três corpos que removem átomos do condensado são incluídas. Usando uma abordagem variacional baseada no princípio de D’Alembert e apropriada para sistemas não-conservativos nós encontramos uma solução analítica para o condensado de Bose-Einstein colapsante. Nós demonstramos que um ansatz Gaussiano captura notavelmente bem a seqüência de implosões e explosões observada em condensados atrativos.

Deep images for use in visual effects work during deep compositing tend to be very large. Quite often the files are larger than needed for their final purpose, which opens up an opportunity for optimizations. This research project is about finding methods for identifying redundant and excessive data use in deep images, and then approximate this data by resampling it and representing it using less data. Focus was on maintaining the final visual quality while optimizing the files so the methods can be used in a sharp production environment. While not being very successful processing geometric data, the results when optimizing volumetric data were very succesfull and over the expectations.

Generating all hexahedral meshes on arbitrary geometries has been an area of important research in recent history. Hexahedral meshes have advantages over tetrahedral meshes in structural mechanics because they provide more accurate results with fewer degrees of freedom. Many different approaches have been used to create all-hexahedral meshes. Grid-based, inside-out, or superposition meshing all refer to a similar meshing approach that is a very common mesh generation technique. Grid-based algorithms provide the ability to generate all hexahedral meshes by introducing a structured mesh that bounds the complete body modeled, marking hexahedra to define an interior and exterior mesh, manipulating the boundary region between interior and exterior regions of the structured mesh to fit the specific boundary of the body, and finally, discarding the exterior hexahedra from the given body. Such algorithms generally provide high quality meshes on the interior of the body yet distort element at the boundary in order to fill voids and match surfaces along these regions. The sculpting algorithm as presented here, addresses the difficulty in forming quality elements near boundary regions in two ways. The algorithm first finds more intelligent methods to define a structured mesh that conforms to the body to lessen large distortions to the boundary elements. Second, the algorithm uses collapsing templates to adjust the position of boundary elements to mimic the topology of the body prior to capturing the geometric boundary.

Ce mémoire de thèse est consacrée à l'étude des problèmes d'évolution où la dynamique est régi par l'opérateur de diffusion de sous-gradient. Nous nous intéressons à deux types de problèmes d'évolution. Le premier problème est régi par un opérateur local de type Leray-Lions avec un domaine borné. Dans ce problème, l'opérateur est maximal monotone et ne satisfait pas la condition standard de contrôle de la croissance polynomiale. Des exemples typiques apparaît dans l'étude de fluide non-Neutonian et aussi dans la description de la dynamique du flux de sous-gradient. Pour étudier le problème nous traitons l'équation dans le contexte de l'EDP non linéaire avec le flux singulier. Nous utilisons la théorie de gradient tangentiel pour caractériser l'équation d'état qui donne la relation entre le flux et le gradient de la solution. Dans le problème stationnaire, nous avons l'existence de la solution, nous avons également l'équivalence entre le problème minimisation initial, le problème dual et l'EDP. Dans l'équation de l'évolution, nous proposons l'existence, l'unicité de la solution. Le deuxième problème est régi par un opérateur discret. Nous étudions l'équation d'évolution discrète qui décrivent le processus d'effondrement du tas de sable. Ceci est un exemple typique de phénomènes auto-organisés critiques exposées par une slope critique. Nous considérons l'équation d'évolution discrète où la dynamique est régie par sous-gradient de la fonction d'indicateur de la boule unité. Nous commençons par établir le modèle, nous prouvons existence et l'unicité de la solution. Ensuite, en utilisant arguments de dualité nous étudions le calcul numérique de la solution et nous présentons quelques simulations numériques. / This thesis is devoted to the study of evolution problems where the dynamic is governed by sub-gradient diffusion operator. We are interest in two kind of evolution problems. The first problem is governed by local operator of Leray-Lions type with a bounded domain. In this problem, the operator is maximal monotone and does not satisfied the standard polynomial growth control condition. Typical examples appears in the study of non-Neutonian fluid and also in the description of sub-gradient flows dynamics. To study the problem we handle the equation in the context of nonlinear PDE with singular flux. We use the theory of tangential gradient to characterize the state equation that gives the connection between the flux and the gradient of the solution. In the stationary problem, we have the existence of solution, we also get the equivalence between the initial minimization problem, the dual problem and the PDE. In the evolution one, we provide the existence, uniqueness of solution and the contractions. The second problem is governed by a discrete operator. We study the discrete evolution equation which describe the process of collapsing sandpile. This is a typical example of Self-organized critical phenomena exhibited by a critical slop. We consider the discrete evolution equation where the dynamic is governed by sub-gradient of indicator function of the unit ball. We begin by establish the model, we prove existence and uniqueness of the solution. Then by using dual arguments we study the numerical computation of the solution and we present some numerical simulations.

<p>Minimum cycle mean (MCM) is an important concept in directed graphs. From clock period optimization, timing analysis to layout optimization, minimum cycle mean algorithms have found widespread use in VLSI system design optimization. With transistor size scaling to 10nm and below, complexities and size of the systems have grown rapidly over the last decade. Scalability of the algorithms both in terms of their runtime and memory usage is therefore important. </p> <p><br></p> <p>Among the few classical MCM algorithms, the algorithm by Young, Tarjan, and Orlin (YTO), has been particularly popular. When implemented with a binary heap, the YTO algorithm has the best runtime performance although it has higher asymptotic time complexity than Karp's algorithm. However, as an efficient implementation of YTO relies on data redundancy, its memory usage is higher and could be a prohibitive factor in large size problems. On the other hand, a typical implementation of Karp's algorithm can also be memory hungry. An early termination technique from Hartmann and Orlin (HO) can be directly applied to Karp's algorithm to improve its runtime performance and memory usage. Although not as efficient as YTO in runtime, HO algorithm has much less memory usage than YTO. We propose several improvements to HO algorithm. The proposed algorithm has comparable runtime performance to YTO for circuit graphs and dense random graphs while being better than HO algorithm in memory usage. </p> <p><br></p> <p>Minimum balancing of a directed graph is an application of the minimum cycle mean algorithm. Minimum balance algorithms have been used to optimally distribute slack for mitigating process variation induced timing violation issues in clock network. In a conventional minimum balance algorithm, the principal subroutine is that of finding MCM in a graph. In particular, the minimum balance algorithm iteratively finds the minimum cycle mean and the corresponding minimum-mean cycle, and uses the mean and cycle to update the graph by changing edge weights and reducing the graph size. The iterations terminate when the updated graph is a single node. Studies have shown that the bottleneck of the iterative process is the graph update operation as previous approaches involved updating the entire graph. We propose an improvement to the minimum balance algorithm by performing fewer changes to the edge weights in each iteration, resulting in better efficiency.</p> <p><br></p> <p>We also apply the minimum cycle mean algorithm in latency insensitive system design. Timing violations can occur in high performance communication links in system-on-chips (SoCs) in the late stages of the physical design process. To address the issues, latency insensitive systems (LISs) employ pipelining in the communication channels through insertion of the relay stations. Although the functionality of a LIS is robust with respect to the communication latencies, such insertion can degrade system throughput performance. Earlier studies have shown that the proper sizing of buffer queues after relay station insertion could eliminate such performance loss. However, solving the problem of maximum performance buffer queue sizing requires use of mixed integer linear programming (MILP) of which runtime is not scalable. We formulate the problem as a parameterized graph optimization problem where for every communication channel there is a parameterized edge with buffer counts as the edge weight. We then use minimum cycle mean algorithm to determine from which edges buffers can be removed safely without creating negative cycles. This is done iteratively in the similar style as the minimum balance algorithm. Experimental results suggest that the proposed approach is scalable. Moreover, quality of the solution is observed to be as good as that of the MILP based approach.</p><p><br></p>