Defesa do Mestrado

Setembro 11, 2011

Segunda-feira passada foi a defesa da minha tese de mestrado. Felizmente correu tudo bem e fui aprovado :)

Do trabalho

O título da minha dissertação foi “Mapas de Símbolos Proporcionais”. O nome ficou bem genérico e não dá nem para saber do que se trata, hehe. Talvez fosse melhor “Problemas de otimização combinatória envolvendo mapas de símbolos proporcionais”.

Mapa de símbolos proporcionais com as maiores cidades brasileiras

De qualquer maneira, basicamente o que fizemos foi abordar dois problemas envolvendo esse tipo de mapa através de programação linear inteira, buscando soluções ótimas. Fizemos estudos teóricos mostrando que a formulação utilizada é forte, além de encontrarmos desigualdades adicionais. Também desenvolvemos técnicas de pré-processamento usando divisão-e-conquista e finalmente contribuímos com a paralelização de uma abordagem heurística.

Da banca

A banca da defesa foi composta pelo meu orientador, o prof. Pedro e pelos professores Carlinhos do IME-USP e o prof. Hélio do IC.

O prof. Carlinhos é um dos grandes responsáveis pela organização da maratona e por isso devo boa parte de minha formação a ele. O prof. Hélio foi o responsável da disciplina de estrutura de dados da qual eu fui monitor em 2010 e também foi meu professor de computação gráfica.

Ambos foram bem tranquilos na arguição, tendo apenas sugerido algumas correções ortográficas e uma melhor explicação aqui e acolá.

Da apresentação

Eu sou bastante tímido e tinha pavor de apresentar em público. Acho que os seminários do LOCo fizeram com que eu me acostumasse a apresentar, pelo menos quando se trata do meu próprio trabalho.

fonte: http://www.greenlights.org/blog/wp-content/uploads/2011/05/ostrich.jpg

Além disso, aprendi várias técnicas com meus orientadores sobre como apresentar melhor. Eis algumas delas:

  • Olhar para a platéia (esse é difícil :P)
  • Não ler os slides (além de te deixar de costas pra platéia, você não convence que sabe o conteúdo da palestra)
  • Não voltar slides. Se você sabe que vai precisar mostrar um slide que apareceu antes, duplique-o na confecção da apresentação. Se não der pra fazer isso, pelo menos avise que está voltando os slides para a plateia não ficar perdida.
  • Use “nós” ao invés de “a gente”. A vantagem é que no primeiro caso podemos usar sujeito oculto, o que torna a fala mais agradável de se ouvir.

Do aprendizado técnico

Embora eu não tenha me dado conta na hora, acho que aprendi bastante coisa no mestrado, principalmente sobre programação linear inteira e desenvolvimento de software em C++. Até então eu só tinha feito programinhas de ~100 linhas para resolver problemas de maratona, sem usar muitos conceitos de orientação de objetos.

No mestrado fiz as coisas pensando em reuso, o que acabou sendo muito bom, pois tive que utilizar código que eu havia escrito depois de um ano. O código ficou com umas 10.000 linhas.

Embora tenha usado bibliotecas como CGAL e XPRESS, se eu fosse reescrever meu código, teria usado mais bibliotecas como por exemplo a Boost.

Do futuro

Acadêmico: Há algumas tarefas possíveis para complementar o que fiz no mestrado e minha ideia é realizá-las assim que sobrar um tempinho. Mesmo não tendo certeza se voltarei para um doutorado, eu gosto bastante de publicar :) e isso me motiva a continuar pesquisando.

Profissional: Pesquisa em áreas como geometria computacional é rara de ser encontrada fora da academia, pelo menos no Brasil. Eu ia fazer meu mestrado em geometria, mas meu orientador sugeriu um problema que no final das contas usou bastante otimização combinatória e eu sou grato pelo rumo que as coisas tomaram. Graças a isso estou trabalhando em uma empresa de pesquisa operacional. Otimização em geral é uma área com aplicação direta na indústria e por isso é possível encontrar algumas empresas do ramo no Brasil.


Sibgrapi 2011

Setembro 4, 2011

Nessa última semana aconteceu o Sibgrapi 2011, que é uma conferência brasileira de abrangência internacional de computação gráfica, padrões e imagens. O evento foi sediado em Maceió, Alagoas. Tivemos um artigo aceito para essa conferência e fui lá apresentar.

O Sibgrapi deste ano foi composto por diversos mini-cursos, palestras de pesquisadores de renome na área, apresentações orais dos artigos (em inglês) e apresentação de pôsteres (artigos e também teses de iniciação/mestrado/doutorado).

Mini-cursos

Acho que a parte mais interessante de conferências são os minicursos. Nessa edição do Sibgrapi, cada mini-curso foi dividido em duas partes.

Houve um particularmente interessante, sobre fotografia computacional, onde eles explicaram alguns conceitos básicos sobre ótica e fotografia e falaram dos principais temas dessa área.


Imagens com diferentes tempos de exposição (fonte)

Foram discutidas diversas técnicas de composição de imagens. A mais legal pra mim, sem dúvida é a do high dynamic range (HDR), que consiste em usar imagens com diferentes tempos de exposição (como no exemplo da figura acima) para compor uma imagem visualmente mais atraente (como no exemplo da figura abaixo). Outros exemplos impressionantes podem ser encontrados nesse site.


Imagem composta (fonte)

Falaram também sobre light fields, que pelo que entendi consiste em representar mais informação a partir de um dado ponto de vista. Um exemplo disso é essa câmera que tira fotos com diferentes focos que podem ser escolhidos depois, na própria imagem. Veja exemplos aqui.

Assisti também a um tutorial sobre OpenCV, mas só peguei a primeira parte, pois a segunda conflitava com o horário do tutorial sobre fotografia computacional.

Apresentação de artigos técnicos

Havia sempre duas seções paralelas de apresentações de artigos técnicos, o que impossibilitou assistir a todas elas. Pelo que pude perceber, uma linha era voltada à computação gráfica e a outra à processamento de imagens. Acabei escolhendo apenas seções de computação gráfica.

Pra dizer a verdade, entendi muito pouco dos trabalhos apresentados, mas os que mais me chamaram a atenção foram de modelagem de terrenos em tempo real usando CPU-GPU (link) e texturização de modelos 3D com poucas características geométricas (link).

Apresentei nosso trabalho em uma seção de visualização. Trata-se de uma solução para uma das variantes do problema de mapas de símbolos proporcionais que abordei no meu mestrado (link). Pretendo comentá-la em um post futuro.

Pôsteres de teses

O projeto mais interessante era a tese de mestrado de Adriana Schulz (IMPA) que estudou animação computadorizada, mais especificamente para simulação de coreografia. Esse site tem diversos vídeos bacanas!

Fato curioso

Embora os artigos tivessem que ser apresentados em inglês, os mini-cursos foram ministrados em português. Além disso, as palestras dadas por convidados brasileiros também estavam sendo dadas em português. Aí houve uma hora em que na seção de dúvidas, um cara fez a pergunta em alemão. Depois de todo mundo ficar com cara de pastel, ele repetiu em inglês, criticando o fato de uma palestra de conferência de nível internacional ter sido dada em português. A partir de então, só tivemos palestras em inglês :)

Turismo

Aproveitei minha ida a Maceió para conhecer alguns pontos turísticos de Alagoas. A cidade de Maceió em particular tem uma boa estrutura para turismo, com empresas de transporte e serviço de guias. Consegui visitar a praia do Gunga, onde existem falésias compostas de camadas coloridas.


Camadas coloridas das falésias

Também fui a Maragogi, famosa por suas piscinas naturais, onde se pode mergulhar em meio a peixes coloridos e corais.


Piscina natural em Maragogi

Conclusão

Foi a primeira vez que apresentei em inglês e para um público desconhecido. Acredito ter sido um bom ensaio para a minha defesa que ocorrerá logo mais.

Os passeios nos últimos dias também serviram como um descanso relâmpago, pois esses últimos três meses têm sido bem puxados :)


Mapas de Símbolos Proporcionais

Abril 17, 2011

Sexta-feira passada apresentei uma palestra na série de seminários do LOCo. Falei sobre o problema que estou atacando no mestrado.

Um mapa de símbolos proporcionais emprega símbolos para exibir eventos associados a alguma localidade e intensidade. O símbolo é posicionado no local de ocorrência do evento e a sua área fica sendo proporcional à intensidade desse evento. Focamos em mapas que usam círculos opacos como símbolos. A figura abaixo é um exemplo representando as populações das maiores cidades do Brasil.

Note que há sobreposição entre os discos. Dependendo da ordem em que os empilhamos, pode ser que haja mais ou menos porções dos discos visíveis. Há casos ruins em que a borda do disco fica totalmente encoberta, como na figura abaixo.


Não podemos inferir o centro nem o raio do disco com bordo escondido.

Para tentar fazer com que o desenho tenha bastante borda visível, usamos uma métrica que consiste em maximizar o comprimento visível total dos discos. Com isso em mente, é possível definir um modelo de programação linear inteira, com um modelo que atribui cada disco a um nível.

Além do modelo básico, desenvolvemos algumas desigualdades adicionais para tornar o modelo mais forte, nos baseando em propriedades geométricas, que impedem certas configurações de acontecerem.

Também desenvolvemos duas técnicas de decomposição de instâncias. Um jeito trivial de decompor instâncias é considerar componentes de discos conexas de maneira independente.

Nossa primeira técnica de decomposição vem da observação que um disco que está contido no outro sempre pode ser desenhado por cima em uma solução ótima. Dessa forma, em uma instância como a da figura abaixo, a componente {a, b} pode ser desenhada de maneira independente de {c, d, e, f} e na hora de construir a solução ótima, basta desenhar a solução obtida para {a, b} em cima da solução {c, d, e, f}.

Componente {a,b} está contida em {f} e pode ser resolvida separadamente.

Podemos definir um grafo Gs sobre os discos de S, com conjunto de vértices correspondendo aos discos e há uma aresta (i, j) em Gs se os discos correspondentes se interceptam. Falei sobre esse tipo de grafo em um post anterior.

A outra técnica consiste em remover um ponto de articulação de Gs e replicá-lo nas componentes conexas resultantes, como na figura abaixo.


O disco f representa um ponto de articulação em Gs. As figuras (ii), (iii) e (iv) são as componentes resultantes de sua remoção, com f replicado.

Mostramos que é possível resolver cada componente com o ponto de articulação replicado de maneira independente. Depois, basta juntar os discos mantendo a ordem relativa de cada sub-solução. Isso pode ser feito através de uma ordenação topológica.

Implementamos todas essas ideias e reportamos os resultados. As instâncias testadas foram as mesmas de um trabalho anterior no qual nos baseamos. As técnicas de decomposição foram efetivas na redução do tamanho das instâncias e o resolvedor XPRESS conseguiu resolver nosso modelo para quase todas as instâncias. Porém, ficaram algumas componentes sem serem resolvidas, o que nos motiva a procurar novos modelos e novas desigualdades.

Esse nosso trabalho foi aceito na Computational Geometry and Applications 2011.


Disk Graphs

Outubro 1, 2010

Semana passada teve início a série de seminários em teoria de computação dos membros do Laboratório de Otimização e Combinatória. Essas palestras ocorrerão intercaladas com os seminários do DTC (Departamento de Teoria de Computação), ocorrendo, a priori, às Sextas-feitas, 10h. Acabei estreando essa série com uma palestra intitulada “Disk Graphs”. A ideia central era definir a classe de grafos chamada disk graphs e mostrar dois problemas clássicos de teoria dos grafos sobre essa classe: o problema da clique máxima e da coloração. Neste post, vou apresentar um pequeno resumo da apresentação (disponível aqui).

