Forum Coders' city Strona Gwna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UytkownicyUytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj si, by sprawdzi wiadomociZaloguj si, by sprawdzi wiadomoci   ZalogujZaloguj 

Potrzebuj szybkiej odpowiedzi na moje pytanie... Zasady

Kodowanie grafu przez LFSR



 
Odpowiedz do tematu    Forum Coders' city Strona Gwna -> Algorytmy + inynieria oprogramowania
Zobacz poprzedni temat :: Zobacz nastpny temat  
Autor Wiadomo
hurgadion



Doczy: 06 Kwi 2011
Posty: 853
Skd: Web :)

PostWysany: 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 sprzeniem zwrotnym (LFSR)... Mam jeden graf... Ma on (to znaczy graf) cztery wierzchoki... ten graf jest budowany w oparciu o rejestr dugoci 6 ze stanem pocztkowym 001011. Do sprzenia zwrotnego brane s dwa bity: pity i szsty... Jak ten graf zdekodowa (krok po kroku, raczej bez teorii Galois prosz) do dowolnej postaci, najlepiej chyba listowej... help... please...

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
marcin_an



Doczy: 26 Maj 2005
Posty: 18822

PostWysany: 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 pojcia, o co pytasz :D.

LFSR reprezentuje sekwencj liczb (symboli), powtarzajc siw cyklu. Sekwencja ta jest staa. Przykadowo dla x⁶+x⁵+1 z XOR jako funkcj zwrotn, uywan zewntrznie (zapewne twersjmiae na myli) jest to sekwencja z zacznika lfsr-6-5.txt (po lewej reprezentacja stanw komrek rejestru, po prawej warto dziesitna jako big-endian). Nic tym nie moesz kodowa, bo jest to z gry ustalona i niezmienna rzecz. To tak, jakby pyta, jak zakodowa graf cigiem (1, 2, 3, ..., 63). Nijak.

Moesz uy LFSR jako rda wartoci do generowania grafu. Ale generowania, a nie kodowania (czyli "zapisu")! Zacznijmy od tego, e dowolny 6-bitowy cig reprezentuje nieskierowany graf o 4 wierzchokach bez uszu. Graf taki ma do 6 krawdzi, numerujemy je, przypisujemy bity; jeli bit 1 - krawd jest, jeli 0 - nie ma. Przykadowo dla 001011:
 Krawd | 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 cigu i z LFSR nie ma nic wsplnego. Mog rzuci kostk 6 razy, wziparzysto wylosowanych oczek i bd mia taki cig. LFSR, ktry podae, ma cykl dugoci 63 - najduszy moliwy dla 6-bitowego rejestru - wic przeglda wszystkie (oprcz 0) wartoci, wic mo zosta uyty do wyliczania grafw. Ale to samo moe zrobi kod Graya czy zwyke zwikszanie licznika o 1. LFSR nie wnosi nic specjalnego.

LFSR jest uywany jako prymitywny generator pseudolosowy, wic moe dostarczy wartoci, ktre mog by uyte do budowania losowego drzewa: np. MST z losowymi wagami albo losowy kod Prfera. W ten sam sposb mona jednak uy dowolnego innego PRNG, szczeglnie takiego z lepszymi parametrami od LFSR.

Tak wic... o czym mwisz?



lfsr-5-6.txt
 Opis:

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


_________________
Nieaktywny od 2017-04-01
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo
hurgadion



Doczy: 06 Kwi 2011
Posty: 853
Skd: Web :)

PostWysany: Pi Lut 10, 2017 7:43 am  OP    Temat postu: Odpowiedz z cytatem Pisownia

chyba rzeczywicie nie sprecyzowaem... czuj si jak studt... :)

chodzi o problemik ze SPOJu... czasem sobie siedz i dubi ciut... chodzi o to zadanko... jak by mi wyjani skd oni bior te krawdzie w grafie, to bybym dwiczny (ale na nic wicej nie licz)... bo dla mnie to czarna magia jak poczy ten magiczny shift(k) ze sprzeniem zwrotnym LFSR od ktrego zaczem wtek...

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
Wywietl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Gwna -> Algorytmy + inynieria oprogramowania Wszystkie czasy w strefie CET (Europa)

Strona 1 z 1

 
Skocz do:  
Moesz pisa nowe tematy
Moesz odpowiada w tematach
Nie moesz zmienia swoich postw
Nie moesz usuwa swoich postw
Nie moesz gosowa w ankietach
Moesz dodawa zaczniki na tym forum
Moesz pobiera pliki z tego forum




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

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