eGospodarka.pl
eGospodarka.pl poleca

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

  • 1. Data: 2013-05-09 14:15:55
    Temat: Zabawy w algorytmikę.
    Od: bartekltg <b...@g...com>

    Hmm, dopiero co była poprzednia edycja, albo obsuwa,
    albo robią co pół roku;-)

    http://potyczki.mimuw.edu.pl/

    21-28 maja.

    pzdr
    bartekltg


  • 2. Data: 2013-05-10 20:15:52
    Temat: Re: Zabawy w algorytmikę.
    Od: Vax <...@i...nie.ma>

    W dniu 2013-05-09 14:15, bartekltg pisze:
    > Hmm, dopiero co była poprzednia edycja, albo obsuwa,
    > albo robią co pół roku;-)

    to może ktoś się podejmie oszacować złożoność obliczeniową takiego problemu:

    Mamy prostokątną tablicę M x N z dwustanowymi komórkami. Przełączenie
    wskazanej komórki powoduje automatyczne przełączenie komórek
    sąsiadujących od góry, dołu, z lewej i prawej (o ile takie występują).
    Modelem może być szachownica zapełniona bierkami z reversi, ruch posiada
    dwie fazy - odwracasz wybraną bierkę, a następnie jej najbliższych
    sąsiadów (poza tymi po przekątnych).

    Należy dla zastanego stanu (w szczególnym przypadku wszystkie komórki w
    stanie "0") odnaleźć sekwencję ruchów, która wszystkie komórki
    doprowadzi do stanu "1" lub stwierdzić, że taka sekwencja nie istnieje.

    Chyba nie za trudne? ;)


  • 3. Data: 2013-05-11 09:14:45
    Temat: Re: Zabawy w algorytmikę.
    Od: "M.M." <m...@g...com>

    W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:

    > to może ktoś się podejmie oszacować złożoność obliczeniową takiego problemu:
    > [...]
    > Chyba nie za trudne? ;)

    Ogolnie dla tego typu problmow to przeszukiwanie drzewa gry ze
    spamietywaniem. Czyli ilosc obliczen x^(NxM) i ilosc pamieci tez x^(NxM),
    gdzie x to ilosc stanow pola. Podales szczegolny przypadek tego
    problemu, byc moze dla niego jest szybszy sposob.

    Pozdrawiam


  • 4. Data: 2013-05-11 11:27:24
    Temat: Re: Zabawy w algorytmikę.
    Od: bartekltg <b...@g...com>

    W dniu 2013-05-11 09:14, M.M. pisze:
    > W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:
    >
    >> to może ktoś się podejmie oszacować złożoność obliczeniową takiego problemu:
    >> [...]
    >> Chyba nie za trudne? ;)

    Na atman nie widać tego posta:(


    pzdr
    bartekltg


  • 5. Data: 2013-05-11 12:28:04
    Temat: Re: Zabawy w algorytmikę.
    Od: bartekltg <b...@g...com>

    W dniu 2013-05-11 09:14, M.M. pisze:
    > W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:
    >
    >> to może ktoś się podejmie oszacować złożoność obliczeniową takiego
    >> problemu: [...] Chyba nie za trudne? ;)

    Z innego serwera:

    > to może ktoś się podejmie oszacować złożoność obliczeniową takiego
    > problemu:
    >
    > Mamy prostokątną tablicę M x N z dwustanowymi komórkami. Przełączenie
    > wskazanej komórki powoduje automatyczne przełączenie komórek
    > sąsiadujących od góry, dołu, z lewej i prawej (o ile takie
    > występują). Modelem może być szachownica zapełniona bierkami z
    > reversi, ruch posiada dwie fazy - odwracasz wybraną bierkę, a
    > następnie jej najbliższych sąsiadów (poza tymi po przekątnych).
    >
    > Należy dla zastanego stanu (w szczególnym przypadku wszystkie komórki
    > w stanie "0") odnaleźć sekwencję ruchów, która wszystkie komórki
    > doprowadzi do stanu "1" lub stwierdzić, że taka sekwencja nie
    > istnieje.
    >
    > Chyba nie za trudne?

    Było niedawno na pl.sci.matematyka
    From: "J.F" <j...@p...onet.pl>
    Newsgroups: pl.sci.matematyka
    Subject: szachownica xor
    Date: Tue, 5 Mar 2013 19:09:02 +0100
    Message-ID: <513634bf$0$1218$65785112@news.neostrada.pl>


    W skrócie, parzysta liczba 'kliknięć' w pole jest redukowana
    do zera. Kolejność klikania też nie ma znaczenie.
    Możesz więc klikną raz lub w ogole. Stąd też wiadomo,
    że kliknięć nie będzie więcej niż pol szachownicy.


    Zapisz kliknięcia jako wektor v. Wtedy stan danego pola możesz
    opisać jakio w = A*v
    gdzie A to niezbyt gęsta macierz (mniej niż 5*n*m elementów).
    Oba wektory mają długość m*n, maciesrz siłą rzeczy (m*n)x(m*n).
    Wszytko dzieje się modulo 2.

    Konfiguracja zapalająca czy konfiguracja gasząca to to samo,
    więc szykamy v, takiego, że w to nasz stan początkowy i
    w = A*v

    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 ?
    Ale nie musi być to rozwiązanie optymalne, do rozwiązania
    możemy zawsze dorzucić wektor z jądra, i to może dać
    mniej jedynek w rozwiązaniu.
    Np dla tablicy 19x19 wymiar jądra to 16, więc trzeba by
    sprawdzić 65 tysiecy przypadków:/
    Czy istnieje jakiś lepszy sposób na przeszukanie takiego zestawu?

    Jeszcze mniej formalny link z wątku z matematyki:

    http://www.jaapsch.net/puzzles/lights.htm


    pzdr
    bartekltg






  • 6. Data: 2013-05-11 18:12:55
    Temat: Re: Zabawy w algorytmikę.
    Od: Vax <...@i...nie.ma>

    W dniu 2013-05-11 12:28, bartekltg pisze:
    [...]

    Zgoda w miejscach w których mowa o kolejności i parzystości, bo tak
    naprawdę wykonujemy serię XOR, które są naprzemienne i odwracalne.

    Haczyk polega na tym, że już wstępnie maksymalna liczbę iteracji możemy
    ograniczyć do 2^(min(M,N)) gdzie min() zwraca mniejszy z argumentów.
    Dlaczego? Ano dlatego, że aby zadanie w ogóle zostało spełnione to obraz
    zapalonych/zgaszonych komórek po wykonaniu "klików" na pierwszym rzędzie
    determinuje wymagane "kliki" rzędu 2, ten zaś narzuca kolejny rząd i tak
    dalej. A w ostatnim rzędzie przekonujemy się o ewentualnym sukcesie lub
    jego braku.
    Następnie możemy się bawić w pomijanie układów symetrycznych, np. 11000
    został już przetworzony jako 00011 itd. itp. - to póki co bez
    zaprzęgania "aparatu matematycznego" ;)


  • 7. Data: 2013-05-11 18:16:57
    Temat: Re: Zabawy w algorytmikę.
    Od: Vax <...@i...nie.ma>

    W dniu 2013-05-11 09:14, M.M. pisze:
    > W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:
    >
    >> to może ktoś się podejmie oszacować złożoność obliczeniową takiego problemu:
    >> [...]
    >> Chyba nie za trudne? ;)
    >
    > Ogolnie dla tego typu problmow to przeszukiwanie drzewa gry ze
    > spamietywaniem. Czyli ilosc obliczen x^(NxM) i ilosc pamieci tez x^(NxM),
    > gdzie x to ilosc stanow pola. Podales szczegolny przypadek tego
    > problemu, byc moze dla niego jest szybszy sposob.

    No wiesz... dla tablicy np. 1xN wystarczy sprawdzić raptem 2 możliwości
    by znaleźć wszystkie rozwiązania, o ile takie istnieją :)


  • 8. Data: 2013-05-11 18:22:41
    Temat: Re: Zabawy w algorytmikę.
    Od: Vax <...@i...nie.ma>

    W dniu 2013-05-11 12:28, bartekltg pisze:
    > W dniu 2013-05-11 09:14, M.M. pisze:

    > Zapisz kliknięcia jako wektor v. Wtedy stan danego pola możesz
    > opisać jakio w = A*v
    > gdzie A to niezbyt gęsta macierz (mniej niż 5*n*m elementów).

    do zapisania każdej serii "kliknięć" to mi zazwyczaj wystarczy INT o
    długości tylu bitów, ile pól liczy krótszy z boków, i nawet nie muszę
    mieć w pamięci miejsca na całą kopię tablicy wejściowej :)


  • 9. Data: 2013-05-12 00:31:50
    Temat: Re: Zabawy w algorytmikę.
    Od: bartekltg <b...@g...com>

    W dniu 2013-05-11 18:12, Vax pisze:
    > W dniu 2013-05-11 12:28, bartekltg pisze: [...]
    >
    > Zgoda w miejscach w których mowa o kolejności i parzystości, bo tak
    > naprawdę wykonujemy serię XOR, które są naprzemienne i odwracalne.
    >
    > Haczyk polega na tym, że już wstępnie maksymalna liczbę iteracji
    > możemy ograniczyć do 2^(min(M,N)) gdzie min() zwraca mniejszy z
    > argumentów.

    > Dlaczego? Ano dlatego, że aby zadanie w ogóle zostało spełnione to
    > obraz zapalonych/zgaszonych komórek po wykonaniu "klików" na
    > pierwszym rzędzie determinuje wymagane "kliki" rzędu 2, ten zaś
    > narzuca kolejny rząd i tak dalej. A w ostatnim rzędzie przekonujemy
    > się o ewentualnym sukcesie lub jego braku.

    Opisany ponizej algorytm dla n*m>64 jest jednak O((2^n)*m) (dla m>=n)
    na współczesnych maszynach.

    Dla samego znalezienia rozwiązania moj algorytm
    jest znacznie lepszy, działa wialomianowo.

    Dla znalezienia rozwiązania optymalnego jest ciut gorzej,
    trzeba dołożyć do tego xorowanie z jądrem (każdą kombinacją),
    które może być duże. Ale jak duże?

    Łatwo pokazać, że wymiar jądra jest mniejszy niż min(n,m).
    Na dzień dobry mamy więc taką samą złożoność.

    Ale to górne ograniczenie, może być znacznie lepiej.
    Pierwsza tabelka z ostatniej strony pokazuje, że
    w co drugim przypadku w ogole nie ma jądra, całą
    wykładnicza zabawa odpada! W pozostałych przypadkach <22
    tylko raz dobijamy do granicy (dla n=4).

    Co więcej, stwierdzenie niemożności rozwiązania danej konfiguracji
    jest wialomianowe. Jeśli rozwiązania nie ma, wiemy to przed
    uruchomieniem wykładniczej części.

    Twoj algorytm będzie szybszy w przypadku, gdy jedna z liczb
    jest bardzo małą.
    Algorytm zmatematyzowany może się z nim ścigać, jeśli macierze
    i ich rozkład zostaną wyznaczone w czasie kompilacji.
    Dla m,n rzedu kilkanaście, mniejsze kilkadziesiąt, nie jest
    to problem techniczny ani pamięciowy.


    > Następnie możemy się bawić w pomijanie układów symetrycznych, np.
    > 11000 został już przetworzony jako 00011 itd. itp. - to póki co bez
    > zaprzęgania "aparatu matematycznego" ;)

    Jednak aparat dał nam nieco;>
    Sztuczkę z "xor" == "+" (w Z_2) da się stosować w obu wersjach.


    > do zapisania każdej serii "kliknięć" to mi zazwyczaj wystarczy INT o
    > długości tylu bitów, ile pól liczy krótszy z boków, i nawet nie muszę
    > mieć w pamięci miejsca na całą kopię tablicy wejściowej

    Oczywista oczywistość. Tylko pamiętaj, żę jeden 64 bitowy int starcza
    na m=n <=8. Mało.



    pzdr
    bartekltg


  • 10. Data: 2013-05-12 01:59:34
    Temat: Re: Zabawy w algorytmikę.
    Od: "M.M." <m...@g...com>

    W dniu sobota, 11 maja 2013 18:12:55 UTC+2 użytkownik Vax napisał:
    > Haczyk polega na tym, że już wstępnie maksymalna liczbę iteracji możemy
    > ograniczyć do 2^(min(M,N)) gdzie min() zwraca mniejszy z argumentów.
    > Dlaczego? Ano dlatego, że aby zadanie w ogóle zostało spełnione to obraz
    > zapalonych/zgaszonych komórek po wykonaniu "klików" na pierwszym rzędzie
    > determinuje wymagane "kliki" rzędu 2, ten zaś narzuca kolejny
    Dobre spostrzezenie.

    Ciekawe jak to mozna wykorzystac do zwyklego algorytmu ze spamietywaniem,
    a moze nawet bez spamietywania.

    Mozna troche przerobic Twoje spostrzezenie. Kazdy klik pewne pola zapala a
    inne gasi. Niech to bedzie klik x. Wiec klik x determinuje kliki ktore
    musza zgasic to co on zapalil. Jesli kolejnosc jest niewazna, to klik x
    moze determinowac je jako kliki w nastepnej kolejnosci. Wiec kazde pole moze
    miec zapamietany numer+1 rekurencyjnego wywolania w ktorym zostalo zapalone
    lub jeden jesli bylo dane w ukladzie poczatkowym. Algorytm w kazdym
    kroku musi zgasic dowolne pole o najmniejszym numrze. To na pewno zmniejszy
    breanch-faktor.

    Pozostaje kwestia czy mozna jakos uniknac spamietywania?

    Algorytm z spamietywaniem jest prosty Jesli docieramy do ukladu ktory byl
    wczesniej, to wnioskujemy ze zaczyna sie petlic. Ale takie podejscie
    wymagaloby sporo pamieci.

    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.

    Pozdrawiam

strony : [ 1 ] . 2 ... 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: