Tesi sul tema "Probabilities – Computer simulations"

Thesis (M.P.H.)--Georgia State University, 2007.
Title from file title page. Russ Toal, committee chair; Michael Eriksen, Valerie Hepburn, committee members. Electronic text (102 p. : ill. (some col.)) : digital, PDF file. Description based on contents viewed Mar. 26, 2008. Includes bibliographical references (p. 71-73).

Orientadores: Siome Klein Goldenstein, Jacques Wainer
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-22T23:53:33Z (GMT). No. of bitstreams: 1 Coelho_RenatoSchattanPereira_M.pdf: 864445 bytes, checksum: 8f57902047a23925af4b81fa0d7f3188 (MD5) Previous issue date: 2013
Resumo: O trânsito é um problema cada vez maior nas cidades, consumindo recursos e agravando a poluição; em São Paulo perdem-se cerca de R$33 bilhões por ano por causa do trânsito. Neste trabalho de mestrado desenvolvemos um sistema que une as áreas de simulação de multidões e planejamento probabilístico para otimizar semáforos de tempo fixo. Essas duas áreas apresentam algoritmos que permitem soluções eficientes para os problemas, mas a sua aplicação ainda depende largamente da intervenção de especialistas no problema a ser estudado, seja descrevendo o problema de planejamento probabilístico, seja interpretando os dados devolvidos pelo simulador. Nosso sistema diminui essa dependência ao utilizar autômatos celulares para simular o tráfego e gerar informações que são então utilizadas para descrever o problema de planejamento probabilístico. Com isso podemos: (i) reduzir a necessidade de coleta de dados, que passam a ser gerados pelo simulador e (ii) produzir bons planos para o controle de semáforos de tempo fixo sem que seja necessária a intervenção de especialistas para a análise dos dados. Nos dois testes realizados a solução proposta pelo sistema diminuiu o tempo médio de percurso em 18:51% e 13:51%, respectivamente
Abstract: Traffic is an ever increasing problem, draining resources and aggravating pollution. In Sao Paulo, for instance, financial losses caused by traffic represent a sum of about R$33 billions a year. In this work we've developed a system that puts together the areas of Crowd Simulation and Probabilistic Planning to optimize fixed time traffic lights. Although both areas present good algorithms their use is limited by their reliance on specialists, whether to describe the probabilistic planning problem or to analyze the data produced by the simulations. Our approach contributes to minimize this dependence by using cellular automata simulations to generate the data that is used to describe the probabilistic planning problem. This allows us to: (i) reduce the amount of data collection, since the data is now generated by the simulator and (ii) produce good policies for fixed time traffic light control without the intervention of specialists to analyze the data. In the two tests performed the solution proposed by the system was able to reduce travel times by 18:51% and 13:51%, respectively
Mestrado
Ciência da Computação
Mestre em Ciência da Computação

Cette th`ese se concentre sur des bases th´eoriques utiles pour l'analyse d'algorithmes et de protocoles
pour des syst`emes r´epartis modernes. Deux caract´eristiques importantes des mod`eles pour
ces syst`emes sont les probabilit´es et la mobilit´e typ´ee : des probabilit´es peuvent ˆetre utilis´ees pour
quantifier des comportements incertains ou impr´evisibles, et des types peuvent ˆetre utilis´es pour
garantir des comportements sˆurs dans des syst`emes mobiles. Dans cette th`ese nous d´eveloppons
des techniques alg´ebriques et des techniques bas´ees sur les types pour l'´etude comportementale des
processus probabilistes et mobiles.

Dans la premi`ere partie de la th`ese nous ´etudions la th´eorie alg´ebrique d'un calcul de processus
qui combine les comportements non-d´eterministe et probabiliste dans le mod`ele des automates probabilistes
propos´es par Segala et Lynch. Nous consid´erons diverses ´equivalences comportementales
fortes et faibles, et nous fournissons des axiomatisations compl`etes pour des processus `a ´etats finis,
limit´ees `a la r´ecursion gard´ee dans le cas des ´equivalences faibles.

Dans la deuxi`eme partie de la th`ese nous ´etudions la th´eorie alg´ebrique du -calcul en pr´esence
des types de capacit´es, qui sont tr`es utiles dans les calculs de processus mobiles. Les types de
capacit´es distinguent la capacit´e de lire sur un canal, la capacit´e d'´ecrire sur un canal, et la capacit´e
de lire et d'´ecrire `a la fois. Ils introduisent ´egalement une relation de sous-typage naturelle et
puissante. Nous consid´erons deux variantes de la bisimilarit´e typ´ee, dans leurs versions retard´ees
et anticip´ees. Pour les deux variantes, nous donnons des axiomatisations compl`etes pour les termes
ferm´es. Pour une des deux variantes, nous fournissons une axiomatisation compl`ete pour tous les
termes finis.

