abstract: In software testing, components are tested individually to make sure each performs as expected. The next step is to confirm that two or more components are able to work together. This stage of testing is often difficult because there can be numerous configurations between just two components. Covering arrays are one way to ensure a set of tests will cover every possible configuration at least once. However, on systems with many settings, it is computationally intensive to run every possible test. Test prioritization methods can identify tests of greater importance. This concept of test prioritization can help determine which tests can be removed with minimal impact to the overall testing of the system. This thesis presents three algorithms that generate covering arrays that test the interaction of every two components at least twice. These algorithms extend the functionality of an established greedy test prioritization method to ensure important components are selected in earlier tests. The algorithms are tested on various inputs and the results reveal that on average, the resulting covering arrays are two-fifths to one-half times smaller than a covering array generated through brute force. / Dissertation/Thesis / Masters Thesis Computer Science 2015

Hamming-distance graphs arise naturally in the study of error-correcting codes and have been utilized by several authors to provide new proofs for (and in some cases improve) known bounds on the size of block codes. We study various standard graph properties of the Hamming-distance graphs with special emphasis placed on the chromatic number. A notion of robustness is defined for colorings of these graphs based on the tolerance of swapping colors along an edge without destroying the properness of the coloring, and a complete characterization of the maximally robust colorings is given for certain parameters. Additionally, explorations are made into subgraph structures whose identification may be useful in determining the chromatic number.

Este trabalho tem como objetivo discutir o conceito formal de distância em matemática, visando depois apresentar exemplos do conceito de distância em situações do dia a dia. Em geral com esse trabalho pretendemos que o leitor menos familiarizado entenda a importância do conceito matemático de distância. Distância é muito mais que o comprimento do segmento entre dois pontos e isso será apresentado em cada capítulo. O assunto foi inspirado pelo livro Encyclopedia of Distances Deza Michel Marie (2009), no qual são apresentados, espaços métricos, métricas em várias áreas e aplicações. No segundo capítulo, será apresentado a definição de espaços métricos. No terceiro capítulo serão apresentados alguns exemplos de métricas. As três primeiras métricas, as mais comuns: métricas euclidiana e máxima em R e R2. Também serão apresentadas as generalizações de cada uma delas em Rn. O próximo capítulo, o quarto, é destinado a apresentar o estudo sobre espaços normados, pois por meio desses conceitos pode-se analisar as distâncias entre vetores e matrizes. Veremos que a relevância dessas distâncias auxilia, por exemplo, na compreensão de aproximações de soluções de sistemas. No capítulo de distância de funções será apresentado um breve comentário sobre a série de Fourier, com relação ao método da aproximação através da decomposição de funções periódicas. Para analisar o quanto as funções trigonométricas estão se aproximando, usa-se o conceito de distância entre funções, as medições são feitas de acordo com as aproximações vão aumentando, essa distância \"erro\" entre elas tende a zero. Na teoria dos códigos, é preciso introduzir o conceito de distância entre \"palavras\", isso permite verificar se o código enviado teve alguma alteração, provocada por uma interferência ou ruídos durante a trajetória. Em algumas situações, o código consegue corrigir e compreender a palavra enviada mesmo tendo sofrido alterações no percurso. Nestes casos, há o estudo da métrica de Hamming. Já pela métrica de Hausdoorf, proposta pelo matemático de mesmo nome, é possível calcular com maior precisão a distância entre conjuntos fechados e limitados. Esta métrica pode ser utilizada em estudos de reconhecimento facial, por exemplo, pois as imagens das faces são transformadas em nuvens de pontos. Além disso, através do algoritmo de Dijkstra será apresentado a distância entre os vértices de um grafo convexo. Existem várias aplicações de distância entre grafos e uma delas é a questão de minimizar o custo decorrente do deslocamento entre uma transportadora e o local de entrega por exemplo. Para finalizar à discussão da importância do consenso de distância, será apresentada uma distância entre genes. Dentro deste tema, o principal cientista foi Thomas Morgan, que por meio de seus estudos conseguiu criar o primeiro mapeamento genético. Com isto, pode relacionar o conceito de distância entre genes à taxa de recombinação gênica. Finalmente, foi elaborada uma atividade com alunos do ensino médio com o objetivo de analisar os conhecimentos que os estudantes têm sobre distância. Esta atividade também foi importante para que os alunos pudessem compreender a necessidade de formalizar matematicamente este conceito e, principalmente, motivá-los por meio da apresentação de aplicações sobre distância, em diferentes âmbitos. / This work has as objective to discuss the formal concept of distance in mathematics, aiming to present examples of the distance concept in everyday situations. In general with this work we want the less familiar reader to understand the importance of the mathematical concept of distance. Distance is much more than the length of the segment between two points and this will be presented in each chapter. The subject was inspired by the book Encyclopedia of Distances Deza Michel Marie (2009), in which are presented, metric spaces, metrics in different areas and applications. In the second chapter, the definition of metric spaces will be presented. In the third chapter some examples of metrics will be presented. The first three metrics, the most common: usual, Euclidean, and maximum metrics in R and R2. Also the generalizations of each of them were presented in Rn. The next chapter, the fourth, is intended to show the study on normed spaces, because through these concepts we can analyze the distances between vectors and matrices. We will see that the relevance of these distances helps in the understanding of systems solutions approximation. In the chapter on distance of functions, a brief comment about Fourier series was presented, regarding the method of approximation through the decomposition of periodic functions. In order to analyze how the trigonometric functions are approaching, the concept of distance between functions is used, the measurements are made as the approximations increase, this distance \"error\" between them tends to zero. In codes theory, it is necessary to introduce the concept of distance between \"words\", this allows to verify if the code had some alteration, caused by an interference or noises during the trajectory. In some situations, the code can correct and understand the sent word even though it has undergone changes in the route. In these cases, there is Hammings metrics study. By the Hausdoorf metric, proposed by the mathematician of the same name, it is possible to calculate with more precision the distance between closed and limited sets. This metric can be used in face recognition studies, for example, because face images are transformed into clouds of dots. Then, through the Dijkstras algorithm will be presented the distance between the vertices of a convex graphic. There are several applications of distance between graphics and one of them is the issue of minimizing the cost of moving between a local carrier company and the place of delivery, for example. To finish the discussion about the importance of distance consensus, the distance between genes will be presented. Within this theme, the main scientist was Thomas Morgan, who through his studies managed to create the first genetic mapping. With this, he was able to relate the concept of distance between genes to the rate of gene recombination. Finally, an activity was elaborated with high school students with the objective of analyzing students knowledge about distance. This activity was also important so that the students could understand about a necessity to formalize this concept mathematically and, mainly, to motivate them through the presentation of applications on distance, in different scopes.

