Lehilton Lelis Chaves Pedrosa

Informações para interessados em orientação

Esta página contém informações para interessados em orientação em iniciação científica, mestrado ou doutorado em alguma das minhas áreas de pesquisa. Você também pode encontrar algumas informações sobre o processo inscrições, bolsas, etc. Se você estiver interessado em orientação, envie um e-mail para lehiton@ic.unicamp.br falando um pouco sobre você, ou venha conversar comigo na minha sala.

Sobre mim

Graduei-me em Ciência da Computação na Universidade de Brasília em 2007 depois completei o Mestrado e Doutorado no Instituto de Computação (IC) da Universidade de Campinas (Unicamp) em 2010 e em 2014. Minha tese de doutorado trata de Algoritmos de Aproximação e foi escolhida como melhor tese em Ciência da Computação pela SBC em 2015. Sou professor no IC desde 2015 e faço parte do Laboratório de Otimização e Combinatória (LOCO). Também já estive na Universidade de Warwick, Reino Unido, durante meu doutorado no ano de 2013, e, antes de voltar ao IC como professor, trabalhei como pós-doutorando no Departamento de Ciência da Computação (DCC/IME) da Universidade de São Paulo (USP).

Meu principal interesse de pesquisa está no Projeto e Análise de Algoritmos. Nessa área estamos interessados em resolver e estudar problemas usando as mais variadas abordagens de Otimização Combinatória, Algoritmos de Aproximação, Algoritmos Online, Algoritmos Parametrizados, Geometria Computacional, etc., ou responder perguntas desafiadoras acerca da estrutura e dificuldades de problemas computacionais, temas de disciplinas como Complexidade Computacional e Grafos. Outras áreas de pesquisa com que já trabalhei ou trabalho são autômatos e linguagens formais.

Principais linhas de investigação

Algoritmos de Aproximação e Otimização Combinatória

Em todo problema computacional devemos identificar a entrada e a saída. Por exemplo, se você quiser encontrar um caminho no entre sua casa e o cinema, então a entrada é o par de origem e destino e a saída é a uma rota construída pelo algoritmo. Mas algumas vezes podem existir várias saídas para a mesma entrada (i.e., você pode chegar ao cinema usando várias rotas). É natural então perguntar qual é a melhor solução. Para isso, atribuímos um valor a cada solução e procuramos alguma que tenha o melhor valor. Definimos assim um problema de otimização . No nosso exemplo, queremos saber qual é a rota mais curta até o cinema!

Infelizmente, nem todo problema de otimização é tão fácil como o problema da rota mais curta. Há diversos problemas importantes (tanto teóricos como da indústria) para os quais não conhecemos qualquer algoritmo rápido: problema do caixeiro-viajante (TSP), k-means, coloração em grafos, cobertura de conjuntos, etc. Na verdade, a maioria dos pesquisadores acredita que de fato não existem algoritmos rápidos (polinomiais) para esses problemas. Mostrar que não existem tais algoritmos é a principal questão em aberto da Ciência da Computação: P ≠ NP?

Ainda que não existam algoritmos rápidos para esses problemas, queremos obter soluções boas rapidamente. Isso é particularmente crítico em problemas industriais, para os quais melhorias nas soluções pode significar economia expressiva (desde milhares até milhões de reais). Assim, devemos abrir mão de encontrar a melhor solução: queremos encontrar uma solução aproximada. Em um algoritmo de aproximação o tempo de execução é polinomial e a razão entre o custo da solução obtida e o custo de uma solução ótima é limitada por uma fator dado. São diversas as técnicas para se obter um algoritmo de aproximação, que incluem algoritmos gulosos, busca local, enumeração, programação dinâmica, métodos probabilísticos e programação linear inteira.

Alguns exemplos de problemas interessantes com que já trabalhei, ou tenho interesse em trabalhar, estão descritos na lista seguir (não exaustiva).

• Problemas de localização de instalações: Nesses problemas, um atacadista tem um conjunto de lojas espalhadas na cidade e precisa decidir que armazéns contratar de forma a minimizar o custo de aluguel e transporte de mercadorias. Esse problema tem motivação principalmente em cadeias de produção de indústrias e têm aplicações em projeto de rede em várias situações.