Dans la derni`ere partie de la th`ese nous d´eveloppons des techniques bas´ees sur les types pour
v´erifier la propri´et´e de terminaison de certains processus mobiles. Nous fournissons quatre syst`emes
de types pour garantir cette propri´et´e. Les syst`emes de types sont obtenus par des am´eliorations
successives des types du -calcul simplement typ´e. Les preuves de terminaison utilisent des techniques
employ´ees dans les syst`emes de r´e´ecriture. Ces syst`emes de types peuvent ˆetre utilis´es pour
raisonner sur le comportement de terminaison de quelques exemples non triviaux : les codages des
fonctions r´ecursives primitives, le protocole pour coder le choix s´epar´e en terme de composition
parall`ele, une table de symboles implement´ee comme une chaˆıne dynamique de cellules.

Ces r´esultats ´etablissent des bases pour une future ´etude de mod`eles plus avanc´es qui peuvent
combiner des probabilit´es avec des types. Ils soulignent ´egalement la robustesse des techniques
alg´ebriques et de celles bas´ees sur les types pour le raisonnement comportemental.

Contrairement aux modèles déterministes, le déroulement d'un modèle stochastique est conditionné par la réalisation de variables aléatoires. L'utilisation de hasard permet d'approcher un résultat le plus souvent incalculable de manière déterministe. En contrepartie, il est nécessaire d'estimer les paramètres des distributions associées aux quantités aléatoires en sortie du modèle stochastique. Ce calcul requiert l'exécution de multiples réplications indépendantes de la même expérience et de ce fait, d'une importante quantité de calcul. Toutes les simulations stochastiques comportent par conception un aspect naturellement parallèle. Elles représentent ainsi une des applications phares pour l'utilisation d'environnements de calculs distribués permettant de partager de la puissance de calcul à l'échelle mondiale, appelée grille de calcul. Bien que 50% des cycles des plus gros supercalculateurs de la planète soient consommés par des calculs stochastiques, les techniques de génération parallèle de nombres pseudoaléatoires sont méconnues. Il existe de ce fait un risque bien réel de produire et de publier des résultats de simulations stochastiques erronés. Cette thèse présente l'état de l'art des méthodes pour la distribution des réplications de simulations stochastiques et contribue à leur développement. Elle propose ainsi des méthodes novatrices permettant d'assurer une traçabilité dans le processus complexe de distribution de simulations stochastiques. Elle expose enfin des applications dans les domaines de l'imagerie médicale nucléaire et des simulations environnementales totalisant plus de 70 années de calcul sur un ordinateur séquentiel.

On définit le concept de plage d'appui d'un échantillon aléatoire, les plages d'appui étant certaines parties de l'enveloppe convexe pouvant coïncider avec l'enveloppe complète. On établit des formules générales pour l'espérance du nombre de sommets ou du nombre de cotes d'une plage d'appui quelconque, ainsi que l'espérance de sa longueur. Ces formules sont ensuite calculées dans le cas d'une loi normale dans le plan, d'une loi uniforme dans un polygone convexe, puis d'une loi uniforme dans une courbe convexe lisse. Des simulations informatiques permettent finalement d'étudier les vitesses de convergence vers les résultats asymptotiques précédemment trouvés (dans le début de cette thèse ainsi que dans d'autres travaux), et d'obtenir des estimations plus fines pour la moyenne, la variance et la loi du nombre de sommets de l'enveloppe convexe.

Actuellement, les choix relatifs à la gestion des sites potentiellement pollués s'appuient, notamment,
sur une évaluation des risques pour l'homme et l'environnement. Cette évaluation est effectuée à l'aide de modèles qui simulent le transfert de polluant depuis une source de pollution vers une cible vulnérable, pour différents scénarii d'exposition. La sélection des valeurs des paramètres de ces modèles s'appuie autant que possible sur les données recueillies lors des investigations de terrain (phase de diagnostic de site). Or pour des raisons de délais et de coûts, l'information recueillie lors de cette phase de diagnostic est toujours incomplète; elle est donc entachée d'incertitude. De même, les modèles de transferts et d'exposition présentent également des incertitudes à intégrer dans les procédures. Cette notion globale d'incertitude doit être prise en compte dans l'évaluation du risque pour que les résultats soient utiles lors la phase décisionnelle.

