Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Donadelli Júnior, Jair | - |
Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | - |
Autor(es): dc.creator | Prado, José Augusto Soares | - |
Data de aceite: dc.date.accessioned | 2025-09-01T11:23:26Z | - |
Data de disponibilização: dc.date.available | 2025-09-01T11:23:26Z | - |
Data de envio: dc.date.issued | 2024-10-22 | - |
Data de envio: dc.date.issued | 2024-10-22 | - |
Data de envio: dc.date.issued | 2005 | - |
Fonte completa do material: dc.identifier | https://hdl.handle.net/1884/3173 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/3173 | - |
Descrição: dc.description | Orientador: Jair Donadelli Jr | - |
Descrição: dc.description | Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 2005 | - |
Descrição: dc.description | Inclui bibliografia | - |
Descrição: dc.description | Resumo: Estudamos, neste trabalho, diversas variações do Quicksort com relação à otimização do cache e percebemos que tal preocupação limita muito o algoritmo e as diferenças resultantes são extremamente específicas com relação à arquitetura utilizada ou simulada. Estudamos então variações do Quicksort que têm como foco modificar a forma de escolha do pivô com o objetivo de minimizar o número de comparações e trocas. Dentre as variações estudadas, os Quicksort probabilísticos caracterizam-se por usarem números pseudo-aleatórios na escolha do pivô. Concentramos-nos então em estudar dois algoritmos geradores de números pseudo-aleatórios (GNPA), um por congruência linear, proposto por Knuth em [Knu00b], e outro penta-independente proposto por Howard Karloff em [KR93]. Analisamos, comparamos e testamos esses dois GNPAs sendo usados na escolha do pivô do Quicksort. Também comparamos essas duas versões probabilísticas como utras três implementações determinísticas que fizemos para o Quicksort. O intuito desse trabalho foi realizar uma análise experimental dessas variações do Quicksort usando GNPAs dando enfoque em analisar o comportamento da versão proposta em [KR93]. | - |
Descrição: dc.description | Abstract: We had studied in this work variations of Quicksort related with cache optimization and we hadrealized that worry about this topic makes the algorithm deeply limited and the resultant diferences are extremely specific and related with the choosen architeture. So we had studied variations of Quicksort which focus in modifying the way of choosing the pivot with the objective ofminimize the number of performed comparisions and changes. Among the looked variations,the probabilistic Quicksort caracterizes itself by using pseudo-random-numbers when choosing the pivot. So we had focused on study two random number genarator (RNG) algorithms, one by linear congruence [Knu00b] and another by five-way-independent [KR93]. We had analised, compared and tested these two RNGs beeing used on the pivot choice in Quicksort. We had alsocompared these two probabilistic versions with other three deterministic versions we had madefor Quicksort. The aim of this work was to perform an experimental analysis of these variations of Quicksort using RNGs and the main focus was to analise the behavior of the version proposedin [KR93]. | - |
Formato: dc.format | 67f. : il., grafs. | - |
Formato: dc.format | application/pdf | - |
Formato: dc.format | application/pdf | - |
Relação: dc.relation | Disponível em formato digital | - |
Palavras-chave: dc.subject | Classificação (Computadores) | - |
Palavras-chave: dc.subject | Algorítmos | - |
Palavras-chave: dc.subject | Ciência da Computação | - |
Título: dc.title | Análise experimental do quicksort probabilístico com gerador de números pseudo-aleatórios penta-independente | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: