skiller10 Posted March 4, 2012 Report Share Posted March 4, 2012 Boas, Alguém me consegue explicar ou indicar alguns bons sítios onde aprender como se multiplica matrizes e dada uma matriz de tamanho DXD, obter a sua i-ésima potência em O(D^3log(N)). Cumprimentos, skiller10 "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
pmg Posted March 4, 2012 Report Share Posted March 4, 2012 Wikipedia? MathWorld? exemplo What have you tried? Não respondo a dúvidas por PM A minha bola de cristal está para compor; deve ficar pronta para a semana. Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código! Link to comment Share on other sites More sharing options...
Warrior Posted March 4, 2012 Report Share Posted March 4, 2012 A multiplicação de matrizes está bem explicada nessa página. Para obteres a n-ésima potência em log(n) é só utilizar o mesmo algoritmo que utilizas para números. Consegues calcular k^n em O(log(n))? Link to comment Share on other sites More sharing options...
skiller10 Posted March 4, 2012 Author Report Share Posted March 4, 2012 Já entendi como funciona a multiplicação de matrizes, mas confirma-me se estou certo sff, exemplo: |1 1| 2 = |2 1| |1 0| |1 1| Sim consigo 😄 "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
Warrior Posted March 4, 2012 Report Share Posted March 4, 2012 Não consigo perceber o teu exemplo de multiplicação de matrizes. Pareces estar a multiplicar uma matriz por um número, mas ainda assim com resultado diferente. Link to comment Share on other sites More sharing options...
skiller10 Posted March 4, 2012 Author Report Share Posted March 4, 2012 No exemplo que fiz estou a multiplicar a matriz {{1,1},{1,0}} por ela própria, ou seja, a matriz ao quadrado. "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
Warrior Posted March 5, 2012 Report Share Posted March 5, 2012 Desculpa, perdi a fiada ao tópico. Sim, está bem multiplicada. Tenta resolver um "tribonacci" depois do Fibonacci, para ver se realmente percebeste a solução. Link to comment Share on other sites More sharing options...
skiller10 Posted March 5, 2012 Author Report Share Posted March 5, 2012 Não pensei muito mas pelo que percebi para um "tribonacci" que pelo que vi é uma sequência igual à de fibonacci mas em que um elemento é a soma dos três elementos anteriores será com o mesmo método, apenas com a alteração que a matriz será de três: Sequência: 1 1 2 4 7 13 ... Matriz: {{2,1,1},{1,1,0},{1,0,0}}^N |2 1 1|^N |1 1 0| |1 0 0| O meu raciocínio está correcto? "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
Warrior Posted March 5, 2012 Report Share Posted March 5, 2012 Podes multiplicar "à mão" (ou usar um qualquer programa para isso, como o excel..) a matriz por si própria algumas vezes e verificar se dá os resultados correctos. Digo isto porque assumo que já resolveste o teu problema inicial. PS: Consegues generalizar para N? Link to comment Share on other sites More sharing options...
skiller10 Posted March 5, 2012 Author Report Share Posted March 5, 2012 O problema inicial ainda não tive tempo para o implementar mas já fiz os cálculos para verificar que estava certo e perceber como funcionava. Vou implementar ainda hoje, se não houver nenhum imprevisto, e depois fazer o mesmo para o "tribonacci". Quanto ao generalizar para N parece-me fácil usando o mesmo raciocínio até agora, ou seja, para "quadribonacci" ficaria uma matriz: | f(n+3) f(n+2) f(n+1) f(n) | ^ N | f(n+2) f(n+1) f(n) f(n-1) | | f(n+1) f(n) f(n-1) f(n-2) | | f(n) f(n-1) f(n-2) f(n-3) | PS: peço desculpa pelo esquema um pouco confuso :x "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
Warrior Posted March 5, 2012 Report Share Posted March 5, 2012 Não me parece que seja isso. Aliás, a tua solução para o tribonacci não me parece correcta. (o primeiro elemento é 2?) Link to comment Share on other sites More sharing options...
djthyrax Posted March 6, 2012 Report Share Posted March 6, 2012 Pelo que percebi do teu post inicial, não sabes como multiplicar matrizes. Considerando 2 matrizes, A e B, 3x3, tens a matriz 3x3 C=A*B, em que os seus elementos c i,j (elemento j da linha i) são dados por (a i,1*b 1,j + a i,2*b 2,j + a i,3*b 3,j). Se quiseres mais informação sobre o uso de matrizes basta consultares os apontamentos de uma cadeira de Álgebra, se quiseres manda-me PM que arranjo-te uns. Para experimentares brincar um pouquinho com matrizes, usa o Matlab. http://www.math.osu.edu/~overman.2/matlab.pdf Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum! Link to comment Share on other sites More sharing options...
skiller10 Posted March 6, 2012 Author Report Share Posted March 6, 2012 Estive a ver e percebi como se multiplicam matrizes mas não percebi a solução do fibonacci bem 😄 Consegues-me explicar ou dar umas dicas para eu tentar entender? "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
pedrosorio Posted March 6, 2012 Report Share Posted March 6, 2012 A solução do Fibonnaci está explicada aqui: http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form Ao multiplicares o vector com os elementos (Fk+1; Fk) pela matriz [1 1; 1 0] obténs o vector (Fk+2, Fk+1) da sequência de fibonnaci. Percebes porquê? E percebes que se multiplicares várias vezes seguidas pela matriz obténs sucessivamente os vectores (Fk+3, Fk+2), (Fk+4, Fk+3), etc.? Não respondo a dúvidas por mensagem. Link to comment Share on other sites More sharing options...
skiller10 Posted March 6, 2012 Author Report Share Posted March 6, 2012 Obrigado pelos apontamentos djthyrax B) Ao multiplicares o vector com os elementos (Fk+1; Fk) pela matriz [1 1; 1 0] obténs o vector (Fk+2, Fk+1) da sequência de fibonnaci. Percebes porquê? Não, tive a ver o link que mandaste da wikipedia, e mais alguns sites sobre este assunto mas ainda não consegui perceber bem 😉 EDIT: Estive a fazer os cálculos em papel e já percebi. Na primeira posição do vector resultado (FK+2) vai aparecer a soma dos dois elementos do primeiro vector, visto a primeira linha da matriz ser {1,1}. A segunda posição do vector resultado (FK+1) vai ser o o valor da primeira posição do primeiro vector. Exemplo: |5| x |1 1| = |5*1 + 3*1| = |8| |3| |1 0| |5*1 + 3*0| |5| Certo? "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
pedrosorio Posted March 6, 2012 Report Share Posted March 6, 2012 É exatamente isso. Tem cuidado que a multiplicação faz-se Matriz x vector e não vector x Matriz, essa forma que colocaste não é válida (Em multiplicação matricial, AxB, o número de colunas da matriz A tem que ser igual ao número de linhas da matriz B). Consegues então perceber que vai gerar todos os elementos da sequência de fibonnaci, ao multiplicar por essa matriz sucessivamente? E para o caso do tribonnaci como seria? Não respondo a dúvidas por mensagem. Link to comment Share on other sites More sharing options...
skiller10 Posted March 6, 2012 Author Report Share Posted March 6, 2012 Consegues então perceber que vai gerar todos os elementos da sequência de fibonnaci, ao multiplicar por essa matriz sucessivamente? Sim, mas ainda não percebi muito bem como é que a matriz multiplicada por ela própria vai gerar todos os elementos, sei que gera e já fiz os cálculos para testar, mas não percebi muito bem a lógica. E para o caso do tribonnaci como seria? Para um"tribonacci" seria: |1 1 1| x | f(n+2) | = | f(n+3) | |1 0 0| | f(n+1) | | f(n+2) | |0 1 0| | f(n) | | f(n+1) | Certo? "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
pedrosorio Posted March 6, 2012 Report Share Posted March 6, 2012 Sim, mas ainda não percebi muito bem como é que a matriz multiplicada por ela própria vai gerar todos os elementos, sei que gera e já fiz os cálculos para testar, mas não percebi muito bem a lógica. Se calhar se pensares em código ajuda. Ao multiplicar: |R2| = |1 1| x |F2| |R1| = |1 0| |F1| (em que F1, e F2 são o primeiro e segundo elemento da sequência de fibonnaci) estás a fazer: R2 = F2+F1; R1 = F2; Concordas que ao executar este código, vamos ter R2 == F3, R1 == F2, certo? Para multiplicar duas vezes pela matriz (i.e. pela matriz ao quadrado), basta pegar nos resultados que obtivemos e executar o mesmo código sobre eles. Para isso guardamos os valores de R2 e R1 nas variáveis iniciais, e executamos o mesmo código outra vez: //multiplica R2 = F2+F1; R1 = F2; //mete o resultado no "vector" que é multiplicado F2 = R2; F1 = R2; //multiplica outra vez R2 = F2+F1; R1 = F2; E agora vamos ter R2==F4 e R1==F3, certo? Para multiplicar N vezes basta-nos fazer um ciclo: int i=0; while(i++ < N) { //multiplica R2 = F2+F1; R1 = F2; //mete resultado no vector que vai multiplicar F2 = R2; F1 = R1; } No final temos R2 == F(N+2), R1 == F(N+1). Para um"tribonacci" seria: |1 1 1| x | f(n+2) | = | f(n+3) | |1 1 0| | f(n+1) | | f(n+2) | |1 0 0| | f(n) | | f(n+1) | Certo? Não, se fizeres a multiplicação no papel vês que o vector resultado não é esse. Pensa bem. Repara que já tens f(n+2) e f(n+1) no vector que está a ser multiplicado... Não respondo a dúvidas por mensagem. Link to comment Share on other sites More sharing options...
skiller10 Posted March 6, 2012 Author Report Share Posted March 6, 2012 Eu tinha alterado a matriz, inicialmente meti assim mas depois pensei melhor e vi que estava mal B) EDIT: Quanto ao fibonacci acho que já percebi, mas mais logo vou implementar para garantir que entendi bem a solução 😉 "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.." Link to comment Share on other sites More sharing options...
pedrosorio Posted March 6, 2012 Report Share Posted March 6, 2012 Eu tinha alterado a matriz, inicialmente meti assim mas depois pensei melhor e vi que estava mal B) Então como é que fica? 😉 EDIT: Quanto ao fibonacci acho que já percebi, mas mais logo vou implementar para garantir que entendi bem a solução B) Tu sabes isto, mas para ficar bem claro a quem ler isto posteriormente, aquilo que meti ali é apenas a implementação da multiplicação sucessiva pela matriz O(N). A solução que tu queres, calcula directamente a matriz elevada a N, o que bem implementado é O(logN). Não respondo a dúvidas por mensagem. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now