Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La prédiction de connexions entre objets, basée soit sur une observation bruitée, soit sur une suite d'observations est un problème d'intérêt pour un nombre d'applications allant de la conception de système de recommandation en commerce électronique et réseaux sociaux jusqu'à l'inférence de réseaux en biologie moléculaire. Ce travail présente des formulations du problème de prédiction de lien, dans les cadres statique et temporel, comme un problème régularisé. Dans le scénario statique c'est la combinaison de deux normes bien connues, la norme L1 et la trace-norme qui permet de prédire les liens, alors que dans le cas dynamique, l'utilisation d'un modèle autoregressif sur des descripteurs linéaires permet d'améliorer la qualité de la prédiction. Nous étudierons la nature des solutions des problèmes d'optimisation à la fois en termes statistique et algorithmique. Des résultats empiriques encourageant mettent en évidence l'apport de la méthodologie adoptée. / Predicting connections among objects, based either on a noisy observation or on a sequence of observations, is a problem of interest for numerous applications such as recommender systems for e-commerce and social networks, and also in system biology, for inferring interaction patterns among proteins. This work presents formulations of the graph prediction problem, in both dynamic and static scenarios, as regularization problems. In the static scenario we encode the mixture of two different kinds of structural assumptions in a convex penalty involving the L1 and the trace norm. In the dynamic setting we assume that certain graph features, such as the node degree, follow a vector autoregressive model and we propose to use this information to improve the accuracy of prediction. The solutions of the optimization problems are studied both from an algorithmic and statistical point of view. Empirical evidences on synthetic and real data are presented showing the benefit of using the suggested methods.

La prophétesse Cassandre se revête d'emblée dans ses différentes manifestations contemporaines d'un caractère polymorphe. Nous avons voulu démontrer dans ce travail la modernité de son personnage en nous appuyant sur des traductions récentes des textes d'Homère, d'Eschyle, et d'Euripide et sur des créations originales où Cassandre tient un rôle significatif pour le déroulement de l'histoire. Ces textes dévoilent une figure de Cassandre par son statut de prophétesse et par sa parole légitime et non crue dont l'essence se déploie à partir de sa parole. Parole de Cassandre dont le fonctionnement s'organise sur une scène d'énonciation qui déplace les cadres habituels de la communication ; un énonciateur multiple, un rapport temporel achronique, un énoncé hyperréférentiel ou silencieux, un interlocuteur qui se situe dans un futur non encore advenu. Par ailleurs, la prophétesse dévoile un rapport à l'autre complexe : une impérative demande, haine et mépris, rejet de sa communauté, désir néanmoins de sauver les siens, de les avertir du danger pour les épargner. Avec les auteurs, Jean Giraudoux, Suzanne Dumarest-Dussauge et Eudes Labrusse, Cassandre dans le genre théâtrale, joue une parole en acte qui se présente comme une énigme à déchiffrer et qui enchaîne l'autre dans une obligation de répondre à ses demandes. Cassandre s'incarne entièrement dans sa voix, dans une réflexion métalinguistique, et dans les actes de sa parole et conséquents à sa parole : effet de vérité, d'inquiétude, d'avertissement. / The prophetess Cassandra is arrayed in the many contemporary manifestations of a polymorphous character. This thesis seeks to demonstrate the modern side of Cassandra, drawing on recent translations of Homer, Aeschylus and Euripides, and on original works in which Cassandra plays an important role in the story's development. These works reveal Cassandra through her role as a seer and through her valid yet veiled words, whose perplexing and disturbing meaning emerges. Cassandra's prophecy, delivered in a statement that breaks the standard framework of communication—a multifaceted speaker, a temporal and spiritual relationship, highly referential or abstract language, an interlocutor from a future that has not yet come to pass. There is a complexity to Cassandra's relationships—an urgent request, hate and disdain, rejection by her community, and the desire to save her people and deliver them from danger through her warnings. The works of Jean Giraudoux, Suzanne Dumarest-Dussauge and Eudes Labrusse bring Cassandra to life on the stage, where she presents a puzzle to be solved and imposes on others a duty to act on her prophesies. Cassandra finds her full expression in her voice, in a metalinguistic reflection, and in the act of prophecy and the actions that follow from it: the impact of truth, concern, warning. But she also embodies a reflection on the current nature of truth and the relationship between our language and truth: how to speak it, how to hear it, what it is, and how to find it.

