Uvod u teoriju dizajna - Diplomski studij - PDF

Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna Uvodno predavanje...

Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna Uvodno predavanje Sanja Rukavina Tin Zrinski moodle.srce.hr Uvod u teoriju dizajna Uvod u teoriju dizajna - uvodno predavanje 1 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Uvod u kolegij - sadržaj predavanja 1 Uvodne napomene o realizaciji kolegija 2 Uvodni primjeri Najava rukometnih utakmica Organizacija istraživanja 3 Osnovni pojmovi teorije dizajna Uvod u teoriju dizajna - uvodno predavanje 2 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Način realizacije kolegija I predavanja I seminari I vježbe Osnovna literatura: D. R. Stinson: Combinatorial Designs with Selected Applications (Lecture Notes) moodle.srce.hr Uvod u teoriju dizajna Uvod u teoriju dizajna - uvodno predavanje 3 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Najava rukometnih utakmica Televizijska kuća koja je 2007. godine pratila 20. svjetsko muško rukometno prvenstvo u Njemačkoj odlučila je kao najavu uoči svake utakmice napraviti razgovor s trojicom igrača prve sedmorke. Kako neki igrači ne bi bili favorizirani, odlučeno je da se svaka dva igrača susretnu točno jednom. Televizijska kuća pravilno je predvidjela da će se Hrvatska plasirati u drugo kolo, odnosno da će odigrati barem 7 utakmica (3 utakmice u skupini prvoga kruga natjecanja i 4 utakmice u skupini drugoga kruga natjecanja). Napravite raspored televizijskih razgovora s igračima! Uvod u teoriju dizajna - uvodno predavanje 4 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Najava rukometnih utakmica Jedan od mogućih rasporeda prikazan je u sljedećoj tablici. utakmica igrači 1. utakmica Džomba, Lacković, Jerković 2. utakmica Jerković, Metličić, Balić 3. utakmica Balić, Kaleb, Džomba 4. utakmica Džomba, Vori, Metličić 5. utakmica Lacković, Vori, Balić 6. utakmica Jerković, Vori, Kaleb 7. utakmica Lacković, Metličić, Kaleb Uvod u teoriju dizajna - uvodno predavanje 5 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Organizacija istraživanja Potrebno je usporediti šest liječnika u okviru istraživanja pouzdanosti dijagnosticiranja na način da svaki pacijent koji sudjeluje u istraživanju bude pregledan od strane različitih liječnika samostalno i nezavisno. Na koji način treba organizirati to istraživanje, ako se zna da svaki pacijent može podnijeti najviše tri pregleda? Uvod u teoriju dizajna - uvodno predavanje 6 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Organizacija istraživanja pacijent 1 2 3 4 5 6 1 1 1 1 0 0 0 2 1 1 0 1 0 0 3 1 0 1 0 0 1 4 1 0 0 1 1 0 5 1 0 0 0 1 1 6 0 1 1 0 1 0 7 0 1 0 1 0 1 8 0 1 0 0 1 1 9 0 0 1 1 1 0 10 0 0 1 1 0 1 Uvod u teoriju dizajna - uvodno predavanje 7 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Osnovni pojmovi teorije dizajna Incidencijska struktura D je uredena trojka (P, B, I), pri čemu je P neprazni skup čije elemente nazivamo točkama, B kolekcija podskupova od P čije elemente nazivamo blokovima i I ⊆ P × B relacija incidencije. Neka su v , k i λ prirodni brojevi. Struktura D = (P, B, I) je t − (v , k, λ) dizajn ako vrijedi: 1 |P| = v , 2 svaki element skupa B incidentan je s točno k elemenata skupa P, 3 svakih t elemenata skupa P incidentno je s točno λ elemenata skupa B. Uvod u teoriju dizajna - uvodno predavanje 8 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna BIBD Definicija Neka su v, k i λ prirodni brojevi takvi da je v > k ≥ 2. Struktura D = (P, B, I) je (v , k, λ)− balansirani nepotpuni blok dizajn ((v , k, λ)−BIBD) ako vrijedi: 1 |P| = v , 2 svaki element skupa B incidentan je s točno k elemenata skupa P, 3 svakih par različitih elemenata skupa P incidentan je s točno λ elemenata skupa B. Uvod u teoriju dizajna - uvodno predavanje 9 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Primjer I Najava rukometnih utakmica: (7,3,1)-BIBD I Organizacija istraživanja: (6,3,2)-BIBD Primjer Neka se B sastoji od svih k-članih podskupova skupa P koji ima v elemenata. Tada je (P, B, I) BIBD s parametrima    v −2 v , k,. k −2 Uvod u teoriju dizajna - uvodno predavanje 10 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Teorem Neka je D = (P, B, I) (v , k, λ)-BIBD. Svaka točka pojavljuje se u dizajnu D točno λ (v − 1) r= k −1 puta. Teorem (v , k, λ)-BIBD ima točno λ v2 − v
vr b= = k k2 − k blokova. I Za 2 − (v , k, λ) dizajn broj n = r − λ zove se red dizajna. Uvod u teoriju dizajna - uvodno predavanje 11 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Matrica incidencije Neka je D = (P, B, I) konačna incidencijska struktura takva da je |P| = v i |B| = b. Označimo elemente skupa P sa P1 ,..., Pv i elemente skupa B sa x1 ,..., xb. Matrica incidencije incidencijske strukture D je v × b matrica M = (mij )  1, (Pi , xj ) ∈ I, mi,j = 0, (Pi , xj ) ∈ / I. Struktura D∗ = (P ∗ , B ∗ , I ∗ ), gdje je P ∗ = B, B ∗ = P, I ∗ = {(x, P) | (P, x) ∈ I} naziva se dualna struktura strukture D. Uvod u teoriju dizajna - uvodno predavanje 12 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Primjer: (7,3,1)-dizajn, najava rukometnih utakmica Džomba→1, Lacković→2, Jerković→3, Metličić→4, Balić→5, Kaleb→6, Vori→7   1 1 1 0 0 0 0   0 0 1 1 1 0 0     1 0 0 0 1 1 0   M=  1 0 0 1 0 0 1     0 1 0 0 1 0 1    0 0 1 0 0 1 1  0 1 0 1 0 1 0 Uvod u teoriju dizajna - uvodno predavanje 13 / 14 Uvodne napomene o realizaciji kolegija Uvodni primjeri Osnovni pojmovi teorije dizajna Teorem Neka je M v × b 0-1 matrica. Matrica M je incidencijska matrica (v , b, r , k, λ)-BIBDa ako i samo ako vrijedi: 1 MMT = λJv + (r − λ) Iv , 2 uv M = kub. Oznake: I In - n × n jedinična matrica, I Jn - n × n matrica čiji su svi elementi jednaki 1, I un - vektor duljine n čiji su svi elementi jednaki 1, I MT - transponirana matrica matrice M. Uvod u teoriju dizajna - uvodno predavanje 14 / 14 Izomorfizmi i automorfizmi Konstrukcija novih dizajna iz postojećih Fisherova nejednakost Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 2. predavanje Uvod u teoriju dizajna - 2. predavanje 1/6 Izomorfizmi i automorfizmi Konstrukcija novih dizajna iz postojećih Fisherova nejednakost Sadržaj predavanja 1 Izomorfizmi i automorfizmi 2 Konstrukcija novih dizajna iz postojećih 3 Fisherova nejednakost Uvod u teoriju dizajna - 2. predavanje 2/6 Izomorfizmi i automorfizmi Konstrukcija novih dizajna iz postojećih Fisherova nejednakost Neka su D = (P, B, I) i D0 = (P 0 , B 0 , I 0 ) incidencijske strukture. Bijektivno preslikavanje f : P → P 0 je izomorfizam iz D na D0 ako je {{f (P) : P ∈ B} : B ∈ B} = B 0. Ako je D0 = D, onda se preslikavanje f naziva automorfizam. Skup svih automorfizama strukture D je grupa s obzirom na kompoziciju funkcija. Ta se grupa naziva puna grupa automorfizama strukture D i označava sa AutD. Struktura D se naziva samodualna struktura ako je izomorfna svojoj dualnoj strukturi. Uvod u teoriju dizajna - 2. predavanje 3/6 Izomorfizmi i automorfizmi Konstrukcija novih dizajna iz postojećih Fisherova nejednakost Teorem h i Neka su M = [mi,j ] i M0 = mi,j 0 incidencijske matrice dva (v , b, r , k, λ) −BIBDa D i D0. Dizajni D i D0 su izomorfni ako i samo ako postoje permutacija γ od {1,... , v } i permutacija β od {1,... , b} takve da je 0 mi,j = mγ(i),β(j) za sve 1 ≤ i ≤ v , 1 ≤ j ≤ b. Uvod u teoriju dizajna - 2. predavanje 4/6 Izomorfizmi i automorfizmi Konstrukcija novih dizajna iz postojećih Fisherova nejednakost Konstrukcija novih dizajna iz postojećih Teorem Ako postoje (v , k, λ1 ) −BIBD i (v , k, λ2 ) −BIBD, onda postoji (v , k, λ1 + λ2 ) −BIBD. Teorem Ako postoji (v , b, r , k, λ) −BIBD, onda postoji (v , b, b − r , v − k, b − 2r + λ) −BIBD. I Dovoljno je proučavati dizajne za koje je k < v2. Uvod u teoriju dizajna - 2. predavanje 5/6 Izomorfizmi i automorfizmi Konstrukcija novih dizajna iz postojećih Fisherova nejednakost Fisherova nejednakost Teorem (Fisherova nejednakost) Ako postoji (v , b, r , k, λ) −BIBD, onda je b ≥ v. I r ≥k I λ (v − 1) ≥ k 2 − k Uvod u teoriju dizajna - 2. predavanje 6/6 Simetrični dizajni Rezidualni i derivirani dizajni Bruck-Ryser-Chowla teorem Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 3. predavanje Uvod u teoriju dizajna - 3. predavanje 1/8 Simetrični dizajni Rezidualni i derivirani dizajni Bruck-Ryser-Chowla teorem Sadržaj predavanja 1 Simetrični dizajni 2 Rezidualni i derivirani dizajni 3 Bruck-Ryser-Chowla teorem Uvod u teoriju dizajna - 3. predavanje 2/8 Simetrični dizajni Rezidualni i derivirani dizajni Bruck-Ryser-Chowla teorem Simetrični dizajni Balansirani nepotpuni blok dizajn za kojega vrijedi da je b = v (ili, ekvivalentno, r = k ili λ (v − 1) = k 2 − k) se naziva simetrični BIBD. Primjer I Najava rukometnih utakmica: (7,3,1)-BIBD je simetrični dizajn I Organizacija istraživanja: (6,3,2)-BIBD nije simetrični dizajn Uvod u teoriju dizajna - 3. predavanje 3/8 Simetrični dizajni Rezidualni i derivirani dizajni Bruck-Ryser-Chowla teorem Teorem Neka su B i B 0 dva različita bloka simetričnog (v , k, λ) −BIBDa. Tada je |B ∩ B 0 | = λ. Korolar Neka je M incidencijska matrica simetričnog (v , k, λ) −BIBDa. Tada je i MT incidencijska matrica simetričnog (v , k, λ) −BIBDa. Uvod u teoriju dizajna - 3. predavanje 4/8 Simetrični dizajni Rezidualni i derivirani dizajni Bruck-Ryser-Chowla teorem Neka je D = (P, B, I) simetrični (v , k, λ)− BIBD i B0 ∈ B. Tada je Der (P, B, B0 ) = (B0 , {B ∩ B0 |B ∈ B, B 6= B0 } , I) derivirani dizajn dizajna D s obzirom na blok B0. Dizajn Res(P, B, B0 ) = (P \ B0 , {B \ B0 |B ∈ B, B 6= B0 } , I) je rezidualni dizajn dizajna D s obzirom na blok B0. Uvod u teoriju dizajna - 3. predavanje 5/8 Simetrični dizajni Rezidualni i derivirani dizajni Bruck-Ryser-Chowla teorem Primjer: simetrični (15,7,3) - blok dizajn   1 1 1 1 1 1 1 0 0 0 0 0 0 0 0   1 1 1 0 0 0 0 1 1 1 1 0 0 0 0     1 1 1 0 0 0 0 0 0 0 0 1 1 1 1     1 0 0 1 1 0 0 1 1 0 0 1 1 0 0     1 0 0 1 1 0 0 0 0 1 1 0 0 1 1     1 0 0 0 0 1 1 1 1 0 0 0 0 1 1   1 0 0 0 0 1 1 0 0 1 1 1 1 0 0     M= 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0    0 1 0 1 0 1 0 0 1 0 1 0 1 0 1     0 1 0 0 1 0 1 1 0 1 0 0 1 0 1        0 1 0 0 1 0 1 0 1 0 1 1 0 1 0      0 0 1 1 0 0 1 1 0 0 1 1 0 0 1     0 0 1 1 0 0 1 0 1 1 0 0 1 1 0    0 0 1 0 1 1 0 1 0 0 1 0 1 1 0  0 0 1 0 1 1 0 0 1 1 0 1 0 Uvod0u teoriju 1 dizajna - 3. predavanje 6/8 Simetrični dizajni Rezidualni i derivirani dizajni Bruck-Ryser-Chowla teorem Teorem Neka je D = (P, B, I) simetrični (v , k, λ)−BIBD i B0 ∈ B. Tada je Der (P, B, B0 ) (k, λ, λ − 1)−BIBD, a Res(P, B, B0 ) je (v − k, k − λ, λ)−BIBD. Uvod u teoriju dizajna - 3. predavanje 7/8 Simetrični dizajni Rezidualni i derivirani dizajni Bruck-Ryser-Chowla teorem Bruck-Ryser-Chowla teorem Bruck-Ryser-Chowla teorem Neka postoji simetrični (v , k, λ)−blok dizajn reda n. I Ako je v paran broj, onda je n potpuni kvadrat. I Ako je v neparan broj, onda moraju postojati cijeli brojevi x, y i z za koje vrijedi (x, y , z) 6= (0, 0, 0), takvi da je v −1 nx 2 + (−1) 2 λy 2 = z 2. Uvod u teoriju dizajna - 3. predavanje 8/8 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 4. predavanje Uvod u teoriju dizajna - 4. predavanje 1 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Sadržaj predavanja 1 Diferencijski skupovi 2 Neke konstrukcije diferencijskih skupova 3 Konstrukcija simetričnih dizajna iz diferencijskih skupova Uvod u teoriju dizajna - 4. predavanje 2 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Diferencijski skupovi Neka je G konačna aditivna Abelova grupa reda v u kojoj je 0 neutralni element. Neka su k i λ prirodni brojevi, pri čemu je 2 ≤ k < v. Tada je D ⊆ G (v , k, λ) −diferencijski skup u G ako vrijedi sljedeće: 1 |D| = k, 2 multiskup {x − y |x, y ∈ D, x 6= y } sadrži svaki element od G \ {0} točno λ puta. Za g ∈ G definiramo translat od D sa D + g = {x + g |x ∈ D}. Skup svih v translata od D je Dev (D) = {D + g |g ∈ G }. Uvod u teoriju dizajna - 4. predavanje 3 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Primjer: (13,4,1)-diferencijski skup u (Z13 , +) D = {0, 1, 3, 9} Razlike (modulo 13) svih parova različitih elemenata od D su: 0 − 1 = 12 3−0=3 0 − 3 = 10 3−1=2 0−9=4 3−9=7 1−0=1 9−0=9 1 − 3 = 11 9−1=8 1−9=5 9−3=6 Svaki element od Z13 \ {0} dobiven je točno jednom. D je (13,4,1)-diferencijski skup. Uvod u teoriju dizajna - 4. predavanje 4 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Primjer Ne postoji (16,6,2)-diferencijski skup u grupi (Z16 , +), ali postoji u grupi (Z4 × Z4 , +). D = {(0, 1) , (0, 2) , (0, 3) , (1, 0) , (2, 0) , (3, 0)} Uvod u teoriju dizajna - 4. predavanje 5 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Neke konstrukcije diferencijskih skupova Neka je q neparni prosti broj. Tada je sa QR(q) = z 2 mod q|z ∈ Fq , 1 ≤ z ≤ q − 1  odreden skup kvadratnih ostataka modulo q (kvadratni ostaci polja Fq ). Kako je z 2 ≡ (q − z)2 (mod q) za sve z ∈ Z , vrijedi   2 q−1 QR(q) = z mod q|z ∈ Z , 1 ≤ z ≤. 2 Definiramo i skup QNR(q) = Fq \ (QR(q) ∪ {0}) kvadratnih neostataka polja Fq. Uvod u teoriju dizajna - 4. predavanje 6 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Teorem   Neka je q ≡ 3 (mod 4) prost broj. Tada je QR(q) q, q−1 q−3 2 , 4 − diferencijski skup u Zq. Teorem (Singerovi diferencijski skupovi) Neka je q potencija prostog broja. Tada postoji q 2 + q + 1, q + 1, q − diferencijski skup u Zq2 +q+1.
Uvod u teoriju dizajna - 4. predavanje 7 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Neka je D (v , k, λ) − diferencijski skup u aditivnoj Abelovoj grupi G. Za prirodan broj m definiramo mD = {mx|x ∈ D} , pri čemu je mx suma m kopija od x. Tada m zovemo multiplikatorom od D ako je mD = D + g za neki g ∈ G. Takoder kažemo da je D fiksiran multiplikatorom m ako je mD = D. Uvod u teoriju dizajna - 4. predavanje 8 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Teorem o multiplikatoru Neka postoji (v , k, λ) − diferencijski skup D u aditivnoj Abelovoj grupi G reda v. Prost broj p je multiplikator od D ako vrijedi: 1 M(p, v ) = 1, 2 k − λ ≡ 0 (mod p), 3 p > λ. Uvod u teoriju dizajna - 4. predavanje 9 / 10 Diferencijski skupovi Neke konstrukcije diferencijskih skupova Konstrukcija simetričnih dizajna iz diferencijskih skupova Teorem Neka je D (v , k, λ) − diferencijski skup u aditivnoj Abelovoj grupi G. Tada je (G , Dev (D)) simetrični (v , k, λ) −BIBD. Primjer Skup D = {1, 2, 4} je (7, 3, 1)−diferencijski skup u (Z7 , +). (Z7 , Dev (D)) je (7, 3, 1)−simetrični dizajn. Uvod u teoriju dizajna - 4. predavanje 10 / 10 Hadamardove matrice Hadamardovi dizajni Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 5. predavanje Uvod u teoriju dizajna - 5. predavanje 1/9 Hadamardove matrice Hadamardovi dizajni Sadržaj predavanja 1 Hadamardove matrice Konstrukcija novih Hadamardovih matrica iz postojećih 2 Hadamardovi dizajni Uvod u teoriju dizajna - 5. predavanje 2/9 Hadamardove matrice Hadamardovi dizajni Hadamardove matrice Hadamardova matrica reda m je m × m matrica H = [hi,j ], hi,j ∈ {−1, 1}, za koju je HHT = mIm. Primjer m = 1: H = [−1]   1 1 m = 2: H = 1 −1 Ako su svi elementi prvog retka i prvog stupca Hadamardove matrice jednaki 1 kažemo da je ta Hadamardova matrica u standardnom obliku. Uvod u teoriju dizajna - 5. predavanje 3/9 Hadamardove matrice Hadamardovi dizajni Teorem Ako postoji Hadamardova matrica reda m > 2, onda je m ≡ 0 (mod 4). Uvod u teoriju dizajna - 5. predavanje 4/9 Hadamardove matrice Hadamardovi dizajni Konstrukcija novih Hadamardovih matrica iz postojećih Kroneckerov produkt Neka je H1 = [hi,j ] Hadamardova matrica reda m1 i H2 Hadamardova matrica reda m2. Kroneckerov produkt H1 ⊗ H2 je matrica reda m1 m2 dobivena tako da se svaki element hi,j matrice H1 zamijeni m2 × m2 matricom hi,j H2 (pri čemu xH2 označava matricu dobivenu iz H2 množenjem svakog elementa sa x). Teorem Ako je H1 Hadamardova matrica reda m1 i H2 Hadamardova matrica reda m2 , onda je H1 ⊗ H2 Hadamardova matrica reda m1 m2. Uvod u teoriju dizajna - 5. predavanje 5/9 Hadamardove matrice Hadamardovi dizajni Hadamardovi dizajni Teorem Hadamardova matrica reda m postoji
ako i samo ako postoji (simetričan) m − 1, 12 m − 1, 14 m − 1 −BIBD. Simetričan blok dizajn s parametrima m − 1, 21 m − 1, 14 m − 1
naziva se Hadamardov dizajn. Dizajn D∗ = (P ∗ , B ∗ , I ∗
) dobiven iz Hadamardovog m − 1, 21 m − 1, 41 m − 1 −dizajna na sljedeći način: I P ∗ = P ∪ {∞} , I B ∗ = {B ∪ {∞} |B ∈ B} ∪ {P \ B|B ∈ B}, je 3 − m, 12 m, 14 m − 1 dizajn i naziva se Hadamardov 3-dizajn.
Uvod u teoriju dizajna - 5. predavanje 6/9 Hadamardove matrice Hadamardovi dizajni Primjer: Hadamardov dizajn i Hadamardova matrica   1 1 1 0 0 0 0  0 0 1 1 1 0 0     1 0 0 0 1 1 0    M=  1 0 0 1 0 0 1  →  0 1 0 0 1 0 1     0 0 1 0 0 1 1  0 1 0 1 0 1 0 1 1 1 1 1 1 1 1    1 1  1 1 −1 −1 −1 −1    1 −1 −1 1 1 1 −1 −1     1 1 −1 −1 −1 1 1 −1  H=  1 1 −1   −1 1 −1 −1 1    1 −1 1 −1 −1 1 −1 1     1 −1 −1 1 −1 −1 1 1  1 −1 1 −1 1 −1 1 −1Uvod u teoriju dizajna - 5. predavanje 7/9 Hadamardove matrice Hadamardovi dizajni Primjer: Hadamardov 3-(8,4,1) dizajn   1 1 1 0 0 0 0 1  0 0 1 1 1 0 0 1     1 0 0 0 1 1 0 1     1 0 0 1 0 0 1 1     0 1 0 0 1 0 1 1     0 0 1 0 0 1 1 1     0 1 0 1 0 1 0 1   0 M =   0 0 0 1 1 1 1 0    1 1 0 0 0 1 1 0       0 1 1 1 0 0 1 0     0 1 1 0 1 1 0 0     1 0 1 1 0 1 0 0     1 1 0 1 1 0 0 0  1 0 1 0 1 0 1 0 Uvod u teoriju dizajna - 5. predavanje 8/9 Hadamardove matrice Hadamardovi dizajni Korolar Ako je m − 1 prost broj, onda postoji Hadamardova matrica reda m. Uvod u teoriju dizajna - 5. predavanje 9/9 Konferencijske matrice Konferencijske matrice i Hadamardove matrice Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 6. predavanje Uvod u teoriju dizajna - 6. predavanje 1/6 Konferencijske matrice Konferencijske matrice i Hadamardove matrice Sadržaj predavanja 1 Konferencijske matrice Kvadratni karakter modulo q Konferencijske matrice 2 Konferencijske matrice i Hadamardove matrice Uvod u teoriju dizajna - 6. predavanje 2/6 Konferencijske matrice Konferencijske matrice i Hadamardove matrice Kvadratni karakter modulo q Kvadratni karakter modulo q Za neparni prost broj q definiramo funkciju   0 , if x = 0, χq (x) = 1 , if x ∈ QR(q), −1 , if x ∈ QNR(q).  Funkciju χq nazivamo kvadratni karakter modulo q. Lema Neka je q neparan prost broj. Tada vrijedi: X 1 χq (x) = 0, x∈Zq X 2 χq (x)χq (x + y ) = −1 za sve y ∈ Zq \0. x∈Zq Uvod u teoriju dizajna - 6. predavanje 3/6 Konferencijske matrice Konferencijske matrice i Hadamardove matrice Konferencijske matrice Konferencijske matrice Konferencijska matrica reda n je kvadratna n × n matrica C = [ci,j ] čiji su elementi 0, 1, ili -1, pri čemu vrijedi ci,i = 0 za sve i i CCT = (n − 1)In. Konferencijska matrica je simetrična ako je ci,j = cj,i za sve i, j ∈ Nn. Uvod u teoriju dizajna - 6. predavanje 4/6 Konferencijske matrice Konferencijske matrice i Hadamardove matrice Konferencijske matrice Teorem Neka je q ≡ 1 (mod 4) prost broj. Matrica W = [wi,j ], čiji su retci i stupci indeksirani sa Zq ∪ {∞}, definirana na sljedeći način:    0 , if i = j = ∞, 1 , if i = ∞, j 6= ∞,  wi,j =   1 , if i 6= ∞, j = ∞, χq (i − j) , if i, j ∈ Zq ,  je simetrična konferencijska matrica reda q + 1. Uvod u teoriju dizajna - 6. predavanje 5/6 Konferencijske matrice Konferencijske matrice i Hadamardove matrice Konstrukcija Hadamardovih matrica pomoću konferencijskih matrica Teorem Neka je C simetrična konferencijska matrica reda m. Tada je matrica   C + Im C − Im H= C − Im −C − Im Hadamardova matrica reda 2m. Korolar Ako je m neparan broj i 2m − 1 prost broj, onda postoji Hadamardova matrica reda 4m. Uvod u teoriju dizajna - 6. predavanje 6/6 Rješivi dizajni Afine ravnine Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 7. predavanje Uvod u teoriju dizajna - 7. predavanje 1/8 Rješivi dizajni Afine ravnine Sadržaj predavanja 1 Rješivi dizajni 2 Afine ravnine Projektivne i afine ravnine Uvod u teoriju dizajna - 7. predavanje 2/8 Rješivi dizajni Afine ravnine Rješivi dizajni Neka je D = (P, B, I) (v , k, λ)−BIBD. Paralelna klasa u D je skup koji se sastoji od disjunktnih blokova iz B čija unija je P. I Paralelna klasa mora sadržavati kv blokova i BIBD može imati paralelnu klasu jedino ako je v ≡ 0 (mod k). Particija od B na r paralelnih klasa se naziva rezolucija, a dizajn D = (P, B, I) je rješiv ako B ima barem jednu rezoluciju. Uvod u teoriju dizajna - 7. predavanje 3/8 Rješivi dizajni Afine ravnine Afine ravnine Afina ravnina reda n je n2 , n, 1 −BIBD, pri čemu je r = n + 1 i
b = n2 + n. Teorem Za svaki
prosti broj p postoji afina ravnina reda p ( p 2 , p, 1 −BIBD). Teorem Svaka afina ravnina je rješiva. Uvod u teoriju dizajna - 7. predavanje 4/8 Rješivi dizajni Afine ravnine Lema Neka je (P, B, I) afina ravnina reda n. Neka je P ∈ P, B ∈ B i P∈/ B. Tada postoji točno jedan blok B 0 ∈ B takav da je P ∈ B 0 i B ∩ B 0 = ∅. Uvod u teoriju dizajna - 7. predavanje 5/8 Rješivi dizajni Afine ravnine Lema Neka je (P, B, I) afina ravnina reda n. Tada je binarna relacija ∼ na skupu blokova B, definirana na sljedeći način: B ∼ B 0 ako je B = B 0 ili B ∩ B 0 = ∅, relacija ekvivalencije. Lema Neka je D = (P, B, I) afina ravnina reda n. Tada je svaka klasa ekvivalencije od ∼ paralelna klasa u D. Uvod u teoriju dizajna - 7. predavanje 6/8 Rješivi dizajni Afine ravnine Projektivne i afine ravnine Projektivne ravnine Projektivna ravnina reda n je n2 + n + 1, n + 1, 1 −BIBD.
I Projektivna ravnina je simetrični BIBD. Primjer Simetrični (7, 3, 1)− dizajn je projektivna ravnina. Uvod u teoriju dizajna - 7. predavanje 7/8 Rješivi dizajni Afine ravnine Projektivne i afine ravnine Teorem Postoji afina ravnina reda n ako i samo ako postoji projektivna ravnina reda n. Uvod u teoriju dizajna - 7. predavanje 8/8 Boseova nejednakost Afino rješivi dizajni Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 8. predavanje Uvod u teoriju dizajna - 8. predavanje 1/4 Boseova nejednakost Afino rješivi dizajni Sadržaj predavanja 1 Boseova nejednakost 2 Afino rješivi dizajni Uvod u teoriju dizajna - 8. predavanje 2/4 Boseova nejednakost Afino rješivi dizajni Boseova nejednakost Teorem: Boseova nejednakost Ako postoji rješivi (v , b, r , k, λ)−BIBD, onda je b ≥ v + r − 1. Lema Neka su (v , b, r , k, λ) parametri balansiranog nepotpunog blok dizajna. Tada je b ≥ v + r − 1 ako i samo ako je r ≥ k + λ. Uvod u teoriju dizajna - 8. predavanje 3/4 Boseova nejednakost Afino rješivi dizajni Afino rješivi dizajni Rješivi BIBD za kojega je b = v + r − 1 je afino rješiv. I BIBD je afino rješiv ako i samo je = k + λ. Teorem Ako postoji Hadamardova
matrica reda m, onda postoji afino rješivi m, 12 m, 21 m − 1 −BIBD. Teorem Bilo koja dva bloka iz različitih paralelnih klasa afino rješivog 2 (v , k, λ)−BIBDa sijeku se u točno kv točaka. Uvod u teoriju dizajna - 8. predavanje 4/4 Steinerov sustav trojki Kvazigrupe i latinski kvadrati Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 9. predavanje Uvod u teoriju dizajna - 9. predavanje 1/8 Steinerov sustav trojki Kvazigrupe i latinski kvadrati Sadržaj predavanja 1 Steinerov sustav trojki 2 Kvazigrupe i latinski kvadrati Uvod u teoriju dizajna - 9. predavanje 2/8 Steinerov sustav trojki Kvazigrupe i latinski kvadrati Steinerov sustav trojki Steinerov sustav trojki reda v , u oznaci STS(v ), je (v , 3, 1)− BIBD. Primjer (7, 3, 1)−BIBD je STS(7). Lema Ako STS(v ) postoji, onda je v ≡ 1, 3 (mod 6), v ≥ 7. Uvod u teoriju dizajna - 9. predavanje 3/8 Steinerov sustav trojki Kvazigrupe i latinski kvadrati Kvazigrupe Neka je S konačan skup i neka je ◦ binarna operacija definirana na S (◦ : S × S → S). Uredeni par (S, ◦) je kvazigrupa ako vrijedi: 1 Za sve x, y ∈ S, jednadžba x ◦ z = y ima jedinstveno rješenje z u S. 2 Za sve x, y ∈ S, jednadžba z ◦ x = y ima jedinstveno rješenje z u S. Uvod u teoriju dizajna - 9. predavanje 4/8 Steinerov sustav trojki Kvazigrupe i latinski kvadrati Latinski kvadrati Neka je S konačan skup i neka je |S| = n. Kvadratna tablica A dimenzije n × n s elementima iz S je latinski kvadrat reda n ako je svaki red od A permutacija od S i svaki stupac od A permutacija od S. Uvod u teoriju dizajna - 9. predavanje 5/8 Steinerov sustav trojki Kvazigrupe i latinski kvadrati Operacijska (Cayleyeva) tablica binarne operacije ◦ : S × S → S je |S| × |S| tablica A = [ax,y ], pri čemu je ax,y = x ◦ y. Teorem Neka je ◦ binarna operacija definirana na konačnom skupu S, |S| = n. Tada je (S, ◦) kvazigrupa ako i samo ako je pripadna operacijska tablica latinski kvadrat reda n. Uvod u teoriju dizajna - 9. predavanje 6/8 Steinerov sustav trojki Kvazigrupe i latinski kvadrati Kvazigrupa (S, ◦) je idempotentna ako je x ◦ x = x, za sve x ∈ S. Kvazigrupa (S, ◦) je simetrična ako je x ◦ y = y ◦ x, za sve x, y ∈ S. Latinski kvadrat A = [ax,y ] je idempotentan ako je ax,x = x za sve x. Latinski kvadrat A = [ax,y ] je simetričan ako je ax,y = ay ,x za sve x, y. Lema Ako postoji simetrična idempotentna kvazigrupa reda n, onda je n neparan. Uvod u teoriju dizajna - 9. predavanje 7/8 Steinerov sustav trojki Kvazigrupe i latinski kvadrati Teorem Simetrična idempotentna kvazigrupa reda n postoji, ako i samo ako je n neparan. Uvod u teoriju dizajna - 9. predavanje 8/8 Boseova konstrukcija Skolemova konstrukcija Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 10. predavanje Uvod u teoriju dizajna - 10. predavanje 1/8 Boseova konstrukcija Skolemova konstrukcija Sadržaj predavanja 1 Boseova konstrukcija 2 Skolemova konstrukcija Simetrične poluidempotentne kvazigrupe parnog reda Uvod u teoriju dizajna - 10. predavanje 2/8 Boseova konstrukcija Skolemova konstrukcija Boseova konstrukcija Neka je v = 6t + 3, t ≥ 1. Neka je (S, ◦) simetrična idempotentna kvazigrupa (neparnog) reda 2t + 1. Neka je < relacija potpunog uredaja definirana na S. Definirajmo P = S × Z3. Za svaki x ∈ S definirajmo blok Bx = {(x, 0) , (x, 1) , (x, 2)}. Za sve x, y ∈ S, x < y i za svaki i ∈ Z3 neka je Bx,y ,i = {(x, i) , (y , i) , (x ◦ y , (i + 1) mod3)}. Tada definiramo B = {Bx |x ∈ S} ∪ {Bx,y ,i |x, y ∈ S, x < y , i ∈ Z3 }. Uvod u teoriju dizajna - 10. predavanje 3/8 Boseova konstrukcija Skolemova konstrukcija I Za ovako definirane P i B i uobičajenu incidenciju, (P, B, I) je STS(v ). Očito je da je |P| = v i da svaki blok iz B sadrži tri točke. Treba još pokazati da se svaki par točaka pojavljuje zajedno u točno jednom bloku. Teorem Za sve v ≡ 3 (mod 6), v ≥ 9, postoji STS(v ). Uvod u teoriju dizajna - 10. predavanje 4/8 Boseova konstrukcija Skolemova konstrukcija Skolemova konstrukcija Skolemova konstrukcija je modifikacija Boseove konstrukcije, U Boseovoj konstrukciji koristi se simetrična idempotentna kvazigrupa. Kako takve grupe parnog reda ne postoje, u ovoj se konstrukciji koriste simetrične kvazigrupe koje su poluidempotentne. Kvazigrupa (Zn , ◦) je poluidempotentna ako vrijedi , ako je 0 ≤ x < n2 ,  x x ◦x = x − 2 , ako je n2 ≤ x < n. n I Na dijagonali operacijske tablice poluidempotentne kvazigrupe (Zn , ◦) nalaze se redom sljedeći elementi: n n 0, 1,... , − 1, 0, 1,... , − 1. 2 2 Uvod u teoriju dizajna - 10. predavanje 5/8 Boseova konstrukcija Skolemova konstrukcija Simetrične poluidempotentne kvazigrupe parnog reda Konstrukcija simetrične poluidempotentne kvazigrupe parnog reda Konstruirajmo simetričnu poluidempotentnu kvazigrupu parnog reda n. Promotrimo (Zn , +) pri čemu je zbrajanje definirano modulo n. (Za n je neparan (Zn , +) je simetrična idempotentna kvazigrupa.) Kada je n paran, tada se medu vrijednostima (x + x (mod n)|x ∈ Zn ) svaki parni ostatak iz Zn nalazi točno dva puta, a glavna dijagonala operacijske tablice je 0, 2,... , n − 2, 0, 2,... , n − 2. Uvod u teoriju dizajna - 10. predavanje 6/8 Boseova konstrukcija Skolemova konstrukcija Simetrične poluidempotentne kvazigrupe parnog reda Dakle, moramo presložiti elemente od Zn tako da na glavnoj dijagonali dobijemo n n 0, 1,... , − 1, 0, 1,... , − 1. 2 2 Jedna permutacija kojom je to moguće postići je  π 2 , ako je x paran, π(x) = x+n−1 2 , ako je x neparan. Operaciju u kvazigrupi (Zn , ◦) definiramo sa x ◦ y = π ((x + y ) (mod n)). Uvod u teoriju dizajna - 10. predavanje 7/8 Boseova konstrukcija Skolemova konstrukcija Simetrične poluidempotentne kvazigrupe parnog reda Teorem Simetrična poluidempotentna kvazigrupa reda n postoji ako i samo ako je n paran. Teorem Za sve v ≡ 1 (mod 6) postoji STS(v ). Teorem STS(v ) postoji ako i samo ako je v ≡ 1, 3 (mod 6). Uvod u teoriju dizajna - 10. predavanje 8/8 Ciklički dizajni Ciklički Steinerov sustav trojki Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 11. predavanje Uvod u teoriju dizajna - 11. predavanje 1 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Sadržaj predavanja 1 Ciklički dizajni Diferencijska familija 2 Ciklički Steinerov sustav trojki Heffterov problem razlika Uvod u teoriju dizajna - 11. predavanje 2 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki (v , k, λ)−BIBD D = (P, B, I) je ciklički ako je P = Zv i ako je za x ∈ P sa x → (x + 1) (mod v ) odreden automorfizam dizajna D. I simetrični BIBD konstruiran iz diferencijskog skupa (Zv , +) je ciklički BIBD. Uvod u teoriju dizajna - 11. predavanje 3 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Diferencijska familija Neka je G konačna aditivna Abelova grupa reda v u kojoj je 0 neutralni element. (v , k, λ) −diferencijska familija u G je kolekcija podskupova D = {D1 ,... , Ds } za koju vrijedi 1 Di ⊆ G za 1 ≤ i ≤ s, 2 |Di | = k za 1 ≤ i ≤ s, 3 kolekcija vrijednosti x − y (x, y ∈ Di , x 6= y , 1 ≤ i ≤ s) sadrži svaki element iz G \ {0} točno λ puta. Podskupovi D1 ,... , Ds se nazivaju bazni blokovi. I Broj baznih blokova je s = λ kv2−1 −k. Definiramo Dev (D) = {Di + g |g ∈ G , 1 ≤ i ≤ s}. Uvod u teoriju dizajna - 11. predavanje 4 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Diferencijska familija Teorem Neka je D (v , k, λ) −diferencijska familija u Abelovoj grupi G. Tada je (G , Dev (D) (v , k, λ) −BIBD. Ako je G = Zv , onda je dobiveni BIBD ciklički. Uvod u teoriju dizajna - 11. predavanje 5 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Ciklički Steinerov sustav trojki Za (v , 3, 1) −diferencijsku familiju, broj blokova je s = v −16. Dakle, kada je v ≡ 1 (mod 6) moguće je, na opisani način, konstruirati ciklički STS(v ) iz (v , 3, 1) −diferencijske familije , dok za v ≡ 3 (mod 6) to nije moguće. I Za koje prirodne brojeve v je moguće konstruirati STS(v ) koji je ciklički? Uvod u teoriju dizajna - 11. predavanje 6 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Heffterov problem razlika Neka je v prirodan broj. Promatrajmo tri različita elementa skupa {1, 2,... v − 1}. Ako je zbroj ta tri elementa jednak 0 (mod v ) ili je jedan od njih jednak zbroju preostala dva (mod v ), onda kažemo da oni čine diferencijsku trojku (trojku razlika). Označimo li elemente diferencijske trojke sa x, y i z, onda vrijedi x + y ≡ ±z (mod v ). Uvod u teoriju dizajna - 11. predavanje 7 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Heffterov problem razlika Heffterov problem razlika Lothar Heffter (1862-1962), 1897. Heffterov problem razlika (modulo v ) 1 Neka je v = 6t + 1. Je li moguće particionirati skup 1, 2,... v −1  2 = 3t u diferencijske trojke? 2 Neka je v = 6t + 3. Je li moguće particionirati skup 1, 2,... v −1  v 2 = 3t + 1 \ 3 = 2t + 1 u diferencijske trojke? Rješenje Heffterovog problema razlika dala je 1939. godine Rose Peltesohn. Odgovor na oba postavljena pitanja je pozitivan za sve v ≥ 7 osim za v = 9. Rješenje Heffterovog problema daje teorem iz čijeg je dokaza vidljiv način konstrukcije cikličkog STS(v ) za sve v ≥ 7, v 6= 9. Uvod u teoriju dizajna - 11. predavanje 8 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Heffterov problem razlika Neka je v = 6t + 3, t ∈ N. Odredimo t baznih blokova koji će dati sve razlike ±1,... , ±2t, ±(2t + 2),... , ±(3t + 1). Promatrat ćemo sve translate baznih blokova, zajedno s prvih 2t + 1 translata baznog bloka {0, 2t + 1, 4t + 2}. Za neparan v promotrimo diferencijsku trojku (modulo v )   v −1 {x, y , z} ⊆ 1, 2,... , , 2 pri čemu je x < y < z. Dakle, vrijedi: 1 x + y = z, ili 2 x + y + z ≡ 0 (mod v ). Uvod u teoriju dizajna - 11. predavanje 9 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Heffterov problem razlika Akoje T = {x, y , z} diferencijska trojka, onda definiramo pridruženi bazni blok kao B(T ) = {0, x, x + y }. Razlike pokrivene sa B(T ) su ±x, ±y , ±z (mod v ). Neka je v ≡ 1, 3 (mod 6). Skup T = {T1 ,... , Tt } od t = b v6 c diferencijskih trojki naziva se rješenje Heffterovog problema razlika modulo v ako je t 1,... , v −1   [ 2 , ako je v ≡ 1 (mod 6), Ti =  1,... , v3 − 1, v3 + 1,... , v −1 2 , ako je v ≡ 3 (mod 6). i=1 Skup T označavat ćemo sa HDP(v ). Uvod u teoriju dizajna - 11. predavanje 10 / 11 Ciklički dizajni Ciklički Steinerov sustav trojki Heffterov problem razlika Teorem Postoji rješenje Heffterovog problema razlika modulo v ako i samo ako postoji STS(v ). Teorem (Peltesohn) Za sve v ≡ 1, 3 (mod 6), v ≥ 7, v 6= 9, postoji rješenje Heffterovog problema razlika modulo v i STS(v ). Uvod u teoriju dizajna - 11. predavanje 11 / 11 Ortogonalni latinski kvadrati Direktni produkt latinskih kvadrata Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 12. predavanje Uvod u teoriju dizajna - 12. predavanje 1/6 Ortogonalni latinski kvadrati Direktni produkt latinskih kvadrata Sadržaj predavanja 1 Ortogonalni latinski kvadrati 2 Direktni produkt latinskih kvadrata Uvod u teoriju dizajna - 12. predavanje 2/6 Ortogonalni latinski kvadrati Direktni produkt latinskih kvadrata Ortogonalni latinski kvadrati Neka je L1 latinski kvadrat reda n s elementima iz skupa X i L2 latinski kvadrat reda n s elementima iz skupa Y. Ako za svaki x ∈ X i svaki y ∈ Y postoji jedinstveni par (i, j) takav da je L1 (i, j) = x i L2 (i, j) = y kažemo da su L1 i L2 ortogonalni latinski kvadrati. Ortogonalnost latinskih kvadrata možemo promatrati i tako da gledamo superpoziciju od L1 i L2 , odnosno tablicu dimenzije n × n u kojoj se na poziciji (i, j) nalazi uredeni par (L1 (i, j), L2 (i, j)). Tada ćemo reći da su L1 i L2 ortogonalni ako i samo ako njihova superpozicija sadrži sve uredene parove iz X × Y. Uvod u teoriju dizajna - 12. predavanje 3/6 Ortogonalni latinski kvadrati Direktni produkt latinskih kvadrata Teorem Za neparan prirodni broj n > 1 postoje ortogonalni latinski kvadrati reda n. Uvod u teoriju dizajna - 12. predavanje 4/6 Ortogonalni latinski kvadrati Direktni produkt latinskih kvadrata Direktni produkt latinskih kvadrata Neka je L latinski kvadrat reda m s elementima iz skupa X i M latinski kvadrat reda n s elementima iz skupa Y. Direktni produkt latinskih kvadrata L i M, u oznaci L × M, je mn × mn tablica definirana sa (L × M) ((i1 , i2 ) , (j1 , j2 )) = (L (i1 , j1 ) , M (i2 , j2 )). Lema Ako je L latinski kvadrat reda m s elementima iz skupa X i M latinski kvadrat reda n s elementima iz skupa Y , onda je L × M latinski kvadrat reda mn definiran na skupu X × Y. Uvod u teoriju dizajna - 12. predavanje 5/6 Ortogonalni latinski kvadrati Direktni produkt latinskih kvadrata Teorem Ako postoje ortogonalni latinski kvadrati redova n1 i n2 , onda postoje ortogonalni latinski kvadrati reda n1 n2. Teorem Postoje ortogonalni latinski kvadrati reda n, n 6≡ 2 (mod 4). Teorem Postoje ortogonalni latinski kvadrati reda n, n ≡ 10 (mod 12). Uvod u teoriju dizajna - 12. predavanje 6/6 Medusobno ortogonalni latinski kvadrati Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 13. predavanje Uvod u teoriju dizajna - 13. predavanje 1/4 Medusobno ortogonalni latinski kvadrati Sadržaj predavanja 1 Medusobno ortogonalni latinski kvadrati Uvod u teoriju dizajna - 13. predavanje 2/4 Medusobno ortogonalni latinski kvadrati Medusobno ortogonalni latinski kvadrati Kažemo da su latinski kvadrati reda n, L1 ,... , Lt , medusobno ortogonalni ako su latinski kvadrati Li i Lj ortogonalni za sve 1 ≤ i < j ≤ t. Takav skup latinskih kvadrata skraćeno označavamo sa MOLS (mutually orthogonal latin squares). Jedan od osnovnih problema je odrediti maksimalni broj MOLS-a reda n. Taj broj označavamo sa N(n). Kako su bila koja dva latinska kvadrata reda 1 ortogonalna, to je N(1) = ∞. Za sve prirodne brojeve n, n > 1, moguće je odrediti konačnu gornju granicu za N(n). Uvod u teoriju dizajna - 13. predavanje 3/4 Medusobno ortogonalni latinski kvadrati Teorem Ne postoji n MOLS-a reda n za n ∈ N, n > 1. (odnosno, N(n) ≤ n − 1 za n ∈ N, n > 1). Slučajevi N(n) = n − 1 odgovaraju afinim ravninama. Naime, iz afine ravnine reda n moguće je konstruirati n − 1 MOLS-a reda n. Teorem N(n) = n − 1 ako i samo ako postoji afina ravnina reda n. Uvod u teoriju dizajna - 13. predavanje 4/4 Ortogonalne tablice i transverzalni dizajni Diplomski studij Diskretna matematika i primjene Uvod u teoriju dizajna 14. predavanje Uvod u teoriju dizajna - 14. predavanje 1/6 Ortogonalne tablice i transverzalni dizajni Sadržaj predavanja 1 Ortogonalne tablice i transverzalni dizajni Ortogonalne tablice Transverzalni dizajni Uvod u teoriju dizajna - 14. predavanje 2/6 Ortogonalne tablice i transverzalni dizajni Ortogonalne tablice Ortogonalne tablice Neka su k ≥ 2 i n ≥ 1 prirodni brojevi. Ortogonalna tablica OA(k, n) je n2 × k tablica A s elementima iz skupa X , |X | = n, takva da se u svaka stupca od A svaki uredeni par elemenata iz X pojavljuje u točno jednom retku od A. I Ortogonalnu tablicu OA(t + 2, n) moguće je konstruirati iz t MOLS-a. Takoder, iz ortogonalne tablice OA(k, n) moguće je konstruirati k − 2 MOLS-a reda n. Uvod u teoriju dizajna - 14. predavanje 3/6 Ortogonalne tablice i transverzalni dizajni Transverzalni dizajni Transverzalni dizajni Neka su k ≥ 2 i n ≥ 1 prirodni brojevi. Transverzalni dizajn TD(k, n) je trojka (P, G, B) za koju vrijede sljedeća svojstva: 1 P je skup koji se sastoji od kn elemenata koje nazivamo točkama, 2 G je particija od P na k n−članih podskupova koje nazivamo grupama, 3 B je skup k−članih podskupova od P koje nazivamo blokovima, 4 svka grupa i svaki blok imaju točno jednu zajedničku točku, 5 svaki par točaka iz različitih grupa sadržan je u točno jednom bloku. Uvod u teoriju dizajna - 14. predavanje 4/6 Ortogonalne tablice i transverzalni dizajni Transverzalni dizajni Teorem Sljedeće strukture su ekvivalentne: 1 k − 2 MOLS-a reda n, 2 OA(k, n), 3 TD(k, n). Uvod u teoriju dizajna - 14. predavanje 5/6 Ortogonalne tablice i transverzalni dizajni Transverzalni dizajni Teorem Neka je n prost broj i m prirodan broj takav da je 3 ≤ m ≤ n. Definirajmo tablicu A, čiji su retci indeksirani elementima iz Zm × Zn a stupci redom sa 0,... , m − 1, tako da je A ((i, j) , c) = i + jc (mod n), i, j ∈ Zn , 0 ≤ c ≤ m − 1. Tada je A ortogonalna tablica OA(m, n). Uvod u teoriju dizajna - 14. predavanje 6/6