eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingZabawy w algorytmikę.
Ilość wypowiedzi w tym wątku: 57

  • 41. Data: 2013-05-13 22:03:44
    Temat: Re: Zabawy w algorytmikę.
    Od: Miroslaw Kwasniak <m...@i...zind.ikem.pwr.wroc.pl>

    bartekltg <b...@g...com> wrote:
    > Hehe, spryciarz;> A dla 39x39?

    No, tak 2^32 rozwiązań nie przejrzę :O

    ? matrank(matker(m))
    time = 84 ms.
    %16 = 32

    Ale przypadkowe poniżej 1s

    ? m=Mod(M(39,39),2); l=m;l=l[,1]+l[,39]+l[,7]; s=matinverseimage(m,l);m*s==l
    time = 889 ms.
    %15 = 1

    Z czego większość zajmuje kiepska procedura budowy m:

    ? m=Mod(M(39,39),2);
    time = 616 ms.

    Bo samo rozwiązanie to nic:

    ? s=matinverseimage(m,l);
    time = 84 ms.


  • 42. Data: 2013-05-13 23:21:50
    Temat: Re: Zabawy w algorytmikę.
    Od: bartekltg <b...@g...com>

    W dniu 2013-05-13 22:03, Miroslaw Kwasniak pisze:
    > bartekltg <b...@g...com> wrote:
    >> Hehe, spryciarz;> A dla 39x39?
    >
    > No, tak 2^32 rozwiązań nie przejrzę :O
    >
    > ? matrank(matker(m))
    > time = 84 ms.
    > %16 = 32

    To wspomniane pari-gp?

    Ile wychodzi dla większych? powiedzmy 55 czy 64.


    > Ale przypadkowe poniżej 1s
    >
    > ? m=Mod(M(39,39),2); l=m;l=l[,1]+l[,39]+l[,7]; s=matinverseimage(m,l);m*s==l
    > time = 889 ms.
    > %15 = 1
    >
    > Z czego większość zajmuje kiepska procedura budowy m:

    Spróbuj może tak:
    N = macierz pasmowa n x n o paśmie [1,0.5,1]
    (na diagonali 0.5. Nad i pod diagonalą 1).
    M = to samo, ale rozmiaru m x m

    Teraz poszukiwana macierz to

    A = M (*) Id[n] + Id[m] (*) N

    gdzie (*) to iloczyn kroneckera, pewnie jest zaimplementowany.

    Mathematice zajmuje to 1.2s, ale matlabowi (w bebechach pewnie
    bliższe pari) wyszło 0.007236s:)

    pzdr
    bartekltg


  • 43. Data: 2013-05-14 00:11:16
    Temat: Re: Zabawy w algorytmikę.
    Od: Miroslaw Kwasniak <m...@i...zind.ikem.pwr.wroc.pl>

    bartekltg <b...@g...com> wrote:
    > W dniu 2013-05-13 22:03, Miroslaw Kwasniak pisze:
    >> bartekltg <b...@g...com> wrote:
    >>> Hehe, spryciarz;> A dla 39x39?
    >>
    >> No, tak 2^32 rozwiązań nie przejrzę :O
    >>
    >> ? matrank(matker(m))
    >> time = 84 ms.
    >> %16 = 32
    >
    > To wspomniane pari-gp?

    Tak

    > Ile wychodzi dla większych? powiedzmy 55 czy 64.

    ? n=55;m=Mod(M(n,n),2);
    time = 1,837 ms.
    ? matrank(matker(m))
    time = 292 ms.
    %5 = 0

    ? n=64;m=[];m=Mod(M(n,n),2);
    time = 3,112 ms.
    ? matrank(matker(m))
    time = 561 ms.


    > A = M (*) Id[n] + Id[m] (*) N
    >
    > gdzie (*) to iloczyn kroneckera, pewnie jest zaimplementowany.

    Chyba nie ma (w tym sensie co myślimy), ale pari jest dziwne, jak wszystko
    co francuskie ;)


  • 44. Data: 2013-05-14 03:29:47
    Temat: Re: Zabawy w algorytmikę.
    Od: "M.M." <m...@g...com>

    W dniu poniedziałek, 13 maja 2013 14:04:26 UTC+2 użytkownik bartekltg napisał:

    > Bo to było w poprzednich postach (ten jest już o nieco czym innym:)),
    Coś jest nie tak, chyba nie mam połowy postów.
    Pozdrawiam




  • 45. Data: 2013-05-14 12:10:31
    Temat: Re: Zabawy w algorytmikę.
    Od: Miroslaw Kwasniak <m...@i...zind.ikem.pwr.wroc.pl>

    bartekltg <b...@g...com> wrote:
    > Po pierwsze, da się rozwiązać, kiedy w siedzi w przestrzeni rozpiętej
    > przez kolumny A (jest a obrazie A, dość trywialny wniosek).
    > Ponieważ obraz A będzie duży, łatwiej do algorytmu wyznaczyć kojądro*)
    > i sprawdzać, czy aby nasza oczekiwana konfiguracja sie z nim nie
    > przecina (iloczynem skalarnym).
    >
    > Wiecej szczegółow.
    > http://www.math.ksu.edu/~dmaldona/math551/lights_out
    .pdf
    >
    > *) tutaj macierz A budujemy tsak, by była symetryczna A^T=A,
    > więc kojądro i jądro (null space) to to samo.
    >
    > Ok, rozwiążemy równanie macierzowe w Z^2 (n*m)^3 ?

    To wygląda ciekawie:

    http://online.redwoods.edu/instruct/darnold/laproj/F
    all2001/Emilia/emilia_paper.pdf

    https://ida.mtholyoke.edu/xmlui/bitstream/handle/101
    66/693/375.pdf?sequence=1
    http://www.unf.edu/~wkloster/fibonacci/switch.ps
    www.unf.edu/~wkloster/fibonacci/lama.pswww.unf.edu/~
    wkloster/fibonacci/lama.ps

    www.m-hikari.com/ijcms-2010/29-32-2010/leeIJCMS29-32
    -2010.pdf



  • 46. Data: 2013-05-14 15:34:51
    Temat: Re: Zabawy w algorytmikę.
    Od: bartekltg <b...@g...com>

    W dniu 2013-05-14 12:10, Miroslaw Kwasniak pisze:
    > bartekltg <b...@g...com> wrote:
    >> Po pierwsze, da się rozwiązać, kiedy w siedzi w przestrzeni rozpiętej
    >> przez kolumny A (jest a obrazie A, dość trywialny wniosek).
    >> Ponieważ obraz A będzie duży, łatwiej do algorytmu wyznaczyć kojądro*)
    >> i sprawdzać, czy aby nasza oczekiwana konfiguracja sie z nim nie
    >> przecina (iloczynem skalarnym).
    >>
    >> Wiecej szczegółow.
    >> http://www.math.ksu.edu/~dmaldona/math551/lights_out
    .pdf
    >>
    >> *) tutaj macierz A budujemy tsak, by była symetryczna A^T=A,
    >> więc kojądro i jądro (null space) to to samo.
    >>
    >> Ok, rozwiążemy równanie macierzowe w Z^2 (n*m)^3 ?
    >
    > To wygląda ciekawie:
    >
    > http://online.redwoods.edu/instruct/darnold/laproj/F
    all2001/Emilia/emilia_paper.pdf

    O, to jest genialne:)

    Dla tych, co nie czytali:
    Gwóźdź jest w rozdziale 4. Zamiast myśleć o równaniu na m*n
    wspolczynnikow patrzymy na to jak na układ m rownań na n
    wspolczynnikow (to jeszcze nic ciekawego), a dzieki odpowiedniej
    strukturze naszej macierzy problem rozbija się na

    m-1 rownań postaci:
    kawałak rozwiązania = Maceirz_i (zapalenia, pierwszy kawałek rozwiązania)

    oraz równanie

    Macierz*pierwszy kawalek rozwiazania = macierze_1 (zapalenia).

    Wszystkie macierze są n x n .

    Cała siłowa cześć siedzi w ostatnim rownaniu (mamy taką intuicję,
    że tylko ostatnia linijka się liczy. W rozwiązaniu Vaxa z tego
    korzystaliśmy, ale nie wiedzialem, że da się w podejściu
    algebraicznym do tego dojść). Zarówno rozwiązanie zadanych zapaleń,
    jak i znalezienie wektorów zerowych wymaga rozłożenia tylko tej
    ostatniej macierzy.
    Za darmo dostajemy też to, co wcześniej trzeba bylo (prosto) sobie
    udowodnić, że dim(ker(A)) <= n (jak wszędzie n<=m)

    Zwłaszcza ogromną korzyść odnosimy, gdy m>>n:)

    > www.m-hikari.com/ijcms-2010/29-32-2010/leeIJCMS29-32
    -2010.pdf

    > https://ida.mtholyoke.edu/xmlui/bitstream/handle/101
    66/693/375.pdf?sequence=1
    > http://www.unf.edu/~wkloster/fibonacci/switch.ps
    > www.unf.edu/~wkloster/fibonacci/lama.pswww.unf.edu/~
    wkloster/fibonacci/lama.ps

    Jeszcze nie poczytałem...

    pzdr
    bartekltg






  • 47. Data: 2013-05-14 15:39:02
    Temat: Re: Zabawy w algorytmikę.
    Od: bartekltg <b...@g...com>

    W dniu 2013-05-14 03:29, M.M. pisze:
    > W dniu poniedziałek, 13 maja 2013 14:04:26 UTC+2 użytkownik bartekltg napisał:
    >
    >> Bo to było w poprzednich postach (ten jest już o nieco czym innym:)),
    > Coś jest nie tak, chyba nie mam połowy postów.

    Na ataman, neostradzie i aoie na oko jest wszytko.

    Zerknij w ten link:

    http://www.math.ksu.edu/~dmaldona/math551/lights_out
    .pdf

    A przed chwilą Mirosław podrzucił jeszcze lepsze prace.
    Message-ID: <kmt2in$9am$1@z-news.wcss.wroc.pl>

    pzdr
    bartekltg


  • 48. Data: 2013-05-14 22:41:44
    Temat: Re: Zabawy w algorytmikę.
    Od: Vax <...@i...nie.ma>

    W dniu 2013-05-13 13:07, Miroslaw Kwasniak pisze:
    > Vax <...@i...nie.ma> wrote:

    > Ale to nie musi to być rozwiązanie optymalne - gdy takiego szukasz, to musisz
    przejrzeć wszystkie :(
    > Chyba, że null-space jest pusta.

    rozwiązanie "optymalne" to nie był mój postulat, algorytm miał podać
    rozwiązanie lub zakomunikować,, że takowe nie istnieje

    > Każda metoda ma swój techniczny zakres stosowalności.
    > Twoja jest dobra dla wąskich macierzy, ale co zrobisz dla 40 x 40?

    Czegoś nie rozumiemy chyba. Prosiłem nie o algorytm, ale o wstępne
    oszacowanie. Ta metoda jest odpowiedzią na oszacowanie, które
    wskazywałoby by na algorytm sprawdź wszystkie kombinacje kliknięć w
    tablicy" i wskazuje, że prostym zabiegiem można znacznie liczbę iteracji
    zmniejszyć (i nie sprawdzać kombinacji z góry skazanych na niepowodzenie).
    Czy ja się upieram, że to najlepsze rozwiązanie dla każdego zestawu
    danych (toż nawet sortowania nie ma uniwersalnego), tylko dlatego, że
    nie wklejam tu linków do innych? Ktoś to już zrobił za mnie więc po co?


  • 49. Data: 2013-05-15 09:21:44
    Temat: Re: Zabawy w algorytmikę.
    Od: Miroslaw Kwasniak <m...@i...zind.ikem.pwr.wroc.pl>

    M.M. <m...@g...com> wrote:
    >
    > Moze wystarczy zapamietac z kazdym polem, ze juz bylo raz zapalone i potem
    > zgaszone? Intuicja podpowiada, ze nie ma sensu zapalac danego pola dwa razy.
    > Nie wiem czy moja intuicja sie nie myli, ale jesli to prawda, to algortym
    > moze przerwac przeszukiwanie danej galezi, jesli nie da sie zgasic jakiegos
    > pola bez zapalania tych pol, ktore juz wczesniej byly zgaszone.

    Jeżeli ja Ciebie rozumiem i się nie mylę - to niestety intuicja się myli ;)

    Dla stanu początkowego
    ? a
    %80 =
    [1 1 1 0 0]

    [1 1 1 1 1]

    [1 1 1 1 1]

    [0 1 0 0 0]

    [0 0 0 1 1]

    Wszytkie 4 nieredundantne rozwiązania zawierają pola, które nawet 4-5 razy zmieniają
    stan.

    nr=0 moves=13
    Solution: changes:
    [0 0 0 1 0] [1 1 1 2 2]

    [1 1 0 1 1] [3 3 3 3 3]

    [1 1 1 0 1] [3 5 3 3 3]

    [0 1 1 0 1] [2 3 4 2 2]

    [0 0 1 0 0] [0 2 2 1 1]

    nr=1 moves=11
    Solution: changes:
    [0 1 1 0 0] [1 3 3 2 0]

    [0 1 1 1 0] [1 3 5 3 1]

    [0 0 1 1 0] [1 3 3 3 1]

    [1 1 0 0 0] [2 3 2 2 0]

    [0 1 0 1 0] [2 2 2 1 1]

    nr=2 moves=15
    Solution: changes:
    [1 0 1 1 1] [1 3 3 4 2]

    [0 1 1 1 0] [3 3 5 3 3]

    [1 1 1 0 1] [3 5 3 3 1]

    [1 1 0 0 0] [4 3 2 0 2]

    [1 0 0 0 1] [2 2 0 1 1]

    nr=3 moves=17
    Solution: changes:
    [1 1 0 0 1] [3 3 1 2 2]

    [1 1 0 1 1] [3 3 3 3 3]

    [0 0 1 1 0] [1 3 3 3 3]

    [0 1 1 0 1] [2 3 4 4 2]

    [1 1 1 1 1] [2 4 4 3 3]




  • 50. Data: 2013-05-15 09:49:21
    Temat: Re: Zabawy w algorytmikę.
    Od: Miroslaw Kwasniak <m...@i...zind.ikem.pwr.wroc.pl>

    Vax <...@i...nie.ma> wrote:
    > W dniu 2013-05-13 13:07, Miroslaw Kwasniak pisze:
    >> Vax <...@i...nie.ma> wrote:
    >
    >> Ale to nie musi to być rozwiązanie optymalne - gdy takiego szukasz, to musisz
    przejrzeć wszystkie :(
    >> Chyba, że null-space jest pusta.
    >
    > rozwiązanie "optymalne" to nie był mój postulat, algorytm miał podać
    > rozwiązanie lub zakomunikować,, że takowe nie istnieje

    OK

    >> Każda metoda ma swój techniczny zakres stosowalności.
    >> Twoja jest dobra dla wąskich macierzy, ale co zrobisz dla 40 x 40?
    >
    > Czegoś nie rozumiemy chyba. Prosiłem nie o algorytm, ale o wstępne
    > oszacowanie.

    Oszacowanie złożoności problemu, zależy od algorytmu ;)

    > Ta metoda jest odpowiedzią na oszacowanie, które
    > wskazywałoby by na algorytm sprawdź wszystkie kombinacje kliknięć w
    > tablicy" i wskazuje, że prostym zabiegiem można znacznie liczbę iteracji
    > zmniejszyć (i nie sprawdzać kombinacji z góry skazanych na niepowodzenie).

    OK

    > Czy ja się upieram, że to najlepsze rozwiązanie dla każdego zestawu
    > danych (toż nawet sortowania nie ma uniwersalnego), tylko dlatego, że
    > nie wklejam tu linków do innych? Ktoś to już zrobił za mnie więc po co?

    Ale istnieje pojęcie złożoności O()
    O ile rozumiem, to Twoja metoda wymaga sprawdzenia do 2^n kombinacji w
    pierwszym wierszu. Metoda macierzowa (n*m)^3, a w świetle

    http://online.redwoods.edu/instruct/darnold/laproj/F
    all2001/Emilia/emilia_paper.pdf

    dla n=m to chyba n^4 zamiast n^6

    Widzisz różnicę?

strony : 1 ... 4 . [ 5 ] . 6


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: