Instituto Superior Técnico

Análise e Sı́ntese de Algoritmos

Ano Lectivo 2021/2022 Exame de Época Especial

RESOLUÇÃO
I. (3 + 3 + 3 + 3 = 12 val.)
I.a) Considere a maior sub-sequência comum entre as strings ABBACBA e ABCBCABA
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, 3], c[2, 6], c[3, 3], c[4, 4], c[5, 6], c[6, 3], c[7, 8].

c[1, 3] c[2, 6] c[3, 3] c[4, 4] c[5, 6] c[6, 3] c[7, 8]

1 2 2 3 4 3 6

1/8
I.b) Considere a rede de fluxo da figura:

s A 5
7
4 t
3
6
3
2
B C

Aplique o algoritmo Relabel-to-Front à rede de fluxo da figura. Considere que as

listas de vizinhos dos vértices intermédios são as seguintes:

• N [A] =< C, B, s, t >

• N [B] =< A, C, s >

• N [C] =< B, t, A >

e que a lista de vértices inicial é L =< A, B, C >. Preencha a tabela abaixo com as
alturas finais dos vértices e a sequência de diferentes configurações da lista L.
s A B C t
h() 5 6 6 7 0
1◦ 2◦ 3◦ 4◦ 5◦ 6◦ 7◦ 8◦
hA, B, Ci hB, A, Ci hA, B, Ci hC, A, Bi

2/8
I.c) Considere a função recursiva:

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

for (i = n; i > 0; i /= 2) {
for (j = i; j > i/2; j--) { // Loop 1
k = k+2*j;
}
}

while (j++ < 4)

r += 2*f(n/2);

while (k-- > 0) { // Loop 2

r = r + 1;
}

return r;
}

1. Determine um upper bound medido em função do parâmetro n para o número de

iterações dos loops 1 e 2 da função f .

2. Determine o menor majorante assimptótico da função f em termos do número n

utilizando os métodos que conhece.

Solução:

1. Analisamos cada loop separadamente:

• Loop 1: j assume os valores n, n − 1, . . . , 1, logo o número de iterações é

n = O(n).
• Loop 2: Observando que após a execução do loop 1, k = nj=1 2j = n(n + 1),
P
e que o número de iterações do loop 2 é igual ao valor de k, temos que o
número de iterações do loop 2 é dado por n(n + 1) = O(n2 ).

2. Observamos que:
T (n) = 4 T (n/2) + O(n2 )
Podemos aplicar o Teorema Mestre na forma simplificada notando que a = 4,
b = 2, d = 2 e logb a = 2 = d. Concluı́mos que T (n) = O(n2 lg n).

3/8
I.d) Considere o grafo dirigido que se apresenta em baixo:

B C D

Aplique o algoritmo que utiliza duas travessias em profundidade primeiro (Kosaraju-

Sharir) para encontrar os componentes fortemente ligados do grafo. Considere que na
primeira DFS os vértices são considerados por ordem alfabética (ou seja, A, B, C, ...).
Em ambas as DFS, os vértices adjacentes são sempre considerados também por ordem
alfabética.

• Indique os tempos de descoberta d e de fim f de cada vértice após a segunda

DFS.

• Indique os componentes fortemente ligados pela ordem em que são descober-

tos.

A B C D
d[i] 1 3 2 7
f[i] 6 4 5 8
SCCs {A, B, C}, {D}

4/8
II. (3 + 3 + 2 = 8 val.)
II.a) Dada uma sequência de inteiros positivos hx1 , ..., xn i, pretende desenvolver-se um
algoritmo que determina o maior valor suceptı́vel de ser obtido a partir da expressão
x1 /x2 /x3 /.../xn , determinando a ordem pela qual as divisões devem ser efectuadas. Por
exemplo, dada a sequência h16, 8, 4, 2i, a parentização que resulta no maior valor final
é: (16/((8/4)/2)) = 16.

