Instituto Superior Técnico

Análise e Sı́ntese de Algoritmos

Ano Lectivo 2020/2021 Exame de Época Especial

RESOLUÇÃO
I. (1.5 + 2 + 2 + 1.5 + 1.5 + 1.5 = 10 val.)
I.a) Considere o grafo dirigido da figura.

C B A

G D E

Aplique o algoritmo de Tarjan para identificar os componentes fortemente ligados, con-

siderando o vértice D como inicial. Durante a aplicação do algoritmo considere que
tanto a escolha dos vértices a visitar, como a pesquisa dos vértices adjacentes são feitas
por ordem lexicográfica (ou seja, A, B, C, ...).
Indique os componentes fortemente ligados do grafo pela ordem segundo a qual são
identificados pelo algoritmo e o valor low calculado para cada vértice. Considere que o
tempo de descoberta d começa em 1.

A B C D E F G
low() 3 2 2 1 1 1 7
SCCs : {C, B, A}, {G}, {F, E, D}

1/16
I.b) Considere o grafo não dirigido e pesado da figura.

A 3 C 4 F 2 E

3 3 5 5 2 2

B G D

1 1

H 1 I

Considere a execução do algoritmo de Kruskal para determinar árvores abrangentes

de menor custo. Durante a aplicação do algoritmo, arcos com o mesmo peso devem ser
considerados por ordem lexicográfica.
Utilize a estrutura em árvore para representação de conjuntos disjuntos com a
aplicação das heuristicas de união por categoria e compressão de caminhos. Para cada
vértice indique os valores de categoria (rank[v]) e o valor do seu pai na árvore que
representa os conjuntos (p[v]).
Nota: Na operação M ake-Set(v), o valor da categoria de v é inicializado a 0. Na
operação de U nion(u, v), em caso de empate, considere que o representante de v é que
fica na raı́z.
A B C D E F G H I
rank[v] 0 1 0 0 2 0 0 1 0
p[v] B E E E E E E E H

Indique ainda o peso da árvore abrangente, bem como o número de total de árvores
abrangentes.

Pesos da MST: 21
Número de MSTs: 54

2/16
I.c) Considere a rede de fluxo da figura onde s e t são respectivamente os vértices fonte
e destino na rede. Aplique o algoritmo Relabel-To-Front na rede de fluxo. Considere
que as listas de vizinhos dos vértices intermédios são as seguintes:
N [A] =< B, D, s, C >
N [B] =< t, A >
N [C] =< D, A, s >
N [D] =< t, A, C >
e que a lista de vértices inicial é L =< B, D, A, C >.

A 7 B

6 9
s 4 3 t

10 7

C 5 D

Indique a altura final de cada vértice, um corte mı́nimo da rede, o valor do fluxo máximo,
e a sequência de diferentes configurações de L.

s A B C D t
h() 6 7 1 7 7 0
Corte : {s, A, C, D}/{B, t} f(S,T) =14
L: < B, D, A, C >, < A, B, D, C >, < B, A, D, C >, < C, B, A, D >,
< A, C, B, D >, < D, A, C, B >, < A, D, C, B >, < D, A, C, B >,
< A, D, C, B >, < D, A, C, B >, < A, D, C, B >
Indique ainda o valor do fluxo final de cada aresta da rede de fluxo.
f(s,A) f(s,C) f(A,B) f(A,D) f(B,t) f(C,A) f(C,D) f(D,t)
5 9 7 2 7 4 5 7

3/16
I.d) Considere a maior sub-sequência comum entre as duas strings ABBACBA e
CABAABCA e calcule a respectiva matriz de programação dinâmica c[i, j] para este
problema, em que o ı́ndice i está associado à string ABBACBA. Indique os seguintes
valores: c[1, 2], c[3, 6], c[4, 3], c[5, 1], c[5, 7], c[6, 4], c[7, 8]. Indique ainda o número de
maior sub-sequências comuns.
c[1,2] c[3,6] c[4,3] c[5,1] c[5,7] c[6,4] c[7,8]
1 3 2 1 4 3 5
Número de maior sub-sequências comuns: 3