Dado um conjunto de discos no plano, definimos um grafo com vértices correspondendo aos centros dos discos. Dois vértices são conectados por uma aresta se seus discos correspondentes se interceptam com área não nula. Denominamos tal grafo Disk Graph (DG).

Exemplo de Disk Graph

Um Disk Graph onde todos os discos têm mesmo tamanho é chamado de Unit Disk Graph.

Exemplo de Unit Disk Graph

No caso particular em que os discos não podem se sobrepor, apenas se tangenciar, chamamos o DG de Coin Graph (CG).

Exemplo de um Coin Graph

Em seguida falei sobre a relação entre diferentes classes de grafos. A mais interessante é devido ao Teorema de Koebe (também conhecido como circle packing theorem) que diz basicamente que grafos planares e coin graphs são equivalentes. Eu desconfiava que todo grafo planar é também um disk graph. O prof. Stolfi, que estava presente, provou com um argumento bem simples: dado um coin graph, a menor distância entre bordos de discos que não se tangenciam é positiva, enquanto a de discos que se tangenciam é exatamente 0. Assim, existe um valor suficientemente pequeno do qual podemos aumentar o raio dos discos de forma que os círculos tangentes passem a ter interseção não nula e os não tangentes assim continuem.

Problemas

Um aspecto importante ao enunciar um problema para essa classe de grafos é especificar se a entrada é dada na forma de discos ou na forma de grafo. Observe que se for dada na primeira forma, conseguimos obter a segunda. Porém, mesmo para unit disk graphs, se a entrada estiver na forma de grafo, foi provado que é NP-difícil encontrar um conjunto de discos que formem tal grafo [1]. (Para coin graphs existe um algoritmo que constrói o conjunto de discos a partir de um grafo planar [2]). Para os problemas apresentados, vamos assumir que a entrada é dada na forma de discos.

Primeiramente apresentei o problema da clique máxima para unit disk graphs. Embora seja NP-difícil encontrar a clique máxima em um grafo geral, para unit disk graphs, existe um algoritmo polinomial . Não se sabe, porém, se o problema da clique máxima para disk graphs está em P ou NP.

Depois apresentei o problema da coloração, que continua NP-difícil, mesmo para unit disk graphs e a entrada sendo dada na forma de discos. Foram desenvolvidos algoritmos aproximados e algoritmos online para unit disk graphs e disk graphs. Para unit disk graphs o melhor algoritmo aproximado até agora tem fator de aproximação 3 (limite superior), sendo que não existe algoritmo aproximado com melhor fator de aproximação menor do que 4/3 (limite inferior) a não ser que P=NP. O melhor algoritmo online tem fator de competitividade 5 (limite superior) e não existe algoritmo com fator de competitividade menor do que 2 (limite inferior) a menos que P=NP. Para disk graphs, o algoritmo aproximado tem limites inferior e superior iguais a 4/3 e 5, respectivamente, e o algoritmo online tem ambos limites inferior e superior iguais a log n, ou seja, o algoritmo online para unit disk graphs é o melhor que se pode conseguir.

Sumário com os limites dos fatores de aproximação e competitividade.

Aplicações

Na palestra acabei não falando das aplicações práticas dos disks graphs. Porém, eles são muito utilizados para projetar topologias de rede wireless. Podemos pensar que cada disco representa uma antena wireless posicionada no centro do disco, com alcance equivalente ao raio do mesmo. Assim, o problema da coloração pode ser usado para encontrar uma atribuição de frequências às antenas, considerando que há interferência entre os sinais de antenas cujos círculos se interceptam.

Referências

[1] Breu, H. and Kirkpatrick, D. G. – Unit Disk graph recognition is NP-Hard
[2] Collins, C. R. and K, Stephenson – A Circle packing algorithm