MC558 - Lab L1
Diretrizes
- Objetivo: Dados dois grafos, dizer se eles são ou
não isomórficos.
- Submissão: Devem ser enviados os seguintes arquivos:
- Arquivo JSP: a ser desenvolvido durante a aula de
laboratório do dia 22/08. Deve ser enviado para o e-mail
divulgado na sala, com a tag "[MC558] Lab01", até quarta
(22/08);
- complexidade.pdf: arquivo que descreve a
complexidade do algoritmo implementado. Neste arquivo também
devem estar as diferenças entre o JSP e a implementação (se
houver). Deve ser enviado até quarta que vem (29/08), como
resposta ao e-mail em que foi enviado o JSP;
- Implementação: conjunto de arquivos *.cpp e *.h, além
de um makefile, que devem ser submetidos via servidor (página e
login ainda serão divulgados). A submissão deve ser feita até
quarta que vem (29/08);
- Critérios de Avaliação: A nota da atividade será
a soma das notas obtidas em cada um dos critérios abaixo:
- JSP: clareza e corretude. Nota entre 0-3.
- Corretude da Implementação: número de casos de teste
executados corretamente. Nota entre 0-3.
- Running time: será feita uma lista em ordem
decrescente de tempo de execução. Nota entre 0-2.
- Complexidade do algoritmo: verificar se a análise de
complexidade do algoritmo está correta (arquivo
complexidade.pdf). Nota entre 0-2.
- Sugestão: No livro do West, Corolário 8.5.26,
existe um algoritmo para testar o isomorfismo entre um par de
grafos. Ele executa em tempo quadrático e funciona para quase todos
pares de grafos, supondo que eles sejam aleatórios. Entretanto
existe uma condição para ele ser usado; esta condição pode ser
testada previamente e, no caso de valer, este algoritmo poderia ser
usado como uma estratégia mais rápida para resolver o problema.
Notas
|
Pesos: |
3 |
2 |
2 |
3 |
|
|
|
JSP |
Complexidade |
Running Time |
Corretude |
Nota Final |
| 83413 |
Davi Costa Clemente |
7 |
8 |
10 |
9.5 |
8.55 |
| 101977 |
Davi Stuart Zilli |
6 |
10 |
8.5 |
9.5 |
8.35 |
| 102113 |
Eric Carvalho Oakley |
6 |
7 |
4.2 |
4 |
5.24 |
| 108171 |
Fabiani de Souza |
8 |
9 |
4 |
5.5 |
6.65 |
| 81391 |
Fernando L. de Arruda |
6.5 |
10 |
9.7 |
9.5 |
8.74 |
| 104941 |
Flávia Pisani |
9 |
10 |
10 |
10 |
9.70 |
| 83681 |
Jonathan F. de Castro |
0 |
0 |
0 |
0 |
0.00 |
| 103147 |
Lucas G. Farris |
6.5 |
6 |
9.1 |
9.5 |
7.82 |
| 108227 |
Maurício Bertanha |
3 |
10 |
8.1 |
9.5 |
7.37 |
| 106228 |
Rafael Timbó Matos |
3 |
8 |
9.5 |
6 |
6.20 |
| 103958 |
Renato T. Lochetti |
6 |
10 |
7.5 |
9.5 |
8.15 |
| 104005 |
Rodrigo E. Gonçalves |
2 |
8 |
10 |
9.5 |
7.05 |
| 108254 |
Thiago A. Rodrigues |
8.5 |
0 |
5.5 |
2.8 |
4.49 |
| 106991 |
Waldir R. de Almeida |
10 |
10 |
5.5 |
2.5 |
6.85 |
MC558 Home
© 2012 João Meidanis