4/16
I.e) Considere o problema de compressão de dados de um ficheiro usando a codificação
de Huffman. Indique o código livre de prefixo óptimo para cada carácter num ficheiro
com 10.000 caracteres com a seguinte frequência de ocorrências:
f (a) = 13, f (b) = 8, f (c) = 5, f (d) = 25, f (e) = 12, f (f ) = 37.
Quando constrói a árvore, considere o bit 0 para o nó com menor frequência. Em
caso de empate, atribua o bit 0 ao nó que inclui o caracter que aparece primeiro por
ordem alfabética. Analogamente, em caso de empate na min-priority queue, considera-se
primeiro o nó que inclui o caracter que aparece primeiro por ordem alfabética.
Indique também o total de bits no ficheiro codificado.
a b c d e f
Codificação 011 001 000 10 010 11
Total Bits 23.800

5/16
I.f ) Considere o padrão P = abbabb e construa o autómato finito que emparelhe este
padrão numa cadeia de caracteres. Indique o estado resultante das seguintes transições:
δ(0, a) δ(1, a) δ(2, a) δ(3, b) δ(4, a) δ(5, a) δ(6, a) δ(6, b)
1 1 1 0 1 1 4 0
Ilustre a sua aplicação no seguinte texto T = aabbaabbabbabba.

q 0 1 1 2 3 4 1 2 3 4 5 6 4 5 6 4

Indique o número total de matches e as posições onde estes ocorrem.

Número total de matches: 2
Matches nas posições: 6e9

6/16
II. (1,5 + 1,5 + 2 + 1,5 + 2 + 1,5 = 10 val.)
II.a) Considere a função recursiva:

int f(int n) {
int i = 0, j = n;

if (n <= 1) return 1;

while(j > 1) {
i++;
j = j / 2;
}

for (int k = 0; k < 8; k++)

j += f(n/2);

while (i > 0) {
j = j + 2;
i--;
}
return j;
}

1. Determine o menor majorante assimptótico medido em função do parâmetro n

para o número total de iterações dos loops 1 e 2 por cada chamada à função f .

2. Determine o menor majorante assimptótico da função f , em função do parâmetro

n, utilizando os métodos que conhece.

Solução:

1. Consideramos os dois loops separadamente.

• Loop 1 : O(log n)
• Loop 2 : O(log n)

2. Equação do tempo:
T (n) = 8.T (n/2) + O(log n)
Observando que logb a = log2 8 = 3 e que log n ∈ O(n3−ǫ ), aplicamos o Teorema
Mestre na forma geral, concluindo que: T (n) ∈ O(n3 ).

7/16
II.b) Dizemos que um grafo dirigido forma uma linha se consiste numa sequência linear
de vértices como se ilustra na figura em baixo:

Pretende desenvolver-se um algoritmo que, dado um grafo dirigido G = (V, E), deter-
mina se G forma uma linha. Admitindo que o grafo G dado como input é representado
com base em listas de adjacências:

1. Proponha um algoritmo que retorna uma lista com os vértices source de G e

indique a respectiva complexidade assimptótica. Não é necessário apresentar o
pseudo-código.

2. Proponha um algoritmo para determinar se G forma uma linha. Deve apresen-

tar o pseudo-código do algoritmo proposto e indicar a respectiva complexidade
assimptótica.

Solução:

1. Criamos um vector ~v com n posições, onde n = |V |, incializado a 0. Intuitivamente,

cada posição i do vector ~v deverá guardar o número de arcos incidentes no vértice
i. Para tal, percorremos as listas de adjacências do grafo G, ao processarmos cada
arco (i, j), incrementamos de uma unidade a posição j do vector ~v (~v [j] = ~v [j]+1).
No final, percorremos o vector ~v , inserindo na lista L a retornar os vértices para os
quais ~v tem o valor 0; isto é, L deverá conter todos os vértices j tais que ~v [j] = 0.
Complexidade: O(V + E)

2. function CheckLine(G)
1: v ← findSource(G)
2: if v == null then
3: return f alse
4: end if
5: visited[1, .., n] ← new array of size |G.V |
6: count ← 1
7: while true do
8: if [Link][v].size > 1 || visited[v] == true then
9: return f alse
10: else if [Link][v].size == 0 then
11: break
12: else
13: visited[v] ← true
14: count ← count + 1
15: v ← [Link][v][0]
16: end if
17: end while
18: return count == |G.V |

Complexidade: o corpo do ciclo While é percorrido no máximo uma vez por cada
vértice pelo que o custo do algoritmo é dominado pela operação findSource que
tem complexidade O(V + E).

8/16
II.c) Por causa do COVID-19, o Eng. António Caracol foi encarregue de projectar
um sistema que permita aos cidadãos de Manhattan deslocar-se a um supermercado
sem se cruzarem com nenhum outro cidadão. Estão disponı́veis no mapa da cidade,
as localizações dos supermercados, que se situam todos em esquinas e as moradas dos
cidadãos que, para este efeito, se situam também nas esquinas.
Tratando-se de Manhattan, as ruas têm um arranjo em quadriculado absolutamente
regular, e considera-se que em todas as ruas se circula em ambos os sentidos. As avenidas
estão numeradas de 1 a m, enquanto que as ruas estão numeradas de 1 a n, como se
ilustra em baixo:

Os cruzamentos são definidos por um par de números, sendo que o par (i, j) corresponde
ao cruzamento da rua i com a avenida j.
Dados um conjunto de supermercados abertos {S1 , ..., Sk } e de cidadãos que querem
fazer compras a uma dada hora {C1 , ..., Cl }, o sistema deverá determinar qual o número
máximo de cidadãos que pode deslocar-se a um supermercado, sem correr o risco de se
encontrar com outro cidadão, numa rua, avenida ou cruzamento, inicial, intermédio ou
final do seu percurso. Por exemplo, dada a grelha ortogonal em baixo, apenas 4 cidadãos
se podem deslocar a um supermercado simultaneamente sem se cruzarem.

Dados adicionais: Podem existir dois supermercados no mesmo cruzamento, mas apenas
um deles poderá ser usado numa soluação, para evitar contactos nesse local. Dois ou mais
cidadãos podem morar no mesmo cruzamento, mas apenas um deles poderá sair à rua de
cada vez, os que ficam em casa não levantam problemas de contágio. Da mesma forma,
se um ou mais cidadãos morarem num cruzamento mas não saı́rem à rua, o cruzamento
pode ser usado por outro cidadão para passar ou aceder a um supermercado, nesse ou
noutro cruzamento.

1. Modele o problema descrito em cima como um problema de fluxo máximo.

2. Indique o algoritmo que utilizaria para a calcular o fluxo máximo, bem como a
respectiva complexidade assimptótica medida em função dos parâmetros do pro-
blema: número de avenidas m, número de ruas n, número de supermercados k e
 número de cidadãos l. Pode admitir que l >> k e l >> n.m. De entre os algorit-
mos de fluxo estudados nas aulas deve escolher aquele que garanta a complexidade
assimptótica mais baixa para o problema em questão.
Nota: A resposta deverá necessariamente incluir as expressões que definem o
número de vértices e de arcos da rede de fluxo proposta (|V | e |E|, respectiva-
mente) em função dos parâmetros do problema, bem como um upper-bound para
o valor do fluxo máximo.

Solução:

1. Construção da rede de fluxo: G = (V, E, c, s, t). Na construção da rede de fluxo