• Problemas de particionamento: Nesses problemas queremos agrupar itens relacionados em um dado número de clusters. Os principais subproblemas nessa classe são o k-median, k-means, k-center. Por exemplo, no k-means, recebemos um conjunto de n pontos no espaço R ^d^ e queremos dividi-los em k partes; esse problema tem aplicações em processamento de sinais, aprendizado de máquinas (classificação, etc.) e vários outros.

• Problemas de logística e abastecimento: Nesses problemas, queremos encontrar um planejamento ou uma política de reabastecimento de estoque de forma a minimizar diversos custos, como custo de armazenamento, custo de compra, etc. Um exemplo clássico é o Problema de Reabastecimento Conjunto (JRP), no qual temos que decidir quando reabastecer simultaneamente um conjunto de lojas de forma a minimizar os custo de armazenamento num dado horizonte de planejamento.

• Problemas de alocação de terminais: Em diversos problemas, há demanda por fluxo de itens entre pares de elementos. Por exemplo, na aviação civil, cada voo é uma demanda por ligar dois pontos. Nessas situações, é comumente mais econômico utilizar um conjunto de terminais e servir cada demanda indiretamente; assim, alguns voos realizam conexões em aeroportos principais, que são chamados de terminais. O problema aqui é como associar cada demanda a um ou mais terminais, de forma a satisfazer toda demanda e minimizar os custos gerais.

Um lista de vários problemas de otimização clássicos e já bastante estudados pode ser encontrada nesse compêndio. Algumas sugestões de referências sobre algoritmos de aproximação seguem:

• Approximation Algorithms: Vazirani. (2001)
  Um dos primeiros livros-textos sobre o assunto

• Uma Introdução Sucinta a Algoritmos de Aproximação: Carvalho, Cerioli, Dahab, Feofiloff,Fernandes, Ferreira, Guimarães, Miyazawa, Pina, Soares e Wabayashi. (2001)
  Um dos primeiros livros-textos sobre o assunto em português e com abordagem bem direta.

• The Design of Approximation Algorithms: Williamson e Shmoys. (2011)
  Um livro mais atual com técnicas recentes.

Algoritmos Parametrizados

Um problema é normalmente analisado a partir do tamanho de sua entrada n. Se ele for NP-difícil, então é bem provável que não exista algoritmo polinomial em n que o resolva. Mas isso não quer dizer que não exista algoritmo prático e viável: a análise de algoritmos multivariada vem dizer que a NP-dificuldade não é a última palavra em tratabilidade. Ao invés de analisar um algoritmo a partir de uma única variável n, em um algoritmo parametrizado, procuramos estudar a estrutura do problema, identificando e isolando uma medida secundária, um parâmetro k, que afeta significativamente a complexidade computacional.

Essa área é relevante tanto para aqueles interessados em estudar problemas do ponto de vista teórico, quanto para aqueles interessados em técnicas algorítmicas para resolver problemas práticos de maneira eficiente. De fato, o campo de Algoritmos Parametrizados é amplamente interdisciplinar, com aplicações em processamento massivo de grandes conjuntos de dados, pesquisa operacional, bioinformática, IA, teoria da escolha social e outras disciplinas.

São diversas as técnicas envolvidas no projeto de algoritmo parametrizados, entre elas kernelização, árvores de busca limitadas, algoritmos aleatorizados paramétricos e programação linear inteira. Diversos problemas estudados na área podem ser modelados como problemas em grafos, então é recorrente perguntas sobre a estrutura do grafo, como largura de árvore (treewidth), etc. Assim, essa linha de pesquisa é particularmente atrativa tanto para aqueles interessados em algoritmos como em Teoria dos Grafos. Além do projeto de algoritmo, a Complexidade Parametrizada fornece um novo meio para estudar e classificar o que entendemos como problemas difíceis.

Algumas sugestões de referências sobre algoritmos parametrizados segue:

• Parameterized Algorithms: Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk e Saurabh. (2015)
  Um livro bem atual focado no projeto de algoritmos

