logo Grupo de Pesquisa em Teoria da Computação, Otimização e Combinatória


O TEORIA (Grupo de Pesquisa em Teoria da Computação, Otimização e Combinatória) é um grupo de pesquisa voltado ao estudo de algoritmos, otimização, complexidade computacional e aspectos teóricos da computação. Aspectos práticos e experimentais de algoritmos também são abordados. O grupo é responsável por organizar seminários de pesquisa, além de ministrar disciplinas avançadas são ofertadas 2 ou 3 vezes ao ano.

Além das áreas tradicionalmente ligadas a algoritmos e complexidade, o grupo também tem interesse nos fundamentos teóricos de outras áreas de computação, como sistemas distribuídos, banco de dados, inteligência artificial, aprendizado de máquina e ciência de dados.

Estudantes e pesquisadores interessados tanto em projetos em áreas teóricas quanto projetos envolvendo uma abordagem mista de aplicações reais com teoria estão convidados a entrar em contato com o grupo.


Notícias e Eventos
  • De 28/11/2018 a 06/12/2018
Calendário de Seminários

Para receber avisos dos seminários em seu email, cadastre-se aqui.

Usuários do Google Calendar podem importar a agenda acima. Neste caso, recebe-se lembretes com antecedência de 1 dia, e também com 4 horas.

Estudantes

Doutorado
  • Aleffer Rocha - “Raízes Quadradas de Grafos”
  • Edmilson Pereira da Cruz (lattes) - “Grafo biclique”
  • Flávio Henrique da Silva (lattes)
  • Henrique Hepp - “Classes de complexidade quânticas próximas de BQP”
Mestrado
  • David Reksidler Júnior (lattes) - “Clique máxima em grafos lei de potência”
  • Matheus de Moraes Cavazotti
Iniciação Científica
  • Gabriel Silva Hermida - “Raízes Quadradas de Grafos”
  • Katriny Zamproni
  • Pietro Polinari Cavassin - “Raízes Quadradas de Grafos”
Trabalho de Graduação
  • André Luis da Silva Machado (lattes) - “algoritmo de Tarjan/Trojanowski para conjunto independente máximo”
  • Cristopher Luiz Assad Carcereri
  • Guilherme Manteuffel Bettu (lattes) - “exploração de vizinhanças de tamanho exponencial em tempo polinomial”
  • Jhoser Alaff dos Santos Matheus
  • Leonardo Stefan - “algoritmos em grafos em bases de dados para grafos”
  • Richard Fernando Heise Ferreira
  • Vinicius Hideyoshi Correa Yoshida
  • Vinicius Tikara Venturi Date