consideramos dois vértices por cruzamento (um vértice de entrada e um vértice
de saı́da), um vértice por residente, um vértice por supermercado e dois vértices
adicionais s e t, respectivamente a fonte e o sumidouro. Formalmente:
•
V = {s, t} fonte e sumidouro
∪ {Si | 1 ≤ i ≤ k} supermercados
∪ {Ci | 1 ≤ i ≤ l} cidadãos
∪ {Pij , Pij′ | 1 ≤ i ≤ n, 1 ≤ j ≤ m} cruzamentos
•
E = {(s, Ci , 1) | 1 ≤ i ≤ l} Ci quer ir a um supermercado
∪{(Co , Pij , 1) | 1 ≤ o ≤ l} se Co vive no cruzamento (i, j)
∪ {(Pij′ , So , 1) | 1 ≤ o ≤ k} se So se encontra em (i, j)
∪ {(So , t, 1) | 1 ≤ o ≤ k}
∪ {(Pij , Pij′ , 1) | 1 ≤ i ≤ m, 1 ≤ j ≤ n} uma pessoa por cruzamento
∪ {(Pij′ , P(i+1)j , 1) | 1 ≤ i < n, 1 ≤ j ≤ m} ligar ao cruzamento de baixo
∪ {(Pij′ , P(i−1)j , 1) | 1 < i ≤ n, 1 ≤ j ≤ m} ligar ao cruzamento de cima
∪ {(Pij′ , Pi(j−1) , 1) | 1 ≤ i ≤ n, 1 < j ≤ m} ligar ao cruzamento da esquerda
∪ {(Pij′ , Pi(j+1) , 1) | 1 ≤ i ≤ n, 1 ≤ j < m} ligar ao cruzamento da direita

2. Complexidade:

• |V | = 2.n.m + k + l + 2 = O(n.m + l) = O(l)

• |E| = 2.l + 2.k + n.m + (n − 1) ∗ m ∗ 2 + n ∗ (m − 1) ∗ 2 = O(n.m + l) = O(l)
• |f ∗ | ≤ k = O(k)
• Edmonds Karp (upper bound de FF): O(|f ∗ |.E) = O(k.l)
• Edmonds Karp (upper bound EK): O(E 2 .V ) = O(l3 )
• Relabel-To-Front: O(l3 )

O algoritmo a utilizar é o algoritmo de Edmonds-Karp.

10/16
II.d) Considere o seguinte programa linear:

max x1 +x2
s.a −x1 −x2 ≤ −1
−x1 +x2 ≤ 5
4x1 +x2 ≤ 20
x1 , x2 ≥ 0

1. Desenhe o conjunto exequı́vel e resolva geometricamente o programa linear. A

resposta deve incluir: o valor máximo, as coordenadas onde esse valor é atingido
e as equações das rectas que delimitam a região exequı́vel.

2. Formule o programa linear auxiliar e indique duas soluções diferentes para o

mesmo.

3. Formule o programa linear dual e calcule a respectiva solução a partir da solução

do programa primal. Indique tanto o valor mı́nimo como as coordenadas onde esse
valor é atingido.

Solução:
1. Representamos a região exequı́vel no diagrama em baixo.

O Teorema Fundamental da Programação Linear estabelece que o valor óptimo da

função objectivo, a existir, ocorre num vértice da região exequı́vel. Assim sendo,
concluı́mos que o valor óptimo é 11 e ocorre no vértice P4 = (3, 8). Equações das
rectas que delimitam o conjunto exequı́vel:

• R1: x2 = 1 − x1
• R2: x2 = 5 + x1
• R3: x2 = 20 − 4.x1

2. O programa linear auxiliar é definido em baixo:

max −x0
s.a −x1 −x2 −x0 ≤ −1
−x1 +x2 −x0 ≤ 5
4x1 +x2 −x0 ≤ 20
x1 , x2 , x0 ≥ 0
 Qualquer ponto da região exequı́vel é uma solução do programa auxiliar. Assim