Le but de l'étude est de comprendre et de prédire les performances de détection en phase gazeuse des capteurs chimiques à surface de matériaux sensibles. Les travaux ont porté sur des microbalances à quartz revêtues de polysiloxanes fonctionnalisés. Des mesures à l'équilibre, en exposant ces capteurs à différentes vapeurs organiques, ont mis en évidence la sélectivité des matériaux employés. Pour rationaliser ces résultats, les étapes impliquées dans la détection ont été examinées. Des mesures par PM-IRRAS ont permis de montrer la proportionnalité de la réponse vis-à-vis de la quantité d'analyte absorbé. Des affinités en phase condensée ont été déterminées par une nouvelle méthode par RMN d’études de mélanges sans solvant. L'application de cette méthode à des composés modèles a validé le calcul de l'enthalpie de mélange par l'approche de Hansen. Celle-ci permet également d’obtenir calculer les coefficients de Hansen des matériaux sensibles avec des méthodes de contributions de groupes. Enfin, sur ces résultats, un modèle numérique a été construit pour calculer a priori la réponse d'un capteur à partir de la formule chimique des composés sensible et de l'espèce détectée. / The aim of this study is to understand and model the responses of coated chemical sensors for gas phase detection. The work exposed here focuses on quartz crystal microbalance (QCM) coated with functionalized polysiloxanes. Measurements were carried with the QCM exposed to organic vapours when equilibrium was reached. It has been shown that selectivity depends on the material used. To understand that selectivity, each step involved in the detection has been investigated. First of all, with PM-IRRAS, we verified that the frequency shift was proportional to the amount of absorbed analyte. Then, affinity in liquid phase has been determined through a new methodology by NMR. It has also been used, on model system to prove the applicability of Hansen solubility coefficient to calculate mixing free enthalpy. For polymers, those coefficients have been determined using NMR combined with group contribution methods. Based on these descriptors, a numerical model has been built to calculate a priori the performance of a sensor based on, the chemical structure of the sensitive material and of the detected compound.

Les réseaux optiques passifs (PONs, Passive Optical Networks) représentant l’une des solutions les plus performantes du réseau d’accès FTTH ont été largement déployés par les opérateurs grâce à leur capacité d’offrir des services de très haut débit. Cependant, en raison de la dynamicité du trafic des différents clients, ces réseaux doivent s’appuyer sur un mécanisme efficace pour l’allocation de ressources, plus particulièrement dans le sens montant. Ce mécanisme est actuellement limité par la nature statique des paramètres SLA (Service Level Agreement). Ceci peut avoir une influence négative sur la qualité de service ressentie par les utilisateurs. L’objectif de cette thèse est de proposer une nouvelle architecture pour optimiser l’allocation de ressources dans les réseaux PON tout en agissant uniquement sur les paramètres SLA, désignés comme des paramètres gérables par l’opérateur. Des techniques de classification basées sur l’apprentissage automatique et la prédiction sont utilisées pour analyser le comportement des différents utilisateurs et déterminer leurs tendances de trafic. Un ajustement dynamique sur la base du concept autonomique de certains paramètres SLA est ensuite effectué afin de maximiser la satisfaction globale des clients vis-à-vis du réseau. / Passive Optical Network (PON) representing one of the most attractive FTTH access network solutions, have been widely deployed for several years thanks to their ability to offer high speed services. However, due to the dynamicity of users traffic patterns, PONs need to rely on an efficient upstream bandwidth allocation mechanism. This mechanism is currently limited by the static nature of Service Level Agreement (SLA) parameters which can lead to an unoptimized bandwidth allocation in the network. The objective of this thesis is to propose a new management architecture for optimizing the upstream bandwidth allocation in PON while acting only on manageable parameters to allow the involvement of self-decision elements into the network. To achieve this, classification techniques based on machine learning approaches are used to analyze the behavior of PON users and to specify their upstream data transmission tendency. A dynamic adjustment of some SLA parameters is then performed to maximize the overall customers’ satisfaction with the network.

