Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Kodowanie grafu przez LFSR



 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Pią Lut 10, 2017 12:21 am  OP    Temat postu: Kodowanie grafu przez LFSR Odpowiedz z cytatem Pisownia

Hej...
mam problemik, chyba nie taki banalny... chodzi o metodę kodowania grafu za pomocą rejestru przesuwnego ze sprzężeniem zwrotnym (LFSR)... Mam jeden graf... Ma on (to znaczy graf) cztery wierzchołki... ten graf jest budowany w oparciu o rejestr długości 6 ze stanem początkowym 001011. Do sprzężenia zwrotnego brane są dwa bity: piąty i szósty... Jak ten graf zdekodować (krok po kroku, raczej bez teorii Galois proszę) do dowolnej postaci, najlepiej chyba listowej... help... please...

_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
marcin_an



Dołączył: 26 Maj 2005
Posty: 18822

PostWysłany: Pią Lut 10, 2017 1:34 am      Temat postu: Odpowiedz z cytatem Pisownia

Wiem, co to LFSR. Wiem, co to graf. Wiem, co to kodowanie grafu. Nadal nie mam bladego pojęcia, o co pytasz :D.

LFSR reprezentuje sekwencję liczb (symboli), powtarzającą się w cyklu. Sekwencja ta jest stała. Przykładowo dla x⁶+x⁵+1 z XOR jako funkcją zwrotną, używaną zewnętrznie (zapewne tę wersję miałeś na myśli) jest to sekwencja z załącznika lfsr-6-5.txt (po lewej reprezentacja stanów komórek rejestru, po prawej wartość dziesiętna jako big-endian). Nic tym nie możesz kodować, bo jest to z góry ustalona i niezmienna rzecz. To tak, jakbyś pytał, jak zakodować graf ciągiem (1, 2, 3, ..., 63). Nijak.

Możesz użyć LFSR jako źródła wartości do generowania grafu. Ale generowania, a nie kodowania (czyli "zapisu")! Zacznijmy od tego, że dowolny 6-bitowy ciąg reprezentuje nieskierowany graf o 4 wierzchołkach bez uszu. Graf taki ma do 6 krawędzi, numerujemy je, przypisujemy bity; jeśli bit 1 - krawędź jest, jeśli 0 - nie ma. Przykładowo dla 001011:
 Krawędź | Bit
A B | (1) (2)
---------+------- | /
1 2 | b1 0 | /
1 3 | b2 0 --> | /
1 4 | b3 1 (4)---(3)
2 3 | b4 0
2 4 | b5 1
3 4 | b6 1
Tyle, że to jest prawdą dla dowolnego ciągu i z LFSR nie ma nic wspólnego. Mogę rzucić kostką 6 razy, wziąć parzystość wylosowanych oczek i będę miał taki ciąg. LFSR, który podałeś, ma cykl długości 63 - najdłuższy możliwy dla 6-bitowego rejestru - więc przegląda wszystkie (oprócz 0) wartości, więc możę zostać użyty do wyliczania grafów. Ale to samo może zrobić kod Graya czy zwykłe zwiększanie licznika o 1. LFSR nie wnosi nic specjalnego.

LFSR jest używany jako prymitywny generator pseudolosowy, więc może dostarczyć wartości, które mogą być użyte do budowania losowego drzewa: np. MST z losowymi wagami albo losowy kod Prüfera. W ten sam sposób można jednak użyć dowolnego innego PRNG, szczególnie takiego z lepszymi parametrami od LFSR.

Tak więc... o czym mówisz?



lfsr-5-6.txt
 Opis:

Pobierz
 Nazwa pliku:  lfsr-5-6.txt
 Wielkość pliku:  747 Bajty
 Pobierano:  70 raz(y)


_________________
Nieaktywny od 2017-04-01
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Pią Lut 10, 2017 7:43 am  OP    Temat postu: Odpowiedz z cytatem Pisownia

chyba rzeczywiście nie sprecyzowałem... czuję się jak studęt... :)

chodzi o problemik ze SPOJu... czasem sobie siedzę i dłubię ciut... chodzi o to zadanko... jak byś mi wyjaśnił skąd oni biorą te krawędzie w grafie, to byłbym dźwięczny (ale na nic więcej nie licz)... bo dla mnie to czarna magia jak połączyć ten magiczny shift(k) ze sprzężeniem zwrotnym LFSR od którego zacząłem wątek...

_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa)

Strona 1 z 1

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.15111 sekund, zapytan = 13
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |