Título
[en] COVERING CODES: BOUNDS AND HEURISTICS
Título
[pt] CÓDIGOS DE COBERTURA: LIMITES E HEURÍSTICAS
Autor
[pt] CARLOS RAONI DE ALENCAR MENDES
Vocabulário
[pt] OTIMIZACAO COMBINATORIA
Vocabulário
[pt] METAEURISTICA
Vocabulário
[pt] GERACAO DE COLUNAS
Vocabulário
[en] COMBINATORIAL OPTIMIZATION
Vocabulário
[en] METAHEURISTIC
Vocabulário
[en] COLUMN GERERATION
Resumo
[pt] Compreensão de dados, codificação digital da fala, telecomunicações via celular, correção de erros de transmissão, são algumas das aplicações práticas do estudo dos códigos de cobertura, um importante ramo da área da matemática denominada teoria dos códigos. Neste trabalho são abordados dois problemas de códigos de cobertura: o problema clássico de códigos de cobertura e o recente problema denominado de códigos curtos de cobertura. Apresenta-se uma aplicação da metaeurística Busca Tabu Reativa, uma importante variação da Busca Tabu clássica, para os problemas citados. Além disto, apresenta-se uma nova técnica heurística para resolução de problemas de otimização combinatória denominada Heurística de Melhoria via Geração de Colunas (HMGC), juntamente com uma aplicação da mesma aos problemas em questão. A HMGC combina a geração atrasada de colunas, técnica usada na resolução de problemas com um grande número de variáveis de decisão (colunas), e heurísticas de busca local. É feita uma comparação dos resultados obtidos pela Busca Tabu Reativa, a Busca Tabu sem o mecanismo de reação e a HMGC, de forma a avaliar a qualidade das heurísticas apresentadas.
Resumo
[en] Data compression, speech coding, móbile telecommunications and error-corretion are some of the practical apllications of the covering codes study, an important field of coding theory. This work addresses two problems of covering codes: the classic code covering problem and the recent short code covering problem. It presents an application of Reactive Tabu Search (RTS) metaheuristic for the problems cited, the RTS is an important variation of the classic Tabu Search. Moreover, it presents a new heuristic technique for solving combinatorial optimization problems named Column Generation Improbement Heuristic (CGIH). It also presents an application of CGIH for the covering codes problems. The CGIH combines the delayed column generation, technique used to solve problems with a large number of decision variables (columns), and local search heuristics. A comparison of results obtained by the Reactive Tabu Search, the Tabu Search without the reaction mechanism and the CGIH is also presented in order to assess the effectivenss of the presented heuristics.
Orientador(es)
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Coorientador(es)
EMERSON LUIZ DO MONTE CARMELO
Banca
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
SERGIO LIFSCHITZ
Banca
EDUARDO UCHOA BARBOZA
Banca
EMERSON LUIZ DO MONTE CARMELO
Catalogação
2010-03-08
Apresentação
2009-08-10
Tipo
[pt] TEXTO
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=15365@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=15365@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.15365
Arquivos do conteúdo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS PDF CAPÍTULO 1 PDF CAPÍTULO 2 PDF CAPÍTULO 3 PDF CAPÍTULO 4 PDF CAPÍTULO 5 PDF CAPÍTULO 6 PDF CAPÍTULO 7 PDF REFERÊNCIAS BIBLIOGRÁFICAS, APÊNDICE PDF