L'incertitude sur les paramètres peut avoir deux origines. La première provient du caractère aléatoire de l'information due à une variabilité naturelle résultant de phénomènes stochastiques. On parle alors d'incertitudes de variabilité ou d'incertitudes stochastiques. La seconde est liée au caractère imprécis de l'information lié à un manque de connaissance et qui résulte par exemple d'erreurs systématiques lors de mesures ou d'avis d'experts.
On parle alors d'incertitudes épistémiques. Dans le calcul de risque, ces deux notions sont souvent confondues alors qu'elles devraient être traitées de manière différente.

L'incertitude en évaluation des risques a surtout été appréhendée dans un cadre purement probabiliste.
Cela revient à supposer que la connaissance sur les paramètres des modèles est toujours de nature aléatoire (variabilité). Cette approche consiste à représenter les paramètres incertains par des distributions de probabilité uniques et à transmettre l'incertitude relative à ces paramètres sur celle du risque encouru par la cible, en appliquant en général la technique dite Monte Carlo. Si cette approche est bien connue, toute la difficulté tient à une définition cohérente des distributions de probabilité affectées aux paramètres par rapport à la connaissance disponible. En effet dans un contexte d'évaluation des risques liés à l'exposition aux polluants, l'information dont on dispose concernant certains paramètres est souvent de nature imprécise. Le calage d'une distribution de probabilité unique sur ce type de
connaissance devient subjectif et en partie arbitraire.

L'information dont on dispose réellement est souvent plus riche qu'un intervalle mais moins riche qu'une distribution de probabilité. En pratique, l'information de nature aléatoire est traitée de manière rigoureuse par les distributions de probabilité classiques. Celle de nature imprécise est traitée de manière rigoureuse par des familles de distributions de probabilité définies au moyen de paires de probabilités cumulées hautes et basses ou, à l'aide de théories plus récentes, au moyen de distributions de possibilité (aussi appelées intervalles flous) ou encore au moyen d'intervalles aléatoires utilisant les fonctions de croyance de Dempster-Shafer.

Un des premiers objectifs de ce travail est de promouvoir la cohérence entre la manière dont on représente la connaissance sur les paramètres
des modèles du risque et la connaissance dont on dispose réellement. Le deuxième objectif est de proposer différentes méthodes pour propager l'information de nature aléatoire et l'information de nature imprécise à travers les modèles du risque tout en essayant de tenir compte des dépendances entre les paramètres. Enfin, ces méthodes alternatives ont été testées sur des cas synthétiques puis sur des cas réels simplifiés, notamment pour proposer des moyens de présenter les résultats pour une phase décisionnelle:
- Calcul de dose : Transfert d'un polluant radioactif (le strontium) depuis le dépôt jusqu'à
l'homme, au travers de la consommation d'un aliment (le lait de vache).
- Risque toxique après un déversement accidentel de trichloréthylène (TCE) au dessus d'une nappe d'eau (modèle semi analytique).

- Risque pour la santé liée aux sols pollués par des retombées de plomb.

Ce travail se compose de deux parties relevant d'applications industrielles différentes.
La première traite d'une antenne spatiale réseau active.
Il faut d'abord calculer les lois d'alimentation pour satisfaire les contraintes de rayonnement. Nous transformons un problème avec de nombreux minima locaux en un problème d'optimisation convexe, dont l'optimum est le minimum global du problème initial, en utilisant le principe de conservation de l'énergie.
Nous résolvons ensuite un problème d'optimisation topologique: il faut réduire le nombre d'éléments rayonnants (ER). Nous appliquons une décomposition en valeurs singulières à l'ensemble des modules optimaux relaxés, puis un algorithme de type gradient topologique décide les regroupements entre ER élémentaires.

La deuxième partie porte sur une simulation type boîte noire d'un accident chimique.
Nous effectuons une étude de fiabilité et de sensibilité suivant un grand nombre de paramètres (probabilités de défaillance, point de conception, et paramètres influents). Sans disposer du gradient, nous utilisons un modèle réduit.
Dans un premier cas test nous avons comparé les réseaux neuronaux et la méthode d'interpolation sur grille éparse Sparse Grid (SG). Les SG sont une technique émergente: grâce à leur caractère hiérarchique et un algorithme adaptatif, elles deviennent particulièrement efficaces pour les problèmes réels (peu de variables influentes).
Elles sont appliquées à un cas test en plus grande dimension avec des améliorations spécifiques (approximations successives et seuillage des données).
Dans les deux cas, les algorithmes ont donné lieu à des logiciels opérationnels.