podemos considerar, por exemplo, quaisquer dois pontos de P1 , P2 , P3 , P4 e P5 ,
definidos na figura (estendidos com a coordenada x0 = 0):

• P1′ = (1, 0, 0)
• P2′ = (0, 1, 0)
• P3′ = (0, 5, 0)
• P4′ = (3, 8, 0)
• P5′ = (5, 0, 0)

3. O programa linear dual é definido em baixo:

min −1y1 +5y2 +20y3

s.a −y1 −y2 +4y3 ≥ 1
−y1 +y2 +y3 ≥ 1
y1 , y2 , y3 ≥ 0

Do Teorema da Dualidade Forte concluı́mos que o valor mı́nimo do programa dual

coincide com o valor máximo do programa primal, 11. Da inspecção da geometria
do programa primal, concluı́mos que as restrições activas no vértice da solução
correspondem às variáveis y2 e y3 do problema dual. Segue, por isso, que y1 = 0
no ponto óptimo do problema dual. Resolvendo o sistema:

−y2 + 4y3 = 1
y2 + y3 = 1

concluı́mos que o valor mı́nimo do programa dual se encontra no ponto (0, 3/5, 2/5).

12/16
II.e) Dadas duas sequências de caracteres X ~ = hX1 , ..., Xn i e Z
~ = hZ1 , ..., Zk i, Z
~ diz-
se uma subsequência contı́gua de X ~ se existir um inteiro 0 ≤ i < n tal que: Xi+1 =
Z1 , Xi+2 = Z2 , ..., Xi+k = Zk . Por exemplo, a sequência de caracteres abb é uma
subsequência contı́gua de ababb (basta escolher o deslocamento i = 2).
Dadas duas sequências de caracteres X ~ = hX1 , ..., Xn i e Y ~ = hY1 , ..., Ym i, pre-
tende desenvolver-se um algoritmo que determine o tamanho da sua maior subsequência
contı́gua comum.

~ = hX1 , ..., Xn i e Y
1. Dadas duas sequências de caracteres X ~ = hY1 , ..., Ym i, seja
B(i, j) o tamanho do maior sufixo comum entre hX1 , ..., Xi i e hY1 , ..., Yj i. Por
exemplo, para X~ = abaabb e Y~ = abbbbb, temos que B(3, 3) = 0 e B(6, 3) = 3.
Defina B(i, j) recursivamente completando os campos em baixo:

 0
 se i = 0 ∨ j = 0
B(i, j) = se
c.c.



Admite-se, para simplificar a formulação, que B(i, j) = 0 quando i = 0 ou j = 0.

2. Complete o template de código em baixo que, dadas duas sequências de carac-

teres hX1 , ..., Xn i e hY1 , ..., Ym i, calcula o tamanho da sua maior subsequência
contı́gua comum.

LongestContiguousCommonSubstring(x[1..n], y[1..m])
let B[0..n, 0..m] be a new matrix of size (n + 1) × (m + 1)
B[0, 0] :=
for i = 1 to n do
B[i, 0] :=
endfor
for j = 1 to m do
B[0, j] :=
endfor
let max = 0
for i = 1 to n do
for j = 1 to m do

endfor
endfor
return max

3. Determine a complexidade assimptótica do algoritmo proposto na alı́nea anterior.

Solução:

1. 
 0 se i = 0 ∨ j = 0
B(i, j) = B(i − 1, j − 1) + 1 se Xi = Yj
0 c.c.


2.
LongestContiguousCommonSubstring(x[1..n], y[1..m])
let B[0..n, 0..m] be a new matrix of size (n + 1) × (m + 1)
B[0, 0] := 0
for i = 1 to n do
B[i, 0] := 0
endfor
for j = 1 to m do
B[0, j] := 0
endfor
let max = 0
for i = 1 to n do
for j = 1 to m do
if x[i] == y[j] then
B[i, j] := B[i − 1, j − 1] + 1
max := max(B[i, j], max)
else B[i, j] := 0
endfor
endfor
return max

