Many aspects of open pit mine planning can be modelled as a combinatorial optimization problem. This thesis reviews some existing mine scheduling methods and some of their short comings. Many of the problems are related to the partially ordered knapsack problem with multiple knapsack constraints. This is a special case of a maximum directed cut problem with multiple knapsack constraints on the arcs in the cut.The major contribution of this thesis is the study of the directed cut polytopeand cone, which are the convex hull and positive hull of all directed cut vectors ofa complete directed graph, respectively. Many results are presented on the polyhedralstructure of these polyhedra. A relation between the directed cut polyhedraand undirected cut polyhedra is established that provides families of facet defininginequalities for the directed cut polyhedra from the undirected cut polyhedra.A polynomial time algorithm for optimizing over the undirected cut polytope isgiven for the special case of when an objective function has the same optimal valueon two relaxations, the rooted metric polytope and the metric polytope. Projectionsof the directed cut polytope onto the arc set of an arbitrary directed graph are researched.A method known as triangular elimination is extended from the undirectedcut context to a directed cut context. A complexity result proving that the problem of selecting a physically connected maximum value set of blocks from a 2D grid is NP-hard is given. In the mining literature such a grid would be called a bench.An implementation of a LP rounding algorithm known as pipage rounding isapplied to a pushback design problem. This simple and efficient technique producesresults within 6.4% of optimal for a real data set. / De nombreux aspects de la planification d'une mine à ciel ouvert peuvent être modélisés comme des problèmes d'optimisation combinatoire. La première partie de cette thèse passe en revue quelques méthodes de planification existantes dans la littérature et certaines de leurs lacunes. Plusieurs problèmes sont liés au "partially ordered knapsack (POK)" problème avec contraintes de type sac à dos. Il s'agit d'un cas particulier du problème de coupe maximale dans un graphe dirigé avec des contraintes de type sac-à-dos sur les arcs de la coupe.La contribution majeure de cette thèse est l'étude du cône et du polytope des coupes dirigées, lesquels sont respectivement l'enveloppe convexe et l'enveloppepositive de toutes les coupes d'un graphe dirigé complet.Plusieurs résultats sur la structure polyèdrale des ces polyèdres sont présentés.Une relation entre les polyèdres de coupes dirigées et les polyèdres de coupes non-dirigées est établie. Cette relation permet d'obtenir des familles de facettes définissant des inégalités valides pour les polyèdres de coupes dirigées à partir desinégalités valides et des facettes du polyèdre de coupes non-dirigées.Un algorithme polynomial pour le polytope des coupes non-dirigées est proposé dans le cas particulier d'une fonction objectif ayant la même valeur optimalepour deux relaxations, le polytope métrique enraciné et le polytope métrique. Les projections du polytope de coupes dirigées sur les arcs d'un graphe dirigé sont également étudiées. Une méthode de projection intitulée "élimination triangulaire" est généralisée du cas non-dirigé au cas dirigé.Le problème qui consiste à sélectionner d'une grille 2D un ensemble de sommets connectés de valeur maximale est également étudié. Dans le contexte des mines, les sommets sont les blocs et la grille 2D est un banc. Un résultat de complexité établissant la NP-complétude de ce problème est présenté. Un algorithme "pipage rounding" qui arrondit la solution de la relaxation linéaire a été implémenté pour résoudre le problème de conception de "pushbacks". Cet algorithme simple et efficace a été testé sur des données réelles et a permis d'obtenir des solutions très proches de la solution optimale (écart de 6.4% par rapport à des données réelles).

Mechanisms to share information from Mechanical Computer Assisted Design (MCAD) to simulation model have been demonstrated using various approaches. However, in all cases the information sharing is unidirectional - from the MCAD to Multi-Body Systems (MBS) simulation - which lacks the bidirectional mapping required in a concurrent engineering context where both models need to develop in parallel while remaining consistent.We present a modelling library and a model mapping that permits and encourages parallel development of the mechanical assembly in both the MBS simulation and MCAD environments while supporting both bidirectional initial full transfer and incremental updates. Furthermore, with the adopted approach and with a careful selection of the simulation language, MCAD parts can be extended with non-mechanical behaviour in the simulation tool. / Des mécanismes pour partager l'information entre un modèle CAD et un modèle de simulation ont été démontrés utilisant divers approches. Pourtant, dans tous les cas, le partage d'information était unidirectionnel - allant du modèle CAD vers le modèle de simulation - donc ne possédant pas les qualités bidirectionnelles nécessaires dans le contexte de l'ingénierie collaborative ou les modèles doivent rester consistantes en permanence.Nous présentons notre librairie de modélisation et de transformations entre modèles qui permettent et encouragent le développement parallèle de l'assemblage mécanique dans les deux environnements de simulation de conception. Notre approche supporte le partage et la synchronisation des deux modèles dans les deux sens et de façon incrémentale si nécessaire. En complément, avec l'approche que nous avons adopté, les modèles mécaniques peuvent être associés a des modèles comportementales non mécanique dans l'outil de simulation.

The least-used direction (LUD) rule is one of a class of largely unanalyzed pivot rules - the history-based rules. History-based pivot rules guide the progression of edge following algorithms like the Simplex method. This thesis investigates the problem of finding an exponential length LUD path on a particular kind of digraph known as an acyclic unique sink orientation of a hypercube (AUSO). In addition, a survey of six well-known history-based pivot rule and examples to illustrate their independence is given. The Fibonacci construction is introduced as a potential way of creating families of AUSOs that allows for exponential LUD paths. The most straight-forward application of this technique is unsuccessful, but there is room for more exploration. An exponential lower bound is given for thenumber of times the least-used direction is used by a Hamiltonian path following the related history-based Zadeh's rule. This result shows that the number of times each direction is used grows at a similar rate and is thus relatively balanced. / La règle de least-used direction (LUD) fait parti de la grande classe des règles pivots history-based. Ceux-ci guident la progression des algorithmes de détection des contours, tel que la méthode Simplex. Ce mémoire examine le problème de la recherche de chemin LUD de longueur exponentielle dans un graphe acyclique dirigé à bloc récepteur unique (acyclic unique sink orientation - AUSO) dans les hypercubes. De plus, une vue d'ensemble de six règles pivots history-based ainsi que des exemples sont fournis pour illustrer leurs indépendances. La structure Fibonacci est présentée comme une possibilité de créer des familles de graphe acyclique dirigé à bloc récepteur unique permettant des chemins LUD de longueurs exponentielles. Exécuter cette technique de façon simple s'avère infructueuse, par contre cela nous laisse la place à plus d'amples explorations. Une borne inférieure exponentielle est fournie pour le nombre de fois que LUD est présent dans un chemin Hamiltonian selon la règle history-based Zadeh. Les résultats obtenus démontrent que le nombre de fois utilisé par chaque direction augmente à une fréquence semblable et est donc relativement équilibré.