• Fundamentals of Parameterized Complexity: Downey e Fellows. (2013)
  Uma atualização do primeiro livro de 1999, com avanços e mais focado em complexidade

Outras áreas de interesse

Alguns outros tópicos com que já trabalhei anteriormente incluem, entre outros, autômatos e linguagens formais. Uma máquinas de estados finitos (MEF) é um autômato que, a cada símbolo de entrada lido, produz um símbolo de saída. As MEFs são utilizadas para modelar especificações e gerar casos de testes, imprescindíveis para validação de sistemas complexos, como protocolos de comunicação e programas de computador. O objetivo de um método de geração automática de casos de testes é obter um conjunto de casos de testes, com o qual é possível verificar se uma dada implementação contém falhas. Um problema importante em métodos de geração de casos de teste com cobertura completa de falhas é o tamanho dos conjuntos de testes, que normalmente é exponencial no número de estados da MEF que está sendo testada.

Também já trabalhei com gramáticas formais, que são os chamados sistemas de Lindenmayer. Um L-system assemelha-se a uma gramática tradicional, mas diferencia-se fundamentalmente pelo fato de que cada símbolo em uma determinada cadeia é substituído paralelamente por uma outra cadeia. Esse sistema foi criado pelo biólogo Lindenmayer para estudar o crescimento de plantas. Assim, as simultaneidade da derivação corresponde ao ao paralelismo envolvido no crescimento das plantas: cada símbolo da gramática corresponde a um pedaço da planta. As sequências derivadas por um L-system são normalmente interpretadas graficamente, de forma que cada símbolo corresponda a um comando, o que permite construir representações gráficas de plantas modeladas por uma gramática.

Sobre a Unicamp e o Instituto de Computação

A Unicamp

A Universidade Estadual de Campinas é uma das principais instituições de ensino superior da América Latina. Anualmente são formados cerca de 2 mil mestres e doutores e a Unicamp responde por 15% da pesquisa acadêmica no Brasil, liderando entre as universidades brasileiras quanto ao número de artigos per capita (considerando revistas indexadas na base de dados ISI/WoS).

A Unicamp fica situada no distrito de Barão Geraldo da cidade de Campinas, que fica no interior do estado de São Paulo a 99 km da capital paulista. Campinas tem 1,1 milhão de habitantes, sendo o terceiro município mais populoso do estado e o décimo-quarto do país. A Região Metropolitana de Campinas é conhecida por ser um polo de indústrias de alta tecnologia e outras, abrigando mais de 10 mil empresas de médio e grande porte.

O Instituto de Computação

A origem do Instituto de Computação (IC) remonta a 1969, quando foi criado o primeiro curso de bacharelado em Ciência da Computação no país, então oferecido pelo Instituto de Matemática, Estatística e Ciência da Computação (IMECC). Em 1996, o Departamento de Ciência da Computação tornou-se independente, fundando 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.

O programa de pós-graduação no Instituto de Computação (IC) é um dos principais programas em Ciência da Computação do país, sendo avaliado pela CAPES com conceito 7 (máximo). Alunos e docentes do programa já receberam diversas distinções e prêmios ao longo dos anos, o que indicam a excelência da formação e da pesquisa do programa. O processo seletivo para ingresso na pós graduação é semestral, com inscrições abertas em maio e em outubro de cada ano.

Bolsas

O Instituto de Computação oferece bolsas de mestrado e doutorado pagas pelas pelo CNPq e pela CAPES dependendo da classificação do candidato no processo seletivo e, depois, de acordo com o seu desempenho acadêmico. Alunos de graduação podem obter bolsa de iniciação científica do CNPq por meio do programa PIBIC.

Além das bolsas institucionais, os alunos de graduação, mestrado ou doutorado podem e são encorajados a submeter projetos de pesquisa à FAPESP, que é a agência de fomento a pesquisa do estado de São Paulo. As bolsas da FAPESP são mais concorridas, mas são prestigiadas e costumam ter valores de mensalidades maiores que os do CNPq e da CAPES. Além disso, a FAPESP oferece valores de reserva técnica para as bolsas de pós-graduação para que os alunos adquiram equipamentos e viajem a congressos e cursos no país ou no exterior.