Exercícios MT1

a) Seleção gulosa: artigos 3 e 2, com valor $42+36=78$. b) Sim, é ótima nesta instância. c) A gulosa pode ser arbitrariamente má: com $v=\{1, W-1\}$ e $w=\{1, W\}$, o rácio guloso/ótimo é $1/(W-1)$.

Os rácios são $70/7=10$, $36/6=6$ e $42/4=10{,}5$. A ordem decrescente é artigo 3, artigo 1, artigo 2. O artigo 3 enche 4 unidades; sobram 6, onde o artigo 1 (peso 7) não cabe e o artigo 2 (peso 6) cabe exatamente, dando $42+36=78$ e enchendo a mochila por completo. Como a mochila fica cheia, nenhuma solução pode ter valor superior a $78$ nesta instância. Em geral, a gulosa pode falhar por um fator arbitrário: com dois artigos de valores $1$ e $W-1$ e pesos $1$ e $W$, a gulosa escolhe o primeiro (valor 1) e a ótima escolhe o segundo (valor $W-1$).

Percorrer as localidades por ordem crescente; para a primeira localidade $t$ ainda não coberta, colocar uma estação em $t+R$. Complexidade $O(n)$ com as localidades ordenadas. A prova de otimalidade compara com uma solução ótima qualquer e troca, uma a uma, cada estação da solução ótima pela estação que o algoritmo guloso coloca na mesma posição, sem nunca uncoverir localidades.

Se a solução ótima colocasse a sua próxima estação antes de $t+R$, a localidade $t$ ficaria descoberta, pelo que a próxima estação ótima tem de estar em $t+R$ ou depois. Trocá-la pela estação em $t+R$ não descubre nenhuma localidade e faz a solução ótima coincidir com a gulosa numa estação a mais. Por troca sucessiva, a solução gulosa é ótima.

Começando com o depósito cheio, parar no posto mais afastado que é alcançável dentro de $n$ milhas e abastecer lá; repetir a partir desse posto. O problema tem subestrutura ótima e a escolha gulosa é segura: nenhum posto para lá do $k$-ésimo é alcançável como primeira paragem, e escolher um posto $j<k$ nunca permite ir mais longe. Com $m$ postos, cada um é inspecionado uma vez, logo $O(m)$.

Se uma solução ótima tem a primeira paragem no posto $k$, o resto tem de ser ótimo para o subproblema dos $m-k$ postos seguintes, caso contrário havia uma solução com menos paragens. Como a escolha do posto $k$ deixa pelo menos tanto combustível como qualquer escolha $j<k$, a gulosa nunca fica em pior posição.

Como todos os artigos valem o mesmo, maximizar o valor é o mesmo que maximizar o número de artigos na mochila. Basta ordenar os artigos por peso crescente e ir enchendo a mochila pelos mais leves; quando a capacidade restante não chega para o artigo seguinte, insere-se a fração correspondente. A complexidade é $O(n\log n)$, dominada pela ordenação.

Ordenar por rácio $v/w$ decrescente é, quando todos os $v$ são iguais, equivalente a ordenar por peso crescente: $v_i/w_i > v_{i+1}/w_{i+1}$ implica $w_i < w_{i+1}$. Assim, réutiliza-se a prova de otimalidade da mochila fracionária clássica. Em alternativa, trocar um artigo mais pesado por um mais leve, de igual valor, liberta capacidade para outro artigo ou fração, aumentando o valor.

Sim. Como todas as arestas têm o mesmo peso, basta varrer as arestas até recolher $N-1$ arestas que não formem ciclo, marcando os nós já alcançados. A complexidade é $O(V+E)$, uma ligeira melhoria sobre a de Prim ou Kruskal com filas de prioridade.

Qualquer conjunto de $N-1$ arestas sem ciclo é uma árvore abrangente e, com pesos unitários, todas as árvores abrangentes têm custo $N-1$. Portanto a ordenação de arestas é dispensável e uma simples travessia com marcação de nós resolve o problema.

Basta uma travessia (por exemplo DFS) que vai adicionando arestas para nós ainda não visitados até perfazer $N-1$ arestas, usando um vetor booleano de visitados. Complexidade $O(E+V)$ e custo da árvore $N-1$.

