The subject of this thesis is to study approximation algorithms for some network design problems in face of uncertainty. We consider two widely studied models of handling uncertainties - Robust Optimization and Stochastic Optimization. We study a robust version of the well studied Uncapacitated Facility Location Problem (UFLP). In this version, once the set of facilities to be opened is decided, an adversary may close at most β facilities. The clients must then be assigned to the remaining open facilities. The performance of a solution is measured by the worst possible set of facilities that the adversary may close. We introduce a novel LP for the problem, and provide an LP rounding algorithm when all facilities have same opening costs. We also study the 2-stage Stochastic version of the Steiner Tree Problem. In this version, the set of terminals to be covered is not known in advance. Instead, a probability distribution over the possible sets of terminals is known. One is allowed to build a partial solution in the first stage a low cost, and when the exact scenario to be covered becomes known in the second stage, one is allowed to extend the solution by building a recourse network, albeit at higher cost. The aim is to construct a solution of low cost in expectation. We provide an LP rounding algorithm for this problem that beats the current best known LP rounding based approximation algorithm.

Pairings have found a range of applications in many areas of cryptography. As such, to utilize the enormous potential of pairing-based protocols one needs to efficiently compute pairings across various computing platforms. In this thesis, we give an introduction to pairing-based cryptography and describe the Tate pairing and its variants. We then describe some recent work to realize efficient computation of pairings. We further extend these optimizations and implement the O-Ate pairing on BN-curves on ARM and x86-64 platforms. Specifically, we extend the idea of lazy reduction to field inversion, optimize curve arithmetic, and construct efficient tower extensions to optimize field arithmetic. We also analyze the use of affine coordinates for pairing computation leading us to the conclusion that they are a competitive choice for fast pairing computation on ARM processors, especially at high security level. Our resulting implementation is more than three times faster than any previously reported implementation on ARM processors.

A continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. We will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. Let A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.

In this thesis, we make some contributions at the interface between algebra and graph theory. In Chapter 1, we give an overview of the topics and also the definitions and preliminaries. In Chapter 2, we estimate the number of possible types degree patterns of k-lacunary polynomials of degree t < p which split completely modulo p. The result is based on a rather unusual combination of two techniques: a bound on the number of zeros of lacunary polynomials and a bound on the so-called domination number of a graph. In Chapter 3, we deal with the determinant of bipartite graphs. The nullity of a graph G is the multiplicity of 0 in the spectrum of G. Nullity of a (molecular) graph (e.g., a bipartite graph corresponding to an alternant hydrocarbon) has important applications in quantum chemistry and Huckel molecular orbital (HMO) theory. A famous problem, posed by Collatz and Sinogowitz in 1957, asks to characterize all graphs with positive nullity. Clearly, examining the determinant of a graph is a way to attack this problem. In this Chapter, we show that the determinant of a bipartite graph with at least two perfect matchings and with all cycle lengths divisible by four, is zero. In Chapter 4, we first introduce an application of spectral graph theory in proving trigonometric identities. This is a very simple double counting argument that gives very short proofs for some of these identities (and perhaps the only existed proof in some cases!). In the rest of Chapter 4, using some properties of the well-known Chebyshev polynomials, we prove some theorems that allow us to evaluate the number of spanning trees in join of graphs, Cartesian product of graphs, and nearly regular graphs. In the last section of Chapter 4, we obtain the number of spanning trees in an (r,s)-semiregular graph and its line graph. Note that the same results, as in the last section, were proved by I. Sato using zeta functions. But our proofs are much shorter based on some well-known facts from spectral graph theory. Besides, we do not use zeta functions in our arguments. In Chapter 5, we present the conclusion and also some possible projects.

No description available.

A presente pesquisa foi desenvolvida para entender como ocorre o processo de ensino e aprendizagem da Combinatória, no caso particular dos problemas de contagem de agrupamentos de objetos, considerado difícil por professores e alunos; e para elaborar e experimentar uma proposta didática, com potencial para trazer algo novo ao processo. Com base na Teoria dos Campos Conceituais de Vergnaud, delineou-se os esquemas de um grupo de alunos do ensino médio: resolvem problemas de contagem direta, mas não resolvem os que exigem multiplicação e divisão. Com a análise de outros trabalhos correlatos, pode-se concluir que o ensino tem melhores chances de iniciar com a resolução de problemas, e não a partir de formulários e definições. Consequência deste estudo, foi organizada e posta em prática uma sequência didática que parte da vivência do “jogo de pôquer”. Entende-se o baralho (sem coringas) como um conjunto de 52 objetos, a partir do qual devemos formar agrupamentos de 5 objetos (“mãos”). Os problemas propostos gerados pelo jogo podem ser resolvidos com as quatro operações aritméticas. Ao final, constatou-se evolução nos esquemas dos alunos, que passaram a utilizar a multiplicação com significado e a utilizar uma organização gráfica adequada para as soluções. Mas ainda apareceram erros no uso da divisão, que foram analisados para poder-se oferecer ao professor/leitor, compreensão das dificuldades. / This research was conducted to understand how the teaching and learning of Combinatorics is, in the particular case of counting issues and groupings of objects, which is considered difficult by teachers and students. Also aims to develop and experience a didactic proposal, with the potential to bring something new to the process. Based on Vergnaud's theory of Conceptual Fields, it was outlined schemes of a group of high school students: they solve problems of direct counting, but do not solve problems that require multiplication and division. With the analysis of other related work, we can conclude that a better way of teaching would be starting with problem solving, and not from formulas and definitions. As a result of this study a teaching sequence that takes advantage of the experience of the poker game, was organized and implemented. It is understood the deck (without wildcards) of 52 cards, from which we form groups of 5 objects ("hands"). The proposed problems generated by the game can be solved with the four arithmetic operations. At the end of our experience, we discover changes in the schemes of the students, who start using multiplication meaning and an organization suitable for finding solutions. We notice that still errors appeared in the use of division, which were analyzed in order to offer the teacher / reader the understanding of the difficulties of the students.

A presente pesquisa foi desenvolvida para entender como ocorre o processo de ensino e aprendizagem da Combinatória, no caso particular dos problemas de contagem de agrupamentos de objetos, considerado difícil por professores e alunos; e para elaborar e experimentar uma proposta didática, com potencial para trazer algo novo ao processo. Com base na Teoria dos Campos Conceituais de Vergnaud, delineou-se os esquemas de um grupo de alunos do ensino médio: resolvem problemas de contagem direta, mas não resolvem os que exigem multiplicação e divisão. Com a análise de outros trabalhos correlatos, pode-se concluir que o ensino tem melhores chances de iniciar com a resolução de problemas, e não a partir de formulários e definições. Consequência deste estudo, foi organizada e posta em prática uma sequência didática que parte da vivência do “jogo de pôquer”. Entende-se o baralho (sem coringas) como um conjunto de 52 objetos, a partir do qual devemos formar agrupamentos de 5 objetos (“mãos”). Os problemas propostos gerados pelo jogo podem ser resolvidos com as quatro operações aritméticas. Ao final, constatou-se evolução nos esquemas dos alunos, que passaram a utilizar a multiplicação com significado e a utilizar uma organização gráfica adequada para as soluções. Mas ainda apareceram erros no uso da divisão, que foram analisados para poder-se oferecer ao professor/leitor, compreensão das dificuldades. / This research was conducted to understand how the teaching and learning of Combinatorics is, in the particular case of counting issues and groupings of objects, which is considered difficult by teachers and students. Also aims to develop and experience a didactic proposal, with the potential to bring something new to the process. Based on Vergnaud's theory of Conceptual Fields, it was outlined schemes of a group of high school students: they solve problems of direct counting, but do not solve problems that require multiplication and division. With the analysis of other related work, we can conclude that a better way of teaching would be starting with problem solving, and not from formulas and definitions. As a result of this study a teaching sequence that takes advantage of the experience of the poker game, was organized and implemented. It is understood the deck (without wildcards) of 52 cards, from which we form groups of 5 objects ("hands"). The proposed problems generated by the game can be solved with the four arithmetic operations. At the end of our experience, we discover changes in the schemes of the students, who start using multiplication meaning and an organization suitable for finding solutions. We notice that still errors appeared in the use of division, which were analyzed in order to offer the teacher / reader the understanding of the difficulties of the students.

Esta dissertação apresenta o desenvolvimento de uma pesquisa referente ao ensino da Análise Combinatória, por meio da Resolução de Problemas, em uma turma de 6º ano do Ensino Fundamental. Para isso, elaborou-se uma sequência didática que buscava proporcionar aos educandos um contato com esse conteúdo antes do Ensino Médio. A partir dessa sequência analisou-se como a Resolução de Problemas, segundo Onuchic e Allevato, auxiliou os alunos a compreender os conceitos iniciais de Análise Combinatória, buscando também como referencial teórico o estudo referente ao Pensamento Matemático, de David Tall. Concluímos que a Resolução de Problemas auxiliou a expandir e modificar as Imagens dos Conceitos que os alunos possuíam com relação à Análise Combinatória. / This dissertation shows the development of research related to teaching Combinatorics, through Problem Solving, at a 6th grade level. A lesson plan was prepared and aimed to confront students of middle school with problems involving Combinatorics, allowing them to work with such concepts before high school. Based on this lesson plan, our intent was to verify how Problem Solving, according to Onuchic e Allevato, helped the students to understand initial concepts of Combinatorics. Also, using David Tall’s studies about Mathematical Thinking as reference. We could verify that the Problem Solving Theory helped the students to expand and modify their Concept Images related to Combinatorics.

Made available in DSpace on 2016-06-02T20:02:49Z (GMT). No. of bitstreams: 1 3865.pdf: 3136083 bytes, checksum: be5f23c6b90589dc90ec3ac89b46af5d (MD5) Previous issue date: 2011-09-01 / This paper has the aim to describe the design, development and application of guiding teaching activities in an area that is usually little explored, the Combinatorics. The study was developed through an intervention that consisted of three activities applied to guiding students in four classes of second grade high school of a state school in São Paulo. The activities were designed with the goal of putting students in a position of action and decision making to facilitate the understanding and the process of knowledge construction and were developed in groups of four or five students. The research classified as naturalist, by the fact that data collection was carried out directly on the site where the problem, is the central issue is to verify whether the teaching of Combinatorics, without the excessive use of formulas, through tutoring activities and use of multiplicative principle, can improve the teaching and understanding of that content. The results were obtained by analyzing the activities addressed by the students who were recorded, by observation, by notes taken by the researchers and also by the evaluation at the end of the research. It was found that the activities were essential for guiding a better performance of students who felt more secure and confident to carry out new activities. These activities represent the final product of this work and it is expected that constitute reference material for teachers who tirelessly seek for new methodologies. / O presente trabalho tem por objetivo descrever a elaboração, o desenvolvimento e a aplicação de atividades orientadoras de ensino numa área que usualmente é pouco explorada, a Análise Combinatória. A pesquisa foi desenvolvida através de uma intervenção que contou com três atividades orientadoras aplicadas a estudantes de quatro turmas da 2ª série do Ensino Médio de uma escola pública estadual no interior paulista. As atividades foram elaboradas com o objetivo de colocar os alunos numa posição de ação e tomadas de decisões para facilitar o entendimento e o processo de construção do conhecimento e foram desenvolvidas em grupos de quatro ou cinco alunos. A pesquisa que classificamos como naturalista, pelo fato de que a coleta de dados foi realizada diretamente no local em que o problema acontece, tem como questão central verificar se o ensino de Análise Combinatória, sem o uso abusivo de fórmulas, através de atividades orientadoras e da utilização do princípio multiplicativo, pode melhorar o ensino e a compreensão desse conteúdo. Os resultados foram obtidos através da análise das atividades resolvidas pelos estudantes que foram filmadas, pela observação e pelas anotações feitas pelos pesquisadores e também pela avaliação realizada ao final da pesquisa. Pôde-se constatar que as atividades orientadoras foram essenciais para um melhor desempenho dos estudantes que se sentiram mais seguros e confiantes para a realização de novas atividades. Essas atividades representam o produto final desse trabalho e espera-se que se constituam em material de consulta para professores que buscam, incansavelmente, novas metodologias.

Cette thèse aborde l'étude de la structuration sémantique de la classe des noms abstraits, appréhendée sous l'angle de l'analysede leurs variations sémantiques régulières. La problématique qui sous-tend cette recherche est la suivante : de quelle façon les mécanismes de variation sémantique régulière permettent-ils d'appréhender la structure du lexique et en particulier celle des noms abstraits ? Cette problématique est abordée par l'étude de cas d'un sous-ensemble de noms abstraits : les noms d'affect. L'analyse des variations interprétatives régulières de ces noms se fonde sur une vaste étude de corpus. Le premier objectif est descriptif : nous mettrons en évidence les contraintes morpho-syntaxiques et sémantiques qui pèsent sur ces variations interprétatives et de nous déterminerons leur statut lexical. Le second objectif est explicatif : nous montrerons qu'il est possible de mettre en évidence des éléments sémantiques propres à expliquer la possibilité ou l'impossibilité de véhiculer une ou plusieurs variations interprétatives. Le dernier objectif est théorique : nous proposerons une réflexion sur la notion de polysémie régulière. Nous montrerons qu'il existe différents mécanismes de variation sémantique régulière qui ne peuvent pas recevoir un traitementidentique. / In this dissertation we study the semantic structure of the category of abstract nouns through the analysis of their regular semantic variations. The research questions underpinning this study are the following: how do the mechanisms of regular semantic variation allow us to apprehend the structure of the lexicon and of the abstract nouns in particular? We tackle these issues through the analysis of a subset of abstract nouns: the affect nouns. The observation of the regular interpretative variations of these nouns is based on a vast corpus study. The primary goal is descriptive: we will underline the morpho-syntactic and semantic constraints which weigh on these interpretative variations and determine their lexical status. The second goal is explanatory: we will show that it is possible to highlight certain semantic elements suitable to explain the possibility or impossibility of conveying one or more interpretative variations. The last goal is theoretical: we will discuss the concept of regular polysemy. We will show that there are various mechanisms of regular semantic variation at work which cannot receive an identical processing.