dc.contributor.author | Netto, Marcelo Vaz | |
dc.date.accessioned | 2018-04-10T00:43:42Z | |
dc.date.available | 2018-04-10T00:43:42Z | |
dc.date.issued | 2018-02-08 | |
dc.identifier.citation | NETTO, Marcelo Vaz. BSCL: algoritmo de Busca Sequencial de Colisões Lineares. 2018. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal de São Carlos, Sorocaba, 2018. Disponível em: https://repositorio.ufscar.br/handle/ufscar/9701. | * |
dc.identifier.uri | https://repositorio.ufscar.br/handle/ufscar/9701 | |
dc.description.abstract | Access to database indexes, compiler symbol tables, operating system commands, routing device ports, telecommunication registers, processor caches, among others, are inserted into areas of Computer Science research with a common point - search algorithm. These applications can handle large sets of elements where the cost of searching for a key can be high. Thus, there is a need to develop algorithms that, in addition to efficiency, focus on efficiency, both in processing time and in the use of system resources. This dissertation aims to propose a sequential search algorithm called Linear Collision Sequential Search (BSCL), based on the probabilistic distribution of Poisson, for large static data arrays
where key columns are ordered and evenly distributed numbers. As a result, we present a comparison of the BSCL with an algorithm already consecrated and in use in several computational routines - Perfect Hash Table. The Experimental validation focuses on three metrics - processing time, number of iterations, and memory resources. The dissertation concludes that BSCL is superior to the Perfect Hash in computation time and memory resources. Its main contribution is to demonstrate that simpler routines can have more expressive computational results. | eng |
dc.description.sponsorship | Não recebi financiamento | por |
dc.language.iso | por | por |
dc.publisher | Universidade Federal de São Carlos | por |
dc.rights.uri | Acesso aberto | por |
dc.subject | Colisões lineares | por |
dc.subject | Distribuição probabilística de Poisson | por |
dc.subject | Busca binária | por |
dc.subject | Busca sequencial | por |
dc.subject | Tabelas hash | por |
dc.subject | Algoritmo de busca | por |
dc.subject | Linear collisions | eng |
dc.subject | Poisson distribution | eng |
dc.subject | Binary search | eng |
dc.subject | Sequential search | eng |
dc.subject | Hash table | eng |
dc.subject | Search algorithm | eng |
dc.title | BSCL: algoritmo de Busca Sequencial de Colisões Lineares | por |
dc.type | Dissertação | por |
dc.contributor.advisor1 | González, Sahudy Montenegro | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/9826346918182685 | por |
dc.description.resumo | Os acessos aos índices dos bancos de dados, às tabelas de símbolos dos compiladores, aos comandos dos sistemas operacionais, às portas dos dispositivos de roteamento, aos registros de telecomunicações, aos caches dos processadores, entre outros, estão inseridos em áreas de pesquisas da Ciência da Computação com um ponto em comum - algoritmo de busca. Estas aplicações podem manipular grandes conjuntos de elementos onde o custo de procurar uma chave pode ser elevado. Assim, há a necessidade de desenvolvimento de algoritmos que além da eficácia foquem - também - em eficiência, tanto no tempo de processamento como no uso dos recursos do sistema. Esta dissertação tem como objetivo propor um algoritmo de busca sequencial intitulado Busca Sequencial de Colisões Lineares (BSCL), baseado na distribuição probabilística de Poisson, para grandes matrizes de dados estáticos onde as colunas de chaves são números ordenados e uniformemente distribuídos. Como resultado, é apresentada uma comparação da BSCL com um algoritmo já consagrado e em uso em
várias rotinas computacionais - Tabela Hash Perfeito. A validação experimental foca em três métricas - tempo de processamento, número de iterações e recursos de memória. A dissertação conclui que a BSCL é superior ao Hash Perfeito em tempo de computação e recursos de memória. Sua principal contribuição é demonstrar que rotinas mais simples podem comportar resultados computacionais mais expressivos. | por |
dc.publisher.initials | UFSCar | por |
dc.publisher.program | Programa de Pós-Graduação em Ciência da Computação - PPGCC-So | por |
dc.subject.cnpq | CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO | por |
dc.ufscar.embargo | Online | por |
dc.publisher.address | Câmpus Sorocaba | por |
dc.contributor.authorlattes | http://lattes.cnpq.br/6289705767101706 | por |