Ce manuscrit de thèse présente une méthode innovante brevetée pour la détection de comportements collectifs. En utilisant des procédés de fusion sur les données issues d'un réseau multi-capteurs, les récents systèmes de surveillance obtiennent les séquences d'observations des personnes surveillées. Ce bas niveau d'évaluation de la situation a été mesuré insuffisant pour aider les forces de sécurité lors des événements de foule. Afin d'avoir une plus haute évaluation de la situation dans ces environnements asymétriques, nous proposons une approche multi-agents qui réduit la complexité du problème par des agents sur trois niveaux - macro, méso et micro - d'observations. Nous utilisons un nouvel état relatif dans les approches de l'état de l'art pour nous permettre la détection, en temps réel, des groupes, de leurs comportements, objectifs et intentions. Dans le cadre de projets européens, nous avons utilisé un serious game simulant une foule dans des scénarios asymétriques. Les résultats montrent un meilleur accord avec les prédictions théoriques et une amélioration significative des travaux précédents. Le travail présenté ici pourrait être utilisé dans de futures études de détection de comportements multi-agents et pourrait un jour aider à résoudre les problèmes liés aux événements catastrophiques de foules incontrôlables.

On s'intéresse à la construction et l'estimation - à partir d'observations incomplètes - de modèles de variables aléatoires à valeurs réelles sur un graphe. Ces modèles doivent être adaptés à un problème de régression non standard où l'identité des variables observées (et donc celle des variables à prédire) varie d'une instance à l'autre. La nature du problème et des données disponibles nous conduit à modéliser le réseau sous la forme d'un champ markovien aléatoire, choix justifié par le principe de maximisation d'entropie de Jaynes. L'outil de prédiction choisi dans ces travaux est l'algorithme Belief Propagation - dans sa version classique ou gaussienne - dont la simplicité et l'efficacité permettent son utilisation sur des réseaux de grande taille. Après avoir fourni un nouveau résultat sur la stabilité locale des points fixes de l'algorithme, on étudie une approche fondée sur un modèle d'Ising latent où les dépendances entre variables réelles sont encodées à travers un réseau de variables binaires. Pour cela, on propose une définition de ces variables basée sur les fonctions de répartition des variables réelles associées. Pour l'étape de prédiction, il est nécessaire de modifier l'algorithme Belief Propagation pour imposer des contraintes de type bayésiennes sur les distributions marginales des variables binaires. L'estimation des paramètres du modèle peut aisément se faire à partir d'observations de paires. Cette approche est en fait une manière de résoudre le problème de régression en travaillant sur les quantiles. D'autre part, on propose un algorithme glouton d'estimation de la structure et des paramètres d'un champ markovien gaussien, basé sur l'algorithme Iterative Proportional Scaling. Cet algorithme produit à chaque itération un nouveau modèle dont la vraisemblance, ou une approximation de celle-ci dans le cas d'observations incomplètes, est supérieure à celle du modèle précédent. Cet algorithme fonctionnant par perturbation locale, il est possible d'imposer des contraintes spectrales assurant une meilleure compatibilité des modèles obtenus avec la version gaussienne de Belief Propagation. Les performances des différentes approches sont illustrées par des expérimentations numériques sur des données synthétiques.

Ces travaux s'intéressent à l'estimation de la fiabilité des évacuateurs de crues vannés. Le comportement fiabiliste de ces systèmes hydrauliques dépend à la fois d'événements aléatoires discrets, mais aussi de l'évolution d'une variable déterministe continue : ce sont des systèmes dynamiques hybrides. Pour ces systèmes, l'événement redouté est réalisé lorsque le niveau de la retenue atteint un seuil de sûreté. La démarche de fiabilité dynamique proposée dans cette thèse vise à prendre en compte l'information temporelle, de la modélisation à la synthèse d'indicateurs fiabilistes pour l'aide à la décision et développe deux contributions : 1) L'élaboration d'une base de connaissances dédiée à la description des évacuateurs de crues en termes de fiabilité dynamique. Chaque classe de composants est décrite par un automate stochastique hybride dont les états sont les différentes phases de son fonctionnement. 2) Le suivi de la simulation de Monte Carlo, le traitement et l'analyse des "histoires" (séquence de tous les états activés et des dates d'activation) obtenues en simulation. Cela permet de construire des indicateurs de fiabilité classique (probabilité d'occurrence de l'évènement redouté, identification des coupes équivalentes prépondérantes, ...). Des indicateurs de fiabilité dynamique basés sur la classification des histoires en fonction des dates de défaillance des composants concernés et sur l'estimation de l'importance dynamique sont aussi proposés.

CAPES
Em ensaios não destrutivos por ultrassom, o sinal obtido a partir de um sistema de aquisição de dados real podem estar contaminados por ruído e os ecos podem ter atrasos de tempo subamostrais. Em alguns casos, esses aspectos podem comprometer a informação obtida de um sinal por um sistema de aquisição. Para lidar com essas situações, podem ser utilizadas técnicas de estimativa de atraso temporal (Time Delay Estimation ou TDE) e também técnicas de reconstrução de sinais, para realizar aproximações e obter mais informações sobre o conjunto de dados. As técnicas de TDE podem ser utilizadas com diversas finalidades na defectoscopia, como por exemplo, para a localização precisa de defeitos em peças, no monitoramento da taxa de corrosão em peças, na medição da espessura de um determinado material e etc. Já os métodos de reconstrução de dados possuem uma vasta gama de aplicação, como nos NDT, no imageamento médico, em telecomunicações e etc. Em geral, a maioria das técnicas de estimativa de atraso temporal requerem um modelo de sinal com precisão elevada, caso contrário, a localização dessa estimativa pode ter sua qualidade reduzida. Neste trabalho, é proposto um esquema alternado que estima de forma conjunta, uma referência de eco e atrasos de tempo para vários ecos a partir de medições ruidosas. Além disso, reinterpretando as técnicas utilizadas a partir de uma perspectiva probabilística, estendem-se suas funcionalidades através de uma aplicação conjunta de um estimador de máxima verossimilhança (Maximum Likelihood Estimation ou MLE) e um estimador máximo a posteriori (MAP). Finalmente, através de simulações, resultados são apresentados para demonstrar a superioridade do método proposto em relação aos métodos convencionais.
Abstract (parágrafo único): In non-destructive testing (NDT) with ultrasound, the signal obtained from a real data acquisition system may be contaminated by noise and the echoes may have sub-sample time delays. In some cases, these aspects may compromise the information obtained from a signal by an acquisition system. To deal with these situations, Time Delay Estimation (TDE) techniques and signal reconstruction techniques can be used to perform approximations and also to obtain more information about the data set. TDE techniques can be used for a number of purposes in the defectoscopy, for example, for accurate location of defects in parts, monitoring the corrosion rate in pieces, measuring the thickness of a given material, and so on. Data reconstruction methods have a wide range of applications, such as NDT, medical imaging, telecommunications and so on. In general, most time delay estimation techniques require a high precision signal model, otherwise the location of this estimate may have reduced quality. In this work, an alternative scheme is proposed that jointly estimates an echo model and time delays for several echoes from noisy measurements. In addition, by reinterpreting the utilized techniques from a probabilistic perspective, its functionalities are extended through a joint application of a maximum likelihood estimator (MLE) and a maximum a posteriori (MAP) estimator. Finally, through simulations, results are presented to demonstrate the superiority of the proposed method over conventional methods.

Dans un contexte industriel compétitif, une prévision fiable du rendement est une information primordiale pour déterminer avec précision les coûts de production et donc assurer la rentabilité d'un projet. La quantification des risques en amont du démarrage d'un processus de fabrication permet des prises de décision efficaces. Durant la phase de conception d'un produit, les efforts de développement peuvent être alors identifiés et ordonnés par priorité. Afin de mesurer l'impact des fluctuations des procédés industriels sur les performances d'un produit donné, la construction de la probabilité du risque défaillance est développée dans cette thèse. La relation complexe entre le processus de fabrication et le produit conçu (non linéaire, caractéristiques multi-modales...) est assurée par une méthode de régression bayésienne. Un champ aléatoire représente ainsi, pour chaque configuration du produit, l'information disponible concernant la probabilité de défaillance. Après une présentation du modèle gaussien, nous décrivons un raisonnement bayésien évitant le choix a priori des paramètres de position et d'échelle. Dans notre modèle, le mélange gaussien a priori, conditionné par des données mesurées (ou calculées), conduit à un posterior caractérisé par une distribution de Student multivariée. La nature probabiliste du modèle est alors exploitée pour construire une probabilité de risque de défaillance, définie comme une variable aléatoire. Pour ce faire, notre approche consiste à considérer comme aléatoire toutes les données inconnues, inaccessibles ou fluctuantes. Afin de propager les incertitudes, une approche basée sur les ensembles flous fournit un cadre approprié pour la mise en oeuvre d'un modèle bayésien imitant le raisonnement d'expert. L'idée sous-jacente est d'ajouter un minimum d'information a priori dans le modèle du risque de défaillance. Notre méthodologie a été mise en oeuvre dans un logiciel nommé GoNoGo. La pertinence de cette approche est illustrée par des exemples théoriques ainsi que sur un exemple réel provenant de la société STMicroelectronics.

Bien que de nombreuses séquences génomiques soient maintenant connues, les mécanismes évolutifs qui déterminent la taille des génomes, et notamment leur part d'ADN non codant, sont encore débattus. Ainsi, alors que de nombreux mécanismes faisant grandir les génomes (prolifération d'éléments transposables, création de nouveaux gènes par duplication, ...) sont clairement identifiés, les mécanismes limitant la taille des génomes sont moins bien établis. La sélection darwinienne pourrait directement défavoriser les génomes les moins compacts, sous l'hypothèse qu'une grande quantité d'ADN à répliquer limite la vitesse de reproduction de l'organisme. Cette hypothèse étant cependant contredite par plusieurs jeux de données, d'autres mécanismes non sélectifs ont été proposés, comme la dérive génétique et/ou un biais mutationnel rendant les petites délétions d'ADN plus fréquentes que les petites insertions. Dans ce manuscrit, nous montrons à l'aide d'un modèle matriciel de population que la taille du génome peut aussi être limitée par la dynamique spontanée des duplications et des grandes délétions, qui tend à raccourcir les génomes même si les deux types de ré- arrangements se produisent à la même fréquence. En l'absence de sélection darwinienne, nous prouvons l'existence d'une distribution stationnaire pour la taille du génome même si les duplications sont deux fois plus fréquentes que les délétions. Pour tester si la sélection darwinienne peut contrecarrer cette dynamique spontanée, nous simulons numériquement le modèle en choisissant une fonction de fitness qui favorise directement les génomes conte- nant le plus de gènes, tout en conservant des duplications deux fois plus fréquentes que les délétions. Dans ce scénario où tout semblait pousser les génomes à grandir infiniment, la taille du génome reste pourtant bornée. Ainsi, notre étude révèle une nouvelle force susceptible de limiter la croissance des génomes. En mettant en évidence des comporte- ments contre-intuitifs dans un modèle pourtant minimaliste, cette étude souligne aussi les limites de la simple " expérience de pensée " pour penser l'évolution. Nous proposons un modèle mathématique de l'évolution structurelle des génomes en met- tant l'accent sur l'influence des différents mécanismes de mutation. Il s'agit d'un modèle matriciel de population, à temps discret, avec un nombre infini d'états génomiques pos- sibles. La taille de population est infinie, ce qui élimine le phénomène de dérive génétique. Les mutations prises en compte sont les mutations ponctuelles, les petites insertions et délétions, mais aussi les réarrangements chromosomiques induits par la recombinaison ectopique de l'ADN, comme les inversions, les translocations, les grandes délétions et les duplications. Nous supposons par commodité que la taille des segments réarrangés suit une loi uniforme, mais le principal résultat analytique est ensuite généralisé à d'autres dis- tributions. Les mutations étant susceptibles de changer le nombre de gènes et la quantité d'ADN intergénique, le génome est libre de varier en taille et en compacité, ce qui nous permet d'étudier l'influence des taux de mutation sur la structure génomique à l'équilibre. Dans la première partie de la thèse, nous proposons une analyse mathématique dans le cas où il n'y a pas de sélection, c'est-à-dire lorsque la probabilité de reproduction est identique quelle que soit la structure du génome. En utilisant le théorème de Doeblin, nous montrons qu'une distribution stationnaire existe pour la taille du génome si le taux de duplications par base et par génération n'excède pas 2.58 fois le taux de grandes délétions. En effet, sous les hypothèses du modèle, ces deux types de mutation déterminent la dynamique spontanée du génome, alors que les petites insertions et petites délétions n'ont que très peu d'impact. De plus, même si les tailles des duplications et des grandes délétions sont distribuées de façon parfaitement symétriques, leur effet conjoint n'est, lui, pas symétrique et les délétions l'emportent sur les duplications. Ainsi, si les tailles de délétions et de duplications sont distribuées uniformément, il faut, en moyenne, plus de 2.58 duplications pour compenser une grande délétion. Il faut donc que le taux de duplications soit quasiment trois fois supérieur au taux de délétions pour que la taille des génomes croisse à l'infini. L'impact des grandes délétions est tel que, sous les hypothèses du modèle, ce dernier résultat reste valide même en présence d'un mécanisme de sélection favorisant directement l'ajout de nouveaux gènes. Même si un tel mécanisme sélectif devrait intuitivement pousser les génomes à grandir infiniment, en réalité, l'influence des délétions va rapidement limiter leur accroissement. En résumé, l'étude analytique prédit que les grands réarrangements délimitent un ensemble de tailles stables dans lesquelles les génomes peuvent évoluer, la sélection influençant la taille précise à l'équilibre parmi cet ensemble de tailles stables. Dans la deuxième partie de la thèse, nous implémentons le modèle numériquement afin de pouvoir simuler l'évolution de la taille du génome en présence de sélection. En choisissant une fonction de fitness non bornée et strictement croissante avec le nombre de gènes dans le génome, nous testons le comportement du modèle dans des conditions extrêmes, poussant les génomes à croître indéfiniment. Pourtant, dans ces conditions, le modèle numérique confirme que la taille des génomes est essentiellement contrôlée par les taux de duplications et de grandes délétions. De plus, cette limite concerne la taille totale du génome et s'applique donc aussi bien au codant qu'au non codant. Nous retrouvons en particulier le seuil de 2.58 duplications pour une délétion en deçà duquel la taille des génomes reste finie, comme prévu analytiquement. Le modèle numérique montre même que, dans certaines conditions, la taille moyenne des génomes diminue lorsque le taux de duplications augmente, un phénomène surprenant lié à l'instabilité structurelle des grands génomes. De façon similaire, augmenter l'avantage sélectif des grands génomes peut paradoxalement faire rétrécir les génomes en moyenne. Enfin, nous montrons que si les petites insertions et délétions, les inversions et les translocations ont un effet limité sur la taille du génome, ils influencent très largement la proportion d'ADN non codant.

