Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIKA U INFORMATICI

De Brujinov niz, Lindonove reči i Duvalov algoritam

Brojni sistemi, Bulova algebra, binarna aritmetika itd.

De Brujinov niz, Lindonove reči i Duvalov algoritam

Postod smarko1983 » Sreda, 18. Januar 2017, 22:27

Prvo, pošto ne znam koliko vas ima predstavu o ova 3 pojma, skroz dole ću ostaviću linkove na engleskom, pošto u našoj literaturi nisam pronašao.

Ovaj problem mi se pojavio u teoriji grafova dok sam učio Ojlerove i Hamiltonove cikluse. De Brujinov niz se dobija tako što se na poseban način nacrtaju čvorovi i spoje sa granama a potom se traži Ojlerov ili Hamiltonov ciklus (u zavisnosti da li koristimo Ojlerov ili Hamiltonov metod). Češće se koristi Ojlerov metod jer postoji algoritam za izračunavanje svih Ojlerovih ciklusa (Fleurov algoritam), gde su upravo svi ti Ojlerovi ciklusi De Brujinovi nizovi.

Ukratko, De Brujinov niz se zapisuje kao [inlmath]B(k,n)[/inlmath] gde [inlmath]k[/inlmath] označava skup iz kojeg biramo elemente a [inlmath]n[/inlmath] je dužina reči. Poenta De Brujinovog niza je da "strpamo" sve permutacije skupa [inlmath]k[/inlmath] u taj De Brujinov niz (koji je inače cikličan niz). Na primer, [inlmath]B(2,3)[/inlmath] je (gde je [inlmath]k=\{0,1\}[/inlmath] ) De Brujinov niz [inlmath]0 0 0 1 0 1 1 1 (0 0)[/inlmath] , jer su permutacije skupa [inlmath]k[/inlmath] dužine 3: [inlmath]000,\;001,\;010,\;101,\;011,\;111,\;110,\;100[/inlmath], idemo s leva na desno, gde svaki put kada pomerimo 3 broja po jedanput u desno, dobijamo drugačiju permutaciju. Videćemo da je [inlmath]k^n=2^3=8[/inlmath] dužina De Brujinovog niza, i na kraju dve nule u zagradi nam govore da smo tu već krenuli da "obmotavamo" oko niza. Broj obmotavanja je uvek [inlmath]n-1[/inlmath].

Dalje...programerski, to može da se dobije preko Duvalovog algoritma koji generiše Lindonove reči. Posle toga se nekako uz pomoć Lindonovih reči konstruiše De Brujinov niz. Lindonove reči su leksikografski najmanje reči od svih mogućih rotacija neke reči. Videti ilustrovani primer ovde, zelenom bojom su obeležene Lindonove reči.

Meni konkretno nije jasan taj Duvalov algoritam koji generiše Lindonove reči, a posle mi nije jasno ni kako se konstruiše De Brujinov niz uz pomoć tih Lindonovih reči. Tačnije, nije mi jasan pseudokod pošto sam taj algoritam opisno, i po primeru, donekle uspeo da razumem, iz ovog linka.

Da napomenem da ne znam nijedan programski jezik i znam da čitam samo pseudokod, i to razumem prostije lupove i algoritme, plus Dijkstrin algoritam koji mi je bio u teoriji grafova. Zato bih vam bio zahvalan ako bi taj pseudokod mogli da mi objasnite uz pomoc nekog primera, gde će se što više redova koda komentarisati.

De Brujinov niz:
Wikipedia
Youtube, prepoznaćete ga :). Evo i rešenja, u opisu videa (show more) postoje dodatna objašnjenja kao i algoritam za generisanje Lindonovih reči.

Lindonove reči:
Wikipedia - dole postoji i Duvalov algoritam u pseudokodu
Odavde sam najviše razumeo, tu je i taj "opisni" Duvalov algoritam
Odavde sam po primeru shvatio šta su Lindonove reči, a onda je postalo veoma komplikovano :D

Kôd: Obeleži sve
Duvalov pseudokod:
w[1] ← a
i ← 1
repeat
     for j = 1 to n–i
          do w[i+j] ← w[j]
     /* at this point, w[1...i] is a Lyndon word */
     i ← n
     while i > 0 and w[i] = M
          do i ← i–1
     if i > 0 [b]then[/b] w[i] ← s(w[i])
until i = 0

Kratak opis: "Jean-Pierre Duval has given an algorithm which gives the sorted list of all Lyndon words of length less than an integer n . This algorithm is reproduced in the pseudocode above. Let a be the smallest letter of the ordered alphabet A and M be the larger one. Furthermore, for every letter x excepted M, s(x) is the letter that immediately larger than x in A. We denote by w[1...n] an array of letters of dimension n"
Ceo pdf je ovde , a na drugoj strani tog linka je pseudokod.

Rešenja u raznim programskim jezicima su ovde ako nekog zanima.

U suštini, ovo ni ne bi trebalo sada da učim ali me zanima.
 
Postovi: 6
Zahvalio se: 3 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Povratak na MATEMATIKA U INFORMATICI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 37 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 22:31 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs