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.

Anúncios

Escrevendo com o emacs

Abril 3, 2011

Desde 2005 uso emacs devido às aulas introdutórias de programação. Nunca estudei muito a fundo esse editor que é capaz de realizar incontáveis tipos de tarefas. Mas aprendi algumas funcionalidades interessantes.

Sátira do xkcd com diversos editores (clique para ampliar)

Editando LaTeX

O auctex é uma extensão que facilita a edição de documentos LaTeX. Para quem usa ubuntu, basta instalar o pacote auctex.

Depois de instalar essa extensão, ao abrir arquivos .tex uma nova interface aparecerá, parecida com a imagem abaixo:

O botão do leão é equivalente a executar o comando latex no arquivo atual. Ele gera um arquivo no formato .dvi. O botão do óculos abre o arquivo .dvi com o programa xdvi. O botão do livrinho executa o comando bibtex sobre o arquivo .aux gerado com o comando latex. O último botão é um preview dentro do próprio emacs, mas eu particularmente não gosto.

Nota: o padrão do auctex é usar o comando latex que gera arquivos dvi. É possível mudar esse padrão para sempre gerar pdf’s usando o comando pdflatex. Para isso, adicione a seguinte linha ao arquivo de configuração do emacs, em ~/.emacs:

(add-hook 'LaTeX-mode-hook 'TeX-PDF-mode)

Observe ainda que existem diferenças entre os comandos latex e pdflatex. Uma delas é que latex só trabalha com imagens no formato .eps enquanto pdflatex trabalha com vários tipos de formatos (pdf, jpg, png), mas não .eps.

Correções ortográficas

O emacs tem uma funcionalidade de indicar erros ortográficos, chamada flyspell. O dicionário padrão é o inglês, mas é possível alterar para português brasileiro. Antes de mais nada, é preciso instalar suporte do aspell a essa linguagem. No ubuntu, basta instalar o pacote aspell-pt-br.

Depois, para trocar o dicionário, abra a linha de comandos no emacs (Alt+X) e digite o seguinte comando:

ispell-change-dictionary

Ele vai pedir o argumento, o qual deve ser:

portugues

Agora, se o seu texto já está escrito e você quer fazer a revisão ortográfica, abra a linha de comandos e digite:

flyspell-buffer

Se você quer começar a fazer a revisão ortográfica conforme vai escrevendo, use

flyspell-mode

As palavras que não estiverem de acordo com o dicionário ficarão destacadas. Clicando com o botão do meio do mouse aparece um menu com sugestões de correção ou opções de ignorar ou adicionar ao dicionário. Para ir para o próximo erro, é possível usar o comando flyspell-goto-next-error ou o atalho

Ctrl+,


George Dantzig e o Algoritmo Simplex

Julho 30, 2010

George Dantzig (1914-2005) pode ser considerado o pai da programação linear, pois ele é o inventor do Simplex, o primeiro algoritmo para resolução de programas lineares. No pior caso, o simplex tem complexidade exponencial em função do tamanho da entrada e já foram desenvolvidos algoritmos polinomiais que resolvem programas lineares como o método dos pontos interiores. Na prática porém, o algoritmo simplex se comporta muito bem. Além disso possui características que os fazem ideais para os algoritmos de Branch and Bound, que resolvem programas lineares inteiros.

Diz a lenda que uma vez Dantizig chegou atrasado para o primeiro dia de aula de estatística na Universidade de Berkeley. Quando entrou, viu dois problemas escritos na lousa e, pensando serem tarefas para casa, anotou-os em seu caderno. Após alguns dias, entregou os exercícios ao professor e se desculpou por demorar tanto para resolvê-los, por estarem mais difíceis do que o normal. O professor pareceu não dar muita importância na hora, mas depois um tempo foi revelar a Dantizig que ele tinha resolvido dois problemas abertos em estatística.

O filme Gênio Indomável inspirou-se nessa história. Para quem não viu ou não lembra, Will Hunting era um faxineiro de uma Universidade, encrenqueiro, com passagens pela polícia e um gênio da matemática. Certa vez professores discutiam sobre um teorema em uma lousa e após irem embora, deixam o enunciado do teorema escrito. No dia seguinte o teorema está resolvido por um autor anônimo. Mais tarde descobrem se tratar do faxineiro e o filme se desenrola com os professores tentando convencer Hunting a estudar matemática e procurar um psicólogo para refrear seus ímpetos. É um filme que eu gostei muito e recomendo.

Uma paródia do filme, Perry Bible Fellowship

