Construção e Análise de Algoritmos

lista de exercı́cios X3

1. Faixa máxima de elementos distintos

Imagine que você tem uma lista que pode ter elementos repetidos.
Por exemplo,

(. . . )

A tarefa consiste em

→ Identificar a maior faixa de elementos consecutivos sem repetição

No exemplo acima, isso nos daria

(. . . )

Apresente um algoritmo que resolve esse problema.

E analise o tempo de execução do seu algoritmo.

2. Antenas de celular
Ao longo de uma estrada bem comprida existem diversos vilarejos isolados.
Alguns desses vilarejos estão próximos uns dos outros, mas às vezes você pode andar kilometros
sem encontrar um pé de gente.

x x xx x x x x xx x
`1 `2 `3 . . . ... `n

Mas, apesar de viverem isolados, as pessoas desses lugares também usam celular.
E para usar celular é preciso ter sinal.
Daı́ que, o problema consiste em determinar localizações ao longo da estrada para a instalação
de antenas de celular, de modo que todos os vilarejos tenham cobertura.
Cada antena possui um raio de cobertura de 4 km, e ela não precisa ser instalada exatamente no
local de um vilarejo.
O objetivo, claro, é resolver o problema utilizando o menor número possı́vel de antenas.
Você recebe uma lista L com as localizações dos vilarejos.
E deve retornar uma lista A com as localizações das antenas.

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.

1
3. Variante do problema das antenas de celular

Agora imagine que existem dois tipos de antenas

- antenas com raio de alcance de 4 km, que possuem custo k > 1

- antenas com raio de alcance de 8 km, que possuem custo k + 1

O objetivo nessa variante, claro, é minimizar o custo total das antenas na solução.
E a solução consiste não apenas nas localizações das antenas, mas também do tipo de antena
que será instalada em cada lugar.

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.

4. Minimizando o número de atividades

Imagine que existe apenas um laboratório no departamento de computação.

E imagine que cada um dos n professores do departamento tem uma atividade para realizar no
laboratório.

Imagine também que o chefe de departamente está aborrecido com os seus colegas, e quer difi-
cultar as coisas.
Daı́ que, ele tem a ideia de alocar o menor número de atividades possı́vel no laboratório.
Mas, ele não pode deixar uma atividade de fora se o laboratório estiver livre durante o seu
intervalo de realização.
Mais especificamente, a tarefa consiste em

→ Selecionar um subconjunto de atividades de tamanho mı́nimo de modo que

toda atividade que não está no subconjunto seja incompatı́vel com
alguma atividade que está lá

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.

5. Minimizando o número de laboratórios

Agora imagine que existe um grande número de laboratórios disponı́veis no departamento.

E imagine que todas as atividades podem ser alocadas em algum laboratório.
A tarefa consiste em

2
 → Alocar as atividades aos laboratórios de modo que o menor número possı́vel
de laboratórios seja utilizado

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.

6. Partição de palı́ndromos

Lembre que um palı́ndromo é uma palavra que é a mesma coisa quando lida em ambas as direções.
Por exemplo,

o v o, o s s o, a r a r a, r e v i v e r, a n i l i n a, etc

Agora imagine que você recebe uma longa lista de lebras.

Por exemplo,

a b a b b b a b b a b a b a

A tarefa consiste em

→ Quebrar a sequência no menor número de pontos possı́vel

de modo que cada segmento é um palı́ndromo

No exemplo acima, nós terı́amos o seguinte

a | b a b b b a b | b | a b a b a

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.

7. O problema do roupeiro

O futebol é democrático: todos podem jogar, tanto os baixinhos como os grandões.

Mas, isso acaba gerando um problema para o roupeiro.
Quer dizer, como hoje em dia os times trocam de jogadores o tempo todo, não dá para ficar
comprando uniformes novos a toda hora — (ao menos na 2a divisão)
Por outro lado, também não pega bem jogar com a roupa muito apertada, nem com os calções
lá embaixo nos joelhos.
E é aqui que aparece o problema do roupeiro.
Mais especificamente, dado um conjunto de jogadores que vestem os tamanhos

t1 , t2 , t3 , . . . , tn

3
 e uma coleção de uniformes com os tamanhos

u1 , u2 , u3 , . . . , um

