Doctor of Philosophy / Department of Statistics / Suzanne Dubnicka / Christopher Vahl / Photoplethysmograph sensors use a light-based technology to sense the rate of blood flow as controlled by the heart’s pumping action. This allows for a graphical display of a patient’s pulse wave form and the description of its key features. A person’s pulse wave has been proposed as a tool in a wide variety of applications. For example, it could be used to diagnose the cause of coldness felt in the extremities or to measure stress levels while performing certain tasks. It could also be applied to quantify the risk of heart disease in the general population. In the present work, we explore its use for identity authentication. First, we visualize the pulse waves from individual patients using functional boxplots which assess the overall behavior and identify unusual observations. Functional boxplots are also shown to be helpful in preprocessing the data by shifting individual pulse waves to a proper starting point. We then employ functional analysis of variance (FANOVA) and permutation tests to demonstrate that the identities of a group of subjects could be differentiated and compared by their pulse wave forms. One of the primary tasks of the project is to confirm the identity of a person, i.e., we must decide if a given person is whom they claim to be. We used an equivalence test to determine whether the pulse wave of the person under verification and the actual person were close enough to be considered equivalent. A nonparametric bootstrap functional equivalence test was applied to evaluate equivalence by constructing point-wise confidence intervals for the metric of identity assurance. We also proposed new testing procedures, including the way of building the equivalence hypothesis and test statistics, determination of evaluation range and equivalence bands, to authenticate the identity.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-08-28T18:26:01Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) TCC Profmat.pdf: 610264 bytes, checksum: 97990024fcad3a6b2b90fe7a7e642a70 (MD5) / Made available in DSpace on 2014-08-28T18:26:01Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) TCC Profmat.pdf: 610264 bytes, checksum: 97990024fcad3a6b2b90fe7a7e642a70 (MD5) Previous issue date: 2013-02-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The study of determinants development through the permutations made on their lines or columns dates back to 1812, a memory presented by Cauchy to the French Academy of Sciences. The present work is, in some way, a historical rescue. Firstly, a permutation is de ned: from a superior point of view there is a bijective application and, as such, the set of permutations has a group structure; from the elementary point of view, there is an ordainment of a group's elements. The fundamental fact is, secondly, that the de nition of determinant adjusts perfectly to both conceptions, based on the parity of the permutations. Based on the de nitions, the determinants properties are presented and, therefore, it is possible to proceed with the appropriate justi cations about their validity. A rule that associates each square matrix to a real number will de ne a real function of the variable matrix, the determinant function. This is the actual way in which determinants are presented in higher levels: the determinant is the unique alternated multilinear function of the lines (columns) of a square matrix, as indicated in [10]. By this presentation there is in mind the fact that it can be served as an inspiration to posterior studies. / O estudo sobre o desenvolvimento dos determinantes por meio das permuta ções efetuadas sobre suas linhas ou colunas remonta a 1812, com uma mem ória apresentada por Cauchy a academia de ciências da Fran ça. O presente trabalho e, em certo sentido, um resgate hist órico. Em primeiro lugar de ve-se uma permuta ção: sob um ponto de vista superior tem-se uma aplica c~ao bijetiva e, como tal, o conjunto das permuta c~oes possui uma estrutura de grupo; do ponto de vista elementar, tem-se um ordenamento de elementos de um conjunto. O fato fundamental e que, em segundo lugar, a de ni c~ao de determinante se ajusta perfeitamente as duas concep ções, tomando por base a paridade das permuta ções. Baseando nas de ni ções, as propriedades dos determinantes s~ao apresentadas e, assim, pode-se proceder com as devidas justi ficativas sobre a validade das mesmas. Uma regra que associe a cada matriz quadrada um n umero real de nir a uma fun c~ao real de vari avel matricial, a fun ção determinante. E a forma atual como os determinantes s~ao apresentados em n veis superiores: o determinante e a unica fun ção multilinear alternada das linhas (colunas) de uma matriz quadrada, conforme exibido em [10]. Com tal apresenta c~ao, tem-se em mente, o fato de poder servir de inspira c~ao em estudos posteriores.