La sélection des meilleurs candidats médicament se base sur des choix multiparamétriques réunissant l’efficacité potentielle, les caractéristiques ADME et le profil de sécurité des nouvelles entités chimiques. En ce sens, la prédiction précoce de la pharmacocinétique est élémentaire pour orienter les prises de décision et donner un cap pertinent aux projets. En raison de son rôle central dans le devenir des médicaments, la clairance métabolique médiée principalement par le foie est l’un des paramètres les plus importants. L’objectif de ce projet était d’améliorer la prédiction de la clairance en se concentrant notamment sur les molécules présentant une bonne stabilité métabolique et qui sont de ce fait encore difficiles à étudier. Les travaux menés dans cette thèse nous ont permis d’étoffer nos connaissances sur les modèles hépatiques in vitro et les méthodes d’extrapolation usuelles mais aussi de découvrir et de développer de nouvelles stratégies de prédiction. Nous nous sommes concentrés en profondeur sur la clairance métabolique et à tout ce qui impacte les prédictions. Le modèle de co-culture microorganisée (MPCC) HepatopacTM qui permet de stabiliser les hépatocytes humains sur plusieurs semaines a ainsi été identifié comme une alternative judicieuse aux modèles de routine lorsque les molécules ne peuvent pas être étudiées en culture 2D classique. L’étude de la fraction libre plasmatique et l’intégration de nouvelles hypothèses physiologiques telles que la théorie de « l’uptake facilité par l’albumine » ont également participé à améliorer les prédictions. Compte tenu des performances du modèle HepatopacTM, nous avons développé une approche innovante basée sur le spotting de précision afin de produire tous types de co-cultures microorganisées. Les co-cultures fabriquées grâce à cette technique démontrent que la méthode est robuste, accessible et simple à mettre en œuvre. Notre méthode de spotting a ensuite été utilisée pour faire évoluer le modèle MPCC et l’ouvrir à de nouvelles applications. / The selection of the best drug candidates is based on multiparametric choices combining the potential efficacy, ADME characteristics and the safety profile of the new chemical entities. In this sense, the early prediction of pharmacokinetic is essential to guide decision-making and provide a relevant course for projects. Because of its central role in drug disposition, metabolic clearance mediated primarily by the liver is one of the most important parameters. The objective of this project was to improve clearance prediction by focusing on low clearance compounds that are still difficult to study. This work allowed us to expand our knowledge on in vitro liver models and usual extrapolation methods but also to discover and develop new prediction strategies. We focused on metabolic clearance and all parameters that impact the predictions. Micropatterned co-cultures (MPCCs) of primary human hepatocytes (HepatopacTM), which stabilizes hepatocytes over several weeks, has been identified as a judicious alternative to routine models when the molecules cannot be studied in conventional monolayer culture. The study of plasma protein binding and the integration of new physiological hypothesis such as the "Albumin-Facilitated Uptake" also contributed to improve the predictions. Given the performance of the HepatopacTM model, we have developed an innovative approach using a digital dispensing system to spot collagen and produce all types of micropatterned co-cultures. Co-cultures manufactured by this technique demonstrate that the method is robust, accessible and easy to use. Our spotting method was used to evolve the MPCC model and explore new applications.

