[pt] CÓDIGOS DE PREFIXO: ALGORITMOS E COTAS
| Ano de defesa: | 2009 |
|---|---|
| Autor(a) principal: | |
| Orientador(a): | |
| Banca de defesa: | |
| Tipo de documento: | Tese |
| Tipo de acesso: | Acesso aberto |
| Idioma: | por |
| Instituição de defesa: |
MAXWELL
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: | |
| Link de acesso: | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13809&idi=1 https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13809&idi=2 http://doi.org/10.17771/PUCRio.acad.13809 |
Resumo: | [pt] Os códigos de prefixo têm importância fundamental na comprenssão e transmissão de dados. Estes códigos também apresentam relações com problemas de busca. Neste tese, apresentamos novos resultados estruturais e algorítimos sobre a classe dos códigos de prefixo. Explicamos teoricamente as boas taxas de compressão observadas para alguns métodos utilizados na prática. Propomos também algoritmos eficientes para construção de códigos de prefixo ótimos e variantes. Os principais resultados aqui descritos são os seguintes: - um novo algoritmo paralelo para construção de códigos de prefixos ótimos: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo alfabéticos: - um algoritmo aproximativo e linear para construção de códigos de prefixo com restrição de comprimento: - um algoritmo aproximativo com complexidade 0(n log n) para construção de códigos de prefixo alfabéticos com restrição de comprimento: - uma nova versão de algoritmo WARM-UP com complexidade fortemente polinomial: - um algoritmo linear para reconhecer códigos de prefixo ótimos com restrição de comprimento: - uma prova afirmativa da conjectura de Vitter sobre o desempenho dos códigos de Huffmann dinâmicos construídos pelo algoritmo FGK (Faller, Gallanger e Knuth) |