L'algorithme Branch-and-Bound (B&B) est une méthode de recherche arborescente fréquemment utilisé pour la résolution exacte de problèmes d'optimisation combinatoire (POC). Néanmoins, seules des petites instances peuvent être effectivement résolues sur une machine séquentielle, le nombre de sous-problèmes à évaluer étant souvent très grand. Visant la resolution de POC de grande taille, nous réexaminons la conception et l'implémentation d'algorithmes B&B massivement parallèles sur de larges plateformes hétérogènes de calcul, intégrant des processeurs multi-coeurs, many-cores et et processeurs graphiques (GPUs). Pour une représentation compacte en mémoire des sous-problèmes une structure de données originale (IVM), dédiée aux problèmes de permutation est utilisée. En raison de la forte irrégularité de l'arbre de recherche, l'équilibrage de charge dynamique entre processus d'exploration parallèles occupe une place centrale dans cette thèse. Basés sur un encodage compact de l'espace de recherche sous forme d'intervalles, des stratégies de vol de tâches sont proposées pour processeurs multi-core et GPU, ainsi une approche hiérarchique pour l'équilibrage de charge dans les systèmes multi-GPU et multi-CPU à mémoire distribuée. Trois problèmes d'optimisation définis sur l'ensemble des permutations, le problème d'ordonnancement Flow-Shop (FSP), d'affectation quadratique (QAP) et le problème des n-dames sont utilisés comme cas d'étude. La resolution en 9 heures d'une instance du FSP dont le temps de résolution séquentiel est estimé à 22 ans demontre la capacité de passage à l'échelle des algorithmes proposés sur une grappe de calcul composé de 36 GPUs. / Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimization problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B generates often generates a huge amount of subproblems to be evaluated. In order to solve large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs. For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is one of the main issues addressed in this thesis. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle problem are used as test-cases. The resolution, in 9 hours, of a FSP instance with an estimated sequential execution time of 22 years demonstrates the scalability of the proposed algorithms on a cluster composed of 36 GPUs.

A transitive decomposition of a graph is a partition of the arc set such that there exists a group of automorphisms of the graph which preserves and acts transitively on the partition. This turns out to be a very broad idea, with several striking connections with other areas of mathematics. In this thesis we first develop some general theory of transitive decompositions, and in particular we illustrate some of the more interesting connections with certain combinatorial and geometric structures. We then give complete, or nearly complete, structural characterisations of certain classes of transitive decompositions preserved by a group with a rank 3 action on vertices (such a group has exactly two orbits on ordered pairs of distinct vertices). The main classes of rank 3 groups we study (namely those which are imprimitive, or primitive of grid type) are derived in some way from 2-transitive groups (that is, groups which are transitive on ordered pairs of distinct vertices), and the results we achieve make use of the classification by Sibley in 2004 of transitive decompositions preserved by a 2-transitive group.

Cette thèse se décompose en deux parties qui correspondent à deux aspect de la cryptologie avec d'une part la conception de nouvelles méthodes de chiffrement et d'autre part la cryptanalyse des systèmes existants. La première partie est consacrée à l'étude des polynômes de permutation. Après avoir introduit les propriétés élémentaires de ces objets mathématiques, nous tenterons de donner un aperçu aussi large que possible des différentes familles connues. Nous verrons aussi quelle est la répartition des polynômes de permutation. Nous détaillerons ensuite plusieurs situations où ces polynômes interviennent en cryptologie. En particulier, nous développerons le lien avec les fonctions APN. La seconde partie traite de la cryptanalyse d'un système de chiffrement classique: le générateur par combinaison. Après avoir rappelé les bases théoriques nécessaires à l'étude de ces systèmes ainsi que les techniques de cryptanalyse existante, nous présenterons nos résultats. L'attaque de ces systèmes se décompose en deux phases: une phase de précalcul, puis la phase active de l'attaque. Nous proposerons pour chacune de ces deux étapes des améliorations.

La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes. Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,...,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées. Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.