Finding near-duplicate documents is an interesting problem but the existing methods are not suitable for large scale datasets and memory constrained systems. In this work, we developed approaches that tackle the problem of finding near-duplicates while improving query performance and using less memory. We then carried out an evaluation of our method on a dataset of 70M web documents, and showed that our method works really well. The results indicated that our method could achieve a reduction in space by a factor of 5 while improving the query time by a factor of 4 with a recall of 0.95 for finding all near-duplicates when the dataset is in memory. With the same recall and same reduction in space, we could achieve an improvement in query-time by a factor of 4.5 while finding first the near-duplicate for an in memory dataset. When the dataset was stored on a disk, we could achieve an improvement in performance by 7 times for finding all near-duplicates and by 14 times when finding the first near-duplicate.

In this thesis we develop a mathematical model to describe HIV-1 evolution during the first stages of infection (approximately within 40-60 days since onset), when one can assume exponential growth and random accumulation of mutations under a neutral drift. We analyze the Hamming distance (HD) distribution under different models (synchronous and asynchronous) in the absence of selection and recombination. In the second part of the thesis, we introduce recombination and develop a combinatorial approach to estimate the new HD distribution. We conclude describing a T statistic to test significance differences between the HD of two genetic samples, which we derive using U-statistics.

No description available.

Abstraction-guided simulation is a promising semi-formal framework for design validation in which an abstract model of the design is used to guide a logic simulator towards a target property. However, key issues still need to be addressed before this framework can truly deliver on it's promise. Concretizing, or finding a real trace from an abstract trace, remains a hard problem. Abstract traces are often spurious, for which no corresponding real trace exits. This is a direct consequence of the abstraction being an over-approximation of the real design. Further, the way in which the abstract model is constructed is an open-ended problem which has a great impact on the performance of the simulator. In this work, we propose a novel approaches to address these issues. First, we present a genetic algorithm to select sets of state variables directly from the gate-level net-list of the design, which are highly correlated to the target property. The sets of selected variables are used to build the Partition Navigation Tracks (PNTs). PNTs capture the behavior of expanded portions of the state space as they related to the target property. Moreover, the computation and storage costs of the PNTs is small, making them scale well to large designs. Our experiments show that we are able to reach many more hard-to-reach states using our proposed techniques, compared to state-of-the-art methods. Next, we propose a novel abstraction strengthening technique, where the abstract design is constrained to make it more closely resemble the concrete design. Abstraction strengthening greatly reduces the need to refine the abstract model for hard to reach properties. To achieve this, we efficiently identify sequentially unreachable partial sates in the concrete design via intelligent partitioning, resolution and cube enlargement. Then, these partial states are added as constraints in the abstract model. Our experiments show that the cost to compute these constraints is low and the abstract traces obtained from the strengthened abstract model are far easier to concretize. / Master of Science