3. Complexidade: O(n2 ). O algoritmo tem de preencher toda a matriz B[0..n, 0..m].

O preenchimento de cada célula faz-se em tempo constante, O(1).

14/16
II.f ) Dado um grafo dirigido G = (V, E), o problema LongestPath consiste em
determinar o tamanho do caminho mais longo entre quaisquer dois vértices em G que
não passa pelo mesmo vértice duas vezes. Formalmente, o problema LongestPath pode
ser modelado através do seguinte problema de decisão:

LongestPath = {hG, ki | G contém um caminho de tamanho k sem vértices repetidos}

1. Ao contrário do problema do caminho mais curto, o problema do caminho mais

longo não possui sub-estrutura óptima. Explique a afirmação fornecendo um exem-
plo com base no grafo que se ilustra em baixo.

2. Mostre que o problema LongestPath está em NP.

3. Mostre que o problema LongestPath é NP-difı́cil por redução a partir do pro-

blema HamiltonianPath que se define em baixo e que é sabido tratar-se de um
problema NP-completo. Não é necessário provar formalmente a equivalência entre
os dois problemas; é suficiente indicar a redução e a respectiva complexidade.

Problema do Caminho Hamiltoniano: Um grafo dirigido G = (V, E) contém um caminho

Hamiltoniano sse existe uma sequência de vértices hvi1 , ..., vin i em G tal que:

V = {vi1 , ..., vin } ∧ n = |V | ∧ ∀i=1,..,n−1 . (vi , vi+1 ) ∈ E

O problema do caminho Hamiltoniano, HamPath, define-se formalmente da seguinte

maneira:

HamPath = {hGi | G contém um caminho Hamiltoniano}

Solução:

1. O problema do caminho mais longo não tem sub-estrutura óptima porque um

caminho mais longo não é necessariamente constituı́do por caminhos mais longos.
Por exemplo, a sequência hv1 , v2 , v4 i é um caminho mais longo entre v1 e v4 .
Contudo, hv2 , v4 i não é um caminho mais longo entre v2 e v4 . O caminho mais
longo entre v2 e v4 é: hv2 , v1 , v3 , v4 i.

2. O algoritmo de verificação recebe como input uma possı́vel instância hG, ki e uma
sequência de vértices em G, ~v = hvi1 , ..., vik i, que constitui o certificado. O algo-
ritmo tem de verificar que:

• Restrição 1: A sequência ~v contém todos os vértices de G e não contém

vértices repetidos;
• Restrição 2: Cada dois vértices consecutivos de ~v correspondem a um arco
de G.
 Em primeiro lugar, observamos que o certificado tem tamanho O(V ). Analisamos
cada restrição separadamente:

• Restrição 1: Percorrer a sequência ~v mantendo um vector de Booleanos de

tamanho n, inicialmente inicializados a f alse; sempre que um vértice é en-
contrado, colocamos o seu Booleano correspondente a true; se encontrarmos
um vértice cujo Booleano seja true, retornamos f alse. Se não encontrar-
mos nenhum vértice repetido, verificamos adicionalmente que o tamanho de
~v coincide com o número de vértices. Complexidade: O(V ).
• Restrição 2: Percorrer a sequência ~v . Verificar para cada dois vértices con-
secutivos que (vi , vi+1 ) ∈ E. Complexidade: O(E), no pior caso percorremos
todos os arcos do grafo.

3. Dada uma instância hGi do problema HamPath temos de construir uma instância
hG′ , ki do problema LongestPath tal que:

hGi ∈ HamPath ⇔ hG′ , ki ∈ LongestPath

Para tal, basta escolher G′ = G e k = |V |. Complexidade da redução: O(V + E).

Número: Nome: 16/16