Ferramentas de Utilizador
inf05504:2011-2-trabalhos
Diferenças
Esta página mostra as diferenças entre as duas revisões da página.
| Ambos os lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
|
inf05504:2011-2-trabalhos [2011/09/05 15:56] marcus [Trabalho 3 (Fluxo s-t máximo)] |
inf05504:2011-2-trabalhos [2011/12/13 23:39] (Actual) marcus [Entregas] |
||
|---|---|---|---|
| Linha 6: | Linha 6: | ||
| ==== Entregas ==== | ==== Entregas ==== | ||
| - | ^ No. ^ T1 ^ T2 ^ | + | |
| - | | 152985 | - | | | + | Atualizado: 13/12/2011 |
| - | | 159011 | - | | | + | |
| - | | 159098 | R | | | + | ^ No. ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ |
| - | | 171359 | R | | | + | | 152985 | - | - | - | - | - | |
| - | | 172072 | R | | | + | | 159011 | - | - | - | - | - | |
| - | | 173256 | - | | | + | | 159098 | P | P | P | P | R | |
| - | | 173361 | R | | | + | | 171359 | P | P | P | P | R | |
| - | | 180658 | R | | | + | | 172072 | P | P | P | P | - | |
| - | | 180689 | - | | | + | | 173256 | P | P | P | - | - | |
| + | | 173361 | P | P | P | P | - | | ||
| + | | 180658 | P | P | P | P | - | | ||
| + | | 180689 | P | P | - | - | - | | ||
| R = recebido | R = recebido | ||
| + | P = avaliado e publicado | ||
| Linha 123: | Linha 127: | ||
| === Objetivos === | === Objetivos === | ||
| * Implementar um heap de Fibonacci e verificar a complexidade das operações experimentalmente. | * Implementar um heap de Fibonacci e verificar a complexidade das operações experimentalmente. | ||
| - | * Verificar a complexidade do algoritmo de Dijkstra usando um heap binomial experimentalmente. | + | * Verificar a complexidade do algoritmo de Dijkstra usando um heap de Fibonacci experimentalmente. |
| * Comparar as complexidades experimentais dos heaps binários e Fibonacci. | * Comparar as complexidades experimentais dos heaps binários e Fibonacci. | ||
| * Comparar as complexidades experimentais do algoritmo de Dijkstra com os dois heaps. | * Comparar as complexidades experimentais do algoritmo de Dijkstra com os dois heaps. | ||
| Linha 185: | Linha 189: | ||
| === Convenções === | === Convenções === | ||
| - | * As implementações do algoritmo devem aceitar uam instância no formato {{http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm|DIMACS}} na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout). | + | * As implementações do algoritmo devem aceitar uma instância no formato {{http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm|DIMACS}} na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout). |
| === Verificação === | === Verificação === | ||
| Linha 236: | Linha 240: | ||
| // (1) determine maximum flow | // (1) determine maximum flow | ||
| - | cout << edmunds_karp_max_flow(g, s, t, | + | cout << edmonds_karp_max_flow(g, s, t, |
| capacity_map(get(&EdgeInformation::edge_capacity,g)). | capacity_map(get(&EdgeInformation::edge_capacity,g)). | ||
| residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)). | residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)). | ||
| Linha 250: | Linha 254: | ||
| === Objetivos === | === Objetivos === | ||
| - | * Implementar um algoritmo de segmentção de imagens como vista em aula. | + | * Implementar um algoritmo de segmentação de imagens como vista em aula. |
| * Usar a própria implementação do fluxo máximo na solução. | * Usar a própria implementação do fluxo máximo na solução. | ||
| * Segmentar uma imagem em pele/não-pele com pesos de separação diferentes. | * Segmentar uma imagem em pele/não-pele com pesos de separação diferentes. | ||
| Linha 365: | Linha 369: | ||
| + | ==== Trabalho 5 (Sequenciamento de tarefas) ==== | ||
| + | |||
| + | Entrega: 12/12/2011 | ||
| + | |||
| + | === Objetivos === | ||
| + | * Resolver o problema P||C_max com algoritmos de aproximação. | ||
| + | * Implementar o sequenciamento em lista (2-aproximação) | ||
| + | * Implementar o sequenciamento em lista em ordem não-crescente (4/3-aproximação) | ||
| + | * Implementar o esquema de aproximação em tempo polinomial | ||
| + | * Comparar a qualidade dos algoritmos com a solução ótima | ||
| + | * Compara o tempo de execução dos algoritmos com os limites teóricos e entre si. | ||
| + | |||
| + | === Casos de teste === | ||
| + | * Disponíveis em [[http://www.or.deis.unibo.it/research_pages/ORinstances/PCmax.htm]] | ||
| + | |||
| + | === Convenções === | ||
| + | * As implementações do algoritmo devem aceitar uma instância na entrada padrão (stdin) e o tempo de término obtido na saída padrão (stdout). | ||
| + | * Para o esquema de aproximação, o primeiro argumento na linha de comando deve ser o parâmetro de qualidade epsilon. | ||
inf05504/2011-2-trabalhos.1315248963.txt.gz · Esta página foi modificada pela última vez em: 2011/09/05 15:56 por marcus
Ferramentas de Página
Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
