A configuration is a finite set of points in the plane. Two configurations have the same order type if there exists a bijection between them that preserves the orientation of every ordered triple. A configuration A contains a copy of a configuration B if some subset of A has the same order type of B and we denote this by B \\subset A. For a configuration B and a integer N, the extremal number ex(N,B)=max{|A|: B ot \\subset A \\subset [N]^2} is the maximum size of a subset of [N]^2 without a copy of B. We give an upper bound for general and convex cases. A random N-set is a set obtained by randomly choosing N points uniformly and independently in the unit square. A configuration is n-universal if contains all order types in general position of size n. We obtain the threshold for the n-universal property up to a log log factor, that is, we obtain integers N_0 and N_1 with log log N_1=O(log log N_0) such that if N >> N_1 (N << N_0), then a random N-set is n-universal with probability tending to 1 (tending to 0). We also determine a bound for the probability of obtaining a random set without a copy of a fixed configuration. / Uma configuração é um conjunto finito de pontos no plano. Duas configurações possuem o mesmo o-tipo se existe uma bijeção entre elas que preserva a orientação de toda tripla orientada. Uma configuração A contém uma cópia da configuração B se algum subconjunto de A possui o mesmo o-tipo que B e denotamos este fato por B \\subset A. Para uma configuração B e um inteiro N, o número extremal ex(N,B)=max{|A|: B ot \\subset A \\subset [N]^2} é o maior tamanho de um subconjunto de [N]^2 sem uma cópia de B. Neste trabalho, determinamos cotas superiores para o caso geral e para o caso convexo. Um N-conjunto aleatório é um conjunto obtido escolhendo N pontos uniformemente e independentemente ao acaso do quadrado unitário. Uma configuração é n-universal se contém todos os o-tipos de tamanho n. Determinamos o limiar da propriedade de um N-conjunto aleatório ser n-universal a menos de erros da ordem de log log, isto é, determinamos inteiros N_0 e N_1 com log log N_0=O(log log N_1) tais que se N >> N_1 (N << N_0), então o N-conjunto aleatório é n-universal com probabilidade tendendo a 1 (tendendo a 0). Também obtivemos cotas para a probabilidade de um conjunto aleatório não possuir determinado o-tipo.

Submitted by Marcos Samuel (msamjunior@gmail.com) on 2017-06-26T11:21:18Z No. of bitstreams: 1 DissertacaoNeildes.pdf: 3355750 bytes, checksum: ecd7c4cbddea6a04aa83a8878bfdee72 (MD5) / Approved for entry into archive by Vanessa Reis (vanessa.jamile@ufba.br) on 2017-06-29T13:03:37Z (GMT) No. of bitstreams: 1 DissertacaoNeildes.pdf: 3355750 bytes, checksum: ecd7c4cbddea6a04aa83a8878bfdee72 (MD5) / Made available in DSpace on 2017-06-29T13:03:37Z (GMT). No. of bitstreams: 1 DissertacaoNeildes.pdf: 3355750 bytes, checksum: ecd7c4cbddea6a04aa83a8878bfdee72 (MD5) / Este trabalho apresenta uma proposta de atividade criativa de descobrir padrões que respeitem restrições para o ensino de conceitos básicos de Geometria envolvendo construções geométricas em redes de pontos. Ele foi aplicado em um colégio estadual do Ensino Médio na cidade de Salvador - BA. Os trabalhos foram desenvolvidos com turmas de 3a série do turno matutino. Sendo solicitada nessa atividade construções de objetos geométricos a partir de alguma característica, propriedade, coloração (vértices e arestas) e visitas a teoremas importantes relacionados ao tema. Essa proposta é uma tentativa de tornar a Geometria mais interessante com um desenvolvimento mais criativo e sem excesso no uso de fórmulas. Tem como objetivo investigar e verificar a colaboração dessa abordagem no desenvolvimento da criatividade, na compreensão e percepção dos objetos geométricos e no fortalecimento do ensino ajudando na melhora da visão geométrica dos estudantes com base em conhecimentos desses conceitos, assim como de favorecer a identificação de padrões das formas geométricas e a percepção das diversas possibilidades de construções das figuras geométricas em rede de pontos. Tem a intenção de levar o estudante a brincar ao mesmo tempo em que aguça seu raciocínio e criatividade, despertando seu interesse e vontade de conhecer um pouco mais a Geometria. Para isso, foi realizada uma atividade de verificação com a qual se determinou o conhecimento prévio dos alunos sobre o tema, uma revisão com base nas dificuldades demonstradas pelos estudantes na resolução da atividade de verificação, para depois serem apresentadas malhas com representação de arranjos de pontos para as diversas construções geométricas com aplicação dos conhecimentos básicos de Geometria Euclidiana utilizando o teorema de Pick, coloração de vértices, arestas e o teorema das quatro cores. Obteve-se um resultado satisfatório, pois se verificou que a maioria deles desenvolveu a iniciativa e persistência na resolução dos problemas propostos e alguns desenvolveram a capacidade de construir os objetos como solicitado.

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T02:29:56Z (GMT). No. of bitstreams: 1 Couto_MarceloCastilho_M.pdf: 3682547 bytes, checksum: 899151df78f8e6950ce90ea8215ded91 (MD5) Previous issue date: 2010 / Resumo: Nesta dissertação, faz-se um amplo estudo multidisciplinar sobre duas variantes de um problema geométrico NP-DIFÍCIL, o Problema da Galeria de Arte, que é analisado tanto pela ótica geométrica quanto combinatória. O objetivo consiste em minimizar o número de guardas suficientes para cobrir todo o interior de uma galeria de arte, representada por um polígono simples. Dentre as muitas variantes desse problema, o foco foi dado àquela onde os guardas são estacionários e restritos aos vértices do polígono, ortogonal ou simples, sem obstáculos. Propõe-se neste trabalho um algoritmo iterativo exato que é capaz de resolver ambas as variantes do problema. Nesse algoritmo, o problema original é discretizado, reduzido a um problema combinatório, o Problema da Cobertura de Conjuntos, e modelado por programação linear inteira. A redução entre os problemas que assegura a corretude do algoritmo e as provas de exatidão e convergência para uma solução ótima do problema original são detalhadas. Apresenta-se também uma extensa experimentação de uma implementação desse algoritmo com o intuito de validar seu uso prático e analisar as várias estratégias propostas aqui para a discretização inicial da galeria. São dados resultados para instâncias com até 2500 vértices, mais de dez vezes o tamanho das maiores instâncias resolvidas exatamente na literatura pré-existente. Mostra-se que o número de iterações executadas pelo algoritmo está extremamente relacionada com o modo como a galeria é inicialmente discretizada. Considerando a estratégia de discretização com o melhor desempenho geral, tem-se que, na prática, o algoritmo converge para uma solução ótima para o problema original em um baixo tempo computacional e em um número de iterações que é ordens de grandeza aquém do limite teórico resultante da análise de pior caso / Abstract: In this dissertation, a broad multidisciplinary study is done on two variants of a geometrical NP-HARD problem, the Art Gallery Problem, which is approached both from geometrical and combinatorics perspectives. The goal is to minimize the number of guards sufficient to cover the interior of an art gallery whose boundary is represented by a simple polygon. Among the many variants of the problem, the focus was on one where the guards are stationary and are restricted to vertices of the polygon, orthogonal or simple, without holes. We propose an iterative exact algorithm to solve both variants of the problem. In this algorithm, the original problem is discretized, reduced to a combinatorial problem, the Set Cover Problem, and modeled as an integer linear program. The reduction between the problems, which ensures the correctness of the algorithm, and the proofs of its exactness and convergence to an optimal solution are detailed. We also present an extensive experimentation of an implementation of this algorithm in order to validate its practical use and analyze the various strategies proposed here for the initial discretization of the gallery. Results are given for instances with up to 2500 vertices, more than ten times the size of the largest instances solved to optimality in prior literature. It is shown that the number of iterations performed by the algorithm is highly related to how the gallery is initially discretized. Considering the discretization strategy with the best performance in practice, the algorithm converges to an optimal solution for the original problem in a low computation time and in a number of iterations that is orders of magnitude below the theoretical bound arising from the worst case analysis / Mestrado / Geometria Computacional e Otimização Combinatória / Mestre em Ciência da Computação