Objectivos para o Teste Prático 2 (9 de Junho)
Aqui fica uma lista de objectivos para o 2º teste prático de DAA, que incidirá sobre os capítulos 6 a 8. Poderá implementar as soluções em C, C++ ou Java.
Formato:
- Data: 9 de Junho de 2022 (quinta)
- Horário: 18:15
- Duração: 2h
- Local: laboratórios do DCC/FCUP
- Valorização: 2.5 valores (como explicado em avaliação)
Informações para o teste:
Podem (pré)submeter um ficheiro com código (e qualquer texto que queiram), ao qual terão acesso durante o teste - ir ao concurso "2º Teste Prático - Pré-Submissão de Código" e submeter um único ficheiro; se submeterem mais do que uma vez, apenas a última submissão estará disponível no dia do teste prático; o ficheiro (.txt) pode conter o que quiserem até um máximo de 500KB (até 23:59 de quarta, dia 8 de Junho).
As pontuações são parciais, significando que cada problema terá vários testes, cada um valendo um determinado número de pontos. Para cada teste pontuável existirá um teste não pontuável de características similares disponível para visualização quando falharem. Os testes pontuáveis são secretos. A sua pontuação é determinada pelos testes em que o seu programa acertar. Para terem 100% num problema será necessário terem uma solução eficiente. Uma solução com "força bruta" poderá portanto dar menos do que a pontuação ótima.
Os enunciados estão "despidos" da uma história mais gira para irem directos ao que é pedido de modo a que possam usar as duas horas de forma adequada. Para alguns dos problemas poderão ser dadas dicas sobre como resolver.
Terão acesso a documentação das vossa linguagens e às classes FastScanner e FastPrint, no Java.
O teste prático terá os seguintes 3+1 problemas para serem resolvidos em 2h (o último problema é para ter nota acima de 100%):
Problema A (34% da nota)
Saber usar pesquisa em profundidade (DFS) para percorrer um grafo
Será pedido algo como:
- Imprimir a ordem em que os nós são visitados com DFS
- Calcular quantidade e/ou tamanho/peso de componentes conexos
- Saber verificar se um grafo é bipartido
- Saber calcular uma ordenação topológica
Problemas exemplo:
- [DAA 025] Redes de circuitos electrónicos
- [DAA 026] Contagem de células
- [DAA 027] Grafos bipartidos
- [DAA 029] Ordem rara (o grafo seria dado mais diretamente se este fosse um problema do teste)
Problema B (33% da nota)
Saber usar pesquisa em largura (BFS) para calcular distâncias num grafo não pesado
Será pedido algo como:
- Diâmetro ou raio de um grafo
- Nó mais perto/longe de um dado conjunto de nós
- Calcular nós a uma dada distância
Problemas exemplo:
- [DAA 030] Análise de uma rede biológica
- [DAA 031] Nuvem de cinzas
(o problema do teste será potencialmente mais fácil, mas o 031 é um bom problema de treino)
Para este problema será obrigatório usar BFS (não poderá por exemplo usar Dijkstra)
Problema C (33% da nota)
Saber usar o algoritmo de Dijkstra para calcular distâncias num grafo pesado
Será pedido algo como:
- Nó mais perto/longe de um dado conjunto de nós
- Calcular nós a uma dada distância
- Caminho mínimo entre dois nós
Para este problema é garantido que os pesos não são negativos (sendo que por isso não precisará de um Bellman-Ford). Se optar por algo como um Floyd-Warshall (ou Bellman-Ford) poderá não ter a cotação completa. Para além disso, para ter 100% será necessário ter uma implementação eficiente em \(\mathcal{O}(|E| \log |V|)\) . Uma implementação quadrática dará apenas pontuação parcial.
Problemas exemplo: - [DAA 033] Viagem para as aulas - [DAA 035] Ligações aéreas (note que com Floyd-Warshall num problema SSSP não terá cotação completa)
Problema D (20% da nota)
Tema Aberto
- Este problema pode dar 20% adicionais (0.5 valores), ou seja, é possível ter nota acima dos 2.5 valores (por exemplo para compensar algo que corra menos bem noutro componente da avaliação)
- É um problema que pode ser um pouco mais complicado que os anteriores, sem dicas dadas no enunciado, e que só deverá ser tentado depois de resolvidos os outros três
- Pode usar qualquer tema/algoritmo dos capítulos 6 a 10, bem como ser necessário combinar com algo dos capítulos anteriores (ex: programação dinâmica).
)