Informações sobre orientações de pesquisa

Esta página contém informações para alunos buscando orientação em projetos de iniciação científica, mestrado ou doutorado. Se você tiver interesse em ser orientado por mim, entre em contato pelo e-mail rafael@ic.unicamp.br e, se possível, envie o seu CV anexado.

Indíce

Quem sou eu?

Sou Professor do Departamento de Teoria da Computação do Instituto de Computação da Universidade Estadual de Campinas (IC-UNICAMP) com Regime de Dedicação Integral à Docência e à Pesquisa.

Fiz meu Doutorado e meu Bacharelado em Ciência da Computação pelo Instituto de Matemática e Estatistica da Universidade de São Paulo.

Atualmente sou Bolsista de Produtividade em Pesquisa do CNPq nível 2, coordeno dois projetos de pesquisa (um da FAPESP e um do CNPq), participo de mais dois projetos de pesquisa (FAPESP e CNPq) e sou Chefe do Departamento de Teoria de Computação.

Você pode encontrar a lista atualizada das minhas publicações no meu Currículo Lattes ou na minha home page.

Áreas de Pesquisa de Interesse

Minhas áreas atuais de interesse são a Teoria dos Jogos Algorítmica e a Otimização Combinatória.

Teoria dos Jogos Algorítmica

Com o crescimento rápido e descentralizado da Internet, o computador deixou de ser uma máquina individual para se tornar parte de uma rede global de comunicação, disseminação de conteúdos e comércio. Desta forma, surgiram também vários problemas computacionais em que não há um controle centralizado dos agentes envolvidos, resultando na necessidade de desenvolver novas técnicas de computação teórica para lidar com tais problemas. A Teoria dos Jogos (uma área de pesquisa da Economia), com seus estudos das interações de cooperação e competição entre indivíduos, teve um papel crucial nesse desenvolvimento.

A área de pesquisa que combina a Teoria da Computação com a Teoria dos Jogos, denominada Teoria dos Jogos Algorítmica, teve um grande crescimento durante os últimos anos.

Entre alguns problemas interessantes abordados pela Teoria dos Jogos Algorítmica estão:

Nesses casos estamos interessando em algoritmos rápidos e que apresentem propriedades teóricas interessantes do ponto de vista da Economia como, por exemplo ser justo com os agentes participantes.

Entre os problemas que já trabalhei ou estou trabalhando nesta linha de pesquisa estão:

Se você quiser saber mais sobre a Teoria dos Jogos Algorítmica sugiro fazer o download (grátis) do seguinte livro Tópicos da teoria dos jogos em computação que escrevi com outros três professores do Instituto de Computação.

Veja também os vídeos abaixo:

E não deixe de jogar o jogo “A Evolução da Confiança” que explora vários conceitos de Teoria dos Jogos e pode ser jogado gratuitamente no seu navegador.

Outros livros sobre o assunto que podem ser consultados são:

Otimização Combinatória

Problemas de Otimização Combinatória são problemas onde desejamos encontrar uma solução de menor custo (ou maior valor), sendo que o conjunto de soluções é discreto (finito ou infinitamente enumerável). Tais problemas aparecem em diversas aplicações como o carregamento de cargas em contêineres, o projeto de redes, o roteamento de veículos para transporte e o escalonamento de tarefas computacionais.

Para tais problemas podemos projetar os chamados algoritmos exatos que encontram uma solução ótima para o problema. Entre as técnicas utilizadas para tanto estão: Programação Linear Inteira, Programação Dinâmica, Branch and Bound, entre outras.

Porém, os problemas mais interessantes de Otimização Combinatória são NP-difíceis, isto é, para tais problemas não existem algoritmos exatos que executem em tempo polinomial no tamanho da entrada a não ser que P = NP. Assim, podemos considerar algoritmos de aproximação e heurísticas para os mesmos.

Em suma, um algoritmo de aproximação é um algoritmo polinomial com uma garantia de qualidade para a solução encontrada. Eles são interessantes tanto do ponto de vista prático, já que podem ser usados para resolver o problema na prática, quanto do teórico, pois para desenvolver um algoritmo de aproximação com uma boa razão de aproximação é, usualmente, necessário explorar a fundo a estrutura combinatória do problema considerado e, por vezes, é necessário também desenvolver novas técnicas que posteriormente podem ser utilizadas em outros problemas.

Heurísticas são algoritmos que não necessariamente dão garantias de encontrar soluções ótimas (ou próximas de uma solução ótima, como no caso de um algoritmo de aproximação). Porém, boas heurísticas dão bons resultados na prática e são geralmente muito mais rápidas do que algoritmos exatos ou de aproximação. Já as metaheurísticas são métodos de alto nível, não necessariamente definidas para um problema específico ou com passos bem definidos, mas com métodos que permitem aplicá-los a uma grande gama de problemas, avançando a busca por novas soluções, seja fazendo modificações nas soluções existentes ou combinando-as na tentativa de se construir soluções que herdem as melhores características das soluções existentes.

Estou interessando também no projeto de Algoritmos Online, quando a entrada é revelada com o passar do tempo, diferentemente dos problemas usuais de Otimização Combinatória.

Entre os problemas que já trabalhei ou estou trabalhando nesta linha de pesquisa estão:

Além de problemas da Teoria dos Jogos Algorítmica que utilizam técnicas da Otimização Combinatória.

Alguns livros clássicos que abordam a resolução de problemas de otimização combinatória são:

Processo Seletivo da Pós-Graduação do IC-UNICAMP

O Instituto de Computação realiza dois processos seletivos anuais para a entrada de alunos na pós-graduação, um para a entrada no primeiro semestre, em geral em outubro do ano anterior, e outro para a entrada no segundo semestre, em geral, em maio do mesmo ano. O aluno não precisa ter se formado no curso anterior para fazer a inscrição, mas sim para realizar a matrícula.

