¹

Resumo: apresentamos neste relatório as atividades de formação de recursos humanos de nossa equipe no período de fevereiro de 1998 a novembro de 1999.

Complexidade de Estruturas Discretas

Y. Kohayakawa

FORMAÇÃO DE RECURSOS HUMANOS

Doutorado

Concluídos

1.

Luerbio Faria [C.M.H. de Figueiredo/IM-COPPE-UFRJ]. Bolsa da CAPES. Título da tese: Alguns Resultados em Invariantes de Não Planaridade em Grafos: Uma Abordagem Estrutural e de Complexidade. Término: agosto/98.

2.

Maria Emília Machado Telles Walter [J. Meidanis/IC-UNICAMP]. Bolsa da CAPES. Título da tese: Algoritmos para Problemas em Rearranjo de Genomas. Término: novembro/99.

Em andamento

1.

Orlando Lee [Y. Wakabayashi/IME-USP]. Título da tese: Coberturas por Circuitos em Grafos Mistos. Bolsa da CAPES. Ingresso no programa: março/95. Data da defesa: 17/dezembro/99.

2.

Bráulio Maia Junior [M. Lemos/DM-UFPE]. Título da tese: Matróides Conexas com Circunferência Pequena. Bolsa da CAPES. Ingresso no programa: março/97. Data da defesa: 20/dezembro/99.

3.

Nalvo Franco de Almeida Jr [J.C. Setubal/IC-Unicamp]. Título da tese: Ferramentas computacionais para genômica . Bolsa PICD-CAPES com sanduíche CAPES-Fulbright. Ingresso no programa: março/95. Defesa prevista para 2000.

4.

Júlio César Lopez Hernandez [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Análise e Implementação de Algoritmos Criptográficos baseados em Curvas Elípticas. Sem bolsa no momento. Ingresso no programa: agosto/95. Defesa prevista para abril/2000.

5.

José Roberto Monteiro [Cláudio L. Lucchesi e (co-orientador) Ricardo Dahab/IC-UNICAMP]. Título do projeto: Protocolos Criptográficos Eficientes para Troca Autenticada. Sem bolsa no momento). Ingresso no programa: março/95. Defesa prevista para agosto/2000.

6.

Jair Donadelli Júnior [Y. Kohayakawa/IME-USP]. Título do projeto: Métodos Probabilísticos e Métodos Topológicos em Combinatória Extremal. Bolsa da CAPES até dezembro/97 e bolsa do CNPq desde janeiro/98. Ingresso no programa: março/96.

7.

Estela Maris Rodrigues [Y. Wakabayashi/IME-USP]. Título do projeto: Algoritmos de Inferência Filogenética. Bolsa do CNPq. Ingresso no programa: março/97.

8.

Guilherme Pimentel Telles [J. Meidanis/IC-UNICAMP]. Título do projeto: Mapas Físicos de DNA. Bolsa da FAPESP. Ingresso no programa: março/97.

9.

Christiane Neme Campos Toledo [Cláudio L. Lucchesi/ IC-UNICAMP]. Título do projeto: Grafos Cobertos por Emparelhamentos. Bolsa do CNPq. Ingresso no programa: março/97.

10.

Liliane Rose Benning Salgado [Y. Wakabayashi/IME-USP]. Título do projeto: Aproximabilidade de Problemas de Otimização em Grafos. Bolsa da FAPESP desde agosto/98. Ingresso no programa: março/98.

11.

Zanoni Dias [J. Meidanis/IC-UNICAMP]. Título do projeto: Rearranjo de Genomas. Bolsa da FAPESP. Ingresso no programa: março/98.

12.

Marco Aurélio Stefanes [J. Soares/IME-USP]. Título do projeto: Algoritmos Paralelos para Grafos e Geometria Computacional. Bolsa da FAPESP desde agosto/98. Ingresso no programa: março/98.

13.

Francisco Elói Soares de Araújo [J. Soares/IME-USP]. Título do projeto: Biologia Computacional. Ingresso no programa: agosto/98.

14.

Glauber Ferreira Cintra [Y. Wakabayashi/IME-USP]. Título do projeto: Algoritmos para Problemas de Corte Multidimensionais. Ingresso no programa: agosto/98.

15.

Emerson Alexandre de Oliveira Lima [S. Lins/DM-UFPE]. Título do projeto: Implementação de uma Dinâmica Combinatória para Classificar 3-variedades. Ingresso no programa: março/99.

