Graphs are a fundamental and widely-used abstraction for representing data. We can analytically study interesting aspects of real-world complex systems such as the Internet, social systems, transportation networks, and biological interaction data by modeling them as graphs. Graph-theoretic and combinatorial problems are also pervasive in scientific computing and engineering applications. In this dissertation, we address the problem of analyzing large-scale complex networks that represent interactions between hundreds of thousands to billions of entities. We present SNAP, a new high-performance computational framework for efficiently processing graph-theoretic queries on massive datasets. Graph analysis is computationally very different from traditional scientific computing, and solving massive graph-theoretic problems on current high performance computing systems is challenging due to several reasons. First, real-world graphs are often characterized by a low diameter and unbalanced degree distributions, and are difficult to partition on parallel systems. Second, parallel algorithms for solving graph-theoretic problems are typically memory intensive, and the memory accesses are fine-grained and highly irregular. The primary contributions of this dissertation are the design and implementation of novel parallel graph algorithms for traversal, shortest paths, and centrality computations, optimized for the small-world network topology, and high-performance multithreaded architectures and multicore servers. SNAP (Small-world Network Analysis and Partitioning) is a modular, open-source framework for the exploratory analysis and partitioning of large-scale networks. With SNAP, we demonstrate the capability to process massive graphs with billions of vertices and edges, and achieve up to two orders of magnitude speedup over state-of-the-art network analysis approaches. We also design a new parallel computing benchmark for characterizing the performance of graph-theoretic problems on high-end systems; study data representations for dynamic graph problems on parallel systems; and apply algorithms in SNAP to solve real-world problems in social network analysis and systems biology.

Made available in DSpace on 2015-05-07T15:08:20Z (GMT). No. of bitstreams: 1 parte1.pdf: 2773821 bytes, checksum: fb76fff21676798c65b8f19a1378b235 (MD5) Previous issue date: 2011-10-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work presents a strategy for teaching mathematics in a meaningful learning perspective, concerning the content of high school called Combinatorial Analysis, to understand the processes of counting from the understanding of the concepts involved. For the development of research, we used the assumptions of a teaching methodology based on the theory of David Ausubel and strategies of concept maps by Joseph Novak and Bob Gowin, as a mechanism for structuring the knowledge of students in the teaching and learning of the content mentioned. Ausubel tells us that knowledge is acquired and retained if the learner able to associate the relevant ideas in our pre-existing cognitive structure with the new information being offered. In this sense, Novak uses the concept maps for this relationship between existing and acquired knowledge is meaningful to the learner. Our study was an experiment, exposing Combinatorial Analysis content through the use of concept maps constructed and systematized by Bloom's Revised Taxonomy, so that we find meaningful learning in the apprentice. To check this, we apply a test before and after exposure of the content, using concept maps in the experimental class and without the use of concept maps in class Control. The results were evaluated on a quantitative and a qualitative analysis, proving that the use of concept maps in the study of mathematics, specifically in the content worked, favored meaningful learning. / Este trabalho apresenta uma estratégia de ensino de matemática numa perspectiva de aprendizagem significativa, referente ao conteúdo do Ensino Médio intitulado Análise Combinatória, a fim de que possamos entender os processos de contagem a partir da compreensão dos conceitos envolvidos. Para o desenvolvimento da pesquisa, utilizaram-se pressupostos de uma metodologia de ensino baseada na teoria de David Ausubel e nas estratégias dos mapas conceituais de Joseph Novak e Bob Gowin, como mecanismo de estruturação do conhecimento dos alunos no processo de ensino e aprendizagem do conteúdo mencionado. Ausubel nos fala que o conhecimento será adquirido e retido se o aprendiz conseguir associar as ideias relevantes pré existentes em sua estrutura cognitiva com as novas informações que estão sendo oferecidas. Nesta direção, Novak utiliza-se dos mapas conceituais para que essa relação entre o conhecimento existente e o adquirido tenha sentido para o aprendiz. Nosso trabalho foi de caráter experimental, expondo o conteúdo Análise Combinatória através do uso de mapas conceituais construídos e sistematizados pela Taxonomia de Bloom-Modificada, de maneira que verificamos a aprendizagem significativa no aprendiz. Para essa verificação, aplicamos um teste antes e depois da exposição do conteúdo, com uso de mapas conceituais na turma experimental e sem o uso de mapas conceituais na turma controle. Os resultados foram avaliados sobre um aspecto quantitativo e uma análise qualitativa, comprovando que o uso de mapas conceituais no estudo de matemática, especificamente no conteúdo trabalhado, favoreceu a aprendizagem significativa.