With the intensively increasing of digital media new challenges has been created for authentication and protection of digital intellectual property. A hash function extracts certain features of a multimedia object e.g. an image and maps it to a fixed string of bits. A perceptual hash function unlike normal cryptographic hash is change tolerant for image processing techniques. Perceptual hash function also referred to as robust hash, like any other algorithm is prone to errors. These errors are false negative and false positive, of which false positive error is neglected compared to false negative errors. False positive occurs when an unknown object is identified as known. In this work a new method for raising false alarms in robust hash function is devised for evaluation purposes i.e. this algorithm modifies hash key of a target image to resemble a different image’s hash key without any significant loss of quality to the modified image. This algorithm is implemented in MATLAB using block mean value based hash function and successfully reduces hamming distance between target image and modified image with a good result and without significant loss to attacked imaged quality.

Un code de permutations G(n,d) un sous-ensemble C de Sym(n) tel que la distance de Hamming D entre deux éléments de C est supérieure ou égale à d. Dans cette thèse, le groupe des isométries de (Sym(n),D) est déterminé et il est prouvé que ces isométries sont des automorphismes du schéma d'association induit sur Sym(n) par ses classes de conjugaison. Ceci mène, par programmation linéaire, à de nouveaux majorants de la taille maximale des G(n,d) pour n et d fixés et n compris entre 11 et 13. Des algorithmes de génération avec rejet d'objets isomorphes sont développés. Pour classer les G(n,d) non isométriques, des invariants ont été construits et leur efficacité étudiée. Tous les G(4,3) et les G(5,4) ont été engendrés à une isométrie près, il y en a respectivement 61 et 9445 (dont 139 sont maximaux et décrits explicitement). D’autres classes de G(n,d) sont étudiées. A permutation code G(n,d) is a subset C of Sym(n) such that the Hamming distance D between two elements of C is larger than or equal to d. In this thesis, we characterize the isometry group of the metric space (Sym(n),D) and we prove that these isometries are automorphisms of the association scheme induced on Sym(n) by the conjugacy classes. This leads, by linear programming, to new upper bounds for the maximal size of G(n,d) codes for n and d fixed and n between 11 and 13. We develop generating algorithms with rejection of isomorphic objects. In order to classify the G(n,d) codes up to isometry, we construct invariants and study their efficiency. We generate all G(4,3) and G(4,5)codes up to isometry; there are respectively 61 and 9445 of them. Precisely 139 out of the latter codes are maximal and explicitly described. We also study other classes of G(n,d)codes.

Made available in DSpace on 2014-06-11T19:29:40Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-05-10Bitstream added on 2014-06-13T19:38:58Z : No. of bitstreams: 1 rogeri_jg_me_sjrp.pdf: 962940 bytes, checksum: 5f86f6439d28c1cc69d98e55069b9b90 (MD5) / Nos últimos anos, a segurança tornou-se uma preocupação constante da grande maioria das pessoas. Os sistemas biométricos vem ganhando destaque em soluções ligadas à segurança, uma vez que tratam de características físicas e comportamentais para reconhecimento dos indivíduos e permissões de acesso. Este trabalho objetivou a proposição e implementação de um método para reconhecimento de indivíduos por meio de características contidas na região interna da íris com um alto percentual de exatidão no reconhecimento e uma grande diminuição no tempo de processamento, se comparado aos demais métodos encontrados na literatura. No método proposto foram utilizados operadores de morfologia matemática para localização da íris, wavelet de log-Gabor para extração das características e a distância de Hamming para o reconhecimento. Os resultados experimentais obtidos utilizando a base de dados CASIA mostraram que o método é confiável e seguro, além de se destacar com relação ao baixo custo computacional / In the recent years, the security became a constant concern of most people. Biometric systems have been highlighted in solutions related to security, since they deal with physical and behavioral characteristics for individuals recognition and access permissions. This work aims at the implementation of a method for individuals recognition based on the characteristics of the inner region of the iris, seeking a high percentage of accuracy in the recognition and a great reduction in the processing time, as compared to other methods published so far. We use mathematical morphology to search the iris in the image, the log-Gabor wavelet for feature extraction and the Hamming distance for recognition. The experimental results obtained from CASIA database show that the method is safe and reliable, and stand out with regard to the low computational cost