Comparative approaches are fundamental to analyzing genomic sequence data, and therefore touch almost all aspects of bioinformatics research. The core tasks of sequence alignment, phylogenetic inference, and ancestral sequence reconstruction must be performed as accurately as possible in order for their results to be useful. Due to the difficult combinatorial nature of these problems, as well as the necessary assumptions made by the models upon which they are based, even the best methods to solve them will make errors. These errors will impact and potentially bias any downstream analysis performed on sequence data. The overall objective of my thesis is to explore algorithmic techniques to quantify sources of error in comparative sequence analysis, and ensure that they are minimized. This work is divided into three results: 1) a novel context-sensitive indel model for more accurate sequence alignment, 2) an algorithm to efficiently compute the expected error of ancestral sequence reconstruction, and 3) an approximation algorithm with tight error bound guarantees for an application of phylogenetic analysis that arises in conservation biology. / Les approches comparatives sont fondamentales pour l'analyse des données de séquences génomiques, et donc touchent presque tous les aspects de la echerche en bioinformatique. Les principales missions de l'alignement de séquences, l'inférence phylogénétique et la reconstruction des séquences ancestrales, doivent être effectuées le plus précisément possible afin que leurs résultats soient utiles. En raison de la nature combinatoire difficile de ces problèmes, ainsi que les hypothèses nécessaires faites par les modèles sur lesquels elles sont fondées, même les meilleures méthodes pour les résoudre font des erreurs. Ces erreurs affectent potentiellement toute analyse de effectuées en aval sur les données de séquence. L'objectif général de ma thèse est d'explorer les techniques algorithmiques pour quantifier les sources d'erreur dans l'analyse comparative des séquences, et de s'assurer qu'elles sont réduites au minimum. Ce travail est divisé en trois résultats: 1) un modèle indel sensible au contexte pour un alignement plus précis des séquences, 2) un algorithme pour calculer efficacement l'erreur attendue de la reconstruction séquence ancestrale, et 3) un algorithme d'approximation avec garanties d'erreur pour un problème d'analyse phylogénétique qui se pose en biologie de la conservation.

The cortical surface in humans is comprised of several folds which are juxtaposed together to form a biologically meaningful pattern. For many biological reasons, the geometry of this pattern changes in time: folds get longer, wider and deeper. The relationship between the shape of cortical folds and biological factors such as gender and aging can be studied using statistical shape analysis techniques.An essential step in this process is the matching of the folds on different cortical surfaces. Fold matching can be done using a scalar field describing the relative depth of folds on a surface. The match between folds is established by comparing the scalar field of each surface. The first contribution of this thesis is to define a function as a solution to a sparse linear system, which characterizes the relative depth of the folds on a surface. This thesis shows that the accuracy of surface registration is improved by 11% using the proposed scalar field as a shape descriptor to register surfaces. The second contribution of this thesis is to propose a statistical method to detect directional differences in the shape of folds on the cerebral cortex. A directional difference can be, for example, a difference in its length in the direction parallel to it. Previous statistical tests for shape analysis only determine if two folds are different locally, and they typically average across multiple local directions. The method proposed in this thesis provides directional information to better understand the factors that relate to differences in fold shape.The third contribution of this thesis is the development of anisotropic diffusion kernels on surfaces to highlight shape differences that affect fold shape. Diffusion of scalar and tensor fields is used in statistical shape analysis to increase the detection power of statistical tests. However, diffusion also decreases the capacity of statistical tests to localize significant shape differences. Prior to this thesis, diffusion kernels used on surfaces were isotropic in shape and blurred information over multiple folds. Anisotropic diffusion kernels, on the other hand, can increase statistical power by concentrating diffusion along fold orientation and highlighting the variability in shape that is localized to specific folds.In summary, this thesis provides tools that increase the amount of information that can be gathered about the morphometry of the cerebral cortex using statistical shape analysis. The accuracy of surface registration is increased, the analysis of the underlying deformation field allows us to determine if a difference in shape affects fold length or width and diffusion kernels produce statistical results that highlight the variability in shape that is localized to specific folds. / La surface corticale du cerveau humain contient plusieurs plis, ou sillons, qui juxtaposés forment un motif cohérent. Pour plusieurs raisons biologiques, la géométrie du motif formé par les plis corticaux change avec le temps: les plis deviennent plus longs, plus ouverts et plus creux. La relation entre la forme des plis corticaux et plusieurs facteurs biologiques, tels que le vieillissement et le genre du sujet peut être étudiée en utilisant des méthodes statistiques d'analyse de formes.Une étape essentielle de l'analyse statistique de la forme du cerveau humain est la mise en correspondance des sillons de surfaces corticales différentes. La mise en correspondance peut se faire à l'aide d'un champ scalaire décrivant la profondeur relative des sillons sur une surface. La correspondance entre les sillons est établie en comparant le champ scalaire respectif de chaque surface. La première contribution de cette thèse est de décrire un champ scalaire rapide à calculer et qui caractérise la profondeur relative des sillons sur une surface. L'utilisation du champ scalaire proposé dans cette thèse a amené une amélioration de 11% de la précision de la mise en correspondance. La seconde contribution de cette thèse est une méthode statistique permettant de localiser des différences directionnelles dans la forme des plis. Par exemple, un sillon plus long aura une différence de longueur dans la direction parallèle au sillon. La méthode statistique présentée dans cette thèse permet de déterminer la direction selon laquelle la forme des sillons diffère le plus. Les autres méthodes statistiques ne pouvant que déterminer si localement deux sillons sont différents, la méthode proposée dans cette thèse procure davantage d'information pour comprendre la forme des sillons.La troisième contribution de cette thèse est de proposer une méthode de diffusion anisotrope sur la surface corticale afin de faire ressortir les différences qui affectent la forme des sillons. La diffusion de champs scalaires et de tenseurs est utilisée afin d'augmenter la capacité de détection des tests statistiques. Par contre, la diffusion réduit aussi la capacité de localisation des méthodes statistiques. Avant cette thèse, la diffusion sur la surface se faisait de façon isotrope et l'information sur la forme des sillons était diffusée sur une région couvrant plusieurs sillons. La diffusion anisotrope permet d'augmenter le pouvoir de détection des tests statistiques sans pour autant réduire la capacité de mettre en évidence une différence dans la forme qui est localisée à un sillon spécifique.Le résultat de cette thèse est qu'il est possible d'analyser la forme des sillons du cortex cérébral en utilisant une méthode générale d'analyse de déformations. La précision de la mise en correspondance a été augmentée, l'analyse des champs de déformations permet de déterminer si une différence affecte la longueur ou la largeur du sillon et la diffusion utilisée pour augmenter la puissance des tests statistiques permet de mettre en évidence des différences dans la forme qui est localisée à un sillon spécifique.

With the advancement of technologies, earth observation data could be obtained with finer spatial and spectral resolution. However, the increasing volume and complexity of those high resolution data presents new challenges in geographic information system (GIS) and remote sensing (RS) research, such as heterogeneous distributed data handling, efficient parallel data processing algorithms, and easy manageability of the underlying cyberinfrastructure, new collaboration model and lower computation costs. Geospatial cloud computing is leveraged in GIS/RS research to address the challenges of heterogeneous distributed data and its processing. Although the early experience has proven it is a great success to utilize cloud computing in GIS/RS research, the manageability of the cyberinfrastructure cannot be neglected. To be manageable, I argue that cloud computing must handle domain specific problems in GIS/RS, manage privacy of data, ease of use, and be inexpensive. In thesis I propose IHC3—integrated hybrid cloud computing cyberinfrastructure for advanced scalability and easy manageability in GIS/RS cyberinfrastructure research. IHC3 is designed to seamlessly integrate the computing resource of local hardware with public cloud providers, and it can dynamically adjust the boundary of private and public cloud with respect to the variable workload. A set of functionalities to simplify the image data processing, analysis, and visualization in GIS/RS research are also implemented in IHC3. I use MODIS data re-projection experiment with IHC3 to evaluate IHC3's performance, and compare the execution time and computation costs with single desktop, private cloud and Amazon EC2. The experiment proves that IHC3 is an effective platform for GIS/RS research, and it can offload the onerous system administration work from GIS/RS scientists, providing them with a tool for enhancing their research. / Avec l'avancement des technologies, des données d'observation de la terre pourrait être obtenu avec une résolution spatiale et spectrale plus fine. Toutefois, le volume et la complexité croissantes de ces données à haute résolution présente de nouveaux défis en matière de système d'information géographique (SIG) et télédétection (RS) de recherche, tels que la manipulation des données distribuées hétérogènes, parallèle efficace des algorithmes de traitement de données, la gestion facile des cyberinfrastructure sous-jacente, nouveau modèle de collaboration et de coût de calcul inférieur. Géospatiales cloud computing ont un effet de levier en matière de SIG / RS de recherche pour relever les défis de données hétérogènes distribués et son traitement. Bien que les premières expériences ont prouvé qu'il est un grand succès d'utiliser le cloud computing dans les SIG / RS recherche, la gestion de l'cyberinfrastructure ne peut pas être négligée. Pour être gérable, je soutiens que le cloud computing doit traiter les problèmes domaine spécifique en matière de SIG / RS, de gérer la confidentialité des données, la facilité d'utilisation, et d'être peu coûteux. Ainsi, dans cet article je propose IHC3 intégrée cyberinfrastructure hybrides de cloud computing pour l'évolutivité de pointe et maniabilité facile dans la recherche cyberinfrastructure SIG / RS. IHC3 s'intègre de façon transparente les ressources de calcul du local de matériel avec les fournisseurs de cloud public, et il pourrait ajuster dynamiquement la limite de cloud privé et public à l'égard de la charge de travail variable. Un ensemble de fonctionnalités pour simplifier le traitement des données d'image, l'analyse et la visualisation de SIG / RS de recherche sont également mis en œuvre dans IHC3. Je utilise des données MODIS re-projection expérimenter avec IHC3 pour évaluer la performance IHC3, et de comparer les temps d'exécution et les coûts de calcul avec le bureau unique, nuage privé et Amazon EC2. L'expérience prouve que IHC3 est une plateforme efficace pour la SIG / RS de recherche, et il peut décharger le travail du système onéreux administration de SIG / RS scientifiques, en leur fournissant un outil pour l'amélioration de leurs recherches.

