Geometria discreta e codigos

Autor(es)

João Eloir Strapasson

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Data de defesa: 2007-11-04

Membros da banca

Sueli Irene Rodrigues Costa; Jayme Luiz Szwarcfiter; Ricardo Dahab; Vilmar Trevisan; Yoshiharu Kohayakawa

• Orientador: Sueli Irene Rodrigues Costa

Resumo

Este trabalho está dividido em duas partes. A primeira e dedicada ao problema de encontrar o menor vetor não nulo de um reticulado. Este é um problema de alta complexidade computacional e que tem grande interesse tanto para a Teoria dos Códigos, como para diversas outras áreas. Esse mínimo está associado a performance do reticulado em termos da codificação: quanto maior for a razão entre este mínimo e o determinante do reticulado, melhor e a distribuição dos pontos no espaço (alta densidade de empacotamento). Nesta tese demos ênfase ao caso especial dos reticulados obtidos por uma projeção ortogonal do reticulado n-dimensional dos inteiros na direção de seus elementos. Tais reticulados estão associados ao problema de codificação contínua fonte/canal. Mostramos nos casos tri e quadridimensionais em que condições podemos garantir reticulados bons, ou seja, com alta densidade de empacotamento. Neste processo foram também construídos dois novos algoritmos, um para cálculo da base de Minkowski de um reticulado e outro específico para a busca da norma mínima do reticulado-projeção. Na segunda parte trabalhamos com grafos em toros planares que são quocientes de reticulados, os quais são isomorfos a grafos circulantes. Estabelecemos a conexão entre estes códigos esféricos rotulados por grupos cíclicos e códigos perfeitos na métrica de Lee. A partir de tal associação foram também obtidos resultados sobre o gênero 1 e a determinação do dos gênero de uma classe especial de grafos circulantes que tem número arbitrariamente grande de conexões (grau) (AU)

• Processo FAPESP: 02/14134-4 - Aplicações de geometria diferencial e geometria discreta à Teoria de Códigos
• Beneficiário: João Eloir Strapasson
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto