Resumo: Este trabalho propõe algoritmos determinísticos que, dado um conjunto com n chaves, constroem em tempo esperado O(n) uma função hash com tempo de busca no pior caso O(1), a qual mapeia sem colisão as chaves para o conjunto {0, . . . , n-1}. Esses esquemas de hashing perfeitos e mínimos são meras variantes dos esquemas aleatorizados de Botelho, Kohayakawa e Ziviani (2005) e Botelho, Pagh e Ziviani (2007) e mostraram resultados empíricos equivalentes aos dos algoritmos originais. As variantes determinísticas foram implementadas a partir dos códigos dos esquemas originais desenvolvidos na biblioteca CMPH pelos próprios autores, a qual é mantida no SourceForge.net. Todos os esquemas foram alimentados com os mesmos conjuntos de chaves, para que pudessem ser comparados com justiça. Foram executados testes para conjuntos com até 25 000 000 de chaves. Ademais, os esquemas propostos contam evidentemente com a vantagem de sempre produzirem a mesma hash para um mesmo conjunto de chaves. Esse comportamento determinístico pode ser útil para o desenvolvimento dum esquema dinâmico de hashing, em que figuram operações como inserção e deleção de chaves, inspirado num dos excelentes esquemas estáticos abordados. Um dos esquemas de Botelho, Pagh e Ziviani (2007), por exemplo de excelência, constrói hashes representáveis por apenas aproximadamente 2,62 bits por chave. Tal resultado é muito próximo da cota inferior justa conhecida, de aproximadamente 1,44 bits por chave. Tanto as versões determinísticas propostas quanto as originais mostram-se práticas para aplicações reais de Hashing. No entanto, na fundamentação teórica do trabalho de Botelho, Kohayakawa e Ziviani (2005) ainda restava uma conjectura. A presente dissertação também propõe uma demonstração para a conjectura e encerra a corretude do esquema.

Made available in DSpace on 2016-04-27T16:58:47Z (GMT). No. of bitstreams: 1 David Luiz Mazzanti.pdf: 2133856 bytes, checksum: 42bf84db8b1bbaacf676eaac575aceed (MD5) Previous issue date: 2008-10-27 / Secretaria da Educação do Estado de São Paulo / This study is a qualitative research that aims to looked at four pairs of students in the 3rd grade of high school segment of the education of the Education of Young and Adults (EJA) from a public school and the central municipality of Franco da Rocha. These students solved problems four situations-problems, which were guided by the Ethnomathematics Ubiratan D'Ambrosio (1975), involving the Calculations labor using the mathematical concepts and Percentage of Rule of Three. Focus our research seeking to answer the following questions: 1) Why do students of the EJA have both interest and curiosity in learning calculations labor? What are those interests? 2) What have previous knowledge that students of EJA need for the resolution of situations-problem involving the calculations labor? 3) What are the difficulties presented by students of the EJA when solve situations-problem involving the calculations labor? 4) What impact caused when the math is presented in a contextualized way to the life of pupils of EJA? We used two instruments for research, the Instrument 1 that identified the labor concepts that the students surveyed had an interest in knowing and learning and Instrument 2 composed of four-problem situations and developed after the Instrument 1. Using us as some elements of the engineering teaching, we seek to build situations that could lead students to an autonomous stance with problem-solving strategies proposed, engaging them and making them actors of the learning process. Both search engines were sufficient to answer the four questions proposed above, and consequently the results were satisfactory, indicating that contextualizing the teaching of rule of three percent and the calculations using labor, the impact on the lives of students is seen so positive, making the learning process more meaningful / Este estudo é uma pesquisa qualitativa que tem como objetivo analisar quatro duplas de alunos da 3ª série do Ensino Médio do segmento de ensino da Educação de Jovens e Adultos (EJA) de uma escola pública e central do município de Franco da Rocha. Esses alunos resolveram quatro situações-problemas contextualizadas, que foram norteadas pela Etnomatemática de Ubiratan D Ambrósio (1975), envolvendo os Cálculos Trabalhistas utilizando os conceitos matemáticos de Porcentagem e Regra de Três. Focamos nossa pesquisa buscando responder às seguintes questões: 1) Por que os alunos da EJA têm tanto interesse e curiosidade na aprendizagem dos cálculos trabalhistas? Quais são esses interesses? 2) Quais os conhecimentos prévios que os alunos da EJA necessitam para a resolução de situações-problema envolvendo os cálculos trabalhistas? 3) Quais as dificuldades apresentadas pelos alunos da EJA quando solucionam situações-problema que envolvam os cálculos trabalhistas? 4) Qual o impacto causado quando a matemática é apresentada de uma maneira contextualizada para a vida dos alunos da EJA? Utilizamos dois instrumentos de pesquisa, o Instrumento 1 que identificava os conceitos trabalhistas que os alunos pesquisados tinham o interesse em conhecer e aprender e o Instrumento 2 composto de quatro situações-problema e elaborado após o Instrumento 1. Utilizando-nos assim de alguns elementos da engenharia didática, buscamos construir situações que levassem os alunos a uma atitude autônoma com estratégias de resolução de problemas propostos, engajando-os e tornando-os atores do processo de aprendizagem. Os dois instrumentos de pesquisa foram suficientes para responder as quatro questões propostas acima e, em conseqüência os resultados obtidos foram satisfatórios, o que revela que contextualizando o ensino de regra de três e porcentagem utilizando os cálculos trabalhistas, o impacto na vida dos alunos é visto de maneira positiva, tornado o processo de aprendizagem mais significativo