Este trabalho é opcional. A nota de "trabalhos de implementação" será a maior nota dentre as dos trabalhos entregues.
A decomposição de um grafo em blocos é um pré-processamento importante quando um problema computacional sobre um grafo pode ser reduzido ao mesmo problema aplicado a cada um de seus blocos, dentro do conhecido esquema de divisão e conquista.
São exemplos disso os problemas de decidir a planaridade de um grafo, colorir seus vértices ou colorir suas arestas.
A divisão e conquista, nestes casos, consiste em decompor o grafo em blocos e aplicar separadamente (em paralelo, se for o caso) um algoritmo para o problema a cada um dos blocos.
Um caso de particular interesse acontece na situação em que se tem um algoritmo (exponencial) que toma tempo O(2n) para o problema computacional em questão. Se o grafo de entrada tem n vértices e seu maior bloco tem k vértices, então a estratégia descrita acima resolve o problema em tempo O(nc) onde c = k ⁄ logn. Noutras palavras, o algoritmo exponencial computa instâncias que podem ser decompostas assim em tempo polinomial.
Este trabalho consiste na implementação de uma função que recebe um grafo e devolve uma análise dos tamanhos de seus blocos, fornecendo assim uma ideia do quão promissora é esta estratégia de divisão e conquista.
A especificação do trabalho está em trabalho-2.tar.gz, onde você vai encontrar os seguintes arquivos.
| trabalho-2/blocos.h: | |
|---|---|
| a especificação do que deve ser implementado; | |
| trabalho-2/{teste.c,makefile}: | |
| como no primeiro trabalho | |
O trabalho deve ser entregue sob a forma de um arquivo de nome fulano-sicrano.tar.gz, como no primeiro trabalho
O arquivo fulano-sicrano.tar.gz, uma vez expandido, deve conter (somente) os seguintes arquivos.
| fulano-sicrano/blocos.c: | |
|---|---|
| a implementação do especificado em trabalho-2/blocos.h. | |
| fulano-sicrano/readme.txt: | |
| como no primeiro trabalho | |
O arquivo fulano-sicrano.tar.gz deve ser entregue como anexo de mensagem enviada para m.v.g.dasilva@gmail.com (Turma BCC1) ou renato.carmo.rc@gmail.com (Turma BCC2). O "Subject:" desta mensagem deve ser "Entrega do trabalho 2".
O prazo para a entrega é às 23h59min do dia 4 de agosto.
Serão avaliados a correção e a aderência à especificação como no primeiro trabalho. Não haverá, entretanto, avaliação por tempo de execução com formação de "ranking".
Veja as Perguntas Frequentes do primeiro trabalho
Tenho outra pergunta/dúvida a respeito do trabalho que não está respondida nas `Perguntas Frequentes do primeiro trabalho <trabalho-1.html#faq>`.