MATLAB is a popular language for scientific and numerical programming. Despite its popularity, there are few active rojects providing open tools for MATLAB related compiler research. This thesis provides the McLAB Static Analysis Framework, McSAF, the goal of which is to simplify the development of new compiler tools for MATLAB. The McLAB project was started in order to develop such tools in the hopes of attracting further research. The goal of the project is to provide an extensible compiler toolkit for MATLAB and scientific programming. It is intended to explore the compilation challenges unique to MATLAB and to explore new language features that could help scientific programmers be more productive. One piece of functionality that is particularly important for compiler research is the ability to perform static analysis. Without the information provided by static analyses, program transformations and optimizations, and automated programmer feedback would not be possible. In order to make the development of static analyses simpler, this thesis contributes a framework for creating static analyses for the MATLAB language. This framework is intended to make writing analyses easier by providing core functionality and API for developing such analyses. It also aims to make analysis development easier by providing an intermediate representation called McLAST, which provides simpler syntax and explicitly exposes some of MATLAB's semantics. In order to give analysis writers a head start, some example analyses are provided. These include simple analyses intended to demonstrate the use of the framework, and some more complicated analyses that provide basic semantic information about MATLAB programs. In addition to the framework making development of analyses simpler, McSAF is also designed to be extended to new language features. Not only can the framework be extended, but existing analyses can also be extended. This allows work that was previously done for analyzing MATLAB code to be applied to future language extensions. / MATLAb est un langage de programmation science et numérique utilisé autant en industrie que dans le milieu académique. Malgré cette popularité, peu de project de rercherhe on été entreprise dans le but de produire une suite de compilation pour MATLAB. Cette thèse contribue le McLAB Static Analysis Framework, McSAF, qui a l'objectif de simplifier le développement des nouveaux outils de compilation pour MATLAB. Le projet McLAB fait suite à ce manque, dans l'espoir d'attiser les recherches sur ce sujet. L'objectif principale ce résume au développent d'une trousse de compilation extensible pour MATLAB et les langage de programmation pour science. Le projet est motivé par des défis de compilation unique à MATLAB, et par l'exploration de nouvelles structures syntaxical améliorant l'expérience de programmation scientifique. L'une des fonctionnalité cher au domaine de la compilation est l'habilité a performer des analyses statique de programme. Sans ces informations que nous procures l'analyse statique, une grande partie des transformations et autres optimisations désiré lors du processus de compilation ne serait pas possible. Pour rendre la développent des analyses statique plus simple, cette thèse contribue un cadre pour créer des analyses statique pour le langage MATLAB. L'objectif de ce cadre est de rendre la programmation des analyses plus simple en fournissant les fonctionnalités de base et une API pour développer de telles analyses. Un autre objectif est de rendre le développent des analyses plus simple en fournissant une représentation intermédiaire, \mclast, qui fourni une syntaxe plus simple est qui expose les sémantiques de MATLAB. Pour aider les écrivains d'analyse, quelques exemples d'analyse sont fournis. En plus, quelques analyses utiles sont également fournis. Ces analyses fournissent des informations de base reliée à les sémantiques de MATLAB. Ils ont des application partout dans le projet. L'objectif final du cadre est d'être extensible. Le framework doit fonctionner avec des nouvelles structure de langue. Sa veut dire que les programmeur peuvent créer des nouvelles analyses pour ces extension, et que les analyses qui existaient pour le langage de base, peut être adapter aux nouvelles structure.

