Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse. / In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.

Na cultura da soja, a ocorrência de doenças fúngicas como o mofo branco e a ferrugem asiática, tem reduzido a produtividade de grãos significativamente nos últimos anos. Esta pesquisa objetivou: a) avaliar o potencial de cruzamentos de soja para a obtenção de progênies com boas características agronômicas, com ênfase em produtividade, resistência ao mofo branco e tolerância à ferrugem; b) avaliar a reação ao fungo causador do mofo branco nos genótipos estudados e c) avaliar a tolerância à ferrugem em gerações precoces por meio da estimação do efeito ferrugem. O material genético foi oriundo de um dialelo parcial, com 50 cruzamentos, entre o grupo I (dez genitores representados por linhagens experimentais (USP) com alta produtividade de grãos) e o grupo II (cinco genitores - com indicações na literatura de possível resistência ao mofo branco). Em 2012/13, dois experimentos foram conduzidos, sendo o primeiro com os 50 cruzamentos (geração F2) e três testemunhas comuns e o segundo envolvendo os 15 genitores e as mesmas três testemunhas. Em 2013/14 e 2014/15, a fim de se estimar o efeito ferrugem (nível de tolerância) por meio da diferença (perda) entre as médias de produtividade de grãos (PG) e tamanho das sementes (peso de cem sementes ou PCS), os experimentos com os cruzamentos (gerações F3 e F4) e os genitores foram esquematizados em quatro experimentos (dois manejos para cruzamentos e dois manejos para genitores): manejo O&P, com aplicações de fungicidas para o controle da ferrugem e outras doenças fúngicas; manejo D, com aplicações de fungicida para controle de doenças fúngicas, exceto a ferrugem. Separadamente, dez plantas F4 de cada cruzamento e os genitores foram avaliados quanto à reação ao mofo branco utilizando o método da inoculação de folhas destacadas, a fim de se estimar a área abaixo da curva de progresso da doença. De modo geral, para todas as gerações avaliadas foi observada superioridade de 2,2% para PG dos cruzamentos em relação aos genitores. As perdas médias dos genótipos na presença da ferrugem foram 2,1% e 5,5% para PG e PCS, respectivamente. Considerando a PG, a resistência ao mofo branco e a tolerância à ferrugem, os cinco melhores cruzamentos foram: 111 (USP70.006 x MSOY6101), 131 (USP70.080 x MSOY6101), 133 (USP70.080 x A4725RG), 113 (USP70.006 x A4725RG) e 126 (USP 70.057 x MSOY 6101). Os melhores genitores foram A4725RG e USP70.080. Como padrões de resistência ao mofo branco foram identificados os cruzamentos 142 (USP70.109 x PI153.282) e 111 (USP70.006 x MSOY6101) e os genitores MSOY6101 e Caiapônia; e de suscetibilidade, os cruzamentos 114 (USP70.006 x EMGOPA313) e 135 (USP70.080 x Caiapônia) e os genitores USP14-01-20 e USP70.004. Além disso, as seguintes conclusões foram obtidas: a) as análises dialélicas foram eficazes em identificar populações F2 de maior potencial de ganho genético na seleção; b) a estratégia de se usar diferentes tipos de fungicidas mostrou-se eficiente para estimar a reação das plantas à ferrugem, em termos de PG e PCS; c) a metodologia da folha destacada foi útil em diferenciar os genótipos quanto à resistência das plantas ao mofo branco. / In soybean, the occurrence of fungal diseases such as white mold and Asian rust has reduced seed yield significantly over the past years. This work aimed to: a) assess the potential of soybean crosses to obtain progenies with good agronomic traits, with emphasis on seed yield, white mold resistance and tolerance to rust; b) assess the reaction of genotypes to Sclerotinia sclerotiorum, fungus that cause white mold; c) assess tolerance to rust in early generations through methods of estimation of the rust effect. The genetic material was derived from a partial diallel with 50 crosses between the group I (ten parents - experimental lines, USP, with high seed yield), and group II (five parents - with evidences from the literature of certain resistance to white mold). In 2012/13, two experiments were conducted, the first with 50 crosses (F2) and three common checks; and, the second one involving the 15 parents and the same three checks. In the 2013/14 and 2014/15, in order to estimate the rust effect (tolerance level) by the difference (loss) between the seed yield (PG) and one hundred-seed weight (PCS), experiments with crosses (F3 and F4 generations) and parents were designed in four experiments (two disease managements to crosses and two disease managements to parents); management O&P, with applications of fungicides to control rust and other fungal diseases; management D, with applications of one fungicide for controlling the late season leaf diseases, except rust. Separately, ten F4 plants of each cross and the parents were evaluated for resistance to white mold using the method of inoculation in detached leaves in order to estimate the area under the disease progress curve. In general, for all evaluated generations it was observed superiority of 2,2% in the PG of the crosses, related to the parents. The average loss of PG was 2,1% on the genotypes under study in the presence of rust and the average loss in seed size was 5,5%. Considering the resistance to white mold, tolerance rust and high means of PG, the five best crosses were: 111 (USP 70.006 x MSOY6101), 131 (USP 70.080 x MSOY6101), 133 (USP 70 .080 x A4725RG), 113 (USP 70.006 x A4725RG) and 126 (USP 70.057 x MSOY 6101). The best parents were A4725RG and USP 70.080. As resistance standards to white mold were identified the crosses 142 (USP 70.109 x PI 153282) and 111 (USP 70.006 x MSOY6101) and the parents MSOY6101 and Caiapônia; Susceptibility standards were the crosses 114 (USP 70.006 x EMGOPA 313) and 135 (USP 70.080 x Caiapônia) and the parents USP14-01-20 and USP 70.004. In addition, the following conclusions were obtained a) the diallel analyzes were effective in identifying F2 populations with higher potential for selection gain; b) the strategy of using different managements of fungicides was efficient to estimate the response of plants to rust in terms of PG and PCS; c) the methodology of detached leaf was useful in differentiating the genotypes for resistance to white mold.

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

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática / Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Zanoni Dias / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T03:52:46Z (GMT). No. of bitstreams: 1 Dias_UlissesMartins_D.pdf: 19168517 bytes, checksum: 463a6e15e1414ce37a0fe80f92de6b07 (MD5) Previous issue date: 2012 / Resumo: Esta tese aborda três aspectos da comparação entre genomas: primeiro, eventos de transposição; segundo, eventos de reversão e de reversão quase-simétrica; terceiro, estudo da distância entre genomas sem ligação com algum tipo específico de rearranjo. O estudo do primeiro aspecto, eventos de transposição, permitiu a criação de um novo algoritmo de aproximação na razão 1.375 e de modelos exatos usando programação em lógica com restrições para o problema da distância de transposição. Ambas as abordagens foram comparadas com outras semelhantes encontradas na literatura e, em ambos os casos, foi mostrado que o produto aqui apresentado é superior 'aqueles previamente conhecidos. Sob o segundo aspecto, eventos de reversões e de reversões quase-simétricas, houve avanços relacionados ao entendimento do processo de diferenciação das espécies na família Pseudomonadaceae e nos gêneros Mycobacterium, Shewanella e Xanthomonas com a criação de uma ferramenta de simulação capaz de gerar um histórico evolutivo com características semelhantes 'as observadas nos referidos grupos. Além disso, foram obtidos avanços em abordagens algorítmicas para o problema de construção de scaffolds usando um genoma de referência. De modo particular, foi obtida uma ferramenta superior 'as demais existentes na literatura para construção de scaffolds de genomas bacteriais. Ainda neste segundo aspecto, tratou-se do problema da distância de reversões quase-simétricas com a geração de um algoritmo guloso que fornece uma sequência de reversões quase-simétricas para ordenar qualquer permutação, além de algoritmos exatos para várias famílias específicas de permutações. No que diz respeito ao terceiro aspecto, foram desenvolvidas duas medidas que podem ser calculadas de forma eficiente (poucos segundos). Uma das medidas é adequada para genomas próximos e a outra é adequada para genomas distantes. Ambas foram avaliadas com genomas bacteriais reais, o que mostrou as vantagens e limitações de cada medida. Com esta tese, espera-se ter contribuído para a área de comparação de genomas em geral e, em particular, para a área de rearranjo de genomas / Abstract: In this PhD thesis, we work on three aspects of genome comparison: first, transposition events; second, inversion and almost-symmetric inversion events; third, whole-genome distance measures that are not connected to any specific kind of rearrangement event. The study of transposition events (first aspect) allowed us to create a new 1.375-approximation algorithm and some exact models using constraint logic programming. These approaches were compared to other published methods and in all cases our methods perform best. The second aspect of this thesis concerns inversion and almost-symmetric inversion events. In this regard, we developed a simulation tool for the study of symmetric inversions in bacterial genomes. Through this work we were able to contribute to the understanding of the evolutionary differentiation process in species of the following groups: the Pseudomonadaceae family, the Xanthomonas genus, the Shewanella genus, and the Mycobacterium genus. We used the knowledge acquired in building our simulation tool to establish a method that uses inversion signatures to generate draft genome sequence scaffolds using a complete genome as a reference. Apart from the practical applications of this research, we contribute to the computer science field by providing a theoretical framework for the almost-symmetric distance problem that can be improved in the future and can serve as a basis for approximation and heuristic algorithms. This framework is comprised of a greedy algorithm for any permutation, exact algorithms for specific families of permutation, and several lemmas and conjectures related to these problems. The third and last aspect of this thesis addresses the need for methods that can quickly and effectively compare large sets of genome sequences. We propose two new methods for efficiently determining whole genome sequence distance measures. One of them is aimed at comparing closely related genomes, and the other is meant to compare more distant genomes. Both measures were evaluated in order to find their limitations and their efficacy. It is our hope that thiswork represents a contribution to knowledge of the genome comparison field in general, and the genome rearrangement field, in particular / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientador: Luiz Carlos Pereira da Silva / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T07:50:24Z (GMT). No. of bitstreams: 1 Alcantara_MarcioVenicioPilar_M.pdf: 1100908 bytes, checksum: 0913d60c47bc87e4c67320408f6905af (MD5) Previous issue date: 2005 / Resumo: É sabido que o maior volume de perdas ocorre nos sistemas de distribuição de energia elétrica. Capacitores shunt são largamente utilizados nos alimentadores primários dos sistemas de distribuição para compensar potência reativa e conseqüentemente obter melhor perfil de tensão, reduções das perdas de potência e energia, e aumento da capacidade da rede de distribuição em atender carga ativa. A decisão do local ótimo de instalação de bancos de capacitores corresponde a um problema de programação matemática combinatorial. A determinação da influência da modelagem da carga na solução do problema, a inclusão de objetivos técnicos relacionados ao controle de tensão, custos de operação e de manutenção, e perdas de potência e energia, resultando numa nova formulação multi-critério com critérios conflitantes para o problema, e a viabilidade da aplicação de algoritmos genéticos como método de solução dessa nova formulação justificaram o desenvolvimento desta pesquisa. A definição do problema, e o desenvolvimento de modelagens matemáticas podem ser encontrados na primeira parte do trabalho. Na segunda parte apresentam-se os métodos de resolução utilizados nesse trabalho, são eles: heurísticos, e um método meta-heurístico. Um dos métodos heurísticos utiliza fatores de participação reativos da teoria de estabilidade de tensão para resolução do problema. O método meta-heurístico é um algoritmo baseado em algoritmos genéticos que resolve a formulação matemática apresentada anteriormente. Os métodos são testados utilizando-se uma rede real de 70 barras. Efeitos de cargas dependentes da tensão no problema são avaliados / Abstract: It is well known that the major portion of active power losses happen in the electric power distribution feeders. Shunt capacitors are broadly used in the primary feeders to compensate reactive power and consequently to obtain better voltage profile, reductions of power and energy losses, and increase the distribution network capacity in supplying active power demand. The decision of the optimal capacitors banks installation corresponds to a combinatorial mathematical programming problem. The determination of the influence of the load modeling in the solution of the problem, the inclusion of technical objectives relating to voltage control, costs of operation and maintenance, and cost of power and energy losses, resulting in a new multi-criteria formulation with conflicting criteria to the problem, and the viability of the application of genetic algorithms as method of solution of that new formulation justified the development of this research. The definition of the problem and the development of mathematical models can be found in the first part of the work. In the second it is presented the resolution methods, they are: heuristic, and a meta-heuristic method. One of the heuristic methods uses reactive participation factors commonly applied for voltage stability analysis of power systems. The meta-heuristic method is an algorithm based on genetic algorithms that solve the mathematical formulation previously presented. The methods are tested by using a real network of 70 bars. Effects of voltage dependent loads in the problem are quantified / Mestrado / Energia / Mestre em Engenharia Elétrica

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.

Orientadores: Christiano Lyra Filho, Celso Cavellucci / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-07T20:13:55Z (GMT). No. of bitstreams: 1 Bueno_EdilsonAparecido_M.pdf: 1593593 bytes, checksum: ff2749c689002cc1c4de48ee0899defc (MD5) Previous issue date: 2005 / Resumo: Este trabalho apresenta uma nova visão para o problema de redução das perdas técnicas em sistemas de distribuição de energia elétrica, através de reconfiguração de redes. A principal inovação consiste em abordar o problema com a consideração explícita das variações de demandas, mas impondo-se a restrição de que as configurações devem permanecer fixas ao longo do período de planejamento. Esta característica abre a perspectiva de que a metodologia venha a ser usada na operação diária dos sistemas de distribuição. No entanto, leva a um problema de otimização bem mais complexo do que o caracterizado pela visão tradicional. Formulações para demandas fixas e variáveis são desenvolvidas. Duas metodologias distintas para abordagem do novo problema são elaboradas. A primeira utiliza a metodologia denominada Busca Menor Energia, inspirada na técnica de Abertura Seqüencial de Chaves. A segunda técnica, denominada Árvore de Aproximação, faz uso das idéias de árvore geradora de custo mínimo. Ambas são combinadas com uma busca local, denominada Troca de Ramos Generalizada, baseada na técnica de Troca de Ramos. Explora-se também uma extensão da metodologia Árvore de Aproximação caracterizada por associação com conceitos do método GRASP (Greedy Randomized Adaptive Search Procedure). Estudos de casos ilustram a aplicação das metodologias em redes de cidades brasileiras / Abstract: This work presents a new point of view for the technical losses reduction problem in electric power distribution systems, through network reconfigurations. The main innovation is the explicit consideration of demand variations and the use of a fixed configuration during the planning period. This last characteristic makes the methodology able to be used in the daily operation of distribution systems. However, it leads to an optimization problem more complex than approaches without demand variations. Formulations for fixed and variable demands are created. Two distinct methodologies for the resolution of the new problem are elaborated. The first one uses the Minimum Energy Losses methodology, inspired by the ¿Sequential Switch Opening¿ technique. The last one, called Approximation Tree, is based on algorithms for the minimum spanning tree problem. Both of them are combined with a local search procedure, called Branch Exchange by Energy, based on the ¿Branch Exchange¿ technique. An extension of the Approximation Tree methodology is proposed by using concepts of the well-known GRASP method (Greedy Randomized Adaptive Search Procedure). Case Studies demonstrate the application of the methodologies in Brazilian cities¿ networks / Mestrado / Automação / Doutor em Engenharia Elétrica

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.

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T03:28:44Z (GMT). No. of bitstreams: 1 Oliveira_SaulloHaniellGalvaode_M.pdf: 1171322 bytes, checksum: 5488cfc9b843dbab6d7a5745af1e3d4b (MD5) Previous issue date: 2015 / Resumo: Biclusterização envolve a clusterização simultânea de objetos e seus atributos, definindo mo- delos locais de relacionamento entre os objetos e seus atributos. Assim como a clusterização, a biclusterização tem uma vasta gama de aplicações, desde suporte a sistemas de recomendação, até análise de dados de expressão gênica. Inicialmente, diversas heurísticas foram propostas para encontrar biclusters numa base de dados numérica. No entanto, tais heurísticas apresen- tam alguns inconvenientes, como não encontrar biclusters relevantes na base de dados e não maximizar o volume dos biclusters encontrados. Algoritmos enumerativos são uma proposta recente, especialmente no caso de bases numéricas, cuja solução é um conjunto de biclusters maximais e não redundantes. Contudo, a habilidade de enumerar biclusters trouxe mais um cenário desafiador: em bases de dados ruidosas, cada bicluster original se fragmenta em vá- rios outros biclusters com alto nível de sobreposição, o que impede uma análise direta dos resultados obtidos. Essa fragmentação irá ocorrer independente da definição escolhida de co- erência interna no bicluster, sendo mais relacionada com o próprio nível de ruído. Buscando reverter essa fragmentação, nesse trabalho propomos duas formas de agregação de biclusters a partir de resultados que apresentem alto grau de sobreposição: uma baseada na clusteriza- ção hierárquica com single linkage, e outra explorando diretamente a taxa de sobreposição dos biclusters. Em seguida, um passo de poda é executado para remover objetos ou atributos indesejados que podem ter sido incluídos como resultado da agregação. As duas propostas foram comparadas entre si e com o estado da arte, em diversos experimentos, incluindo bases de dados artificiais e reais. Essas duas novas formas de agregação não só reduziram significa- tivamente a quantidade de biclusters, essencialmente defragmentando os biclusters originais, mas também aumentaram consistentemente a qualidade da solução, medida em termos de precisão e recuperação, quando os biclusters são conhecidos previamente / Abstract: Biclustering involves the simultaneous clustering of objects and their attributes, thus defin- ing local models for the two-way relationship of objects and attributes. Just like clustering, biclustering has a broad set of applications, ranging from an advanced support for recom- mender systems of practical relevance to a decisive role in data mining techniques devoted to gene expression data analysis. Initially, heuristics have been proposed to find biclusters, and their main drawbacks are the possibility of losing some existing biclusters and the inca- pability of maximizing the volume of the obtained biclusters. Recently efficient algorithms were conceived to enumerate all the biclusters, particularly in numerical datasets, so that they compose a complete set of maximal and non-redundant biclusters. However, the ability to enumerate biclusters revealed a challenging scenario: in noisy datasets, each true bicluster becomes highly fragmented and with a high degree of overlapping, thus preventing a direct analysis of the obtained results. Fragmentation will happen no matter the boundary condi- tion adopted to specify the internal coherence of the valid biclusters, though the degree of fragmentation will be associated with the noise level. Aiming at reverting the fragmentation, we propose here two approaches for properly aggregating a set of biclusters exhibiting a high degree of overlapping: one based on single linkage and the other directly exploring the rate of overlapping. A pruning step is then employed to filter intruder objects and/or attributes that were added as a side effect of aggregation. Both proposals were compared with each other and also with the actual state-of-the-art in several experiments, including real and artificial datasets. The two newly-conceived aggregation mechanisms not only significantly reduced the number of biclusters, essentially defragmenting true biclusters, but also consistently in- creased the quality of the whole solution, measured in terms of Precision and Recall when the composition of the dataset is known a priori / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica