Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
.anchy. Forumaš(ica)
Pridružen/a: 14. 11. 2007. (20:03:46) Postovi: (1BC)16
Lokacija: Zgb
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
Postano: 18:22 uto, 26. 10. 2010 Naslov: |
|
|
Pa probaj po def bijekcije: (injekcija + surjekcija)
Pretp. da se dva skupa slikaju u isti skup => dokazi da moraju biti jednaki
Takodjer, dokazi da je surjekcija, (tj da za svaki skup postoji neki koji se slika u njega). Lako je vidjet da ako promatramo neki skup S imamo dva slucaja:
Ako S sadrzi n, onda se u njega slika skup S\n
ako S ne sadrzi n, onda se u njega slika S unija n
U ovom iducem bi trebao stajat "i":D
A u zadnjem isto po def:
f je surjekcija =>
f^-1({y}) je neprazan (upravo zbog surjektivnosti)
f^-1({y}) i f^-1({x}) su disjunktni za x!=y (za to ne trebamo surjektivnost)
unija svih f^-1({y}) kad y prolazi po B je cijela domena (jer se svaki element iz A slika u neki iz B)
a ako vrijedi da je familija {f^-1({y}), y iz B} particija, onda je dovoljno primjetiti da ni za jedan y f^-1({y}) nije prazan skup (tj da postoji x iz A koji se slika u njega)
Pa probaj po def bijekcije: (injekcija + surjekcija)
Pretp. da se dva skupa slikaju u isti skup => dokazi da moraju biti jednaki
Takodjer, dokazi da je surjekcija, (tj da za svaki skup postoji neki koji se slika u njega). Lako je vidjet da ako promatramo neki skup S imamo dva slucaja:
Ako S sadrzi n, onda se u njega slika skup S\n
ako S ne sadrzi n, onda se u njega slika S unija n
U ovom iducem bi trebao stajat "i"
A u zadnjem isto po def:
f je surjekcija =>
f^-1({y}) je neprazan (upravo zbog surjektivnosti)
f^-1({y}) i f^-1({x}) su disjunktni za x!=y (za to ne trebamo surjektivnost)
unija svih f^-1({y}) kad y prolazi po B je cijela domena (jer se svaki element iz A slika u neki iz B)
a ako vrijedi da je familija {f^-1({y}), y iz B} particija, onda je dovoljno primjetiti da ni za jedan y f^-1({y}) nije prazan skup (tj da postoji x iz A koji se slika u njega)
|
|
[Vrh] |
|
miam Forumaš(ica)
Pridružen/a: 03. 11. 2009. (11:19:45) Postovi: (70)16
Spol:
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
Postano: 11:04 sri, 27. 10. 2010 Naslov: |
|
|
1.8:
Ova tvrdnja, kolko vidim, ne vrijedi... Npr, za n=5 i r=2 ocito ne valja
Trebalo bi staviti da i ide od 1 do r+1
Tada se jednakost (koja vrijedi) moze kombinatorno argumentirati ovako:
s desne strane, ocito, biramo r clanova n-clanog skupa.
lijeva strana je rastav po slucajevima:
poredamo clanove skupa (pridruzimo im indekse 1,...,n)
onda gledamo slucajeve po tom koji je indeks najmanjeg clana koji ne sudjeluje u podskupu.
Ako je to indeks i, onda smo odabrali vec sve prije njega (i-1 element) pa trebamo od preostalih (m-i) odabrati (r-(i-1))=r-i+1. Posto su slucajevi disjunktni, na kraju samo zbrojimo sve te mogucnosti i vidimo da smo dobili sumu na lijevoj str.
1.9:
Slicna prica, s desne strane biramo n+1 element od n+k+1 clanog skupa.
S lijeve strane rastavimo po slucajevima (promatramo najveci indeks od clanova koji sudjeluju)
Ako je to indeks n+i+1 (ne moze biti manji ili jednak n jer onda nemamo n+1 element), onda za preostale clanove podskupa moramo izabrati n elemenata od n+i (to su ovi sa manjim indeksima). To nam daje sumande na lijevoj strani
1.8:
Ova tvrdnja, kolko vidim, ne vrijedi... Npr, za n=5 i r=2 ocito ne valja
Trebalo bi staviti da i ide od 1 do r+1
Tada se jednakost (koja vrijedi) moze kombinatorno argumentirati ovako:
s desne strane, ocito, biramo r clanova n-clanog skupa.
lijeva strana je rastav po slucajevima:
poredamo clanove skupa (pridruzimo im indekse 1,...,n)
onda gledamo slucajeve po tom koji je indeks najmanjeg clana koji ne sudjeluje u podskupu.
Ako je to indeks i, onda smo odabrali vec sve prije njega (i-1 element) pa trebamo od preostalih (m-i) odabrati (r-(i-1))=r-i+1. Posto su slucajevi disjunktni, na kraju samo zbrojimo sve te mogucnosti i vidimo da smo dobili sumu na lijevoj str.
1.9:
Slicna prica, s desne strane biramo n+1 element od n+k+1 clanog skupa.
S lijeve strane rastavimo po slucajevima (promatramo najveci indeks od clanova koji sudjeluju)
Ako je to indeks n+i+1 (ne moze biti manji ili jednak n jer onda nemamo n+1 element), onda za preostale clanove podskupa moramo izabrati n elemenata od n+i (to su ovi sa manjim indeksima). To nam daje sumande na lijevoj strani
|
|
[Vrh] |
|
miam Forumaš(ica)
Pridružen/a: 03. 11. 2009. (11:19:45) Postovi: (70)16
Spol:
|
|
[Vrh] |
|
Tomy007 Forumaš(ica)
Pridružen/a: 08. 11. 2009. (19:45:28) Postovi: (94)16
|
|
[Vrh] |
|
Flame Forumaš(ica)
Pridružen/a: 12. 08. 2009. (02:14:39) Postovi: (53)16
Spol:
|
|
[Vrh] |
|
meda Forumaš(ica)
Pridružen/a: 09. 01. 2010. (09:29:23) Postovi: (A0)16
|
|
[Vrh] |
|
.anchy. Forumaš(ica)
Pridružen/a: 14. 11. 2007. (20:03:46) Postovi: (1BC)16
Lokacija: Zgb
|
Postano: 12:00 pet, 7. 1. 2011 Naslov: |
|
|
mi može netko objasniti zadnju rečenicu na str 53. "neka je X univerzalan skup i...", i ovu jednakost sa presjekom..
tu isto nisam sigurna kužim li što su Ai-ovi, npr.za X={1,2,3}, je li onda npr.A1={1,2} i A2={3}, ili može biti da je A1={1,2} i A2={2,3},tj.moraju li biti disjunktni?
edit:never mind,skužila sam.. pretp.da sam dobro shvatila,znači Ai-ovi nemoraju biti disjunktni i nemoraju uopće u uniji davat cijeli X?
mi može netko objasniti zadnju rečenicu na str 53. "neka je X univerzalan skup i...", i ovu jednakost sa presjekom..
tu isto nisam sigurna kužim li što su Ai-ovi, npr.za X={1,2,3}, je li onda npr.A1={1,2} i A2={3}, ili može biti da je A1={1,2} i A2={2,3},tj.moraju li biti disjunktni?
edit:never mind,skužila sam.. pretp.da sam dobro shvatila,znači Ai-ovi nemoraju biti disjunktni i nemoraju uopće u uniji davat cijeli X?
|
|
[Vrh] |
|
Tomy007 Forumaš(ica)
Pridružen/a: 08. 11. 2009. (19:45:28) Postovi: (94)16
|
|
[Vrh] |
|
frutabella Forumaš(ica)
Pridružen/a: 09. 10. 2010. (16:35:36) Postovi: (24E)16
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
Postano: 16:20 sri, 26. 10. 2011 Naslov: |
|
|
@meda, anchy, Tomy:
Ako se pripremate za prvi kolokvij, malo ste se pogubili. Formula ukljucivanja-ukljucivanja i teorija grafova bit ce tek na drugom kolokviju. To cu tumaciti na predavanju pa cu sad preskociti.
@frutabella:
Recimo da generiras podskupove od X={1,2,3} drugim algoritmom na str. 30. Pocnes od praznog skupa:
[latex]\emptyset[/latex]
Koji je najveci element iz X koji nije u trenutnom podskupu? 3. Ubacim ga i izbacim sve elemente iza njega (nema ih) i tako dobijem drugi podskup:
{3}
Sad ponavljam. Najveci element koji nije u podskupu je 2. Ubacim ga i izbacim sve poslije njega (3) pa dobijem
{2}
Ubacim 3, izbacim nista:
{2,3}
Ubacim 1, izbacim sve poslije njega (2,3) itd:
{1}
{1,3}
{1,2}
{1,2,3}
Sad su svi elementi u podskupu pa stanem. Nasao sam sve podskupove.
Probaj sama ispisati sve 3-podskupove od {1,2,3,4,5} onako kako bi radio prvi algoritam na str. 31!
@meda, anchy, Tomy:
Ako se pripremate za prvi kolokvij, malo ste se pogubili. Formula ukljucivanja-ukljucivanja i teorija grafova bit ce tek na drugom kolokviju. To cu tumaciti na predavanju pa cu sad preskociti.
@frutabella:
Recimo da generiras podskupove od X={1,2,3} drugim algoritmom na str. 30. Pocnes od praznog skupa:
Koji je najveci element iz X koji nije u trenutnom podskupu? 3. Ubacim ga i izbacim sve elemente iza njega (nema ih) i tako dobijem drugi podskup:
{3}
Sad ponavljam. Najveci element koji nije u podskupu je 2. Ubacim ga i izbacim sve poslije njega (3) pa dobijem
{2}
Ubacim 3, izbacim nista:
{2,3}
Ubacim 1, izbacim sve poslije njega (2,3) itd:
{1}
{1,3}
{1,2}
{1,2,3}
Sad su svi elementi u podskupu pa stanem. Nasao sam sve podskupove.
Probaj sama ispisati sve 3-podskupove od {1,2,3,4,5} onako kako bi radio prvi algoritam na str. 31!
_________________ Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
[Vrh] |
|
frutabella Forumaš(ica)
Pridružen/a: 09. 10. 2010. (16:35:36) Postovi: (24E)16
|
Postano: 17:30 sri, 26. 10. 2011 Naslov: |
|
|
Evo tek sad,nakon tri dana razmisljanja, skontala sam algoritam, puno jasnije raspisan nego sto je napisan u skripti (meni skroz nejasan u skripti).
Također ovaj drugi algoritam mi nikako ne ide:
Npr. Trazit cu 3-podskupove od {1,2,3,4}, znaci n=4, k=3
Kako kaze skripta:
Prvi podskup je Y={1, ..., k}, u nasem slucaju to je valjda, recimo Y={1,2,3}.
SLJEDECI PODSKUP poslije Y={y1=1,y2=2,y3=3,} (gdje je 1<2<3) je
------> nađi prvi i takav da je yi + 1 nije elemenz iz trenutnog Y,
to znaci, da je taj i=3, i s tim y3+1=4 nije element iz trenutnog Y
------> povecaj yi za jedan, stavi yj=j za j< i i [b]vrati novi Y[/b]
to znaci y3+1=4, a j < i jesu j=1,2 < i=3, i stavim y1=1, y2=2,
[b]da li onda ovo znaci vratiti novi Y ----> Y= {1,2,4} ????[/b]
Ali onda drugi krug opet ne znam, (jer pretpostavljam ni ovo nije dobro), jer sljedeci i takav da yi+1 nije element iz trenutnog Y, je i=2, jer y2+1=3, a on nije element trenutnog Y, a kako onda odrediti yj, kad je samo j=1 < i=2 ???
Evo tek sad,nakon tri dana razmisljanja, skontala sam algoritam, puno jasnije raspisan nego sto je napisan u skripti (meni skroz nejasan u skripti).
Također ovaj drugi algoritam mi nikako ne ide:
Npr. Trazit cu 3-podskupove od {1,2,3,4}, znaci n=4, k=3
Kako kaze skripta:
Prvi podskup je Y={1, ..., k}, u nasem slucaju to je valjda, recimo Y={1,2,3}.
SLJEDECI PODSKUP poslije Y={y1=1,y2=2,y3=3,} (gdje je 1<2<3) je
------> nađi prvi i takav da je yi + 1 nije elemenz iz trenutnog Y,
to znaci, da je taj i=3, i s tim y3+1=4 nije element iz trenutnog Y
------> povecaj yi za jedan, stavi yj=j za j< i i vrati novi Y
to znaci y3+1=4, a j < i jesu j=1,2 < i=3, i stavim y1=1, y2=2,
da li onda ovo znaci vratiti novi Y ----> Y= {1,2,4} ????
Ali onda drugi krug opet ne znam, (jer pretpostavljam ni ovo nije dobro), jer sljedeci i takav da yi+1 nije element iz trenutnog Y, je i=2, jer y2+1=3, a on nije element trenutnog Y, a kako onda odrediti yj, kad je samo j=1 < i=2 ???
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
Postano: 17:52 sri, 26. 10. 2011 Naslov: |
|
|
Dobro je! Sad imas ovaj podskup:
{1,2,4}
Znaci y1=1, y2=2, y3=4. Kao sto si napisala i=2, stavimo y2=3 i y_j=j za j<2 (tj. y1=1 sto vec je). Sljedeci podskup je
{1,3,4}
Sad je i=1, dobijemo
{2,3,4}
i gotovi smo ako je n=4. Ako je n=5 imali bismo i=3, y3=5 i stavimo y_j=j za j<3 (tj. y1=1 i y2=2):
{1,2,5}
Kako ide dalje?
Dobro je! Sad imas ovaj podskup:
{1,2,4}
Znaci y1=1, y2=2, y3=4. Kao sto si napisala i=2, stavimo y2=3 i y_j=j za j<2 (tj. y1=1 sto vec je). Sljedeci podskup je
{1,3,4}
Sad je i=1, dobijemo
{2,3,4}
i gotovi smo ako je n=4. Ako je n=5 imali bismo i=3, y3=5 i stavimo y_j=j za j<3 (tj. y1=1 i y2=2):
{1,2,5}
Kako ide dalje?
_________________ Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
[Vrh] |
|
frutabella Forumaš(ica)
Pridružen/a: 09. 10. 2010. (16:35:36) Postovi: (24E)16
|
Postano: 18:59 sri, 26. 10. 2011 Naslov: |
|
|
{ 1, 3, 5}
{2, 3, 5}
{1, 4, 5}
{2, 4, 5}
{3, 4, 5}
:D :D :D :D :D :D
Nadam se da je dobro.
Sad me samo jos zanima ovaj zadnji dio algoritma koji kaze:
----> ovaj postupak propada ukoliko je i=k, yk=n; u tom slucaju
Y={ n-k+1, ..., n} je zadnji skup
A ja sam skroz u prvom koraku imala i=3, sto je jednako k=3, i y3=4 ?
(ma da je istina da mi je zadnji skup ono sto veli zadnji dio alg)
Podsjetnik:
Prvi podskup je Y={1, ..., k}, u nasem slucaju to je valjda, recimo Y={1,2,3}.
SLJEDECI PODSKUP poslije Y={y1=1,y2=2,y3=3,} (gdje je 1<2<3) je
------> nađi prvi i takav da je yi + 1 nije elemenz iz trenutnog Y,
to znaci, da je taj[b] i=3[/b], i s tim [b]y3+1=4[/b] nije element iz trenutnog Y
{ 1, 3, 5}
{2, 3, 5}
{1, 4, 5}
{2, 4, 5}
{3, 4, 5}
Nadam se da je dobro.
Sad me samo jos zanima ovaj zadnji dio algoritma koji kaze:
----> ovaj postupak propada ukoliko je i=k, yk=n; u tom slucaju
Y={ n-k+1, ..., n} je zadnji skup
A ja sam skroz u prvom koraku imala i=3, sto je jednako k=3, i y3=4 ?
(ma da je istina da mi je zadnji skup ono sto veli zadnji dio alg)
Podsjetnik:
Prvi podskup je Y={1, ..., k}, u nasem slucaju to je valjda, recimo Y={1,2,3}.
SLJEDECI PODSKUP poslije Y={y1=1,y2=2,y3=3,} (gdje je 1<2<3) je
------> nađi prvi i takav da je yi + 1 nije elemenz iz trenutnog Y,
to znaci, da je taj i=3, i s tim y3+1=4 nije element iz trenutnog Y
|
|
[Vrh] |
|
pedro Forumaš(ica)
Pridružen/a: 21. 10. 2010. (14:08:21) Postovi: (19B)16
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
|
[Vrh] |
|
pedro Forumaš(ica)
Pridružen/a: 21. 10. 2010. (14:08:21) Postovi: (19B)16
|
|
[Vrh] |
|
Phoenix Forumaš(ica)
Pridružen/a: 15. 05. 2010. (18:46:07) Postovi: (164)16
Sarma: -
|
Postano: 12:09 uto, 1. 11. 2011 Naslov: |
|
|
Zato što, ako je zadnja domina na ploči na mjestima [tex](k+1)[/tex] i [tex](k+2)[/tex], sve poslije nje su kockice (sve do [tex](n+1)[/tex] pozicije). Međutim, mjesta od [tex](1)[/tex] do [tex](k)[/tex] mogu biti popunjena kako god želiš, stoga i imaš [tex]J_k[/tex] načina za ovaj slučaj.
I, naravno, ovisno o tome gdje se nalazi posljednja domina, napiši odgovarajuću sumu po [tex]k[/tex] i imaš rješenje.
Zato što, ako je zadnja domina na ploči na mjestima [tex](k+1)[/tex] i [tex](k+2)[/tex], sve poslije nje su kockice (sve do [tex](n+1)[/tex] pozicije). Međutim, mjesta od [tex](1)[/tex] do [tex](k)[/tex] mogu biti popunjena kako god želiš, stoga i imaš [tex]J_k[/tex] načina za ovaj slučaj.
I, naravno, ovisno o tome gdje se nalazi posljednja domina, napiši odgovarajuću sumu po [tex]k[/tex] i imaš rješenje.
|
|
[Vrh] |
|
Lepi91 Forumaš(ica)
Pridružen/a: 15. 09. 2010. (15:22:23) Postovi: (C8)16
Spol:
|
|
[Vrh] |
|
|