O objectivo deste exercício é ter algoritmos de diferentes complexidades para um mesmo problema e ir verificando a sua eficiência temporal. Começe por ler o enunciado do problema, disponível em [ED198] Um Jogo com Sequências (Volume 5).
Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios que pode submeter desta aula são:
Prazo de submissão: 29 de Maio (submeter no Mooshak de EDados)
É encorajado que vão falando com os docentes e outros colegas se tiverem dificuldades. No entanto, qualquer ajuda mais direta que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota.
Cada aula vale 10% da nota desta componente. Como existem 12 aulas com submissões, pode ter pontuação máxima mesmo sem ter feito tudo.
Para um problema contar tem acertar todos os testes (ou seja, ter accepted). Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Para ter 100% bastará sempre resolver os exercícios do guião principal.
Nesta aula iremos abordar conceitos de complexidade algorítmica. Será por isso conveniente ver o que foi falado nas teóricas:
[ver slides 25 a 34]
Para os pares de funções seguintes indique se é verdadeira ou falsa cada uma das seguintes afirmações: \(f(n) \in \mathcal{O}(g(n)\), \(f(n) = \Omega(g(n))\) e \(f(n) = \Theta(g(n))\). Explique sucintamente as suas opções.
| f(n) | g(n) | |
| a) | \(5n^2 - 100n + 34\) | \(2n^3 - 97\) |
| b) | \(54n + 100\) | \(6n - 24\) |
| c) | \(2^n\) | \(6n^2\) |
| d) | \(30\) | \(\log 30\) |
| e) | \(n \log n + n\) | \(n^2\) |
| f) | \(\sqrt{n}\) | \(\log n\) |
Para a implementação ArrayListIntSet (que usava um array como lista dos números do conjunto), qual a complexidade temporal de cada um dos seguintes métodos? (use notação \(\Theta\), para ser mais preciso - espreite o slide 40 para um exemplo nos métodos de listas):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| F | T | F | F | F | T | F | T | F | F |
[ver slides 35 a 37]
Imagine que tem um programa P implementado, que recebe como input n números. Ao experimentar executá-lo com testes aleatorizados, obteve os seguintes tempos de execução:
O objectivo deste exercício é ter algoritmos de diferentes complexidades para um mesmo problema e ir verificando a sua eficiência temporal. Começe por ler o enunciado do problema, disponível em [ED198] Um Jogo com Sequências (Volume 5).
Quais são todas as subsequências contíguas possíveis? Seja \(v[]\) um array contendo a sequência e começado na posição 0. As sequências possíveis são então todos os subarrays \(v[i \dots j]\) tal que \(0 \leq i \leq j \lt n\).
Uma solução exaustiva seria passar por todas estas subsequências e para cada uma delas calcular o valor da respectiva soma, escolhendo a melhor possível. Supondo que já temos a leitura feita para o array \(v[]\), uma maneira de fazer isto seria a indicada pelo código seguinte:
int maxSoFar = v[0]; // porque é esta uma boa escolha para a melhor soma inicial? for (int i=0; i<n; i++) // Todas as posicoes iniciais possiveis for (int j=i; j<n; j++) { // Todas as posicoes finais possiveis int sum = 0; for (int k=i; k<=j; k++) // Calcular soma entre posicoes i e j sum += v[k]; System.out.println("Soma entre " + i + " e " + j + " = " + sum); if (sum > maxSoFar) maxSoFar = sum; } System.out.println(maxSoFar);
Perceba o que faz o código de cima, implemente a parte restante (leitura) e submeta-o no Mooshak. Veja quantos pontos obtém e porque motivo o programa falha nos testes maiores (basta clicar no resultado da submissão para ter acesso a uma tabela detalha com os resultados).
Intuitivamente, olhando para o código anterior podemos notar que em cada soma estamos a repetir muitos cálculos. Quando passamos do cálculo de \(soma(v[i \ldots j])\) para \(soma(v[i \ldots j+1])\) não precisamos de voltar a recalcular tudo (começando novamente em \(i\), e basta-nos adicionar \(v[j+1]\) à soma anterior!
Dito de outro modo, \(soma(v[i \ldots j+1]) = soma(v[i \ldots j]) + v[j+1]\). Podemos utilizar isto para remover o terceiro ciclo com \(k\) que tínhamos na solução anterior.
Implemente esta nova solução e submeta-a. Quantos pontos passa a obter? Porque é que passa em mais testes?
Uma solução quadrática ainda não é suficiente e temos de a melhorar para tempo linear. Para isso vamos usar o algoritmo de Kadane.
Considere que \(best(i)\) representa o melhor subarray que termina na posição \(i\). Sabemos como "caso base" que \(best(0) = v[0]\) (é o único subarray possível que termina na primeira posição).
Se soubermos o valor de \(best(i)\), como calcular o valor de \(best(i+1)\)?
| \(i\) | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| \(v[i]\) | 4 | -2 | 1 | 5 |
| \(best(i)\) | 4 | 2 | 3 | 8 |
\(best(2) = 3\), obtido através do subarray \([4,-2,1]\).
\(best(3) = best(2) + v[3] = 3 + 5 = 8\), obtido através subarray \([4,-2,1,5]\) (estendeu-se o subarray anterior).
| \(i\) | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| \(v[i]\) | -5 | 2 | -3 | 4 |
| \(best(i)\) | -5 | 2 | -1 | 4 |
\(best(2) = -1\), obtido através do subarray \([2,-1]\).
\(best(3) = v[3] = 4\), obtido através subarray \([4]\) (não se estendeu o subarray anterior).
No final de tudo, o melhor subarray é o melhor valor de \(best(i)\) para um qualquer \(i\) (o melhor pode terminar em qualquer posição).
Para calcular isto basta-nos percorrer uma única vez o array \(v[]\) e em cada iteração calcular em tempo constante o valor da melhor soma a terminar na posição actual usando a melhor soma a terminar na posição anterior. A complexidade temporal fica portanto linear.
Implemente esta solução e submeta-a, verificando que já consegue passar todos os testes sem exceder o tempo limite.
O exercicio de desafio desta semana é um problema de uma fase de qualificação das Olimpíadas Nacionais de Informática, um concurso para alunos do secundário, e tem precisamente a ver com eficiência algorítmica. Deve tentar resolver o seguinte problema, que está disponível para submissão no Mooshak, no volume de Desafios:
O problema não é muito complicado (era da fase de qualificação), mas uma solução "bruta" não passa no tempo. Ao pensarem numa solução procurem sempre perceber qual a complexidade do que estão a pensar para conseguirem "prever" se vai ou não passar.
Como é um mini-desafio, não vou dar mais dicas, mas se precisarem de alguma ajuda avisem. Fico à espera de ver os vossos programas :)