Ex-alunos
  • Alane Marie de Lima (lattes) (Doutorado) - “Complexide de amostra em problemas de aproximação”
  • Alexandre Züge (Doutorado) - “Algoritmos para o Problema da Clique Máxima: análise e comparação experimental”
  • Cleiton Almeida dos Santos (lattes) (Doutorado) - “Planificação de rota em 3D”
  • Diego Roberto Antunes (Doutorado) - “Proposta de um Modelo Computacional para Representaçâo de Sinais em uma Arquitetura de Serviços HCI-SL para Línguas de Sinais”
  • Fabricio Schiavon Kolberg (lattes) (Doutorado) - “Circular Arc Bigraphs and their Helly subclass”
  • Leandro Miranda Zatesko (lattes) (Doutorado) - “Novel Procedures for Graph Edge-colouring”
  • Renato Silva de Melo (lattes) (Doutorado) - “Maximização de Influência”
  • Santiago Viertel (lattes) (Doutorado) - “Small World Models and a Compact Routing Scheme”
  • Alane Marie de Lima (Mestrado) - “Algoritmos exatos para o problema da coloração de grafos”
  • Alessandro Rodrigues Zamboni (Mestrado) - “Uma Proposta de Sistema de Software para Auxílio na Geracão de Transformacões do Formalismo BAV para Integracão de Bancos de Dados”
  • Alexandre Züge (Mestrado) - “Solução Exata do Problema da Clique Máxima”
  • Alissar Moussa (lattes) (Mestrado) - “Extração e Seleção de Atributos em Streams de Dados de Ataques Zero-Day”
  • Amilcar Fernandes Costa de Abreu (lattes) (Mestrado) - “Indexação de Imagens de Profundidade Baseada em Conteúdo”
  • Bruna Vello Colnago (lattes) (Mestrado) - “Uma proposta para a formalização do problema de clusterização em grafos”
  • Camile Frazão Bordini (Mestrado) - “Técnicas Probabilísticas Aplicadas em Algoritmos de Aproximação”
  • Cleverson Sebastião dos Anjos (Mestrado) - “Análise Experimental de Algoritmos”
  • Cloris Ragna Ferreira (Mestrado) - “Uso de Grafos em Recuperação de Imagem por Conteúdo”
  • Edgar de Oliveira Cabral Filho (Mestrado) - “Cobertura por Vértices Mínima em Grafos Lei de Potência”
  • Edmilson Pereira da Cruz (lattes) (Mestrado) - “Grafos Biclique de Grafos de Bi-Intervalos e Bi-Arco-Circulares”
  • Fabricio Schiavon Kolberg (Mestrado) - “Grafos Bi-Arco-Circulares”
  • Fernando Claudecir Erd (lattes) (Mestrado) - “Bloqueio de maximização de influência em redes complexas”
  • Flávio Henrique da Silva (lattes) (Mestrado)
  • Gabriel Augusto Gonçalves Sobral (lattes) (Mestrado) - “Biclique-aresta coloração por listas”
  • Geoffrey Alberto Vitorio Martins (Mestrado) - “Manutenção de Caminhos Mínimos em Grafos Dinâmicos”
  • Georgea Danielewicz (Mestrado) - “Análise de uma Métrica Alternativa para Predição de Laços Sociais em Grafos Lei de Potência”
  • Guilherme Bastos de Oliveira (lattes) (Mestrado) - “Geometria Computacional”
  • Gustavo Gasparetto Higuchi (lattes) (Mestrado)
  • Helds de Medeiros Souza (lattes) (Mestrado) - “Classificação de Lançamentos Contábeis”
  • Jonilso Novacoski (Mestrado) - “Uma Introdução à Complexidade Computacional Parametrizada”
  • João Pedro Winckler Bernardi (lattes) (Mestrado) - “Coloração de arestas”
  • Leandro Miranda Zatesko (Mestrado)
  • Lucas Ferreira Glir (lattes) (Mestrado)
  • Matheus Vinícius Correa (lattes) (Mestrado) - “Busca em Largura Lexicográfica e Algoritmos de Solução Exata para o Problema da Clique Máxima”
  • Murilo Vicente Gonçalves da Silva (lattes) (Mestrado) - “Teste de Perfeição de Grafos”
  • Nicollas Mocelin Sdroievski (lattes) (Mestrado) - “Conhecimento Zero Estatístico e Reduções Eficientes para o Problema MKTP”
  • Pedro Ribeiro de Andrade Neto (lattes) (Mestrado) - “Reconhecimento de Padrões em Subdivisões Planares”
  • Rafael Cubas (Mestrado) - “Algoritmos Exatos para Coloração de Grafos”
  • Regina de Cássia Nandi (Mestrado) - “Isomorfismo de Grafos Aplicado à Comparação de Impressões Digitais”
  • Renato Silva de Melo (Mestrado) - “Maximização de Influência em Grafos Lei de Potência”
  • Santiago Viertel (Mestrado) - “Programação Matemática e Imersões Métricas para Aproximações em Problemas de Corte.”
  • Sílvio Luiz Bragatto Boss (Mestrado)
  • Thiago Henrique de Araújo Lemos (Mestrado) - “Comparação de invariantes da teoria dos grafos na previsão da estabilidade de fulerenos”
  • Vitor Hugo Santos Alencar (Mestrado) - “análise experimental de algoritmos para o problema de raízes quadradas em grafos”
  • Vitor Hugo Santos Alencar (lattes) (Mestrado)
  • Viviane Frida Belli (lattes) (Mestrado)
  • Vytor dos Santos Bezerra Calixto (lattes) (Mestrado)
  • Zeno Stivanin (Mestrado) - “Traçado Automático de Hipergrafos Direcionados”
  • Alvaro Ronaldo de Souza Dziadzio (lattes) (IC)
  • Bruno Henrique Labres (lattes) (IC) - “Características Topológicas de Redes do Mundo Real”
  • Caio Renato Bedulli do Carmo (IC)
  • Cássio Jandir Pagnoncelli (IC) - “Grafos Extremais Quanto ao Número de Cliques”
  • Eduardo Augusto Ribas (IC) - “Clustering em Grafos”
  • Eduardo Stefanel Paludo (lattes) (IC)
  • Ermelindo Paulo Breviglieri Schultz (lattes) (IC) - “computação e construções de régua e compasso”
  • Fabricio Schiavon Kolberg (IC) - “algoritmos para o problema de isomorfismo de grafos”
  • Francieli Triches (IC) - GeoGebra
  • Gabriel Augusto Gonçalves Sobral (lattes) (IC) - “Algoritmos Branch & Bound”
  • Guilherme Carbonari Boneti (lattes) (IC)
  • Jedian Marcos Brambilla (lattes) (IC) - “Combinatória Analítica”
  • João Denis Rodrigues Cabral (IC) - “divulgação de computação simbólica com sagemath”
  • Letícia Pasdiora (IC) - “divulgação de computação simbólica com sagemath”
  • Nico Iancoski Guimarães Ramos (lattes) (IC)
  • Odair Mario Ditkun Junior (lattes) (IC) - “clique máximo e biologia computacional”
  • Paulo Guilherme Inça (IC) - “estimativa de tempo de execução para algoritmos de branch and bound”
  • Rafael Veiga Pocai (IC) - “combinatória analítica”
  • Raphael Henrique Ribas (IC)
  • Vinícius Mioto (lattes) (IC)
  • Adolfo Sabino (TCC) - “Implementação de Framework de Modelos Epidemiológicos Estocásticos Compartimentais sobre Grafos”
  • Adriano Guareschi Peña (TCC) - “integração sage/python/c/c++”
  • Adriel Kotviski (TCC) - “Introdução à Teoria dos Jogos”
  • Alessandro Azevedo (TCC) - “Hipergrafos Direcionados e Computação Paralela”
  • Ander Conselvan de Oliveira (TCC)
  • André Coradin Gulin (TCC) - “Introdução ao Algoritmo de Lemke-Howson para Cálculo de Equilíbrio de Nash”
  • André Medeiros Mendes (TCC) - “Redutibilidade em Hipergrafos Direcionados”
  • André Mendes (TCC) - “Qualidade e Comparação de Malhas Triangulares”
  • Aramis Stach Haiduski Fernandes (TCC) - “Um algoritmo parametrizado para calcular o Conjunto Independente de peso Máximo de um Grafo”
  • Arthur Pechebea da Costa (TCC) - “Evolução do Cinema Brasileiro: Uma Análise de Gênero Contada por Grafos”
  • Bruno Henrique Meyer (lattes) (TCC) - “ESTUDO DO ALGORITMO DE APRENDIZADO DE MÁQUINA NCHC: APLICAÇÕES EM CLASSIFICAÇÃO DE EXPRESSÃO GÊNICA”
  • Carlos Eduardo Meira Tavares (TCC)
  • Cassiano Yudi Nishiguchi (lattes) (TCC)
  • Claudinei de Jesus Braine (TCC) - “Biblioteca de Grafos”
  • Cássio Jandir Pagnoncelli (TCC) - “Somas hipergeométricas definidas e indefinidas”
  • Dante da Silva Aleo (TCC)
  • Edmilson Pereira da Cruz (TCC) - “Árvores Geradoras Independentes”
  • Fabricio Schiavon Kolberg (TCC) - “Uma Introdução à Lógica Aplicada à Programação”
  • Felipe Cys Laskoski (TCC) - “Estrutura para minimização do desvio padrão do fluxo de veículos de uma região”
  • Felipe Velloso Alves (TCC)
  • Felipe do Nascimento (TCC) - “Evolução do Cinema Brasileiro: Uma Análise de Gênero Contada por Grafos”
  • Felix Yowtang Liu (TCC) - “teste de propriedades”
  • Fernando Claudecir Erd (lattes) (TCC)
  • Fernando Druszcz (TCC)
  • Fernando Rodrigo Bilinski (TCC) - “integração de rotinas C em programas Python/Sage”
  • Gabriel Augusto Gonçalves Sobral (lattes) (TCC) - “Aplicando o Problema do Caixeiro Viajante num Método de Construção de Árvores Filogenéticas”
  • Gabriel J. Amarante Netto (TCC) - “Redutibilidade em Hipergrafos Direcionados”
  • Gabriela Yukari Kimura (lattes) (TCC)
  • Gabriele Rodrigues Brancalhão (lattes) (TCC) - “INSATISFAZIBILIDADE MINIMAL: COMPLEXIDADE E ALGORITMOS”
  • Giovane Marcelo dos Santos (lattes) (TCC)
  • Guilherme Bastos de Oliveira (lattes) (TCC) - “aceleração de branch & bound para clique máxima”
  • Guilherme Gomes dos Santos (TCC) - “Coligações Partidárias no Brasil: Uma Análise em Grafos”
  • Gustavo Aschwanden Soviersovski (lattes) (TCC) - “INSATISFAZIBILIDADE MINIMAL: COMPLEXIDADE E ALGORITMOS”
  • Gustavo Gasparetto Higuchi (TCC) - “Refinamentos de um Limitante de Algoritmos “”Branch and Bound”” Para o Problema da Clique Máxima”
  • Hugo Paulino Bonfim Takiuchi (TCC) - “Compressão e Descompressão para Arquivos de Áudio WAV”
  • Issam Ibrahim (TCC) - “Hipergrafos Direcionados e Computação Paralela”
  • Jedian Marcos Brambilla (lattes) (TCC) - “classes limítrofes de grafos”
  • João Furtado Resende (TCC) - “Aplicação de conceitos e técnicas de Pesquisa Operacional e Otimização Combinatória para a resolução de um problema NP-difícil”
  • Lucas Akihiko Osato Ikeda (TCC) - “Grafos Biclique em Grafos de Bi-intervalos”
  • Lucas Benvegnú Zambon (TCC) - “Web Graphs”
  • Lucas Ferreira Glir (lattes) (TCC) - “Quadrado do grafo linha de bipartidos de permutação”
  • Luis Guilherme Marinho dos Santos Almeida (TCC)
  • Manuela Lais Puhl (TCC) - “Grafos e Cliques na Modelagem de Problemas”
  • Marco Antonio Pio Mendes (TCC) - “Alianças em Grafos”
  • Marcus Dudeque (TCC)
  • Mateus Ravedutti Lúcio Machado (lattes) (TCC) - “Algoritmos parametrizados para o problema de Cobertura por Vértices em Grafos”
  • Mateus Veshagem Nascimento (TCC) - “Áudio - sua Forma Digital - Representação e Compactação: Fundamentos e Propostas”
  • Matheus Agio Nerone (TCC) - “Sistema de Recomendação de Matrículas Baseado em Técnicas de Aprendizado de Máquina”
  • Matheus Dall Rosa (TCC) - “Implementações do Algoritmo de Fortune para Variantes do Diagrama de Voronoi”
  • Matheus de Moraes Cavazotti (TCC)
  • Michele Macedo Weber (TCC) - “Teoria da Computação: Uma Nova Perspectiva”
  • Paulo Baran (TCC) - “FileDB - Leitura e Manipulação de Arquivos XLSX através de Linguagem SQL”
  • Paulo Guilherme Inça (TCC) - “estimativa de tempo de execução para algoritmos de branch and bound”
  • Rafael Capaci Pereira (TCC) - “Coligações Partidárias no Brasil: Uma Análise em Grafos”
  • Rafael Veiga Pocai (TCC) - “Classes Combinatórias - Funções Geradoras e Aproximações Assintóticas”
  • Rodrigo Camargo dos Reis (lattes) (TCC) - “estimativa de tempo de execução para algoritmos de branch and bound”
  • Rodrigo Gryzinski (TCC) - criptomoedas
  • Sérgio Samuel Furlaneto (TCC) - “Web Graphs”
  • Thiago Leucz Astrizi (TCC) - “Algoritmos de Criptografia RSA”
  • Tiago Vignatti (TCC) - “Sistemas de Prova Interativa com Conhecimento Zero”
  • Victor Luis Perszel (lattes) (TCC)
  • Victor Mocelin (TCC) - “Sistema de Recomendação de Matrículas Baseado em Técnicas de Aprendizado de Máquina”
  • Vinícius Máximo da Silva (TCC) - “Biblioteca de Geometria Computacional”
  • William Sussumo Komura (TCC) - “Estudo sobre a Estrutura de Árvore Van Emde Boas”