Numerous techniques mine change data captured in software archives to assist software engineering efforts. These change-based approaches typically analyze change sets -- groups of co-committed changes -- under the assumption that the development work represented by change sets is both meaningful and related to a single change task. However, we have found that change sets often violate this assumption by containing changes that we consider to be non-essential, or less likely to be representative of the kind of meaningful software development effort that is most interesting to typical change-based approaches. Furthermore, we have found many change sets addressing multiple subtasks -- groups of isolated changes that are related to each other, but not to other changes within a change set. Information mined from such change sets has the potential for interfering with the analyses of various change-based approaches. We propose a catalog of non-essential changes and describe an automated technique for detecting such changes within version histories. We used our technique to conduct an empirical investigation of over 30000 change sets capturing over 25 years of cumulative development activity in ten open-source Java systems. Our investigation found that between 3% and 26% of all modified code lines and between 2% and 16% of all method updates consisted entirely of non-essential modifications. We further found that eliminating such modifications reduces the amount of false positive recommendations that would be made by an existing association rule miner. These findings are supported by a manual evaluation of our detection technique, in which we found that our technique falsely identifies non-essential method updates in only 0.2% of all cases. These observations should be kept in mind when interpreting insights derived from version repositories. We also propose a formal definition of "subtasks" and present an automated technique for detecting subtasks within change sets. We describe a new benchmark containing over 1800 manually classified change sets drawn from seven open-source Java systems. We evaluated our technique on the benchmark and found that the technique classifies single- and multi-task change sets with a precision of 80% and a recall of 24%. In contrast, the current "default strategy" of assuming all change sets are single-task classifies single- and multi-task change sets with a precision of 95% and a recall of 0%. We further characterized the performance of our technique by manually assessing its false classifications. We found that in most cases (78%), false classifications made by our technique can be further refined to produce useful recommendations for change-based approaches. Our observations should aid future change-based seeking to derive more precise representations of the changes they analyze. / De nombreuses techniques de génie logiciel exploitent l'information stockée dans des systèmes de gestion de versions. Ces techniques analysent généralement des groupes de changements (ou change sets) sous l'hypothèse que le travail de développement contenus dans ces change sets est à la fois pertinent et relié à une seule tâche. Nous avons constaté que les change sets violent souvent cette hypothèse lorsqu'ils contiennent des changements que nous considérons comme non-essentiels, c'est-à-dire, non-représentatif des changements normalement associés au développement de logiciel. Par ailleurs, nous avons trouvé de nombreux change sets qui contiennent plusieurs sous-tâches -- des groupes de changements isolés qui sont reliés les uns aux autres, mais pas à d'autres changements du même change set. L'information extraite de change sets contenants des changements non-essentiels ou des changements reliés à plusieurs sous-tâches peut interférer avec les diverses techniques qui exploitent des systèmes de gestion de versions. Nous proposons un catalogue de modifications non-essentielles et une technique automatisée pour détecter de tels changements dans les systèmes de gestion de versions. Nous avons utilisé notre technique pour mener une étude empirique de plus de 30,000 change sets dans dix logiciels libres en Java. Notre étude a révélé que entre 3% et 26% de toutes les lignes de code modifiés et entre 2% et 16% de toutes les méthodes modifiées sont modifiés seulement par des modifications non-essentielles. Nous avons également constaté que l'élimination de telles modifications réduit la quantité de fausses recommandations qui seraient faites par un analyse de type "associtation rule mining." Ces conclusions sont appuyées par une évaluation manuelle de notre technique de détection, par laquelle nous avons constaté que notre technique identifie faussement des méthodes non-essentielles dans seulement 0,2% des cas. Ces observations devraient être tenues en compte dans l'interprétation des résultats d'analyse de données contenues das des systèmes de gestion de versions. Nous proposons aussi une définition formelle de "sous-tâches" et présentons une technique automatisée pour détecter les sous-tâches dans les change sets. Nous décrivons un benchmark contenant plus de 1800 change sets tirées de sept systèmes Java. Nous avons évalué notre technique sur cette référence et avons trouvé que la technique classifie des change sets mono-tâche et multi-tâche avec une précision de 80% et un rappel de 24%. En revanche, la "stratégie par défaut" qui assume que tous les change sets sont mono-tâches classifie les change sets avec une précision de 95% et un rappel de 0%. Nous avons également caractérisé la performance de notre technique en évaluant manuellement ses classifications erronées. Nous avons constaté que dans la plupart des cas (78%), les classifications fausses faites par notre technique peuvent être améliorées pour produire des recommandations utiles.