CAPES / O presente trabalho tem dois objetivos: o primeiro está relacionado ao ensino da análise combinatória nas séries do ensino fundamental 2 e ensino médio. O segundo objetivo e buscar aprofundar meus conhecimentos relacionados aos conceitos combinatoriais. Com relação ao primeiro objetivo, o ensino da análise combinatória, na minha trajetória como docente, tem sido uma das tarefas mais árduas que o professor de matemática da educação básica enfrenta. Diante disso, surgem algumas perguntas. Por que um assunto totalmente aplicável ao cotidiano tem gerado tanta dificuldade de compreensão? Um dos objetivos desse trabalho e buscar respostas para essa pergunta e propor sugestões que possam melhorar o entendimento desse conceito. Como segundo objetivo proposto, busquei compreender conceitos que até então, por mim, não dominados, aprofundando meu conhecimento combinatorial. Para tanto, esse trabalho possui uma parte dedicada ao estudo de conceitos combinatorias mais complexos, não o abordados junto aos alunos de ensino médio mas que permitem compreender situações combinatoriais mais complexas. / The present work has two major goals. The first one is related to the teaching of combinatorics in elementary school and high school. The second one is to seek further knowledge related to combinatorial concepts. Regarding the first goal, the teaching of combinatorics, in my trajectory as a teacher, has been one of the most arduous tasks that the math teacher of basic education faces. Therefore, some questions arise. Why a subject fully applicable to everyday, has generated so much trouble understanding? One of the goals of this work is to seek answers to this question and propose suggestions that can improve the understanding of this concept. As a second proposed goal, I sought to understand concepts that hitherto were not dominated, deepening my combinatorial knowledge. Therefore, this work has section devoted to the study of more complex combinatory concepts, not addressed to the students of high school but they allow us to understand more complex combinatorial situations.

