É 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 11% da nota desta componente. Como existem 11 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.
Conteúdos das teóricas
Nesta aula iremos abordar conceitos de complexidade algorítmica. Será por isso conveniente ver o que foi falado nas teóricas:
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\)
O que está no fundo a ser pedido é perceber qual função "domina" a outra, ou seja, qual função cresce mais rapidamente.
(a): qual dos polinómios tem maior grau e por isso cresce mais rapidamente?
(b): se os polinómios são do mesmo grau...
(c): Uma função polinomial vs uma função exponencial...
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):
contains(int x)
add(int x)
remove(int x)
size()
clear()
contains(int x) - \(\Theta(n)\) [é preciso percorrer a lista de elementos]
add(int x) - \(\Theta(n)\) [adicionar em sié \(\Theta(1)\), mas primeiro chama-se o contains que custa \(\Theta(1)\)]
remove(int x) - \(\Theta(n)\) [é preciso percorrer a lista de elementos]
size() - \(\Theta(1)\) [é só devolver o conteúdo de uma variável]
clear() - \(\Theta(1)\) [é só modificar o conteúdo de uma variável]
Na aula #05 foi sugerida uma implementação usando um array de booleanos (ao invés de manter uma lista de números). Recordando o que foi pedido na sua essência:
- Manter um array isElem[] de valores booleanos (verdadeiro ou falso). isElem[i] diz-nos se o número i está ou não no conjunto. O tamanho do array determina o tamanho do número máximo. Manter numa outra variável size o número de elementos. Por exemplo, o conjunto {1,5,7} seria representado por isElem[]={F,T,F,F,F,T,F,T,F,F,F} e size=3
0
1
2
3
4
5
6
7
8
9
F
T
F
F
F
T
F
T
F
F
Para esta implementação com o array de booleanos, qual é a complexidade temporal de cada um dos 5 mesmos métodos do TAD IntSet? O que melhorou em relação ao ArrayListIntSet? Qual é o tradeoff? (ou seja, para conseguir melhor complexidade temporal, o que passamos a precisar em termos de memória? quais as limitações desta nova implementação?)
contains(int x) - \(\Theta(1)\) [é devolver a posição do array]
add(int x) - \(\Theta(1)\) [é só marcar uma posição do array a true]
remove(int x) - \(\Theta(1)\) [é só marcar uma posição do array a false]
size() - \(\Theta(1)\) [assumindo que guarda a quantidade de elementos num atributo]
clear() - \(\Theta(k)\) [percorrer toda a lista de valores até ao valor máximo k]
Essencialmente melhoramos complexidade do contains, add e remove, e só pioramos a do clear. O tradeoff é que passamos a precisar de mais memória, \(\Theta(k)\) vs \(\Theta(n)\), onde k é o maior elemento possível de armezenar, sendo que por isso estamos limitados a elementos cuja magnitude caiba na memória (ex: guardar dois longs seria fácil num ArrayList mas num array de booleanos implicaria ter espaço para \(2^{63}-1\) elementos, o que é não de todo possível num computador de hoje em dia). Além disso, só podemos guardar coisas indexáveis (ex: era fácil guardar um conjunto de Strings num ArrayList, mas num array de booleanos implicaria ter maneira de convertar Strings em posições inteiras).
Exercício 3) Previsão do tempo de execução
[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:
Com n=300 demorou 1.5 segundos
Com n=600 demorou 12.0 segundos
Com n=1200 demorou 1m36s
Qual será a complexidade temporal mais provável do programa P? Justifique.
Quando o tamanho do input duplica, o tempo aumenta 8x (\(\frac{12s}{1.5s} = \frac{96s}{12s} = 8\)). Desse modo a complexidade parece ser \(\mathcal{O}(n^3)\), pois \(\frac{(2n)^3}{n^3} = 8\).
Indique uma estimativa de quanto tempo demoraria o programa para um caso com 5000 números. Justifique.
Seja \(f(n) = n^3\) e considermos \(n_1=300\) e \(t_1 = 1.5\). Sabendo que \(n_2 = 5000\) queremos estimar \(t_2\).
Exercício 4) Problema do subarray contíguo de soma máxima
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).
Uma primeira solução com força bruta com tempo \(\Theta(n^3)\)
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 possiveisfor(int j=i; j<n; j++){// Todas as posicoes finais possiveisint 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).
Melhorando a solução para \(\Theta(n^2)\)
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?
Melhorando ainda mais para \(\Theta(n)\)
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)\)?
Se \(best(i)\) for um valor positivo, então \(best(i+1) = best(i) + v[i+1]\) pois como os subarrays têm de ser contíguos, então se aproveitarmos algo "de trás", terá que ser o melhor possível a terminar na posição anterior. Imagine por exemplo o array \([4,-2,1,5]\):
\(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).
Se \(best(i)\) for um valor negativo, então \(best(i+1) = v[i+1]\), pois o que está "para trás" só pode fazer decrescer a soma do array a terminar na posição \(i+1\). Imagine por exemplo o array \([-5,2,-3,4]\):
\(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.
Exercícios extra para consolidação de conhecimentos
Tem disponível no Volume 5 mais dois pequenos problemas onde a solução mais "bruta" em termos de complexidade temporal não passa e tem de fazer algo um pouco mais eficiente. Estes dois problema foram o problema mais fácil da qualificação (do respectivo ano) das Olimpíadas Nacionais de Informática um concurso para alunos do secundário:
[ED222] Salvando os Ruivacos
Para este problema uma solução "bruta" que tente todos os intervalos e para cada um deles percorra todos os seus elemento para verificar quantos são maiores ou iguais a \(T\) pode demorar \(\Theta(N^2)\) (basta imaginar o caso onde \(K=N/2\): teremos nesse caso \(N/2+1\) intervalos, cada um com tamanho \(N/2\) que temos de verificar). Isto não é suficiente para passar no tempo, e precisamos de uma solução melhor...
Imagine que já processou o intervalo \([a,b]\) (entre as posições \(a\) e \(b\), tendo obtido \(Q_a\), a quantidade de elementos maiores ou iguais a \(T\) nesse intervalo.
O próximo intervalo a considerar é o intervalo \([a+1,b+1]\). O que muda nesse intervalo? Apenas desaparece a posição \(a\) e é inserida a posição \(b+1\). O (novo) valor de \(Q_{a+1}\) é portanto igual a \(Q_a\) subtraíndo 1 caso o valor da posição \(a\) seja \(\gt T\) e somando 1 caso o valor da posição \(b+1\) seja \(\gt T\).
Para cada novo intervalo precisamos então apenas de um número constante de operações (considerar o elemento a retirar e considerar o elemento a inserir). Em termos de eficiência, isto corresponde a um ciclo inicial para o primeiro intervalo de tamanho \(K\) e depois percorrer os restantes \(N-K\) intervalos, gastando em cada um tempo constante. Outra maneira de pensar no mesmo algorito é ver que cada elemento é adicionado uma vez ao intervalo actual, e retirado uma vez. Esta é portanto uma solução com tempo \(\Theta(N)\) que passa em todos os casos e dá os 100 pontos.
Esta ideia de reutilizar o resultado do intervalo anterior para calcular mais rapidamente o intervalo atual chama-se sliding window, pois estamos a fazer "deslizar" a janela corrente ao longo do input.
[ED199] Tesouros de Kilmia
Para este problema uma solução "bruta" que simule todas as instruções pode demorar \(\Theta(I \times N)\), pois cada uma das \(I\) instruções pode obrigar a percorrer \(N\) posições no pior caso. Isto não é suficiente para passar no tempo, e precisamos de uma solução melhor...
É preciso pensar um pouco sobre o que está a acontecer no problema e assim fazer uma observação importante: o Daniel cobre sempre um intervalo contígo de posições. Se a posição mais à direita que o Daniel chegou foi a posição \(p_d\), então o Daniel teve que passar por todas as posições de \(B\) a \(p_d\), pois ele nunca "salta" posições. Analogamente, se a posição mais à esquerda que o Daniel chegou foi a posição \(p_e\), então o Daniel teve
que passar por todas as posições de \(p_e\) a \(B\).
Assim, sabendo \(p_e\) e \(p_d\), basta fazer um ciclo a percorrer todas
as posições entre \(p_e\) e \(p_d\) e calcular quantos tesouros há nesse
intervalo. Para calcular \(p_e\) e \(p_d\), basta calcular a posição após
seguir cada instrução e manter a menor e maior, respetivamente.
Em termos de eficiência, isto corresponde a um ciclo para processar
todas as instruções e calcular \(p_e\) e \(p_d\), e a um segundo ciclo
para verificar as arcas entre \(p_e\) e \(p_d\), o que corresponde a \(I + N\) operações.
Esta é portanto uma solução \(\Theta(I + N)\) que passa em todos os casos e dá os 100 pontos.
Exercício de Desafio
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:
[ED253] Desorientados (Fase de Qualificação das Olimpíadas Nacionais de Informática'2019)
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 :)