Re: [obm-l] Algoritmo de Graham

[Carlos Maçaranduba <soh_lamento@xxxxxxxxxxxx>]

para nota de esclarecimento ,"scheduling" em portugues
é escalonamento......esse problema é interessante para
computaçao pois a CPU dos computadores possui uma
politica de escalonamento para os programas em
execuçao(mais neste caso é uma maquina só, a CPU).Se
eu nao me engano esse problema é NP e o que a turma
tenta fazer é se aproximar polinomialmente da soluçao
otima.Nesse caso, o algoritmo de Graham é 33% mais
custoso. 

 --- Claudio Buffara <claudio.buffara@terra.com.br>
escreveu: > Oi, Pessoal:
> 
> O Domingos Jr. me falou de um problema interessante,
> envolvendo o algoritmo
> de Graham para "scheduling" (qual a palavra em
> portugues?):
> 
> Suponha que vc tem m máquinas idênticas e n tarefas
> (cujo tempo de execução
> está num vetor v[1..n] de reais positivos).
> O algoritmo de Graham é assim:
> - ordene v de forma decrescente (v(1) >= v(2) >= ...
> >= v(n));
> - na i-ésima (1 <= i <= n) iteração aloque a i-ésima
> tarefa na máquina mais
> livre (aquela cuja soma dos respectivos v(k)'s é a
> menor de todas)
> (se há empate coloque na máquina de índice menor,
> por exemplo).
>  
> Mostre que o algoritmo acima sempre dá uma solução
> cujo tempo de execução é
> no máximo igual a 4/3 do ótimo.
>  
> Um abraco,
> Claudio.
> 
>
=========================================================================
> Instruções para entrar na lista, sair da lista e
> usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>
========================================================================= 

Yahoo! Mail - o melhor webmail do Brasil
http://mail.yahoo.com.br
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================