Made available in DSpace on 2015-03-03T15:36:09Z (GMT). No. of bitstreams: 1 JoseRAB_DISSERT.pdf: 776491 bytes, checksum: bef691e2a550b6345b490b668bd8cb38 (MD5) Previous issue date: 2013-02-22 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Humans, as well as some animals are born gifted with the ability to perceive quantities. The needs that came from the evolution of societies and technological resources make the the optimization of such counting methods necessary. Although necessary and useful, there are a lot of diculties in the teaching of such methods.In order to broaden the range of available tools to teach Combinatorial Analysis, a owchart is presented in this work with the goal of helping the students to x the initial concepts of such subject via pratical exercises / Os seres humanos, assim como alguns animais, nascem dotados da capacidade de perceber quantidades. Portanto t?cnicas para contar quantidades foi um passo natural no desenvolvimento do homem. As necessidades provindas da evolu??o das sociedades e recursos tecnol?gicos tornam necess?rio a otimiza??o de tais m?todos de contagem. Apesar de necess?rio e ?til, o estudo desses m?todos no Ensino M?dio esbarram em dificuldades did?ticas. Com o objetivo de ampliar o leque de ferramentas dispon?veis aos professores para o ensino de An?lise Combinat?ria apresentamos neste trabalho um fluxograma que pretende dinamizar o processo de fixa??o dos conceito via resolu??o de exerc?cios

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2016-12-09T12:17:44Z No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2017-02-02T18:18:37Z (GMT) No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) / Made available in DSpace on 2017-02-02T18:18:37Z (GMT). No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) Previous issue date: 2016-10-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research analyses how an approach in the classroom via Problem Solving, Exploration and Posing can potentialize the teaching and learning of Combinatorial Analysis. A literature review was performed aiming to understand the contributions of other researchers on the researched theme, so that it could be possible to realize what is possible to deepen and add for the scientific community, regarding the teaching and learning process of the Combinatorial Analysis. Besides this, an interview with mathematics teachers was performed, aiming to know their ideas on teaching and learning of Combinatory Analysis and, afterwards, scrutinize until where they could help to plan a sequence of activities. The research was conducted according to a qualitative approach, aiming to search meanings, interpreting and comprehend the information obtained. The modality of research can be characterized as teacher research; according to which the professor is the researcher of his or her own classroom (LANKSHEAR AND KNOBEL, 2008). The teaching and learning Methodology chosen to work in the classroom was the one of the problem solving, exploration and posing, developed with a sequence of activities in a group of the 2nd year of Secondary School of a public school in the city of Alagoinha-PB, Brazil. During the intervention, this researcher acted as a researcher teacher, working in the classroom as a regent teacher, giving a utonomy to the students on the construction of the essential ideas of the Combinatory Analysis, in such a way that the author acted as a mediator and instigator. Data were collected during the lessons through observation and records of the materials used by the students, as well as sound recording. Twenty-one meetings were performed, totaling 25 lessons, each lesson lasting, at most, 45 minutes. The classroom was organized in groups of three students and, in some cases, in pairs, in order to carry out a cooperative and collaborative work, where it was considered important, in this process, the mutual respect among them, respecting the ideas arisen on the search of the problem solution. The results of the research highlighted that through the Mathematics teaching and learning approach via Problem Solving, Exploration and Posing it was possible to monitor the growth of the students, who created their own ideas to solve the problems, and, consequently, found multiple strategies for solution of them; posteriorly, justify their solutions, participating effectively of the construction of their knowledge. Besides this, the students engaged in activities of mathematical exploration, which enabled the comprehension of the essential ideas of Combinatorial Analysis, as well as assuming the role of investigators in the classroom, generalizing, formulating new problems and, afterwards, solving them. From which it follows that such methodology allows learning with more comprehension, strengthening the student to solve problems of Combinatorial Analysis with focus not only on the search of the problem solution, but also on the process of the solution and being able to go far beyond, like the performance of a work of problem posing and exploration. / A presente pesquisa analisa como uma abordagem em sala de aula via Resolução, Exploração e Proposição de problemas pode contribuir/potencializar com o ensino-aprendizagem de Análise Combinatória. Foi realizada uma revisão de literatura com o intuito de compreender as contribuições de outros pesquisadores acerca do tema pesquisado, para que se pudesse perceber o que é possível aprofundar e acrescentar para a comunidade científica, no que diz respeito ao processo de ensino-aprendizagem da Análise Combinatória. Além disso, foi realizada uma entrevista com professores de Matemática, com o intuito de conhecer as suas ideias acerca do ensino-aprendizagem de Combinatória e, posteriormente, perscrutar até que ponto elas poderiam colaborar a planejar uma sequência de atividades. A pesquisa foi empreendida segundo uma abordagem qualitativa, visando buscar significados, interpretar e compreender as informações obtidas. A modalidade de pesquisa pode ser caracterizada como pedagógica, segundo a qual o professor é o pesquisador de sua própria sala de aula (LANKSHEAR E KNOBEL, 2008). A Metodologia de ensino-aprendizagem escolhida para trabalhar em sala de aula foi a de resolução, exploração e proposição de problemas, desenvolvida com uma sequência de atividades em uma turma do 2ª ano do Ensino Médio de uma escola pública na cidade de Alagoinha-PB. Durante a intervenção, o presente pesquisador agiu como professor-pesquisador, trabalhando em sala de aula como professor regente, dando autonomia aos alunos na construção das ideias essenciais de Combinatória, de modo que o autor agiu como mediador e incentivador. Os dados foram levantados durante as aulas através das observações e registros dos materiais utilizados pelos alunos, bem como de gravação sonora. Foram realizados 21 encontros, totalizando 25 aulas, cada aula com duração de, no máximo, 45 minutos. A sala foi organizada em grupos de três alunos e, em alguns casos, em duplas, com o intuito de se realizar um trabalho cooperativo e colaborativo, onde se considerou importante, nesse processo, o respeito mútuo entre eles, respeitando as ideias levantadas na busca da solução dos problemas. Os resultados da pesquisa evidenciaram que através da abordagem via Resolução, Exploração e Proposição de problemas foi possível acompanhar o crescimento dos alunos, que criaram suas próprias ideias para resolver os problemas, e, consequentemente, encontraram múltiplas estratégias de resolução deles; posteriormente, justificam suas soluções, participando efetivamente da construção do seu conhecimento. Além disso, os alunos engajaram-se em atividades de exploração matemática que lhes possibilitaram a apreensão de ideias essenciais de Análise Combinatória, como também assumiram o papel de investigadores em sala de aula, fazendo generalizações, formulando novos problemas e, em seguida, os resolvendo. De onde se conclui que tal metodologia permitiu um aprendizado com mais compreensão, potencializando o aluno para resolver problemas de Análise Combinatória com foco não apenas na busca da solução do problema, mas no processo da resolução e podendo ir muito além, como a realização de um trabalho de proposição e exploração de problemas.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Counting techniques studied in basic education aim at the resolutions os simplest combinatorial problems. In this work, we present the generating functions, a powerful tool to solving more complex problems of counting. In this way, we discuss the contents of combinatorial analysis through the study of generating functions, proposing a didactic sequence on the subject for teachers of basic education can expand and diversify their teaching strategies, by means of this counting method. / As t ecnicas de contagem estudadas na educação b ásica visam as resolu ções de problemas combinat órios mais simples. Neste trabalho, apresentaremos as funções geradoras, uma poderosa ferramenta para solucionar problemas mais complexos de contagem. Destaforma, abordaremos o conte udo de an alise combinat ória atrav és do estudo de funções sgeradoras, propondo uma sequência did ática sobre o tema para que os professores da educação b ásica possam ampliar e diversi car as suas estrat égias de ensino, a a partir deste novo método de contagem.

Orientador: José Plínio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T04:32:08Z (GMT). No. of bitstreams: 1 BrasilJunior_NelsonGomes_M.pdf: 980636 bytes, checksum: dd8d61baeb633d5f598abc3523def800 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, estudamos a sequência dos Números de Catalan, uma sequência que aparece como solução de vários problemas de contagem envolvendo árvores, palavras, grafos e outras estruturas combinatórias. Atualmente, são conhecidas cerca de 200 interpretações combinatórias distintas para os Números de Catalan, o que motiva o estudo de relações entre estas interpretações, isto é, entre conjuntos cuja cardinalidade é dada pelos termos desta sequência. O principal objetivo do nosso trabalho é, portanto, mostrar bijeções entre esses conjuntos. No início do texto fazemos uma pequena introdução histórica aos números de Catalan, assim como definimos algumas formas de representar a sequência estudada. Depois mostramos algumas bijeções clássicas entre conjuntos contados pela sequência de Catalan. Além disso, apresentamos outras bijeções entre conjuntos envolvendo diversos objetos combinatórios. No total, são exibidas 29 bijeções / Abstract: In this work, we study the sequence of Catalan Numbers, which appears as a solution of many counting problems involving trees, words, graphs and other combinatorial structures. Nowadays, about 200 different combinatorial interpretations of the Catalan Numbers are known and that motivates the study between them, i. e., the study between sets whose cardinality is given by the terms of this sequence. The main objective of our work is therefore to show bijections between these sets. In the beginning, we make a short historical introduction of the Catalan Numbers and define some ways to represent the sequence. After that, we show some classical bijections between sets counted by the Catalan Numbers. Additionally, we exhibit other bijections between sets involving several combinatorial objects. Altogether, 29 bijections are presented / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Jacques Wainer / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:42:33Z (GMT). No. of bitstreams: 1 Passos_AlexandreTachard_D.pdf: 2615030 bytes, checksum: 93841a46120b968f6da6c9aea28953b7 (MD5) Previous issue date: 2013 / Resumo: Em processamento de linguagem natural, e em aprendizado de máquina em geral, é comum o uso de modelos gráficos probabilísticos (probabilistic graphical models). Embora estes modelos sejam muito convenientes, possibilitando a expressão de relações complexas entre várias variáveis que se deseja prever dado uma sentença ou um documento, algoritmos comuns de aprendizado e de previsão utilizando estes modelos são frequentemente ineficientes. Por isso têm-se explorado recentemente o uso de relaxações usando programação linear deste problema de inferência. Esta tese apresenta duas contribuições para a teoria e prática de relaxações de programação linear para inferência em modelos probabilísticos gráficos. Primeiro, apresentamos um novo algoritmo, baseado na técnica de geração de colunas (dual à técnica dos planos de corte) que acelera a execução do algoritmo de Viterbi, a técnica mais utilizada para inferência em modelos lineares. O algoritmo apresentado também se aplica em modelos que são árvores e em hipergrafos. Em segundo mostramos uma nova relaxação linear para o problema de inferência conjunta, quando se quer acoplar vários modelos, em cada qual inferência é eficiente, mas em cuja junção inferência é NP-completa. Esta tese propõe uma extensão à técnica de decomposição dual (dual decomposition) que permite além de juntar vários modelos a adição de fatores que tocam mais de um submodelo eficientemente / Abstract: In natural language processing, and in general machine learning, probabilistic graphical models (and more generally structured linear models) are commonly used. Although these models are convenient, allowing the expression of complex relationships between many random variables one wants to predict given a document or sentence, most learning and prediction algorithms for general models are inefficient. Hence there has recently been interest in using linear programming relaxations for the inference tasks necessary when learning or applying these models. This thesis presents two contributions to the theory and practice of linear programming relaxations for inference in structured linear models. First we present a new algorithm, based on column generation (a technique which is dual to the cutting planes method) to accelerate the Viterbi algorithm, the most popular exact inference technique for linear-chain graphical models. The method is also applicable to tree graphical models and hypergraph models. Then we present a new linear programming relaxation for the problem of joint inference, when one has many submodels and wants to predict using all of them at once. In general joint inference is NP-complete, but algorithms based on dual decomposition have proven to be efficiently applicable for the case when the joint model can be expressed as many separate models plus linear equality constraints. This thesis proposes an extension to dual decomposition which allows also the presence of factors which score parts that belong in different submodels, improving the expressivity of dual decomposition at no extra computational cost / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The present work is about didactic proposal, applied in high school students. This proposal objective approaches a mode with more means to the students, concepts of combinatorial analysis. A content that put away teachers and students to like the mathematics, in this dissertation the proposal is through the pedagogical trend of resolution problems. Trend this that have how characteristics the development of concepts by the students through problems prepared for this challenge. Propose a method more free of the formulas, that a lot of times are used too much at the traditional teach way. To this experimentation went choose the high school João Thiches, localized in Caxias do Sul-RS. Before the experience was made all the substantiation to use the propose, the why of its importance, where found the suitable material and some examples about how approach a class with this trend that we defend. / O presente trabalho refere-se a uma proposta didática aplicada aos alunos do Ensino Médio. Esta proposta tem o intuito de abordar de modo mais significativo para os discentes conceitos de análise combinatória. Um conteúdo que afasta professores e estudantes do gosto pela matemática é proposto nesta dissertação através da tendência pedagógica de Resolução de Problemas, tendência que tem como característica o desenvolvimento dos conceitos pelo aluno através de problemas elaborados para esse desafio. Propõe-se um método livre de fórmulas, muitas vezes, usadas em demasia nos métodos mais tradicionais de ensinar análise combinatória. Para essa experimentação, foi escolhida a Escola Estadual de Ensino Médio João Triches, localizada na cidade de Caxias do Sul-RS. Antes da experiência propriamente dita foi ofertada toda a fundamentação para a utilização da proposta, o porquê da sua importância, onde encontrar o material adequado e alguns exemplos de como abordar uma aula com a tendência que defendemos.

