Re: [obm-l] Cramer vs Eliminacao

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 26.05.04 18:08, Nicolau C. Saldanha at nicolau@mat.puc-rio.br wrote:

> On Wed, May 26, 2004 at 03:44:34PM -0300, Claudio Buffara wrote:
>> Oi, pessoal:
>> 
>> Multiplicaoes e divisoes sao operacoes muito mais demoradas numa CPU do que
>> somas e subtracoes. Assim, para se determinar a eficiencia de um dado
>> algoritmo, eh usual que se estime apenas o numero de multiplicaoes e/ou
>> divisoes que ele requer.
>> 
>> Pra ter uma ideia do quanto a regra de Cramer eh ineficiente pra se resolver
>> sistemas lineares, calcule o seguinte:
>> 
>> 1) Quantas multiplicacoes e/ou divisoes sao necessarias para se resolver um
>> sistema linear n x n (suposto consistente)?
>> 
>> 2) Qual o numero maximo de multiplicacoes e/ou divisoes necessarias para se
>> resolver o mesmo sistema via eliminacao gaussiana (escalonamento)?
> 
> É difícil fazer esta comparação direito se não soubermos qual algoritmo
> vai ser usado para calcular os determinantes na fórmula de Cramer.
> Uma boa maneira de calcular determinantes é justamente fazer
> eliminação gaussiana na matriz, e neste caso Cramer fica sendo
> quase exatamente n vezes mais lento do que usar diretamente
> eliminação gaussiana no sistema.
> 
> Existem algoritmos mais lentos para calcular o determinante
> (por exemplo: olhar para todas as permutações ou expandir
> recursivamente por linhas ou colunas) mas eu não acho que
> seja justo medir a eficiência de Cramer usando um algoritmo ineficiente
> para calcular o determinante.
> 
> []s, N.

Justo. Mas mesmo assim fica proposto o problema (razoavelmente facil):
Expandindo os determinantes pela definicao (somas dos produtos com sinal),
quantas multiplicacoes/divisoes sao necessarias?
E a parte 2 dah uma cota superior interessante (que por acaso eu nao
calculei ainda).

[]s,
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
=========================================================================