16.

Simone Dantas de Souza [C.M.H. de Figueiredo/IM-COPPE-UFRJ]. Título do projeto: Problemas-sanduíche em Grafos. Bolsa da CAPES. Ingresso no programa: março/99.

17.

Alexandre Melo Braga [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Segurança de Sistemas Móveis. Bolsa do CNPq. Ingresso no programa: agosto 1999.

18.

Lucas de Carvalho Ferreira [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Métodos Formais em Protocolos Criptográficos. Sem bolsa-com vínculo empregatício em outra instituição. Ingresso no programa: agosto/99.

19.

Loana Tito Nogueira [S. Klein/IM-COPPE-UFRJ]. Título do projeto: Complexidade de Problemas de Partição em Grafos. Bolsa do CNPq. Ingresso no programa: outubro/99.

Mestrado

Concluídos

1.

Marco Aurélio Stefanes [J. Soares/IME-USP]. Bolsa do CNPq de março/95 a fevereiro/97. Título da dissertação: Algoritmos e Implementações Paralelas para Florestas Geradoras Mínimas. Término: fevereiro/98.

2.

Edinson Raul Montoro Alegre [C.M.H. de Figueiredo/IM-COPPE-UFRJ]. Bolsa da CAPES. Título da dissertação: Algoritmos Dinâmicos para Árvore Geradora Mínima. Término: fevereiro/98.

3.

Glauber Ferreira Cintra [Y. Wakabayashi/IME-USP]. Bolsa do CNPq. Título da dissertação: Algoritmos Híbridos para Problemas de Corte Unidimensional. Término: julho/98. 1o. Prêmio no VI Concurso CLEI-UNESCO de Teses de Mestrado, 1999.

4.

Francisco Elói Soares de Araújo [J. Soares/IME-USP]. Bolsa da CAPES. Título da dissertação: Rearranjo de Genomas por Reversões. Término: agosto/98.

5.

Cristina Célia Cavalcante [Cid de Carvalho de Souza/IC-UNICAMP]. O Problema de Escalonamento com Restrições de Mão-de-Obra. Bolsa da FAPESP. Início: março/96. Término: agosto/98.

6.

Lucas de Carvalho Ferreira[Ricardo Dahab/IC-UNICAMP]. Título da dissertação: Sistemas de Pagamento Eletrônico: Análise e Implementação. Bolsa do CNPq. Término: 1998.

7.

Armando Ramos Gouveia [Y. Kohayakawa/IME-USP], Mestre. Bolsa da CAPES. Título da dissertação: Provas Holográficas de Tamanho Quase-linear. Término: novembro/98.

8.

Márcia Graci Carneiro de Oliveira [M. Lemos/DM-UFPE]. Bolsa do CNPq. Título da dissertação: Decomposição de Grafos Planares em Ciclos Pares. Término: maio/99.

9.

Ivan da Silva Sendim [Ricardo Dahab/IC-UNICAMP]. Título da dissertação: Funções de Hashing para Aplicações Criptográficas. Bolsa da CAPES. Término: julho/99.

10.

Alexandre Melo Braga [Ricardo Dahab e Cecília M. F. Rubira/ IC-UNICAMP]. Título da dissertação: Análise Comparativa e Proposta de Extensão à Arquitetura Criptográfica JAVA. Bolsa do CNPqe posteriormente FAPESP. Término: agosto/99.

11.

Loana Tito Nogueira [S. Klein/IM-COPPE-UFRJ]. Bolsa da CAPES. Título da dissertação: Grafos Split e Grafos Split Generalizados. Término: setembro/99.

12.

Ricardo Scachetti Pereira [Cid de Carvalho de Souza/IC-UNICAMP]. Algoritmos Exatos e Heurísticas para Problemas de Otimização Combinatória encontrados na Logística de Distribuição de Revistas. Bolsa da FAPESP. Início: agosto/96. Término: setembro/99.

13.

Andrea Rosario Pari Soto [S. Klein/IM-COPPE-UFRJ e N. Maculan/COPPE-UFRJ]. Bolsa da CAPES. Título da dissertação: Algoritmos Aproximativos para o Problema do Caixeiro Viajante. Término: outubro/99.

14.

Alexandre Scalzitti [Y. Kohayakawa/IME-USP]. Título da dissertação: Convergência na Teoria dos Grafos Aleatórios. Término: outubro/99.

15.

Mário Leston Rey [P. Feofiloff/IME-USP]. Título da dissertação: T-junções, T-cortes e funções conservativas. Bolsa do CNPq. Término: novembro/99.

Em andamento

1.

Edésio R. Sibrão [C.E. Ferreira/IME-USP]. Título do projeto: Escalonamento em Sistemas de Produção: um Estudo de Caso. Bolsa da CAPES de agosto/96 até julho/98. Ingresso no programa: agosto/96. Data da defesa: 13/dezembro/99.

2.

Carlos R. Pantaleon Dionisio [J.C. de Pina/IME-USP]. Título do projeto: Geometria Computacional de Pontos em Movimento. Bolsa do CNPq até fevereiro de 1997. Ingresso no programa: março/96.

3.

Fábio Ribeiro Cerqueira [J. Meidanis/IC-UNICAMP]. Título do projeto: Montagem de Fragmentos de DNA. Bolsa do CNPq até fevereiro de 1997. Ingresso no programa: março/96.

4.

Aritanan Borges Garcia Gruber [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos e Estruturas de Dados para Problemas em Grafos Dinâmicos. Bolsa do CNPq. Ingresso no programa: março/97.

5.

Said Sadique Adi [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos Combinatórios para Seqüenciamento de DNA. Bolsa do CNPq. Ingresso no programa: março/98.

6.

Cassio Polpo de Campos [C.E. Ferreira/IME-USP]. Título do projeto: Problemas Dinamicos em Geometria Computacional. Bolsa da FAPESP. Ingresso no programa: março/99.

7.

Eduardo Garcia de Freitas [C.E. Ferreira/IME-USP]. Título do projeto: Problemas Cineticos em Geometria Computacional. Bolsa da FAPESP. Ingresso no programa: março/99.

8.

Ademakson Souza Araujo [M. Lemos/DM-UFPE]. Título do projeto: Fluxos em Grafos. Bolsa do CNPq. Ingresso no programa: março/98.

9.

Cláudio Tadeu Cristiano [M. Lemos/DM-UFPE]. Título do projeto: Polinômio de Tutte. Bolsa do CAPES. Ingresso no programa: agosto/98.

10.

Débora Cristina Alves Rego [S. Klein/IM-COPPE-UFRJ]. Título do projeto: Grafos de Interseção Geométrica. Bolsa do CNPq. Ingresso no programa: março/99.

11.

Vagner Katsumi Okura [J.C. Setubal/IC-Unicamp]. Título da dissertação: Infraestrutura de bioinformática para projetos genoma. Bolsa CNPq/FAPESP. Ingresso no programa: março/96.

12.

Lidio Nunes de Abreu Jr. [J.C. Setubal/IC-Unicamp]. Título da dissertação: Aspectos do problema da designação. Bolsa CNPq/FAPESP. Ingresso no programa: março/97.

13.

Arlindo Flávio da Conceição [J.C. Setubal/IC-Unicamp]. Título da dissertação: Problemas combinatórios de congestionamento. Bolsa CNPq. Ingresso no programa: março/97.

14.

Tallys Hoover Yunes [Cid de Carvalho de Souza/IC-UNICAMP]. Problemas de Escalonamento no Transporte Coletivo: Programação por Restrições e Outras Técnicas. Bolsa da FAPESP. Ingresso no programa: março/98. (Em co-orientação com o Prof. Dr. Arnaldo Moura do IC-UNICAMP).

15.

Marília Dias Vieira Braga [J. Meidanis/IC-UNICAMP]. Título do projeto: O Problema de Minimizar o Número de Contigs. Bolsa da FAPESP. Ingresso no programa: março/98.

16.

Lin Tzy Li [J. Meidanis/IC-UNICAMP]. Título do projeto: O Método OSS de Seqüenciamento de DNA. Bolsa da FAPESP. Ingresso no programa: março/98.

17.

Felipe Carneiro Calheiros [Cid de Carvalho de Souza/IC-UNICAMP]. Problemas de Cobertura, Empacotamento e Partição de Polígonos Retilineares. Sem bolsa (funcionário do BNDES-Rio). Ingresso no programa: março/98.

18.

Eduardo Kazuaki Gondo [Cristina G. Fernandes/IME-USP]. Título do projeto: Algoritmos de Aproximação para Árvores de Steiner. Ingresso no programa: março/98.

19.

Luiz Carlos Rozante [José Augusto Soares/IME-USP]. Título do Projeto: Algoritmos para Predição de Estrutura Secundária do RNA. Bolsa do CNPq. Ingresso no programa: março/98.

20.

Clésio Takahashi [Cristina G. Fernandes/IME-USP]. Título do projeto: Computação Quântica. Ingresso no programa: agosto/98.

21.

Maikol Magalhães Rodrigues [Cid de Carvalho de Souza/IC-UNICAMP]. Problema de Planejamento de Viagens no Transporte Coletivo Urbano. Bolsa da FAPESP. Ingresso no programa: março/99.

22.

Liana D. Duenha [M.H. Carvalho/DCT-UFMS]. Título do projeto: O Problema das Quatro Cores. Ingresso no programa: março/99.

23.

Cândida Nunes da Silva [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Fluxos Inteiros em Grafos: Conjeturas de Tutte e Resultados Recentes. Bolsa do CNPq. Ingresso no programa: março/99.

24.

Danival Taffarel Calegari [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Proposta de Extensão Criptográfica da API JavaCard. Bolsa do CNPq. Ingresso no programa: março/99.

25.

Rogério Albertoni Miranda [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Criptossistemas Baseados em Curvas Elípticas. Bolsa do CNPq. Ingresso no programa: março/99.

26.

Ronney Rodger Sales de Castro [Cristina G. Fernandes/IME-USP]. Título do projeto: Algoritmos de Aproximação para Supercadeia Mínima e Problemas Correlatos. Bolsa da CAPES. Ingresso no programa: março/99.

27.

Eduardo Tengan [A. Mandel/IME-USP]. Título do projeto: Uso de ideais quando poliedros falham. Ingresso no programa: agosto/99.

28.

Rogério Theodoro Brito [José Augusto Soares/IME-USP]. Ingresso no programa: agosto/99.

29.

Márcio Grossi de Almeida [Y. Kohayakawa/IME-USP]. Título do projeto: Números de Ramsey Induzidos e Semi-induzidos . Bolsa do CNPq. Ingresso no programa: março/98.

Iniciação científica

1.

Cassio Polpo de Campos [C.E. Ferreira/IME-USP]. Título do projeto: Geometria Computacional: Algoritmos e Aplicações. Bolsa da FAPESP de fevereiro a dezembro de 1998.

2.

Dan Faccio [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos Combinatórios para Rearranjo de Seqüências de DNA. Bolsa do PIBIC-CNPq de fevereiro de 1997 a janeiro de 1998.

3.

Eduardo Garcia de Freitas [C.E. Ferreira/IME-USP]. Título do projeto: Geometria Computacional: Algoritmos e Aplicações. Bolsa da FAPESP de fevereiro a dezembro de 1998.

4.

Rodrigo Nonamor Pereira Mariano de Souza [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos Combinatórios para Árvores Filogenéticas. Bolsa do PIBIC-CNPq de maio a dezembro de 1998.

5.

Rogério Theodoro de Brito [J. Soares/IME-USP]. Título do projeto: Compressão de Dados. Período: desde março de 1995. Bolsa do CNPq de agosto de 1995 a julho de 1997.

6.

Sérgio Gabriel Tavares [C.E. Ferreira/IME-USP]. Título do projeto: Heurísticas para o Problema de Decomposição de Matrizes. Bolsa do PIBIC-CNPq de fevereiro de 1997 a maio de 1998.

7.

Thiago Teixeira Santos [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos Combinatórios para Rearranjo de Seqüências de DNA. Bolsa do PIBIC-CNPq de fevereiro a dezembro de 1998.

8.

Fabricio Chalub Barbosa do Rosário [S. Klein/IM-COPPE-UFRJ]. Título do projeto: Estudo e implementação de algoritmos de decomposição por conjuntos homogêneos e por pares homogêneos. Bolsa do CNPq-UFRJ de agosto de 1996 a dezembro de 1998.

9.

Guilherme Dias da Fonseca [C.M.H. de Figueiredo/IM-COPPE-UFRJ]. Título do projeto: Casamentos Estáveis. Bolsa do CNPq-UFRJ de setembro de 1998 a julho de 2000.

10.

Adriano Brito Brito Pereira [S. Klein/IM-COPPE-UFRJ]. Título do projeto: Estudo de algoritmos gulosos. Bolsa do CNPq-UFRJ desde janeiro de 1999.

11.

Bruno Crotman [C.M.H de Figueiredo e C.F. Bornstein/IM-COPPE-UFRJ]. Título do projeto: Algoritmos Paralelos. Bolsa do CNPq-PI de março de 1999 a fevereiro de 2001.

12.

Raphael Perret [C.M.H. de Figueiredo e C.F. Bornstein/IM-COPPE-UFRJ]. Título do projeto: Algoritmos Paralelos. Bolsa do CNPq-PI de março de 1999 a fevereiro de 2001.

13.

Thiago Souza Mendes Guimarães [C.M.H. de Figueiredo e C.F. Bornstein/IM-COPPE-UFRJ]. Título do projeto: Algoritmos Paralelos. Bolsa do CNPq-PI de março de 1999 a fevereiro de 2001.

14.

Tahuana Araujo Cirati Gomes [C.M.H. de Figueiredo e M.R. Cerioli/IM-COPPE-UFRJ]. Título do projeto: Coloração em Grafos. Bolsa do CNPq-UFRJ de setembro de 1999 a julho de 2000.

15.

Alex Martins Daher [F.K. Miyazawa/IC-UNICAMP]. Título do projeto: Problemas de Empacotamento em Placas. Bolsa do PIBIC-CNPq de setembro de 1998 a julho de 1999.

16.

Alexandre Gonçalves Silva [F.K. Miyazawa/IC-UNICAMP]. Título do projeto: O Problema de Corte Bidimensional. Bolsa do PIBIC-CNPq de setembro de 1998 a julho de 1999.

17.

Alexandre Corrêa Barbosa [J.C. Setubal/IC-Unicamp]. Título do projeto: Montagem do genoma da Xanthomonas citri. Bolsa solicitada à FAPESPde janeiro a junho de 2000.

18.

Fernando Gonçalves Urzedo [J.C. Setubal/IC-Unicamp]. Título do projeto: Suporte computacional para projetos genoma de EST. Bolsa solicitada à FAPESPde janeiro a junho de 2000.

19.

Renato Werneck [J.C. Setubal/IC-Unicamp]. Título do projeto: Suporte computacional para projetos genoma. Bolsa da FAPESP, dezembro de 1998 a maio de 1999.

20.

Cesar Augusto da Silva Scolar [J.C. Setubal/IC-Unicamp]. Título do projeto: Algoritmos e programas para determinação de estruturas em DNA genômico. Bolsa da FAPESP, agosto de 1998 a julho de 1999.

21.

Paulo Fabiano Macedo [J.C. Setubal/IC-Unicamp]. Título do projeto: Implementação de algoritmo distribuído para o problema do fluxo máximo. Bolsa da FAPESP, agosto de 1997 a julho de 1998.

22.

Cláudia Cristina Cepukas. [J.C. Setubal/IC-Unicamp]. Título do projeto: Algoritmos perpendiculares. Bolsa da FAPESP, agosto de 1997 a julho de 1998.

23.

Alerso Souza Delgado [Fábio H.V. Martinez/DCT-CCET]. Título do projeto: Mapeamento Físico de DNA. Bolsa do PIBIC-CNPq de agosto de 1998 a julho de 1999.

24.

Edson Borin [M.H. Carvalho/DCT-CCET]. Título do projeto: Algoritmos para Desenho de Grafos. Bolsa do PIBIC-CNPq de agosto de 1999 a julho de 2000.

25.

Graziela Santos de Araújo [Fábio H.V. Martinez/DCT-CCET]. Título do projeto: Comparação entre Múltiplas Seqüências em Biologia Molécular Computacional. Bolsa do PIBIC-CNPq de agosto de 1998 a julho de 1999.

26.

Joe Américo Colombo [M.H. Carvalho/DCT-CCET]. Título do projeto: Emparelhamento em Grafos. Bolsa do PIBIC-CNPq de agosto de 1998 a julho de 1999.

27.

Marcelo Abdalla dos Reis [M.H. Carvalho/DCT-CCET]. Título do projeto: O Problema das Quatro Cores. Bolsa do PIBIC-CNPq de agosto de 1998 a julho de 1999.

28.

Welton Luiz Faria Balani [Fábio H.V. Martinez/DCT-CCET]. Título do projeto: Comparação de Duas Seqüências em Biologia Molecular Computacional. Bolsa do PIBIC-CNPq de agosto de 1998 a julho de 1999.

Footnotes

... ¹

Data: 30 de novembro de 1999. Projeto no. 107/97