The history of Brazilian education is marked by traditional teaching, so that the school curriculum has contributed for many decades to the passive formation of students. In this context, the teacher was the central figure of knowledge and the student was seen as being incapable, therefore, it was up to him to only listen to the teacher and memorize formulas devoid of meanings. Obviously listening to the teacher remains important, and memorizing formulas may be helpful in some circumstances. However, to restrict the teaching of mathematics to such procedures would be to limit the potential of the human being and would no longer meet the aspirations of contemporary society. The actuality is marked by the excess of information, therefore, the learner can collect data in the virtual world directly, not needing the mathematics teacher to transmit a formula. Faced with this reality, the teaching of mathematics needs to be rethought, so that the contents worked out have a social (or personal) sense for the student, as well as enable students to use early research techniques, to value collective work, contributing to that act in a critical, patitious and autonomous way. Based on these principles, the theme PROBABILITY IN AVERAGE EDUCATION: active methodology as support presents a rescue of the socio-historical dimension of this area of knowledge, valuing the challenges and contributions of several mathematicians precursors of Pascal. These studies focused on the properties and applications of probability in random phenomena and experiments, emphasizing their use in the area of genetics. As a pedagogical proposal, Webquest presented itself as an alternative, since it presents activities structured in virtual environments, which, when guided by research and collaborative work, contribute to the development of the student's critical and autonomous sense. / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A história da educação brasileira é marcada pelo ensino tradicional, de modo que o currículo escolar contribuiu por muitas décadas para a formação passiva dos alunos. Neste contexto, o professor era a figura central do conhecimento e o aluno era visto como ser incapaz, portanto, cabia ao mesmo apenas ouvir atentamente ao professor e memorizar fórmulas desprovidas de significados. Obviamente que ouvir o professor permanece importante, e a memorização de fórmulas pode ser útil em algumas circunstâncias. Todavia, restringir o ensino de matemática a esses procedimentos seria limitar o potencial do ser humano e não atenderia mais aos anseios da sociedade contemporânea. A atualidade é marcada pelo excesso de informação, assim sendo, o educando pode coletar dados no mundo virtual de forma direta, não necessitando do professor de matemática para transmitir uma fórmula. Diante desta realidade, o ensino da matemática precisa ser repensado, de modo que os conteúdos trabalhados apresentem um sentido social (ou pessoal) para o aluno, bem como possibilitem aos educandos fazer uso de técnicas iniciais da pesquisa, valorizar o trabalho coletivo, contribuindo para que atuem de forma crítica, participativa e autônoma. Partindo destes princípios, o tema PROBABILIDADE NO ENSINO MÉDIO: metodologia ativa como suporte apresenta um resgate da dimensão socio-histórica dessa área de conhecimento, valorizando os desafios e as contribuições de diversos matemáticos precursores de Pascal. Estes estudos enveredaram em direção as propriedades e aplicações da Probabilidade em fenômenos e experimentos aleatórios, enfatizando seu emprego na área de genética. Como proposta pedagógica, apresentou-se a Webquest como alternativa, uma vez que a mesma apresenta atividades estruturadas em ambientes virtuais, que ao serem norteadas pela pesquisa e pelo trabalho colaborativo, contribuem para o desenvolvimento do senso crítico e autônomo do alunado.