Skyline analysis is important for multi-criteria decision making applications. The data in some of these applications are inherently uncertain due to various factors. Although a considerable amount of research has been dedicated separately to efficient skyline computation, as well as modeling uncertain data and answering some types of queries on uncertain data, how to conduct skyline analysis on uncertain data remains an open problem at large. In this thesis, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all the objects whose skyline probabilities are at least p. Computing probabilistic skylines on large uncertain data sets is challenging. An uncertain object is conceptually described by a probability density function (PDF) in the continuous case, or in the discrete case a set of instances (points) such that each instance has a probability to appear. We develop two efficient algorithms, the bottom-up and top-down algorithms, of computing p-skyline of a set of uncertain objects in the discrete case. We also discuss that our techniques can be applied to the continuous case as well. The bottom-up algorithm computes the skyline probabilities of some selected instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show that probabilistic skylines are interesting and useful, and our two algorithms are efficient on large data sets, and complementary to each other in performance.

A research report submitted to the Faculty of Engineering and the Built Environment, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Master of Science in Engineering, 2017
The main problem to be investigated is how short duration data records can be augmented using existing data from nearby catchments with data with long periods of record. The purpose of the investigation is to establish a method of improving hydrological data using data from a gauged catchment to improve data from an ungauged catchment. The investigation is undertaken using rainfall data for catchments in Lesotho. Marginal distributions describing the annual maximum rainfall for the catchments, and a joint distribution of pairs of catchments were established. The parameters of these distributions were estimated using the Bayesian – Markov Chain Monte Carlo approach, and using both the single-site (univariate) estimation and the two-site (bivariate) estimations. The results of the analyses show that for catchments with data with short periods of record, the precision of the estimated location and scale parameters improved when the estimates were carried out using the two-site (bivariate) method. Rainfall events predicted using bivariate analyses parameters were generally higher than the univariate analyses parameters. From the results, it can be concluded that the two-site approach can be used to improve the precision of the rainfall predictions for catchments with data with short periods of record. This method can be used in practice by hydrologists and design engineers to enhance available data for use in designs and assessments.
CK2018

Dans ce mémoire, je démontre que la distribution de probabilités de l'état quantique Greenberger-Horne-Zeilinger (GHZ) sous l'action locale de mesures de von Neumann indépendantes sur chaque qubit suit une distribution qui est une combinaison convexe de deux distributions. Les coefficients de la combinaison sont reliés aux parties équatoriales des mesures et les distributions associées à ces coefficients sont reliées aux parties réelles des mesures. Une application possible du résultat est qu'il permet de scinder en deux la simulation de l'état GHZ. Simuler, en pire cas ou en moyenne, un état quantique comme GHZ avec des ressources aléatoires, partagées ou privées, et des ressources classiques de communication, ou même des ressources fantaisistes comme les boîtes non locales, est un problème important en complexité de la communication quantique. On peut penser à ce problème de simulation comme un problème où plusieurs personnes obtiennent chacune une mesure de von Neumann à appliquer sur le sous-système de l'état GHZ qu'il partage avec les autres personnes. Chaque personne ne connaît que les données décrivant sa mesure et d'aucune façon une personne ne connaît les données décrivant la mesure d'une autre personne. Chaque personne obtient un résultat aléatoire classique. La distribution conjointe de ces résultats aléatoires classiques suit la distribution de probabilités trouvée dans ce mémoire. Le but est de simuler classiquement la distribution de probabilités de l'état GHZ. Mon résultat indique une marche à suivre qui consiste d'abord à simuler les parties équatoriales des mesures pour pouvoir ensuite savoir laquelle des distributions associées aux parties réelles des mesures il faut simuler. D'autres chercheurs ont trouvé comment simuler les parties équatoriales des mesures de von Neumann avec de la communication classique dans le cas de 3 personnes, mais la simulation des parties réelles résiste encore et toujours.
In this Master's thesis, I show that the probability distribution of the Greenberger-Horne-Zeilinger quantum state (GHZ) under local action of independent von Neumann measurements follows a convex distribution of two distributions.The coefficients of the combination are related to the equatorial parts of the measurements, and the distributions associated with those coefficients are associated with the real parts of the measurements. One possible application of my result is that it allows one to split into two pieces the simulation of the GHZ state. Simulating, in worst case or in average, a quantum state like the GHZ state with random resources, shared or private, as well as with classical communication resources or even odd resources like nonlocal boxes is a very important in the theory of quantum communication complexity. We can think of this simulation problem as a problem in which many people get the description of a von Neumann measurement. Each party does not know the description of any other measurements belonging to the other parties. Each party after having applied his measurement on the subsystem of the state that he shares with the others gets a classical outcome. The joint distribution of the outcomes of every parties follows the distribution studied in this thesis in the case of the GHZ state. My result indicates that in order to simulate the distribution, we can first simulate the equatorial parts of the measurements in order to know which distribution associated to the real parts of the measurements to simulate. Other researchers have found how to simulate the equatorial parts of the von Neumann measurements with classical resources in the case of 3 parties, but it is still unknown how to simulate the real parts.

