[Doc2012] Defesa de Proposta de Tese de Doutorado

[Manoel Orley]

Caros amigos,
Haverá uma defesa de Proposta de Tese de Doutorado conforme dados abaixo:

Aluno: Pablo Mayckon Silva Farias

Data: 26/10/2012, às 16h.

Banca examinadora:

Prof. Ricardo Cordeiro Corrêa (Orientador)
Prof. Manoel Bezerra Campêlo Neto (MDCC)
Prof.Críston Pereira de Souza (UFC/Quixadá)
Profa. Cristiana Gomes Huiban (Grupo ParGO)

Título: Minimização de memória em redes de rádio e problemas de otimização
associados

Resumo:
-----------------------------------------------
O presente trabalho divide-se em duas partes. Na primeira delas, nós
estendemos o chamado Problema de Ponderação de Rodadas (PPR) [1], que
trata da maximização da vazão em comunicações TDMA de redes de rádio, com
um segundo passo, o Problema de Ordenação de Rodadas, que diz respeito à
minimização do uso de memória da solução obtida no primeiro passo. Nós
apresentamos uma justificação formal completa para a definição do POR,
estendendo os resultados que justificam a definição do PPR. Além disso,
nós demonstramos que o POR é NP-difícil mesmo no caso de um modelo de
interferência de rádio simples e redes com estrutura restrita.

A segunda parte do trabalho é um estudo sobre problemas de otimização que,
assim como o POR, giram em torno do conceito de "soma máxima" de uma
sequência finita de números A, que é a maior soma dos elementos de uma
subsequência contígua de A. O primeiro problema que consideramos é o de,
dadas uma sequência A e um número x, encontrar uma posição p para a
inserção de x em A que minimize a soma máxima da sequência resultante. Nós
demonstramos que esse problema pode ser resolvido em tempo linear,
superando a solução quadrática imediata [2]. O segundo problema que
consideramos é o de, dada uma sequência A, obter uma permutação A' de A
que possua a menor soma máxima possível. Em colaboração com o colega
Críston Souza, foi demonstrado que esse problema é NP-difícil, mas também
que ele admite uma 2-aproximação em tempo O(n.log n).

Nós concluiremos a apresentação discutindo o trabalho planejado para a
conclusão da tese e o trabalho já em andamento.

-- 
Manoel Orley Mendes Carneiro
Mestrado e Doutorado em Ciência da Computação
Universidade Federal do Ceará
Telefones:55 85 3366-9847 (Ext-216) e 9997-4809