com m ≥ n, o problema consiste em distribuir uniformes para o jogadores de modo a minimizar

a seguinte função objetivo
1 P
2
· i ti − u(i)
n
onde u(i) é o uniforme dado ao i-ésimo jogador. (A ideia dessa função objetivo é que ninguém
fique com um uniforme de tamanho muito diferente do seu.)

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.

8. Armazenamento na nuvem

Imagine que você deseja disponibilizar um arquivo na internet, e você tem n servidores S1 , . . . , Sn
à sua disposição.
O padrão de acesso ao arquivo é o seguinte:

→ se um acesso é feito ao servidor Si e o arquivo não está lá,

então os servidores Si+1 , Si+2 , . . . serão tentados em seguida nessa ordem

Para a coisa funcionar, é claro, é preciso que o servidor Sn tenha uma cópia do arquivo.
Mas você deve escolher outros servidores para armazenar o arquivo de modo a minimizar a soma
dos seguintes componentes de custo:

• C1 (j): custo de armazenamento do arquivo no servidor Sj

• C2 (j): custo de acesso associado ao servidor Sj , definido como o número de servidores

que serão consultados em seguida caso o arquivo não esteja lá

O custo de armazenamento C1 (j) associado a cada servidor Sj é conhecido.

E o custo de acesso C2 (j) para cada servidor depende dos lugares onde você vai armazenar o seu
arquivo.
A tarefa consiste em

→ Encontrar um subconjunto T de servidores para armazenar uma cópia do arquivo,

minimizando a função
X
C1 (j) + C2 (j)
Sj ∈T

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.

4
9. Minimizando o custo máximo

Em alguns casos, pode ser conveniente minimizar o custo da aresta de maior custo na árvore
geradora, ao invés da soma total dos custos.
Nesse caso, nós poderı́amos chamar a árvore resultante de uma árvore geradora de custo máximo
mı́nimo.

a) É o caso que toda árvore geradora de custo máximo mı́nimo é também uma árvore geradora
mı́nima?
Prove ou dê um contra-exemplo.

b) É o caso que toda árvore geradora mı́nima é também uma árvore geradora de custo máximo
mı́nimo?
Prove ou dê um contra-exemplo.

10. Árvores geradoras para grafos direcionados

Na variante do problema da AGM para grafos direcionados, além do grafo G = (V, E) com pesos
(positivos) associados às arestas, nós também temos um vértice r ∈ V designado como raiz.
Uma árvore geradora para o grafo G com raiz r é uma coleção de arestas S que contém caminhos
do vértice r para todos os outros vértices do grafo.
Por exemplo,

1 1
• • • •
2 1 r 3 2 r 3 2

7
•
4
⇒ 7
•

• 2 • • •
1 7 7
• •

O objetivo do problema é encontrar uma árvore geradora para G, r com peso total mı́nimo.

a) A adaptação do algoritmo de Prim para esse problema seria o seguinte

- coloque o vértice r em A, e defina N = V − r

- a cada passo, selecione uma aresta (v → w) de peso mı́nimo,
onde v ∈ A e w ∈ N, e passe o vértice w para o conjunto A

Esse algoritmo encontra uma solução ótima para o problema?

Prove ou dê um contra-exemplo.
— (Assuma que existem caminhos de r para todos os outros vértices do grafo)

b) A adaptação do algoritmo de Kruskal para esse problema considera as arestas do grafo em

ordem crescente de peso
a1 , a2 , a3 , . . . , am

e faz uso da seguinte observação:

5
 → Uma árvore geradora mı́nima para G, r não contém arestas chegando em r.
Isso é óbvio.
E ela contém no máximo uma aresta chegando em cada vértice v 6= r.
A razão é simples: se S é uma árvore geradora G, r com duas arestas chegando em
v, então removendo uma dessas arestas nós obtemos uma coleção S 0 que ainda é uma
árvore geradora para G, r e tem peso menor que S.

Daı́ que, a ideia do algoritmo é percorrer a lista de arestas em ordem crescente de peso, e
selecionar a aresta aj = (v → w) caso ainda não exista nenhuma aresta em S que chega no
vértice w.

Esse algoritmo encontra uma solução ótima para o problema?

Prove ou dê um contra-exemplo.