Dans ce travail, on propose un nouveau package Sim.DiffProc pour la simulation des processus de diffusion, muni d'une interface graphique (GUI), sous langage R. Le développement de l'outil informatique (logiciels et matériels) ces dernières années, nous a motivé de réaliser ce travail. A l'aide de ce package, nous pouvons traiter beaucoup de problèmes théoriques difficiles liée à l'utilisation des processus de diffusion, pour des recherches pratiques, tels que la simulation numérique trajectoires de la solution d'une ÉDS. Ce qui permet à beaucoup d'utilisateurs dans différents domaines à l'employer comme outil sophistiqué à la modélisation de leurs problèmes pratiques. Le problème de dispersion d'un polluant, en présence d'un domaine attractif que nous avons traité dans ce travail en est un bon exemple. Cet exemple montre l'utilité et l'importance pratique des processus de diffusion dans la modélisation simulation de situations réelles complexes. La fonction de densité de la variable aléatoire tau(c) "instant de premier passage" de la frontière de domaine d'attraction peut être utilisée pour déterminer le taux de concentration des particules polluantes à l'intérieur du domaine. Les études de simulation et les analyses statistiques mises en application à l'aide du package Sim.DiffProc, se présentent efficaces et performantes, comparativement aux résultats théoriques explicitement ou approximativement déterminés par les modèles de processus de diffusion considérés.