1. Seja M [i, j] o maior valor que é possı́vel obter a partir da expressão xi /xi+1 /.../xj
e m[i, j] o menor valor. Por exemplo, dada a sequência h16, 8, 4, 2i, M [1, 4] = 16 e
m[1, 4] = 0.25. Admitindo que a sequência dada como input é hx1 , ..., xn i, defina
M [i, j] e m[i, j] recursivamente completando os campos em baixo:
(
se i = j
M (i, j) =
se j > i
(
se j = i
m(i, j) =
se j > i

2. Complete o template de código em baixo que, dada uma sequência de inteiros

hx1 , ..., xn i, calcula m[1, n] e M [1, n].

GreatestValue(x[1..n])
let M [1..n, 1..n] be a new matrix of size n × n
let m[1..n, 1..n] be a new matrix of size n × n
for i = 1 to n do
M [i, i] :=
m[i, i] :=
endfor
for s = 1 to n−1 do
for i = 1 to n−s do

endfor
endfor
return M [1, n]

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

Solução:

1. 
x[i] se i = j
M (i, j) =
max{M [i, k]/m[k + 1, j] | i ≤ k < j} se j > i

x[i] se j = i
m(i, j) =
min{m[i, k]/M [k + 1, j] | i ≤ k < j} se j > i

2.
GreatestValue(x[1..n])
let M [1..n, 1..n] be a new matrix of size n × n
let m[1..n, 1..n] be a new matrix of size n × n
for i = 1 to n do
M [i, i] := x[i]
m[i, i] := x[i]
endfor
for s = 1 to n−1 do
for i = 1 to n−s do
let j = i + s
let M [i, j] = −∞
let m[i, j] = +∞
for k = i to j−1 do
M [i, j] := max(M [i, j], M [i, k]/m[k + 1, j])
m[i, j] := min(m[i, j], m[i, k]/M [k + 1, j])
endfor
endfor
endfor
return M [1, n]

3. Complexidade: O(n3 ). O algoritmo tem de preencher a metade diagonal superior

das matrizes M [1..n, 1..n] e m[1..n, 1..n], sendo que para cada posição da matriz
o algoritmo pode percorrer s posições. Formalmente:
Pn−1 Pn−s Pj−1
s=1 Pi=1 Pk=i O(1)
n−1 n−s Pi+s−1
= s=1 i=1 k=i O(1)
Pn−1 Pn−s
= s=1 i=1 O(1).(i + s − 1 − i + 1)
Pn−1 Pn−s
= s=1 O(s)
Pn−1 i=1
= s=1 O(s).(n − s)
Pn−1
= O( s=1 n.s − s3 )
Pn−1
≤ O(n. s=1 s)
≤ O(n3 )

6/8
II.b) O Departamento de Informática da Universidade Técnica de Caracolândia decidiu
implementar uma nova aplicação para determinar automaticamente a composição dos
júris de dissertações de mestrado. No semestre em consideração existem n estudantes que
pretendem defender as suas dissertações, {S1 , ..., Sn }, e m professores disponı́veis para
participar em júris, {P1 , ..., Pm }. O problema da constituição dos júris deve respeitar as
seguintes restrições:

• Cada professor Pj , com 1 ≤ j ≤ m, pode participar em no máximo lj júris;

• Cada júri deve ser constituı́do por três professores.

Admita que o problema tem solução, isto é, que, dadas as disponibilidades dos profes-
sores, é possı́vel constituir o júri de todos os alunos. Pretende-se agora calcular uma
atribuição de professores a júris.

1. Modele o problema da constituição de júris como um problema de fluxo máximo.

A resposta deve incluir o procedimento utilizado para determinar a constituição
dos júris a partir do fluxo calculado.

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 alunos, n, e número de professores, m).
Nota: De entre os algoritmos de fluxo estudados nas aulas deve escolher aquele
que garanta a complexidade assimptótica mais baixa para o problema em questão.

Solução:

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

consideramos um vértice por professor, um vértice por estudantes e dois vértices
adicionais s e t, respectivamente a fonte e o sumidouro. Formalmente:

• V = {Si | 1 ≤ i ≤ n} ∪ {Pj | 1 ≤ i ≤ m} ∪ {s, t}