An exponential growth in internet usage and penetration amongst the general population has led to an ever increasing demand for e-commerce applications and other internet-based services. E-commerce applications must provide high levels of service that include reliability, low response times and scalability. Most e-commerce applications follow a multi-tier architecture. As they are highly dynamic and data-intensive, the database is often a bottleneck in the whole system as most systems deploy multiple application servers in the replicated application tier, while only deploying a single database as managing a replicated database is not a trivial task. Hence, in order to achieve scalability, caching of data at the application server is an attractive option.In this thesis, we develop effective load balancing and caching strategies for read-only transaction workloads that help scaling multi-tier architectures and improve their performance. Our strategies have several special features. Firstly, our strategies take into account statistics about the objects of the cache, such as access frequency. Secondly, our algorithms that generate the strategies, despite being object-aware, are generic in nature, and thus, not limited to any specific type of applications. The main objective is to direct a request to an appropriate application server so that there is a high probability that the objects required to serve that request can be accessed from the cache, avoiding a database access. We have developed a whole suite of strategies, which differ in the way they assign objects and requests to application servers. We use distributed caching so as to make better utilization of the aggregate cache capacity of the application servers. Experimental results show that our strategies are promising and help to improve performance. / Une croissance exponentielle de l'utilisation d'Internet et sa pénétration dans la population générale ont conduit à une demande toujours croissante d'applications de commerce électronique et d'autres services basés sur l'internet. Les applications de commerce électronique doivent fournir des niveaux élevés de services qui comprennent la fiabilité, un court temps de réponse et de la variabilité dimensionnelle. La plupart des applications de commerce électronique suivent une architecture multi-niveau. Comme elles sont très dynamiques et possèdent une forte intensité de données, la base de données est souvent un goulot d'étranglement dans le système en entier comme la plupart des systèmes déploient des serveurs d'applications multiples dans l'application tierce reproduite. D'un autre côté, le déploiement d'une base de données unique pour la gestion d'une base de données répliquée n'est pas une tâche simple. Ainsi, afin de parvenir à une variabilité dimensionnelle, la mise en cache des données au serveur d'applications est une option attrayante.Dans cette thèse, nous développons un équilibrage de charge efficace et des stratégies de mise en cache qui aident à échelonner les architectures multi-niveaux et à améliorer leurs performances. Nos stratégies ont plusieurs caractéristiques particulières. Premièrement, nos stratégies prennent en compte les statistiques sur les objets de la mémoire cache, comme la fréquence d'accès. Deuxièmement, nos algorithmes qui génèrent les stratégies, tout en étant conscients des objets, sont de nature générique, et donc, ne se limitent pas à un type spécifique d'applications. L'objectif principal est de diriger une requête au serveur d'applications approprié afin qu'il y ait une forte probabilité que les objets requis pour servir cette demande puissent être consultés à partir de la mémoire cache, évitant un accès à la base de données. Nous avons développé toute une série de stratégies qui différent dans leur façon d'assigner des objets et des requêtes aux serveurs d'applications. Nous utilisons une mise en cache distribuée de manière à mieux utiliser la capacité totale de la mémoire cache des serveurs d'applications. Les résultats expérimentaux montrent que nos stratégies sont prometteuses et permettent d'améliorer les performances.

