Abaixo, uma relação dos trabalhos de alunos concluídos sob minha orientação.
Algoritmos exatos para o problema da Clique Máxima (Alexandre P. Züge, doutorado, PPGInf - UFPR)
Os melhores algoritmos com desempenho de pior caso conhecido para o problema da Clique Máxima tem custo de tempo exponencial. Porém, resultados experimentais encontrados na literatura indicam que instâncias de tamanho considerável podem ser resolvidas em pouco tempo usando algoritmos de Branch and Bound. Com isso, observa-se uma distância entre os melhores resultados analíticos e os melhores resultados experimentais. Tal fenômeno não é bem compreendido e é a motivação deste trabalho. Até o momento foram estudados e implementados diversos algoritmos de bnb, obtidos resultados analíticos para algumas famílias de instâncias e estabelecida uma metodologia para comparação experimental de algoritmos.
Algoritmos exatos para o problema da Coloração de Grafos (Alane M. de Lima, mestrado, PPGInf - UFPR)
Construções de Régua e Compasso modelo de Computação (Ermelindo P. B. Schultz, Iniciação Científica, BCC - UFPR)
Algoritmos para Identidades de Somas Hipergeométricas (João D. R. Cabral e Letícia Pasdiora Iniciação Científica, |pet| - BCC - UFPR)
Estimativa de Tempo de Execução de Algoritmos de Branch and Bound (Paulo G. Inça, Iniciação Científica, BCC - UFPR)
Grafos Bi-Arco Circulares (Fabrício S. Kolberg, mestrado 2016, PPGInf - UFPR, em co-orientação com Marina Groshaus)
Grafos bi-arco-circulares são grafos formados por duas famílias de arcos sobre um círculo, com um vértice correspondente a cada arco, e arestas ocorrendo entre vértices se seus arcos correspondentes intersectam e estão em conjuntos diferentes.
Um dos objetivos do trabalho é a tentativa de obter uma nova caracterização para a classe que potencialmente permita a descoberta de um algoritmo eficiente de reconhecimento e, em particular, uma caracterização por subgrafos induzidos proibidos. Também estão sendo estudados algoritmos de reconhecimento de outras classes que possam ser adaptados para o reconhecimento da classe de grafos bi-arco-circulares. Além disso, estão sendo estudados resultados da bibliografia cujas provas podem precisar ser revisadas ou passadas a limpo.
Também dentre os objetivos da dissertação está o estudo (e caracterização) de algumas subclasses dos grafos bi-arco-circulares, como, por exemplo, a subclasse própria (sem arcos contidos) e Helly (com alguma definição análoga à de famílias Helly, mas para duas famílias de arcos sobre o mesmo círculo).
Melhoria de Desempenho de Algoritmos para o Problema da Clique Máxima via Satisfatibilidade (Gustavo G. Higuchi, Trabalho de Graduação 2015, BCC - UFPR)
Estudo de uma heurística utilizando a coloração para formar uma instância MaxSAT, que ao resolver essa instância, nos devolve um limite superior mais enxuto para o bound. Também será apresentado uma recodificação que elimina o MaxSAT e apresenta a solução apenas em termos teóricos de grafos, e então comparado com outras implementações feitas sob um framework unificado[2] e testado sob as mesmas condições.
Análise Experimental de Algoritmos (Cleverson S. dos Anjos, mestrado 2015, PPGInf - UFPR)
Aplicamos os conceitos de análise experimental de algoritmos, de acordo com o livro "A Guide to Experimental Algorithmics", da autora Catherine C. McGeogh de forma a analisar experimentalmente o comportamento de dez algoritmos exatos para o problema da clique máxima. O fazemos através da definição de um processo experimental, estabelecimento de um ambiente de testes estruturado, aplicação de um modelo de e apresentação dos dados sob diferentes perspectivas. Enquanto realizamos uma comparação entre tais algoritmos buscamos também reportar nossa experiência e algumas das ideias e metodologia de análise experimental
Aplicações do Problema da Clique Máxima (Manuela Laís Puhl, Trabalho de Graduação 2014, Bacharelado em Matemática Industrial)
O Problema da Clique é um problema fundamental em ciência da computação com diversas aplicações. Foram escolhidas cinco que serão abordadas no decorrer do trabalho: teias alimentares, modularidade de imagens, geometria da visão, classificação estrutural de proteínas e ligações proteína-proteína.
Uma Introdução à Complexidade Computacional Parametrizada (Jonilso Vianei Novacoski, mestrado 2013, PPGInf - UFPR)
A Complexidade Parametrizada é uma maneira de analisar a complexidade computacional de um problema computacional. Nesta dissertação damos uma Introdução à Complexidade Computacional Parametrizada com atenção aos problemas computacionais em grafos, concluindo com uma aplicação ao Problema da Clique Máxima.
Classes Combinatórias, Funções Geradoras e Aproximações Assintóticas (Rafael Veiga Pocai, Iniciação Científica e Trabalho de Graduação 2013, BCC - UFPR)
Uma Introdução à Lógica Aplicada à Programação (Fabrício S. Kolberg, Trabalho de Graduação 2013, BCC - UFPR)
Neste trabalho são descritos e demonstrados métodos de verificação formal e derivação de programas voltados para o paradigma imperativista, bem como uma revisão histórica do desenvolvimento dos métodos.
Apresentamos a base axiomática de corretude de programa introduzida por C. A. R. Hoare em 1969 e a aplicação da mesma sobre um programa exemplo. Em seguida, apresentamos a lógica das pré-condições mais fracas introduzida por E. W. Dijkstra em 1976, e o modo como a mesma pode ser estendida para ser usada como um método rudimentar de derivação de programas.
Somas Hipergeométricas Definidas e Indefinidas (Cássio Jandir Pagnoncelli, Iniciação Científica e Trabalho de Graduação 2013, BCC - UFPR)
Um algoritmo parametrizado para calcular o Conjunto Independente de peso Máximo de um Grafo (Aramis Stach Haiduski Fernandes, Trabalho de Graduação 2013, BCC - UFPR)
O problema do Isomorfismo de Grafos e o Algoritmo de McKay (Fabrício S. Kolberg, Iniciação ientífica 2012, BCC - UFPR)
Grafos Extremais Quanto ao Número de Cliques (Cássio Jandir Pagnoncelli, Iniciação Científica 2012, BCC - UFPR)
Solução Exata do Problema da Clique Máxima (Alexandre P. Züge, mestrado 2011, PPGInf - UFPR, finalista do XXV Concurso de Teses e Dissertações da Sociedade Brasileira de Computação)
O Problema da Clique Máxima é um problema fundamental com diversas aplicações. Vários algoritmos para sua solução são encontrados na literatura, grande parte deles empregando a técnica de Branch and Bound. Nesta dissertação é descrito um algoritmo genérico de Branch and Bound para solução exata do Problema da Clique Máxima, são revisados oito algoritmos disponíveis na literatura e cada um dos algoritmos é descrito como uma modificação do algoritmo genérico. Implementamos estes algoritmos e executamos experimentos cujos resultados são apresentados para comparação.
Correlação Vestibular x Desempenho Acadêmico (Viviane Neves Batata, Trabalho de Graduação 1994, BCC - UFPR)
Pascal Feito na Hora (Clevan Ricardo da Costa, Jorge Sucaria Leonel, , Trabalho de Graduação 1992, BCC - UFPR)