W dniu 2013-05-13 11:54, Miroslaw Kwasniak pisze:
> bartekltg <b...@g...com> wrote:
>> W dniu 2013-05-12 23:01, Vax pisze:
>>> W dniu 2013-05-12 22:51, bartekltg pisze:
>>>
>>>>> Rozpatrywanie tego algorytmu jest mało sensowne, ale skoro chcesz:
>>>>> mamy 2^(m*n) prób. W każdej musimy wygenerować tablicę opisującą
>>>>> stan lampek. Jeśli rzeczywiście będziemy budować ją od początku,
>>>>> wykonamy O(m*n) operacji. Ale nie musimy tego robić, wystarczy, że
>>>>> naniesiemy poprawki. Jeśli różnił się jeden bit, poprawka jest w 5
>>>>> miejscach. Super.
>>>
>>> tablica 5 x 100 - z dowolnej kombinacji masz 500 innych "różnych o jeden
>>> bit", ale czymże to jest wobec 2^500...
>>
>> Jesteś jedyną osobą, która w ogole wspomina o czymś takim!
>> Czyżbyś sugerował, że "mój" alg tyle działa? Czyli jednak nie
>> załapałeś;>
>>
>> Opisany prze zemnie algorytm ma cześć 'wykładniczą'
>> 2^l, gdzie l jest co najwyżej 5.
>
> Dla 5 x 100 l=0 ;)

n = 100;
m = 5;
Nn = DiagonalMatrix[ConstantArray[1/2, n]] +
DiagonalMatrix[ConstantArray[1, n - 1], 1] +
DiagonalMatrix[ConstantArray[1, n - 1], -1];
M = DiagonalMatrix[ConstantArray[1/2, m]] +
DiagonalMatrix[ConstantArray[1, m - 1], 1] +
DiagonalMatrix[ConstantArray[1, m - 1], -1];

A = KroneckerProduct[M, IdentityMatrix[n]] +
KroneckerProduct[IdentityMatrix[m], Nn];

m*n - MatrixRank[A, Modulus -> 2]

Out[310]= 0

Zgadza się:)

Masz jakiś sprytniejszy pomysł na liczenie tego?


Odpaliłem wczoraj wieczorem bardzo niewydajną maszynkę,
która zrobiła tabelkę:
http://www.sendspace.com/file/xl0izd

Przy okazji, zna ktoś sprawniejszą maszynkę do takich
działań? Lapack dla ciał Z_p ;)

pzdr
bartekltg