Complexidade de Algoritmos

Prévia do material em texto

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
INF05515 – Complexidade de Algoritmos
2014/1
Profa. Mariana Kolberg
Lista de Exerćıcios Sobre Algoritmos Gulosos
1. (Escalonamento)
Considere o problema de escalonamento de n jobs de duração t1, ..., tn para que sejam executados
em um processador. Os jobs podem ser executados em qualquer ordem, um job por vez. O tempo
gasto por um job é a soma do tempo de execução dele com o tempo que ele precisou esperar para
executar. Por exemplo: você tem dois jobs com tempos de execução 5 para cada um, o tempo
gasto pelo primeiro job é 5 e o segundo é 5+5=10. Desta forma o tempo gasto é de 15.
a) Descreva um algoritmo guloso que minimiza o total de tempo gasto por todos os jobs no
sistema.
2. (Grafos) Para as afirmações abaixo, decida se ela é verdadeira ou falsa. Caso seja verdadeira,
justifique. Caso seja falsa, dê um contraexemplo.
a) Supondo que temos uma instância do problema da árvore geradora mı́nima com um grafo G,
com arestas com todos os custos positivos e diferentes. T é a árvore geradora mı́nima para esta
instância. Agora suponha que nós substituimos todas as arestas de custo ce por seu quadrado,
(ce)
2, criando uma nova instância para o problema, com o mesmo grafo mas diferentes custos.
Neste caso, T continuará sendo a AGM para a nova instância. Verdadeiro ou falso?
b) Supondo que nós temos uma instância para o problema do caminho mais curto do vértice s para
t em um grafo direcionado G. Nós assumimos que todos os custos das arestas são positivos
e distintos. P é o caminho de custo mı́nimo para esta instância. Agora suponha que nós
substituimos cada custo ce das arestas por seu quadrado (ce)
2, criando uma nova instância
com o mesmo grafo mas diferentes custos. Neste caso, P continua sendo o caminho de custo
mı́nimo para a nova instância. Verdadeiro ou falso?
3. (Soma) Dado um conjunto N de números naturais ai para i = 1..n (N = a1, a2, a3, ..., an),
encontrar uma permutação dos elementos em N que minimize a soma 1∗a1+2∗a2+3∗a3+...+n∗an.
Descreva um algoritmo guloso que resolva este problema. Justifique sua resposta.
(a) Desenvolva um algoritmo guloso que resolva este problema.
(b) Argumente o porque o algoritmo é correto.
4. (Problema da Mochila fracionária) Considere um conjunto de elementos S = s1, s2, ..., sn. Cada
elemento si possui dois valores associados que se referem ao peso pi e ao custo do elemento ci.
Suponha que alguns elementos serão inseridos numa mochila que suporta no máximo um peso
P . Considere o problema fracionário, ou seja, um elemento pode ser selecionado por inteiro, ou
apenas uma fração do mesmo pode ser inserida na mochila.
(a) Desenvolva um algoritmo guloso que seleciona um conjunto de elementos cuja soma dos seus
custos seja máxima, respeitando a capacidade de peso da mochila. O algoritmo deve retornar
informação sobre que elementos foram selecionados, e qual a fração usada de cada um.
(b) Analise o seu algoritmo.
(c) Argumente o porque o algoritmo é correto.
5. (Troco em moedas) Considere o problema de fazer a troca de K centavos usando o menor número
de moedas. Suponha que o valor de cada moeda seja um inteiro. Suponha que as moedas
dispońıveis tenham as denominações que são potências de c, isto é, as denominações são c0, c1,
..., cn para inteiros c > 1 e n ≥ 1.
(a) Para moedas de valores R$ 3, R$ 1, R$ 9, qual o número mı́nimo de moedas para fornecer
troco para R$ 52?
(b) Descreva um algoritmo guloso que efetue a troca consistindo em n valores de moedas diferentes.
O algoritmo recebe como entrada um conjunto de n moedas e K.
(c) Analise seu algoritmo.
(d) Argumente porque o seu algoritmo sempre produz uma solução ótima.
v–revision– 1