|
ZADACI S 2. KOLOKVIJA
(Rješenja će uslijediti nešto kasnije)
Bodovi: 1(12), 2(8), 3(10), 4(10 - bonus *)
1. (a) Je li istinita tvrdnja: projektivna ravnina reda 7 ima cikličku grupu automorfizama
koja na njoj djeluje regularno?
Kojoj tvrdnji o postojanju
diferencijskih skupova je ova tvrdnja ekvivalentna? Ako je tvrdnja istinita,
mora li za odgovarajući diferencijski skup postojati multiplikator i
koji je to multiplikator? Navedite teorem(e) na kojima se zasnivaju odgovori.
Kako biste započeli pokušaj konstrukcije projektivne ravnine reda 7 na
temelju prethodnog i u čemu bi nastao problem?
(b) Tzv. Golomb-Songova hipoteza o Hadamardovim diferencijskim skupovima
(tj. (v,k, λ ) diferencijskim skupovima s Hadamardovim parametrima
v = 4λ +3, k = 2λ +1) govori da ako
takav skup postoji u cikličkoj grupi reda v, onda je
v ili prim broj ili umnožak dva susjedna neparna prim broja
ili je za 1 manji od neke potencije broja 2.
Navedite primjere odgovarajućih diferencijskih skupova za sva tri navedena oblika v,
s tim da to budu tri različite vrijednosti v, v > 7.
2. Televizijska kuća emitira program na dva kanala i želi usporediti gledanost
svojih 7 najpopularnijih serija, kroz sve dane u tjednu,
tako da se u tih 7 dana svaka serija emitira po jedanput na svakom kanalu.
Plan je da se u svakom dnevnom terminu istodobno
prikažu dvije serije i da svake dvije serije budu
"suprotstavljene" dva puta (jedna na 1. kanalu, druga na 2. i obrnuto).
Radi jednostavnosti sheme može se uzeti dnevni "nulti" termin
u kojem se na oba
kanala emitira ista serija. Označe li se dani npr. nedjelja = 0, …,
subota = 6, dnevni termini i same serije numeriraju također
s 0,1,...,6, zadatak je načiniti traženu shemu
(uputa: poznata algebarska metoda mod 7).
Ako tehničari dobiju poruku oblika (2, 3, 5, 0) koja znači:
u utorak u terminu br. 3 na 1. kanalu ide serija br. 5,
a na 2. kanalu serija br. 0, hoće li moći ustanoviti da je
jedan od 4 podatka pogrešan i ispraviti ga?
3. Odredite parametre (duljinu n, dimenziju k, minimalnu
težinu d) linearnog ternarnog koda C tako da bude savršen,
da ima sposobnost ispravljanja dvije pogreške i da
razlika n-k ("redundancija") bude što manja.
(Alfabet je pritom
polje GF(3) = {0,1,2} s operacijama modulo 3).
Ako postoji C s tim parametrima, koji su parametri dizajna
koji tada postoji po Assmus- Mattsonovom teoremu?
Bi li taj dizajn mogao ujedno biti i dizajn s λ = 1
(za neku veću vrijednost parametra t )? Za vektor a = (1,0,2,0,1,0,2,0,...)
iz prostora (GF(3))^n "dovršite" njegov zapis tako da a
sigurno [i]ne[/i] pripada kodu C, a zatim
navedite još neki (konkretni) vektor iz tog prostora koji
također ne pripada kodu C.
Može li se, ako je kod C poznat, odrediti ispravna poruka iz koje je dobiven a ?
4. * ("bonus" zadatak za dodatnih 10 bodova, uzima se u obzir ako je na prva tri
zadatka ostvareno barem 15 bodova)
Projektivnoj ravnini reda n može se pridružiti binarni linearni kod C
kao linearna ljuska
redaka ili stupaca incidencijske matrice ravnine.
U slučaju parnog n, kod C, točnije kod
dobiven proširivanjem C pomoću "parity check" (dodatna koordinata 0
ili 1, za parnu odnosno neparnu težinu riječi iz C) ,
može pružiti značajne informacije o (moguće
hipotetičkoj) ravnini P. Naprotiv, za neparni n kod C je praktički beskoristan,
jer uvijek je
dim C = v-1 i C se sastoji od svih vektora parne težine,
duljine v nad GF(2).
Dokažite posljednju tvrdnju.
Upute: svaki vektor iz C je zbroj nekih redaka matrice
(skalari su samo 0 i 1 pa je linearna kombinacija uvijek zbroj nekih izvodnica – redaka).
Pokažite da je svaki vektor u C parne težine. Pogodnim izborom
nekih izvodnica - redaka pokažite da C sadrži sve vektore
koji imaju "obrnute" koordinate od vektora standardne baze.
Izvedite odatle potrebne zaključke.
ZADACI S 2. KOLOKVIJA
(Rješenja će uslijediti nešto kasnije)
Bodovi: 1(12), 2( , 3(10), 4(10 - bonus *)
1. (a) Je li istinita tvrdnja: projektivna ravnina reda 7 ima cikličku grupu automorfizama
koja na njoj djeluje regularno?
Kojoj tvrdnji o postojanju
diferencijskih skupova je ova tvrdnja ekvivalentna? Ako je tvrdnja istinita,
mora li za odgovarajući diferencijski skup postojati multiplikator i
koji je to multiplikator? Navedite teorem(e) na kojima se zasnivaju odgovori.
Kako biste započeli pokušaj konstrukcije projektivne ravnine reda 7 na
temelju prethodnog i u čemu bi nastao problem?
(b) Tzv. Golomb-Songova hipoteza o Hadamardovim diferencijskim skupovima
(tj. (v,k, λ ) diferencijskim skupovima s Hadamardovim parametrima
v = 4λ +3, k = 2λ +1) govori da ako
takav skup postoji u cikličkoj grupi reda v, onda je
v ili prim broj ili umnožak dva susjedna neparna prim broja
ili je za 1 manji od neke potencije broja 2.
Navedite primjere odgovarajućih diferencijskih skupova za sva tri navedena oblika v,
s tim da to budu tri različite vrijednosti v, v > 7.
2. Televizijska kuća emitira program na dva kanala i želi usporediti gledanost
svojih 7 najpopularnijih serija, kroz sve dane u tjednu,
tako da se u tih 7 dana svaka serija emitira po jedanput na svakom kanalu.
Plan je da se u svakom dnevnom terminu istodobno
prikažu dvije serije i da svake dvije serije budu
"suprotstavljene" dva puta (jedna na 1. kanalu, druga na 2. i obrnuto).
Radi jednostavnosti sheme može se uzeti dnevni "nulti" termin
u kojem se na oba
kanala emitira ista serija. Označe li se dani npr. nedjelja = 0, …,
subota = 6, dnevni termini i same serije numeriraju također
s 0,1,...,6, zadatak je načiniti traženu shemu
(uputa: poznata algebarska metoda mod 7).
Ako tehničari dobiju poruku oblika (2, 3, 5, 0) koja znači:
u utorak u terminu br. 3 na 1. kanalu ide serija br. 5,
a na 2. kanalu serija br. 0, hoće li moći ustanoviti da je
jedan od 4 podatka pogrešan i ispraviti ga?
3. Odredite parametre (duljinu n, dimenziju k, minimalnu
težinu d) linearnog ternarnog koda C tako da bude savršen,
da ima sposobnost ispravljanja dvije pogreške i da
razlika n-k ("redundancija") bude što manja.
(Alfabet je pritom
polje GF(3) = {0,1,2} s operacijama modulo 3).
Ako postoji C s tim parametrima, koji su parametri dizajna
koji tada postoji po Assmus- Mattsonovom teoremu?
Bi li taj dizajn mogao ujedno biti i dizajn s λ = 1
(za neku veću vrijednost parametra t )? Za vektor a = (1,0,2,0,1,0,2,0,...)
iz prostora (GF(3))^n "dovršite" njegov zapis tako da a
sigurno ne pripada kodu C, a zatim
navedite još neki (konkretni) vektor iz tog prostora koji
također ne pripada kodu C.
Može li se, ako je kod C poznat, odrediti ispravna poruka iz koje je dobiven a ?
4. * ("bonus" zadatak za dodatnih 10 bodova, uzima se u obzir ako je na prva tri
zadatka ostvareno barem 15 bodova)
Projektivnoj ravnini reda n može se pridružiti binarni linearni kod C
kao linearna ljuska
redaka ili stupaca incidencijske matrice ravnine.
U slučaju parnog n, kod C, točnije kod
dobiven proširivanjem C pomoću "parity check" (dodatna koordinata 0
ili 1, za parnu odnosno neparnu težinu riječi iz C) ,
može pružiti značajne informacije o (moguće
hipotetičkoj) ravnini P. Naprotiv, za neparni n kod C je praktički beskoristan,
jer uvijek je
dim C = v-1 i C se sastoji od svih vektora parne težine,
duljine v nad GF(2).
Dokažite posljednju tvrdnju.
Upute: svaki vektor iz C je zbroj nekih redaka matrice
(skalari su samo 0 i 1 pa je linearna kombinacija uvijek zbroj nekih izvodnica – redaka).
Pokažite da je svaki vektor u C parne težine. Pogodnim izborom
nekih izvodnica - redaka pokažite da C sadrži sve vektore
koji imaju "obrnute" koordinate od vektora standardne baze.
Izvedite odatle potrebne zaključke.
|