We present a real-time, physically based simulation method for animating high-resolution elastic deformations with a focus on haptic interaction. To achieve interactive rates without losing accuracy, the reduced material stiffness matrix is precomputed by removing the equations that correspond to the internal nodes of the system. In addition, we employ linear modal analysis to precompute the natural vibration modes of the system. We introduce a deformation-coupling technique in order to achieve the reduced dynamic behaviour while keeping the high-resolution local deformations. During real-time simulation, the high-spatial-frequency static deformations are coupled with the low-spatial-frequency dynamics, by projecting the reduced coordinate deformations onto an orthogonal basis constructed from natural vibration modes. To explore the implications of the coupling system, we describe different integration techniques to time-step the reduced dynamic solution in addition to evaluating the force feedback. Moreover, we show how we handle multiple contact points for non-sticky materials. To improve the contact-handling procedure, we employ our sliding technique to include friction. We compare our proposed method to the previously existing techniques in terms of run-time complexity and deformation properties using 3D meshes embedded in finite elements. / Nous présentons une méthode de simulation temps réel conforme aux lois de la physique pour animer des déformations élastiques à haute résolution, tout en portant une attention particulière aux interactions haptiques. Pour obtenir un résultat permettant une interaction temps réel sans perte de précision, la matrice réduite de rigidité du matériau est précalculée en excluant les équations correspondant aux noeuds internes du système. De plus, nous avons recours à l'analyse modale linéaire pour pré-calculer les modes de vibration naturelle du système. Nous proposons une technique de couplage des déformations afin d'obtenir le comportement à dynamique réduite recherché tout en préservant les propriétés des déformations locales à haute résolution. Lors de la simulation temps réel, les déformations statiques à haute fréquence spatiale sont couplées à la dynamique spatiale réduite à basse fréquence en projetant les déformations en coordonnées réduites sur une base orthogonale construite à partir des modes de vibration naturelle. Afin d'explorer l'impact du système de couplage, nous décrivons différentes techniques d'intégration pour avancer la solution de dynamique réduite dans le temps tout en évaluant le retour de force haptique. De plus, nous détaillons notre approche pour la gestion de points de contact multiples pour des matériaux non-adhésifs ainsi que notre méthode pour la gestion du glissement. Nous comparons la méthode que nous avançons aux techniques existantes en termes de complexité du temps d'exécution et en termes des propriétés de déformation, et ce en utilisant un maillage 3D intégré à un système à éléments finis.