Projetos de pesquisa

  • Teoria algorítmica de grafos
  • Este projeto de pesquisa tem como objetivo investigar problemas computacionais envolvendo grafos. A ênfase principal deste projeto (embora este projeto não se limite apenas a isto) são algoritmos exatos para problemas computacionalmente difíceis como o problema da clique máxima, o problema da cobertura mínima e os problemas de coloração de vértices e de arestas.
  • Teoria estrutural de grafos
  • Este projeto de pesquisa tem como objetivo investigar propriedades estruturais de grafos e de classes de grafos. A ênfase principal (embora este projeto não se limite a isso) são problemas envolvendo biclique, classes de grafos definidas por subgrafos induzidos proibidos e aplicação de teoremas de decomposição a classes de grafos.
  • Otimização e aproximação
  • Este projeto tem como objetivo estudar problemas cujo objetivo é maximizar ou minimizar algum recurso. O grupo de pesquisa tem interesse uma série de tópicos de pesquisa dentro desta área, incluindo algoritmos de aproximação, inaproximabilidade de problemas, análise suavizada, métodos de pontos interiores e programação linear inteira.
  • Grafos aleatórios e redes complexas
  • Com a ascensão da Web, a computação teve que lidar com um mundo em que as restrições dos sistemas não eram apenas tecnológicas, mas também humanas, impostas pelos complexos efeitos que pessoas criam quando coletivamente usam a Web para comunicação, auto-expressão e criação de conhecimento. As ferramentas ideais para essas situações são a teoria dos grafos e probabilidade. Alguns tópicos de interesse do grupo nesta área são Grafos Lei de Potência, Grafos de Mundo Pequeno, Disseminação de Informação, Transições de Fase e Redes de Atributos.
  • Geometria computacional
  • Este projeto de pesquisa tem como objetivo investigar algoritmos para problemas geométricos em computação tanto do ponto de vista teórico (análise de algoritmos, estruturas de dados, etc), quanto do ponto de vista aplicado (aplicação de algoritmos e teoria de geometria computacional em problemas práticos).
  • Teoria de complexidade computacional
  • Além das famosas classes P e NP, uma série de outras classes de complexidade são conhecidas na literatura e também estão intimamente ligadas ao famoso problema P vs NP. Neste projeto estamos interessados em investigar várias destas classes. Os tópicos de pesquisa de interesse neste projeto incluem Computação Aleatorizada e Interativa (classes PP, BPP, SZK etc,) Provas de Conhecimento Zero, conexões entre Complexidade Computacional e Teoria Algorítmica da Informação (Complexidade de Kolmogorov, Complexidade KT), Complexidade Parametrizada e Classes de Computação Quântica (BQP, QMA, etc).
  • Fundamentos de ciência de dados e aprendizado computacional
  • Cada vez mais os pesquisadores estão envolvidos no uso de computadores para entender e extrair informações úteis de dados maciços. Os desafios estão relacionados à grande quantidade de informação, fluxo contínuo de informação, além de como usar tais informações para aprendizado de regras, buscando classes de funções que são aprendíveis em tempo polinomial. Neste contexto, as técnicas empregadas têm ênfase na probabilidade, estatística e métodos numéricos. Entre os tópicos de interesse do grupo estão incluídos Algoritmos Sub-lineares, Análise de Algoritmos de Aprendizado, Algoritmos Espectrais, Data Streams, Complexidade de Amostragem e Redução de Dimensionalidade.
  • Computação quântica
  • Este projeto de pesquisa tem como objetivo investigar problemas em computação quântica com especial ênfase em algoritmos quânticos para problemas concretos e classes de complexidade computacional quânticas e como estas classes se relacionam com classes de complexidade computacional clássicas.