c) Caso nenhum dos dois algoritmos acima é correto e ótimo, faça os ı́tens abaixo.

c1) Apresente um algoritmo que resolve esse problema em tempo polinomial.

c2) Argumente que o seu algoritmo sempre produz uma solução correta e ótima.

11. Caminhos mais curtos com cidades fantasma

Imagine que o grafo G representa o mapa de uma certa região, onde os vértices correspondem às
cidades, e as arestas corresponde a estradas entre essas cidades.
Imagine que existem marcações de distância associadas a cada aresta.
E imagine que algumas cidades são marcadas como cidades fantasma.
A tarefa consiste em

→ Encontrar caminhos mais curtos do vértice v para todos os outros vértices

que passam por no máximo uma cidade fantasma
— (assuma que v não é uma cidade fantasma)

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E argumente que ele encontra uma solução ótima para o problema.

12. Controlando o telescópio

O laboratório de astronomia da universidade possui um telescópio sofisticado de alta precisão.

Como o equipamento é bastante sensı́vel, ele se desloca muito lentamente de uma posição para
outra: apenas o ângulo de 1o por minuto.
A cada dia existe uma sequência de eventos que podem ser observados no céu

e1 , e2 , e3 , ... ..., en

6
 ordenados pelo instante em que eles vão ocorrer.
Para observar o j-ésimo evento, o telescópio deve estar na posição correta no instante ej (e, por
simplicidade, nós podemos assumir que a observação é instantânea).
Mas, em geral, não é possı́vel mover o telescópio rápido o suficiente para poder observar todos
os eventos.
Daı́ que o problema consiste em escolher um subconjunto de eventos para serem observados

ei1 , ei2 , ..., eik

com base em uma matriz D = [dij ] que informa a distância angular dij entre os eventos ei , ej .
Além disso, nós também assumimos que no instante e0 (algum momento anterior a e1 ) o telescópio
se encontra na posição angular 0, e que no final do dia (algum momento en+1 posterior a en ) o
telescópio deve estar de volta na posição angular 0.
A matriz D também fornece distâncias d0j da posição angular 0 para cada evento ej .
O objetivo, claro, é observar o maior número de eventos possı́vel.

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.

13. Prioridade para todos (acima de 80 anos)

A administração superior da universidade adotou como prioridade para a sua gestão dar priori-
dade aos idosos em todos os espaços e atividades da UFC.
E o centro de supercomputação atendeu prontamente ao chamado lançando o programa: “O
programa da vovó tem prioridade”.
Quer dizer, todos os dias o centro de supercomputação recebe uma lista de solicitações de pro-
gramas para serem executados no supercomputador.
A polı́tica padrão sempre foi tentar minimizar o tempo médio de espera:

1 X
· Tj
n
j

onde Tj é o tempo de espera do j-ésimo programa (veja a nota adicional da aula 16).
Mas agora as coisas vão ser diferentes.
Quer dizer, no formulário de solicitação a pessoa deve indicar se ela tem mais de 80 anos.
Daı́, os programas são agrupados em dois conjuntos

P = {p1 , . . . , pm } V = {v1 , . . . , v` }

onde V contém os programas das pessoas idosas, e P contém os demais programas.

A prioridade associada aos programas no grupo V é estabelecida pela seguinte regra

RV : Enquanto houverem programas para executar no conjunto V,

7
 o número de programas já executados do conjunto P deve ser menor ou igual
o número de programas já executados do conjunto V

Por exemplo, se P = {p1 , p2 , p3 } e V = {v1 , v2 , v3 }, então as seguintes ordens de execução são

todas válidas:

• (v1 , v2 , v3 , p1 , p2 , p3 ) • (v3 , p2 , v1 , p1 , v2 , p3 ) • (v1 , v3 , p3 , v2 , p2 , p1 )

mas a seguinte ordem é inválida

• (v1 , p1 , p3 , v3 , v2 , p2 )

O problema consiste em encontrar uma ordem de execução para os programas que

→ obedece a regra RV
→ minimiza o tempo médio de espera

Apresente um algoritmo que resolve esse problema.

Analise o tempo de execução do seu algoritmo.
E se for o caso, argumente que o seu algoritmo encontra uma solução ótima para o problema.