Sexta-feira, 17 de Março de 2006
Conjectura de Poincaré
Texto interessante sobre a Conjectura de Poncaré, citada na última aula de FM (o acesso é restrito, mas a revista existe na biblioteca do IFGW).
- Collins, GP "The Shapes of Space." Sci. Amer. 291, 94-103, July 2004.
Comments:
Links to this post:
<< Home
É interessante tomar consciência dos problemas que inquietam a mente dos matemáticos nos dias de hoje, como a Conjectura de Poincaré. Um outro artigo, também da Scientific American (versão brasileira), de Dezembro de 2005, fala da questão P = NP?, relacionado com soluções polinomiais e não polinomiais para problemas. Vale a pena dar uma conferida (talvez algum dia a gente realmente entenda porque não pode usar a Regra de Cramer...).
Uma boa fonte de informações sobre o problema que o Antonio comenta pode ser encontrada aqui. Há de tudo, desde papers técnicos impenetráveis até textos elementares e de divulgação. Boa leitura!
O problema não é exatamente da Regra de Cramer, mas da fórmula de Laplace para o determinante.
Para ter idéia dos problemas, façam a seguinte comparação:
1) Calcule quantas operações são necessárias para de escalonar uma matriz geral (o pior caso) n x n. Operações, aqui, são somas e multiplicações de números reais.
2) Calcule, agora, quantas operações seriam necessárias para se calcular um determinante de uma matrix n x n usando-se a fórmula de Laplace.
3) Compare os resultados! Suponha que voce tivesse que resolver um sistema 1000 x 1000. Suponha que seu super-pentium-7 fosse capaz de fazer cada operação em 1 micro segundo. Quanto tempo voce gastaria para escalonar essa matriz? E para calculuar seu determinante usando-se Laplace?
Para ter idéia dos problemas, façam a seguinte comparação:
1) Calcule quantas operações são necessárias para de escalonar uma matriz geral (o pior caso) n x n. Operações, aqui, são somas e multiplicações de números reais.
2) Calcule, agora, quantas operações seriam necessárias para se calcular um determinante de uma matrix n x n usando-se a fórmula de Laplace.
3) Compare os resultados! Suponha que voce tivesse que resolver um sistema 1000 x 1000. Suponha que seu super-pentium-7 fosse capaz de fazer cada operação em 1 micro segundo. Quanto tempo voce gastaria para escalonar essa matriz? E para calculuar seu determinante usando-se Laplace?
Em tempo:
1 micro segundo = 0.000001 segundo.
Quem fizer aqui a comparação acima, da melhor maneira, ganha 500.000 micro pontos na nota do primeiro teste.
1 micro segundo = 0.000001 segundo.
Quem fizer aqui a comparação acima, da melhor maneira, ganha 500.000 micro pontos na nota do primeiro teste.
Acho que a minha resposta não vale nem 1 nano ponto, mas lá vai:
1)
Para o escalonamento de uma matriz nxn:
i. nº de somas = Cn,2
ii. nº de multiplicações = 2.Cn,2
iii. nº total de operações = 3.Cn,2
obs.: não fiz o escalonamento por Gauss-Jordan por precisar multiplicar pelo inverso (tempo da operação da divisão não foi informado).
2)
Para o teorema de Laplace:
i. para o cálculo do determinante de uma matriz 2x2 por Cramer, teremos 3 operações (duas multiplicações e uma soma);
ii. se utilizarmos o teorema de Laplace até chegarmos numa soma de determinantes 2x2, teremos n!/2 deteminantes 2x2;
iii. nº total de operações = (3n!/2) - 1 = 3n!/2;
obs.: ao invés da operação de potenciação para (-1)^(i+j) comparo a soma de i+j para determinar o sinal do cofator, ou seja:
n!/2 * 2 = n! operações (soma de i+j e módulo da divisão desta soma
por 2), nem vou somar isso aí...
3) para 1) teremos 3*1000!/(998!2!) = 1498500 operações, ou seja
1,498500 segundos de cálculo!(acho que fiz besteira...)
para 2) teremos 3*1000!/2 = 10^2567 operações!
ou seja, 10^2561 segundos de cálculo (10^2553 anos-luz!)
1)
Para o escalonamento de uma matriz nxn:
i. nº de somas = Cn,2
ii. nº de multiplicações = 2.Cn,2
iii. nº total de operações = 3.Cn,2
obs.: não fiz o escalonamento por Gauss-Jordan por precisar multiplicar pelo inverso (tempo da operação da divisão não foi informado).
2)
Para o teorema de Laplace:
i. para o cálculo do determinante de uma matriz 2x2 por Cramer, teremos 3 operações (duas multiplicações e uma soma);
ii. se utilizarmos o teorema de Laplace até chegarmos numa soma de determinantes 2x2, teremos n!/2 deteminantes 2x2;
iii. nº total de operações = (3n!/2) - 1 = 3n!/2;
obs.: ao invés da operação de potenciação para (-1)^(i+j) comparo a soma de i+j para determinar o sinal do cofator, ou seja:
n!/2 * 2 = n! operações (soma de i+j e módulo da divisão desta soma
por 2), nem vou somar isso aí...
3) para 1) teremos 3*1000!/(998!2!) = 1498500 operações, ou seja
1,498500 segundos de cálculo!(acho que fiz besteira...)
para 2) teremos 3*1000!/2 = 10^2567 operações!
ou seja, 10^2561 segundos de cálculo (10^2553 anos-luz!)
Vitor M,
sua resposta vale quase 5x10^8 nano pontos. Não conferi as contas, mas devem estar certas.
Porém, ano-luz é unidade de distância, não de tempo....
O desafio continua...
sua resposta vale quase 5x10^8 nano pontos. Não conferi as contas, mas devem estar certas.
Porém, ano-luz é unidade de distância, não de tempo....
O desafio continua...
Esqueci de contar as operações individualmente:
1)
Para o escalonamento de uma matriz nxn:
Através de uma matriz genérica calculei por indução o número de operações de somas e de multiplicações:
i. nº de operações de somas é n(n+1)(2n+1)/6 - n(n+1)/2
ii. nº de operações de multiplicações é n(n+1)(2n+1)/6
obs.: para chegar a estas fórmulas utilizei a fórmula da PA de a1=1 e r=1, para n termos; e uma fórmula da soma dos quadrados, é melhor escrever a seqüência: 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6.
iii. nº de operações total = n(n+1)(2n+1)/3 - n(n+1)/2 = (4n^3 + 3n^2 - n)/6
3) para 1) teremos (4*1000^3 + 3*1000^2 - 1000)/6 = 667166500 operações, ou seja, 11,12 minutos.
ps.:"Não se apoquente não" = Apoquente
1)
Para o escalonamento de uma matriz nxn:
Através de uma matriz genérica calculei por indução o número de operações de somas e de multiplicações:
i. nº de operações de somas é n(n+1)(2n+1)/6 - n(n+1)/2
ii. nº de operações de multiplicações é n(n+1)(2n+1)/6
obs.: para chegar a estas fórmulas utilizei a fórmula da PA de a1=1 e r=1, para n termos; e uma fórmula da soma dos quadrados, é melhor escrever a seqüência: 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6.
iii. nº de operações total = n(n+1)(2n+1)/3 - n(n+1)/2 = (4n^3 + 3n^2 - n)/6
3) para 1) teremos (4*1000^3 + 3*1000^2 - 1000)/6 = 667166500 operações, ou seja, 11,12 minutos.
ps.:"Não se apoquente não" = Apoquente
OK, ganhou. O n^3 apareceu...
E n^3 é muito menor que n! para n grande. Essa é a origem dos problemas com a fórmula de Laplace e, consequentemente, com a fórmula de Cramer.
Um problema como o escalonamento é dito de classe de complexidade "P", já que pode ser resolvido, para qualquer matriz n x n, em tempo polinomial (de ordem 3) em n, como mostrou o Vitor. Os problemas de classe "P" são "mais simples" que os de classe "E", aqueles que podem ser resolvidos em tempo exponencial, já que n^p < exp(n) para n suficientemente grande, não importa para que p. Um problema que precisa de um tempo n! para ser resolvido é muito pior que um problema "E", já que n! > exp(n) para n grandes. Chega a ser impraticável, como ficou claro nos cálculos do Vitor.
PS.: Só por curiosidade, o big bang ocorreu há não mais do que 15 bilhões (15 x 10^9) de anos atras.
E n^3 é muito menor que n! para n grande. Essa é a origem dos problemas com a fórmula de Laplace e, consequentemente, com a fórmula de Cramer.
Um problema como o escalonamento é dito de classe de complexidade "P", já que pode ser resolvido, para qualquer matriz n x n, em tempo polinomial (de ordem 3) em n, como mostrou o Vitor. Os problemas de classe "P" são "mais simples" que os de classe "E", aqueles que podem ser resolvidos em tempo exponencial, já que n^p < exp(n) para n suficientemente grande, não importa para que p. Um problema que precisa de um tempo n! para ser resolvido é muito pior que um problema "E", já que n! > exp(n) para n grandes. Chega a ser impraticável, como ficou claro nos cálculos do Vitor.
PS.: Só por curiosidade, o big bang ocorreu há não mais do que 15 bilhões (15 x 10^9) de anos atras.
E se... ("a la" super interessante)
fosse criado um método para se calcular determinantes mais rapidamente que o de Laplace? É possível?
fosse criado um método para se calcular determinantes mais rapidamente que o de Laplace? É possível?
Existe tal método. Veremos que o determinante não muda se aplicarmos certas operações elementares. Assim, podemos escalonar primeiro, e depois calcular o determinante da matriz triangular, que será o produto dos elementos da diagonal.
Postar um comentário
Links to this post:
<< Home