Ce mémoire traite d'une application pratique de deux méthodes statistiques non paramétriques : le bootstrap et le test de permutation. La méthode du bootstrap a été proposée par Bradley Efron (1979) comme une alternative aux modèles mathématiques traditionnels dans des problèmes d'inférence complexe; celle-ci fournit plusieurs avantages sur les méthodes d'inférence traditionnelles. L'idée du test de permutation est apparue au début du XXème siècle dans les travaux de Neyman, Fisher et Pitman. Le test de permutation, très intensif quant au temps de calcul, est utilisé pour construire une distribution empirique de la statistique de test sous une hypothèse afin de la comparer avec la distribution de la même statistique sous l'hypothèse alternative. Notre objectif est de déterminer l'intervalle de confiance pour un estimateur à maximum de vraisemblance d'une méthode de cartographie génétique existante (MapArg, Larribe et al. 2002) et de tester la qualité de cet estimateur, c'est-à-dire d'établir des seuils de signification pour la fonction de la vraisemblance. Les deux méthodes utilisent le calcul répétitif d'une même statistique de test sur des échantillons obtenus à partir de l'échantillon initial, soit avec le «bootstrap», soit avec des permutations. Dans un test d'hypothèse, les deux méthodes sont complémentaires. Le but de ce mémoire est de proposer différentes variantes pour la construction de l'intervalle de confiance, et de tester des hypothèses distinctes, afin de trouver la meilleure solution adaptée pour la méthode MapArg. Pour faciliter la compréhension des décisions prises, un rappel de l'inférence statistique et des tests d' hypothèse est fait dans les chapitres 4 et 5 où la théorie du bootstrap et celle de test de permutation sont présentées. Comme les qualités d'un estimateur dépendent de la méthode utilisée pour le calculer, les chapitres 1 et 2 présentent la base biologique et la base en mathématiques sur lesquelles la méthode MapArg est construite, tandis qu'on trouvera dans le chapitre 3 une explication de la méthode MapArg. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Mutation, Recombinaison, Coalescence, Cartographie génétique, «Bootstrap», Test de permutation.

Dans la pratique clinique, on fait souvent appel aux études de bioéquivalence afin de comparer deux médicaments. Un premier objectif de ce mémoire est d'introduire la notion pharmacocinétique et statistique de ce type d'étude, ainsi que de définir et de présenter l'application des tests d'équivalence à travers les études de bioéquivalence. Pour réaliser l'inférence statistique des études de bioéquivalence, en pratique on utilise le test t de Student. Le second but de ce mémoire est l'utilisation du test de permutations dans le cas où les hypothèses du test paramétrique ne sont pas satisfaites. À travers une étude de simulation des données de plusieurs lois on compare la performance du test de permutations avec le test t de Student et le test de WiIcoxon pour deux échantillons. Ce dernier est le test non paramétrique utilisé dans la pratique courante des études de bioéquivalence. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Bioéquivalence, Tests d'hypothèses, Plan d'expérience croisé, Test de permutation.

The O'Nan-Scott Theorem classifies finite primitive permutation groups into one of five isomorphism classes. This theorem is very useful for answering questions about finite permutation groups since four out of the five isomorphism classes are well understood. The proof of this theorem currently relies upon the classification of the finite simple groups, as it requires a consequence of this classification, the Schreier Conjecture. After reviewing some needed group theoretic concepts, I give a detailed proof of the O'Nan-Scott Theorem. I then examine how the techniques of this proof have been applied to an open problem which asks whether every finite lattice can be embedded as an interval into the subgroup lattice of a finite group.

Okun's Law postulates an inverse relationship between movements of the unemployment rate and the real gross domestic product (GDP). Empirical estimates for US data indicate that a two to three percent GDP growth rate above the natural or average GDP growth rate causes unemployment to decrease by one percentage point and vice versa. In this investigation we check whether this postulated relationship exhibits structural breaks by means of Markov-Chain Monte Carlo methods. We estimate a regression model, where the parameters are allowed to switch between different states and the switching process is Markov. As a by-product we derive an estimate of the current state within the periods considered. Using quarterly Austrian data on unemployment and real GDP from 1977 to 1995 we infer only one state, i.e. there are no structural breaks. The estimated parameters demand for an excess GDP growth rate of 4.16% to decrease unemployment by one percentage point. Since only one state is inferred, we conclude that the Austrian economy exhibits a stable relationship between unemployment and GDP growth. (author's abstract) / Series: Working Papers SFB "Adaptive Information Systems and Modelling in Economics and Management Science"