•
E = {(s, Pj , lj ) | 1 ≤ j ≤ m} Pj só pode participar em lj defesas
∪ {(Pj , Si , 1) | j ∈ SP(i)} Pj pode participar no júri do estudante Si
∪ {(Si , t, 3) | 1 ≤ i ≤ n} 3 membros por júri

Como sabemos que é possı́vel formar todos os jurı́s, concluı́mos que o fluxo máximo
é 3.n. Uma vez calculado o fluxo máximo, f ∗ , o júri do aluno Si é constituı́do pelos
professores Pj1 , Pj2 e Pj3 tais que: f ∗ (Pj1 , Si ) = 1, f ∗ (Pj2 , Si ) = 1, e f ∗ (Pj3 , Si ) =
1.

2. Complexidade.

• |V | = n + m + 2 ∈ O(n + m)
• |E| = m + m.n + n ∈ O(n.m)
• |f ∗ | ≤ 3n ∈ O(n)
• Ford-Fulkerson: O(n2 .m)
• RF: O((n + m)3

A melhor solução consiste em usar um algoritmo baseado no método de Ford

Fulkerson.

7/8
II.c) Uma matriz de incompatibilidades é uma matriz quadrada cujas células guardam
valores decimais entre 0 e 1. Intuitivamente, dada uma matriz de incompatibilidades
M , n × n, a célula Mij guarda a incompatibilidade entre os ı́ndices i e j; Mij = 0 se i e
j são completamente compatı́veis e Mij = 1 se i e j são completamente incompatı́veis.
Dado um sub-conjunto
P de ı́ndices I ⊆ {1, ..., n}, o nı́vel de incompatibilidade do conjunto
é dado por: i,j∈I Mij . O problema das incompatibilidades define-se formalmente da
seguinte maneira:

Incompat = {hM, k, vi | M contém um sub-conjunto de ı́ndices

de tamanho k e incompatibilidade igual ou inferior a v}

1. Mostre que o problema Incompat está em NP.

2. Mostre que o problema Incompat é NP-difı́cil por redução a partir do problema

ISet, que é sabido tratar-se de um problema NP-completo e que se define em
baixo. Não é necessário provar formalmente a equivalência entre os dois problemas;
é suficiente indicar a redução e a respectiva complexidade.
Pista: Dado um grafo G indique como construir uma matriz de incompatibilidades
cujos ı́ndices correspondem aos vértices de G tendo em conta o problema ISet.

Problema ISet: Seja G = (V, E) um grafo não dirigido; dizemos que V ′ ⊆ V é um

conjunto de vértices independentes em G se e apenas se ∀u, v ∈ V ′ .(u, v) 6∈ E. O
problema ISet define-se formalmente da seguinte maneira:

ISet = {hG, ki | G contém um conjunto de vértices independentes de tamanho k}

Solução:

1. O algoritmo de verificação recebe como input uma possı́vel instância hM, k, vi e

um conjunto
P de ı́ndices I (o certificado). O algoritmo tem de verificar que |I| = k
e que i,j∈I Mij ≤ v. Observamos os certificados têm tamanho O(n) e que a
verificação se faz em tempo O(n2 ), o tempo de calcular o somatório.

2. Dada uma possı́vel instância hG, ki do problema ISet, começamos por construir
uma matriz de incompatibilidades MG cujos ı́ndices correspondem aos vértices de
G. Para tal, admitimos que |V | = n e que os vértices de V estão numerados de
1 a n, sendo vi o i-ésimo vértice. Assim sendo, definimos a matriz MG como se
segue: 
1 se (vi , vj ) ∈ E
(MG )ij =
0 caso contrário
Uma vez estabelecida a matriz MG , a redução é definida da seguinte maneira:

f (hG, ki) = hMG , k, 0i

• Equivalência a estabelecer: hG, ki ∈ ISet ⇐⇒ hMG , k, 0i ∈ Incompat

• Complexidade da redução: O(|V |2 ).

Número: Nome: 8/8