Com pesos todos iguais, a parte mais cara de Prim, a ordenação das arestas, torna-se desnecessária: qualquer aresta que ligue um nó novo serve. Uma DFS com marcação de nós visitados escolhe essas arestas em tempo linear.

a) Inicialização $\{0,4,8,1,4,\infty\}$; após a primeira iteração (nó $d$ selecionado) $\{0,2,8,1,2,\infty\}$; finais $\{0,2,5,1,2,6\}$. b) O peso de $(a,e)$ não pode ser inferior a 2.

Após inicializar com as arestas diretas de $a$, seleciona-se $d$ (distância 1) e relaxam-se $b$ e $e$ para 2. Depois seleciona-se $b$ (empate com $e$, vence $b$), depois $e$, que leva $c$ a $2+3=5$, e por fim $c$, que leva $f$ a $5+1=6$. Se o peso de $(a,e)$ fosse menor que 2, o nó $e$ passaria a ser alcançado diretamente por $a$, alterando a árvore de caminhos mais curtos e, via $e$, os caminhos para $c$ e $f$.

a) Ordem $A;B;D;E;C$, com $\{d(B),d(C),d(D),d(E)\}=\{2,8,4,6\}$. b) Sim: $d(D)=4$ deveria ser 2 e $d(E)=6$ deveria ser 1. c) Remove-se a aresta $(C,E)$.

O Dijkstra só é correto com pesos não negativos. Aqui, depois de fixar $D=4$ e $E=6$, a aresta negativa $C\to E$ já não é reaplicada: o caminho $A\to C\to E$ dá $8-7=1$ e $A\to C\to E\to D$ dá 2. Sem a aresta $(C,E)$, todos os pesos são não negativos e o Dijkstra produz os caminhos corretos.

a) Corte $S_1=\{t\}$, $S_2=\{s,a,b,c,d,e,f\}$, capacidade 3. b) $s\to a\to d\to t$, $s\to a\to e\to t$, $s\to b\to f\to t$ (capacidade 1 cada). c) Fluxo máximo = corte mínimo = 3. d) Uma aresta por cada nó de $\{a,b,c\}$.

Só entram em $t$ três arestas de capacidade 1, pelo que o fluxo máximo é no máximo 3; o corte $\{t\}$ mostra que 3 é atingível com os três caminhos indicados. Em cada nó de $L$ há duas arestas para $R$, pelo que retirar uma delas não impede desviar o fluxo pela outra.

a) Fluxo máximo $=\min(20,\min(X,Y)+\min(X,Z))$. b) $X=Y=Z=10$. c) Não, pois o gargalo do caminho é a aresta de capacidade $X$.

O fluxo que chega a $d$ vem dos caminhos $s\to a\to b\to d$ (limitado por $\min(20,X,Y)$) e $s\to c\to\ldots\to d$ (limitado por $\min(20,X,Z)$), e a aresta $d\to t$ limita tudo a 20. Para saturar as arestas de $s$ (20 cada) e a de $t$, cada ramo tem de transportar 10, ou seja $X=Y=Z=10$. Aumentar $Y$ além de $X$ não ajuda, porque o troço partilhado de capacidade $X$ continua a limitar o caminho.

$T(n)=4T(n/4)+f(n)$. Como $a=4$ e $b=4$, $\log_b a=1$: se $f(n)=\Theta(n)$, caso 2 do teorema mestre, $T(n)=\Theta(n\log n)$; se $f(n)=O(n^{1-\varepsilon})$ (por exemplo $O(\sqrt{n})$), caso 1, $T(n)=\Theta(n)$; se $f(n)=\Omega(n^{1+\varepsilon})$ (por exemplo $\Theta(n^2)$), caso 3, $T(n)=\Theta(n^2)$.

Cada chamada gera 4 subproblemas de tamanho $n/4$, pelo que a árvore de recursão tem profundidade $\log_4 n$ e o trabalho fora das folhas domina conforme o expoente de $f(n)$ comparado com $n^{\log_4 4}=n$.

Pesquisa binária sobre o índice em que o vetor muda de 1 para 0: se $S[1]=0$ há $k$ zeros; se $S[k]=1$ não há zeros; caso contrário divide-se o intervalo ao meio até encontrar a transição. O número de zeros é $k-i$ (ou $k-i+1$) onde $i$ é o último índice com valor 1. Complexidade $O(\log k)$.

Como o vetor está ordenado (todos os 1 antes de todos os 0), a posição da mudança é monotónica e a pesquisa binária encontra-a em $\log_2 k$ passos, cada um de custo constante.

$T(n)=3T(n/9)+f(n)$, com $a=3$, $b=9$ e $\log_9 3=0{,}5$. Se $f(n)=\Theta(n)$ ou $\Theta(n^2)$, domina a solução homogénea: $T(n)=\Theta(n)$ e $\Theta(n^2)$. Se $f(n)=\Theta(\sqrt{n})$, caso 2: $T(n)=\Theta(\sqrt{n}\log n)$. Se F fosse $O(\log n)$, continuava a ser polinomialmente inferior a $\sqrt{n}$ e $T(n)=\Theta(\sqrt{n})$: não vale a pena investir numa implementação mais eficiente de F.

O expoente crítico é $0{,}5$. Qualquer $f(n)$ polinomialmente acima de $\sqrt{n}$ domina a recorrência; o próprio $\sqrt{n}$ dá o caso 2 com fator logarítmico; abaixo disso, o custo das $3^{\log_9 n}=\sqrt{n}$ folhas domina.

$T(n)=9T(n/3)+f(n)$, com $a=9$, $b=3$ e $\log_3 9=2$. Se $f(n)=\Theta(n)$, caso 1: $T(n)=\Theta(n^2)$. Se $f(n)=\Theta(n^2)$, caso 2: $T(n)=\Theta(n^2\log n)$. Se F fosse mais eficiente que linear, a complexidade continuava $\Theta(n^2)$, pelo que não faz sentido investir nisso.

O número de folhas é $9^{\log_3 n}=n^2$, que já domina qualquer $f(n)$ de expoente inferior a 2. Só um F quadrático (caso 2) ou superior altera a ordem de grandeza, e nesse caso o custo de F passa a dominar.

a) $X=35$. b) $A=\{5,12,18\}$, $B=\{7,13,15\}$. c) 0 estados totalmente explorados; 16 podados.

A soma total é $5+7+12+13+15+18=70$, logo $X=35$. Com $x_1=0$ e $x_2=1$, a poda pelo limite superior (soma parcial + próximo elemento > $X$) e pelo limite inferior (soma parcial + soma dos restantes < $X$) impede qualquer ramo de chegar ao fim: a primeira solução válida, o estado $(0,1,1,0,1,0)$, corresponde a $B=\{7,13,15\}$.

A árvore de estados (soma, nível, resto) é:

(0,1,13)
├── x1=1 → (1,2,12)
│   ├── x2=1 → (4,3,9)
│   │   ├── x3=1 → (8,4,5)
│   │   │   ├── x4=1 → 13 > 8, podado
│   │   │   └── x4=0 → (8,5,0), solução {1,3,4}
│   │   └── x3=0 → (4,4,5), ambos os ramos seguintes podados
│   └── x2=0 → (1,3,9), todos os ramos podados
└── x1=0 → (0,2,12)
    ├── x2=1 → (3,3,9)
    │   ├── x3=1 → (7,4,5), podado
    │   └── x3=0 → (3,4,5)
    │       ├── x4=1 → (8,5,0), solução {3,5}
    │       └── x4=0 → 3 < 8, podado
    └── x2=0 → (0,3,9), todos os ramos podados

As soluções são $\{1,3,4\}$ e $\{3,5\}$.

A poda superior impede continuar quando a soma parcial mais o próximo elemento ultrapassa $M=8$ (por exemplo, em (4,4,5) o próximo elemento 5 daria 9); a poda inferior impede continuar quando nem com todos os restantes se chega a $M$ (por exemplo, em (3,4,5) com $x_4=0$ a soma fica 3 < 8). Só os estados (8,5,0) atingem a soma exata.