À l'origine de cette thèse, nous nous sommes intéressés à l'algorithme de tri TimSort qui est apparu en 2002, alors que la littérature sur le problème du tri était déjà bien dense. Bien qu'il soit utilisé dans de nombreux langages de programmation, les performances de cet algorithme n'avaient jamais été formellement analysées avant nos travaux. L'étude fine de TimSort nous a conduits à enrichir nos modèles théoriques, en y incorporant des caractéristiques modernes de l'architecture des ordinateurs. Nous avons, en particulier, étudié le mécanisme de prédiction de branchement. Grâce à cette analyse théorique, nous avons pu proposer des modifications de certains algorithmes élémentaires (comme l'exponentiation rapide ou la dichotomie) qui utilisent ce principe à leur avantage, améliorant significativement leurs performances lorsqu'ils sont exécutés sur des machines récentes. Enfin, même s'il est courant dans le cadre de l'analyse en moyenne de considérer que les entrées sont uniformément distribuées, cela ne semble pas toujours refléter les distributions auxquelles nous sommes confrontés dans la réalité. Ainsi, une des raisons du choix d'implanter TimSort dans des bibliothèques standard de Java et Python est probablement sa capacité à s'adapter à des entrées partiellement triées. Nous proposons, pour conclure cette thèse, un modèle mathématique de distribution non-uniforme sur les permutations qui favorise l'apparition d'entrées partiellement triées, et nous en donnons une analyse probabiliste détaillée / At first, we were interested in TimSort, a sorting algorithm which was designed in 2002, at a time where it was hard to imagine new results on sorting. Although it is used in many programming languages, the efficiency of this algorithm has not been studied formally before our work. The fine-grain study of TimSort leads us to take into account, in our theoretical models, some modern features of computer architecture. In particular, we propose a study of the mechanisms of branch prediction. This theoretical analysis allows us to design variants of some elementary algorithms (like binary search or exponentiation by squaring) that rely on this feature to achieve better performance on recent computers. Even if uniform distributions are usually considered for the average case analysis of algorithms, it may not be the best framework for studying sorting algorithms. The choice of using TimSort in many programming languages as Java and Python is probably driven by its efficiency on almost-sorted input. To conclude this dissertation, we propose a mathematical model of non-uniform distribution on permutations, for which permutations that are almost sorted are more likely, and provide a detailed probabilistic analysis

Dans le domaine du calcul haute performance, de nombreux programmes étalons ou benchmarks sont utilisés pour mesurer l’efficacité des calculateurs,des compilateurs et des optimisations de performance. Les benchmarks de référence regroupent souvent des programmes de calcul issus de l’industrie et peuvent être très longs. Le processus d’´étalonnage d’une nouvelle architecture de calcul ou d’une optimisation est donc coûteux.La plupart des benchmarks sont constitués d’un ensemble de noyaux de calcul indépendants. Souvent l’´étalonneur n’est intéressé que par un sous ensemble de ces noyaux, il serait donc intéressant de pouvoir les exécuter séparément. Ainsi, il devient plus facile et rapide d’appliquer des optimisations locales sur les benchmarks. De plus, les benchmarks contiennent de nombreux noyaux de calcul redondants. Certaines opérations, bien que mesurées plusieurs fois, n’apportent pas d’informations supplémentaires sur le système à étudier. En détectant les similarités entre eux et en éliminant les noyaux redondants, on diminue le coût des benchmarks sans perte d’information.Cette thèse propose une méthode permettant de décomposer automatiquement une application en un ensemble de noyaux de performance, que nous appelons codelets. La méthode proposée permet de rejouer les codelets,de manière isolée, dans différentes conditions expérimentales pour pouvoir étalonner leur performance. Cette thèse étudie dans quelle mesure la décomposition en noyaux permet de diminuer le coût du processus de benchmarking et d’optimisation. Elle évalue aussi l’avantage d’optimisations locales par rapport à une approche globale.De nombreux travaux ont été réalisés afin d’améliorer le processus de benchmarking. Dans ce domaine, on remarquera l’utilisation de techniques d’apprentissage machine ou d’´echantillonnage. L’idée de décomposer les benchmarks en morceaux indépendants n’est pas nouvelle. Ce concept a été aappliqué avec succès sur les programmes séquentiels et nous le portons à maturité sur les programmes parallèles.Evaluer des nouvelles micro-architectures ou la scalabilité est 25× fois plus rapide avec des codelets que avec des exécutions d’applications. Les codelets prédisent le temps d’exécution avec une précision de 94% et permettent de trouver des optimisations locales jusqu’`a 1.06× fois plus efficaces que la meilleure approche globale. / In high performance computing, benchmarks evaluate architectures, compilers and optimizations. Standard benchmarks are mostly issued from the industrial world and may have a very long execution time. So, evaluating a new architecture or an optimization is costly. Most of the benchmarks are composed of independent kernels. Usually, users are only interested by a small subset of these kernels. To get faster and easier local optimizations, we should find ways to extract kernels as standalone executables. Also, benchmarks have redundant computational kernels. Some calculations do not bring new informations about the system that we want to study, despite that we measure them many times. By detecting similar operations and removing redundant kernels, we can reduce the benchmarking cost without loosing information about the system. This thesis proposes a method to automatically decompose applications into small kernels called codelets. Each codelet is a standalone executable that can be replayed in different execution contexts to evaluate them. This thesis quantifies how much the decomposition method accelerates optimization and benchmarking processes. It also quantify the benefits of local optimizations over global optimizations. There are many related works which aim to enhance the benchmarking process. In particular, we note machine learning approaches and sampling techniques. Decomposing applications into independent pieces is not a new idea. It has been successfully applied on sequential codes. In this thesis we extend it to parallel programs. Evaluating scalability or new micro-architectures is 25× faster with codelets than with full application executions. Codelets predict the execution time with an accuracy of 94% and find local optimizations that outperform the best global optimization up to 1.06×.

L’objectif de cette thèse est la gestion de la QdS des systèmes publier/souscrire sur MANET. Ceci provoque un maintien permanent de la connectivité entre les parties communicantes du système. Plus précisément, les contributions de cette thèse, sont organisées autour de deux grands axes relatifs aux modules de monitoring et d’analyse de la QdS de ces systèmes dans un contexte ad-hoc. Ceci englobe les etapes de collecte des paramètres de QdS au cours du fonctionnement du système, et de détection des dégradations pouvant l’affecter.Contrairement à ce qui existe dans la littérature, notre module d’analyse, basé sur des méthodes statistiques, se base sur des seuils adaptatifs qui tiennent en comptes de la dynamicité du réseau et des changements affectant le contexte ad-hoc. En outre, le module d’analyse proposé offre à l’utilisateur une variété de choix entre une analyse réactive, proactive et hybride. Notre module permet aussi une localisation des pannes une fois détectées ou prédites. Des expérimentations menées à l’aide du simulateur Jist/Swans ont montré l’efficacité des modules developpés. De plus, une mesure des paramètres de performance du système avant et après introduction des modules développés a montré leur efficacité. Finalement, une étude de la complexité spatiale et temporelle du module analytique proposé a été réalisée. / Mobile ad-hoc networks (MANET) is a set of nodes, communicating meaning wireless channel without any centralized control. The main characteristic of MANET is the frequent mobility of its nodes leading to some dynamic changes of topology. Nodes mobility in such networks introduces possible disconnections between adjacent nodes, and more generally quality of service (QoS) degradation issues that do not fit well with QoS requirements of QoS sensitive applications. Publish/subscribe communicating system has been proposed at the middleware layer in order to communicate mobile entities in MANET. Such system is a decoupled interaction between publishers (or producers) and receivers (or consumers).Our goal in this thesis is to provide a QoS management for publish/subscribe systems when deployed on MANET while assuming a best effort flux at the routing layer. This thesis proposes an analytical model for latency aware publish/subscribe systems on mobile ad-hoc networks. The proposed approach combines both proactive and reactive statistical analysis.On the one hand, the reactive analysis, suitable for multimedia applications, detects failures by approximating latency series with Gumbel distribution. On the other hand, the proactive analysis, suitable for crisis management applications, forecasts failures occurrence relying on Auto Regression or Auto Regressive Integrated Moving Average Formulas. Finally, a hybrid analysis was proposed by dynamically switching from reactive to predictive forms of analysis whenever quality of service violations are noticed. In order to extract failure cause, we refer to the correlation method once failure was detected or predicted. Simulations done, using Jist/Swans simulator, under different scenariosproved the efficiency and accuracy of the proposed scheme.

Les milieux biologiques et alimentaires sont généralement des mélanges contenant un nombre élevé de constituants (eau, solvants organiques, solides dissous, gaz dissous, espèces ioniques, macromolécules). La prédiction des propriétés d’équilibre de tels milieux requiert l’utilisation d’un modèle thermodynamique entièrement prédictif. Ce modèle doit également permettre d’assurer la cohérence entre des données expérimentales et garantir la robustesse de la représentation simultanée des équilibres physiques (liquide-vapeur, solubilité, etc.) et chimiques (dissociation, oxydo-réduction, complexation, etc.). Le potentiel chimique est une donnée indispensable pour modéliser ces équilibres. Sa connaissance dépend de la prédiction de deux variables : l’enthalpie libre de formation dans un état de référence choisi, et le coefficient d’activité qui dépend aussi de l’état de référence choisi. Le modèle COSMO-RS est un excellent modèle de prédiction des coefficients d’activité très largement utilisé dans le domaine du génie chimique où on s’intéresse essentiellement à des molécules neutres. Ce travail de thèse a permis d’étendre les performances du modèle COSMO-RS au traitement des milieux biologiques et alimentaires dans lesquels on trouve systématiquement des électrolytes en solution (en plus des molécules neutres). Un nouvel outil utilisant les récentes avancées de la mécanique quantique a été développé pour prédire les propriétés de formation à l’état gaz. En combinant des concepts de la thermodynamique, de la mécanique quantique, de l’électrostatique, et de la physique statistique, il a été démontré qu’il est possible d’utiliser le modèle COSMO-RS pour faire la transition entre l’état gaz et la phase condensée. Partant de là, ce travail démontre qu’il est maintenant possible de traiter simultanément les équilibres physiques et chimiques et donc de prédire les propriétés physico-chimiques (aW, pH, Eh) dans les milieux biologiques et alimentaires par le modèle COSMO-RS. / Food and biological systems are generally multicomponent mixtures (including water, organic solvents, dissolved solids, dissolved gases, ionic species, macromolecules). The prediction of the equilibrium properties of such environments requires the use of a fully predictive thermodynamic model. This model must be able to ensure the consistency between experimental data and to ensure the robustness of the simultaneous representation of physical equilibria (liquid-vapour, solubility, etc.) and chemical equilibria (dissociation, redox, complexation, etc.). The chemical potential is an essential property for modelling such equilibria. Its determination depends on two variables: the Gibbs free energy of formation in a chosen reference state, and the prediction of the activity coefficient which also depends on the chosen reference state. The COSMO-RS model is an excellent model for predicting activity coefficients that is widely used in chemical engineering where the studied molecules are generally neutral. This PhD study enabled to extend the performance of the COSMO-RS model toward the treatment of food and biological systems where there are systematically electrolytes in solution (in addition to neutral molecules). A new tool based on the recent advances of quantum mechanics has been developed in order to predict gas phase formation properties. By combining concepts of thermodynamics, quantum physics, electrostatics and statistical physics, it has been demonstrated that it is possible to use the COSMO-RS model to ensure the transition between the gas phase and the condensed phase. In this context, this work demonstrates that it is possible to treat simultaneously physical and chemical equilibria and thus to predict physico-chemical properties (aW, pH, Eh) in food and biological systems using the COSMO-RS model.