Para os alunos de graduação do IC que pensam em fazer pós-graduação, é interessante ingressar no Programa Integrado de Formação (PIF) que permite acelerar a pós-graduação através da realização de um projeto de pesquisa e disciplinas da pós-graduação.

Bolsas de Iniciação Científica, Mestrado e Doutorado

O Instituto de Computação oferece bolsas de mestrado e doutorado pagas pelas agências CNPq e CAPES dependendo da qualificação do candidato no processo seletivo para a entrada na pós-graduação e, posteriormente, de acordo com o seu desempenho acadêmico.

Para os alunos da graduação, é possível obter uma bolsa de iniciação científica do CNPq (PIBIC) através de uma chamada anual da Pró-Reitoria de Pesquisa da UNICAMP que ocorre em abril. Veja mais sobre isso na página sobre PIBIC/PIBITI da Pró-Reitoria de Pesquisa.

Outra possibilidade tanto para a pós-graduação quanto para a iniciação científica é obter uma bolsa da FAPESP, a agência de fomento do estado de São Paulo. Para tanto, é necessário submeter um projeto de pesquisa que demora em torno de 90 dias para ser avaliado.

Essa uma agência de grande prestígio no estado (e no país), assim suas bolsas são bastante concorridas e destinada aos alunos com os melhores históricos de graduação e pós-graduação e com os melhores projetos. Em compensação, as mensalidades das bolsas da FAPESP costumam ser maiores do que as mensalidades das bolsas do CNPq e da CAPES. Além disso, a FAPESP oferece uma Reserva Técnica para as bolsas de pós-graduação para que os alunos possam adquirir equipamentos para a pesquisa e fazer viagens para congressos ou cursos, mesmo no exterior.

Para mais informações, consulte as regras para o pedido de Bolsa de Mestrado, Bolsa de Doutorado, Bolsa de Doutorado Direto e Bolsa de Iniciação Científica da FAPESP.

Sobre a UNICAMP

A Universidade Estadual de Campinas é uma das principais instituições de ensino superior da América Latina. Destaca-se por sua graduação e, também, por sua qualidade nos cursos de pós-graduação reconhecidos como os melhores do país, segundo a CAPES.

A cada ano são formados cerca de 2 mil mestres e doutores e a UNICAMP responde por 15% da pesquisa acadêmica no Brasil, além de manter a liderança entre as universidades brasileiras no que diz respeito a patentes e ao número de artigos per capita publicados anualmente em revistas indexadas na base de dados ISI/WoS.

Sobre o Instituto de Computação

O Instituto de Computação é a principal unidade de ensino e pesquisa da UNICAMP nas áreas de tecnologia da informação e teoria da computação. O Programa de Pós-Graduação do IC conta com 45 docentes com formação em diversas linhas de pesquisa e com papel de destaque no desenvolvimento da área de Ciência da Computação no Brasil. Alunos e docentes do programa já receberam diversas distinções e prêmios que indicam a excelência da formação e dos resultados de pesquisa obtidos ao longo dos anos.

As origens do Instituto de Computação da UNICAMP remontam a 1969, quando foi criado um curso de Bacharelado em Ciência da Computação no Instituto de Matemática, Estatística e Ciência da Computação (IMECC). Posteriormente, em 1996, o Departamento de Ciência da Computação deixou de fazer parte do IMECC para se tornar o Instituto de Computação.

Atualmente, o IC oferece cursos de graduação em Engenharia de Computação (conjuntamente com a Faculdade de Engenharia Elétrica e de Computação) e Bacharelado em Ciência da Computação, bem como cursos de pós-graduação como Mestrado e Doutorado.

Os cursos de pós-graduação do IC têm nota 7 (máxima) na CAPES, estão bem consolidados e já formaram mais de 800 mestres e mais de 190 doutores (dados de janeiro/2016). Atualmente, estes cursos contam com cerca de 300 alunos, oferecendo anualmente cerca de 50 disciplinas de pós-graduação, sendo que em torno de 40% delas ministradas em inglês.

Para maiores informações, veja também os materiais de divulgação da Pós-Graduação do IC: Folder e Cartaz

Sobre o LOCo

O Laboratório de Otimização e Combinatória do IC-UNICAMP é um espaço destinado para os alunos de pós-graduação dos professores associados. Conta com computadores, impressoras e livros para a utilização dos alunos membros. Atualmente existem 11 professores e uma grande lista de alunos de mestrado e doutorado associados ao laboratório. Essa equipe trabalha em problemas de várias áreas:

A interação entre os alunos do laboratório permite a disseminação de ideias que ajudam na pesquisa e também no bom andamento nas disciplinas dos programas.

Sobre Campinas

Campinas é uma cidade do estado de São Paulo com 1,1 milhão de habitantes localizada a 99 km da capital paulista, sendo o terceiro município mais populoso do estado (atrás apenas de São Paulo e Guarulhos) e o décimo quarto mais populoso do país. Sua região metropolitana é formada por vinte municípios e possui mais de três milhões de habitantes, formando a décima maior área metropolitana do Brasil.

Campinas é responsável por pelo menos 15% de toda a produção científica nacional, sendo o terceiro maior polo de pesquisa e desenvolvimento brasileiro, e concentra cerca de um terço da produção industrial do estado. Nesse sentido, destacam-se as indústrias de alta tecnologia e o parque metalúrgico. A região abriga mais de 10 mil empresas de médio e grande porte tais como: Honda, Toyota, Unilever, 3M do Brasil, Bosch, Bridgestone, Dell, IBM, BASF, Ericsson, General Electric, Texas Instruments, AmBev, Lenovo, entre muitas outras.