Universidade Federal do Rio Grande do Sul INF05515 – Complexidade de Algoritmos

Instituto de Informática 2025/1

Departamento de Informática Teórica André Grahl Pereira

Lista 2
ˆ Os exercı́cios podem ser resolvidos com colaboração, mas a entrega é individual informando even-
tuais colaboradores.
ˆ A entrega é feita pelo Moodle com um único arquivo em formato PDF preferencialmente não
escrito a mão. Se escrito a mão a letra deve ser legı́vel.

ˆ O nome do arquivo deve ser “l2 número do cartão do aluno”. Exemplo: “l2 [Link]”.

ˆ As folhas de respostas devem conter a resolução das questões na ordem apresentada no enunciado.

ˆ Para receber pontos todas as respostas devem ser justificadas.

ˆ Somente entregue respostas se você sabe explicar pessoalmente.

Observação.
Para a questões 3 até 5, e 8 até 10, espera-se uma prova de corretude do algoritmo e uma análise do
tempo de execução em função do tamanho da entrada.

Questão 1.
Encontre a árvore geradora mı́nima do seguinte grafo. Aplique o algoritmo de Prim: apresente a
execução do algoritmo com os vértices e suas chaves na fila de prioridades em cada iteração do algoritmo.

12 7 3
A B C D

13 2 8 4 9 1 10

5 11 6
E F G H

Questão 2.
Dado um grafo não direcionado, armazenado em uma lista de adjacência, G = (V, E) com arestas com
custos positivos e sua árvore geradora mı́nima A = (V, T ). Suponha que uma aresta e ∈ E tem seu
custo modificado de ce para c′e . Para cada caso apresente um algoritmo linear que atualiza a árvore
geradora mı́nima A. Prove que o algoritmo é correto.

/ T e ce < c′e .
(a) e ∈
/ T e ce > c′e .
(b) e ∈

Questão 3.
Considere dois vetores A e B de tamanho n com números inteiros positivos e um número inteiro k.
Você pode escolher um elemento i de A e um elemento j de B com 1 ≤ i, j ≤ n, para troca-los de vetor.
Assim, ai se torna bj , e bj se torna ai . Apresente um algoritmo o(n2 ) que fazendo no máximo k trocas
maximiza a soma dos elementos no vetor B.
Universidade Federal do Rio Grande do Sul INF05515 – Complexidade de Algoritmos
Instituto de Informática 2025/1
Departamento de Informática Teórica André Grahl Pereira

Questão 4.
Considere um vetor A com n números inteiros positivos e um número inteiro k. Apresente um al-
goritmo o(n2 ) que seleciona o maior número de elementos A de forma que a soma dos elementos
selecionados é menor ou igual a k.

Questão 5.
Suponha que existem n processos com rótulos de 1, . . . n para serem executados em uma máquina que
executa um único processo por vez. O processo i usa tempo ti para ser executado. A máquina executará
processos definidos por um escalonamento que pode ser descrito por uma permutação dos processos.
Seja Ci o tempo de término do processo i. Se o processo j é o primeiro a ser completado, então seu tempo
de término será Cj = tj (assuma que a execução dos processos inicia no tempo zero). Se o processo k é
o segundo processos a ser executado, então seu tempo de término será Ck = Cj + tk = tj + tk e assim
por diante. Cada processo possui uma prioridade denotada por um peso wi (para o processo Pni). Assim
temos como objetivo minimizar a soma ponderada dos tempos de término dos n processos i=1 wi · Ci .
Apresente um algoritmo de tempo O(nlog n) que resolve esse problema. São dados um conjunto de n
processos com tempo de execução ti e peso wi (assuma que ti , wi são inteiros positivos). Determine
uma ordenação de execução dos processos que minimiza a soma ponderada dos tempos de término.

Questão 6.
Suponha que existe uma penalidade de 1 para cada gap e uma penalidade de 2 para o alinhamento
de dois sı́mbolos diferentes. Determine o custo do alinhamento das sequências AGCTCC e AGTCAC.
Apresente a matriz resultante da aplicação do algoritmo de alinhamento de sequências e o alinhamento
obtido.

Questão 7.
Determine o custo do caminho mı́nimo de s até t no seguinte grafo G = (V, E) onde V = {s, u, v, w, t} e
E = {(s, v, 4), (s, u, 2), (u, v, −1), (u, w, 2), (v, t, 4), (w, t, 2)}. Apresente a matriz resultante da aplicação
do algoritmo de Bellman-Ford e o caminho mı́nimo obtido.

Questão 8.
Uma subsequência contı́gua de uma lista S é uma subsequência composta de elementos consecutivos
em S. Apresente um algoritmo de tempo O(n) para resolver o seguinte problema. Dado uma lista
de números a1 , a2 , . . . , an determinar a subsequência contı́gua de soma maxima (uma subsequência de
tamanho zero tem soma zero).

Questão 9.
Considere um vetor A = ⟨a1 , a2 , . . . , an ⟩ de números de inteiros positivos. Apresente um algoritmo O(n)
que encontra o valor de uma subsequência de A com ⟨ai1 , ai2 , . . . , aik ⟩ onde i1 < i2 < · · · < ik que
maximiza a seguinte soma ai1 − ai2 + ai3 − ai4 + · · · ± aik .

Questão 10.
Considere um grafo G = (V, E) com vértices V e arestas E, onde G é uma árvore e cada vértice v ∈ V
tem um peso wv . Assuma que a árvore é enraizada em algum vértice r que define a noção de pais e filhos
na árvore, e que C(v) para v ∈ V seja o conjunto de filhos do vértice v. Apresente um algoritmo O(n)
para uma árvore com n vértices que encontra o peso de um conjunto independente de peso máximo.
Universidade Federal do Rio Grande do Sul INF05515 – Complexidade de Algoritmos
Instituto de Informática 2025/1
Departamento de Informática Teórica André Grahl Pereira

Questão 11.
Explique com detalhes e dê um exemplo ilustrativo para cada redução A ≤p B abaixo. Devido a
redução, o que pode-se afirmar sobre o problema B?

3-SAT ≤p k-Clique

ˆ Entrada de 3-SAT: Um conjunto de variáveis x1 , x2 , . . . , xn e um conjunto de cláusulas C1 , C2 , . . . , Cm ,

onde cada cláusula é uma disjunção de literais (variáveis ou suas negações).
ˆ Pergunta de 3-SAT: Existe uma atribuição de valores (verdadeiro ou falso) para as variáveis
de forma que Φ = C1 ∧ C2 ∧ . . . Cm seja verdadeiro?

ˆ Entrada de k-Clique: Um grafo não direcionado G = (V, E) e um número k.

ˆ Pergunta de k-Clique: Existe um conjunto C de k vértices em G tal que todo par de vértices
em C está conectado por uma aresta?

Questão 12.
Explique com detalhes e dê um exemplo ilustrativo para cada redução A ≤p B abaixo. Devido a
redução, o que pode-se afirmar sobre o problema B?

k-Clique ≤p Conjunto Independente (Independent Set)

ˆ Entrada de k-Clique: Um grafo não direcionado G = (V, E) e um número k.

ˆ Pergunta de k-Clique: Existe um conjunto C de k vértices em G tal que todo par de vértices
em C está conectado por uma aresta?

ˆ Entrada de Conjunto Independente: Um grafo não direcionado G′ = (V ′ , E ′ ) e um número

k.

ˆ Pergunta de Conjunto Independente: Existe um subconjunto S ⊆ V ′ tal que |S| = k e

nenhum par de vértices em S está conectado por uma aresta?

Questão 13.
Dado um grafo G = (V, E), um ciclo de G é Hamiltoniano se passar por todos os vértices do grafo.
Analogamente, um caminho que passa por todos os vértices é Hamiltoniano.
(a) Considerando que é NP-Completo o problema de decidir se um grafo tem um caminho Hamiltoniano,
mostre que o problema de decidir se um grafo tem um ciclo Hamiltoniano é também NP-completo.

(b) Considerando que é NP-Completo o problema de decidir se um grafo tem um ciclo Hamiltoniano,
mostre que o problema de decidir se um grafo tem um caminho Hamiltoniano é também NP-
completo.
Utilize reduções para demonstrar os itens acima.

Questão 14.
Suponha que X, Y , e Z são problemas com as seguintes propriedades:
ˆ O problema X é NP-Difı́cil.

ˆ Y ≤p SAT e SAT ≤p Y .
Universidade Federal do Rio Grande do Sul INF05515 – Complexidade de Algoritmos
Instituto de Informática 2025/1
Departamento de Informática Teórica André Grahl Pereira

ˆ Z pertence a P.

Para cada afirmação abaixo, determine se ela é verdadeira, falsa, ou desconhecida. Justifique sua
resposta.
(a) X ≤p SAT.
(b) Z ≤p X.

(c) Y ≤p X.