Em 1975, os economistas Tjalling Koopmans e Leonid Kantorovich foram laureados com o prêmio Nobel por sua teoria de alocação ótima de recursos, que era essencialmente programação linear. Injustamente Dantizig não foi premiado. Para quem tem interesse em saber mais sobre ele, eis uma biografia mais completa.

Enfim, o principal objetivo do meu post foi falar sobre um outro post que eu li no blog de teoria Gödel’s Lost Letter and P=NP, que começa falando sobre Dantzig para então apresentar uma excelente introdução a PLI. No post ele também apresenta uma modelagem para o problema de decidir se um grafo cúbico tem uma 3-coloração, que é NP-Completo.

Ele utiliza uma técnica interessante para modelar uma variável que pode assumir valores discretos não-contíguos, no caso 1, 2 e 4. Sejam variáveis binárias e que representa a cor de um vértice . Temos o modelo para cada :

(1)
(2)

Para cada três vértices adjacentes :

(3)

A desigualdade (2) diz que exatamente um, entre deve valer 1. Combinada com (1), temos que vale 1, 2 ou 4. A única forma para (3) ser satisfeita é com 1 + 2 + 4, ou seja devem ter cores diferentes, justamente a restrição do problema da 3-coloração. Assim, se existir uma solução satisfazendo tais desigualdades, o grafo possui uma 3-coloração.

Exemplo de uma 6-coloração de um Grafo

Há um problema mais genérico do que a 3-coloração em grafos cúbicos, que é determinar se um grafo G qualquer possui uma k-coloração. Definimos variáveis binárias se o vértice v possui cor c e 0 caso contrário. Temos o seguinte modelo:

(4) Para todo vértice v = 1,…,n,

(5) Para todo par de vértices adjacentes i e j, e toda cor c,

A igualdade (4) força que todo vértice tenha uma única cor. A igualdade (5) impede que dois vértices adjacentes tenham a mesma cor. Se existir algum y que satisfaz todas as igualdades, o grafo possui uma k-coloração.


Seres humanos a serviço das máquinas

Outubro 1, 2009

Recentemente o Google postou em seu blog a aquisição da empresa reCAPTCHA. Eles prometem matar dois coelhos com uma só cajadada: filtrar bots e auxiliar na conversão de imagens para texto (“stop spam. read books“). Esse último processo chama-se OCR (optical character recognition) e é um assunto estudado em inteligência artificial.

Exemplo de um recaptcha

Durante o primeiro semestre de 2008, participei de um projeto no qual uma das tarefas era fazer o reconhecimento ótico de uma placa de carro. O processo mais eficaz para fazê-lo foi através de inteligência artificial. A técnica é conhecida como aprendizado assistido. Nela você passa um conjunto de treinamento, ou seja, um monte de imagens de placa e diz qual o número da placa para cada uma dessas imagens. Aí a máquina “aprende” e é capaz de dizer o número de uma placa que não está no conjunto de treinamento. O problema é que esse conjunto de placas de treinamento geralmente é grande, e quem tem que dizer o número da placa é um ser humano (por isso o nome aprendizado assistido).

Enfim, não sei como funciona o esquema do reCAPTCHA, mas dá para ter uma noção e ver que a ideia deles é interessante. Eles pegam algumas palavras de um livro scaneado. Isso pode ser feito facilmente através de processamento de imagens. Dão uma distorcida nessas palavras e jogam para o usuário quando ele estiver logando em algum site, por exemplo. Obviamente ele vai tentar acertar a palavra e como a capacidade de um ser humano reconhecer uma palavra é infinitamente maior do que uma máquina, provavelmente vai acertar. Eis que temos usuários de todo o mundo ajudando a construir um conjunto de treinamento para fazer o OCR de um dado livro.

Piada genial do Apokalips

Mas ainda falta uma coisa: se eles querem que a gente diga a palavra correta, então eles não sabem a resposta. Logo, se um bot vier e digitar qualquer coisa, ele não só vai passar pelo sistema de segurança como irá poluir o conjunto de treinamento com informações erradas. Uma ideia é colocar uma outra imagem que eles já sabem qual é a palavra. Se o usuário acertar essa palavra, assumem que ele é um ser humano e que a outra palavra que ele digitou está certa!

Um outro lugar que se usa aprendizado assistido é no reconhecimento de rosto em fotos. Essa tarefa também fica bem fácil se você tem um conjunto de treinamento. Há algum tempo o Orkut reconhece rostos em fotos que você coloca nos seus álbuns. Mas antes disso, você é que tinha que marcar os rostos manualmente. Querendo ou não, os usuários do Orkut podem (não sei se eles utilizaram essa informação) ter prestado serviço ao site de relacionamentos, construindo o conjunto de treinamento para eles.