#1: skripta Autor/ica: .anchy., Lokacija: ZgbPostano: 17:53 uto, 26. 10. 2010 molila bih pomoć..kao dokazati zad 1.6 na 15-oj stranici?
i nebi li s lijeve strane trebalo još pomnožiti s i u primjeru 1.3.10 str 19?
i zad 1.12 sa strane 27?
#2: Autor/ica: pbakic, Postano: 18:22 uto, 26. 10. 2010 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)
#3: Autor/ica: miam, Postano: 6:42 sri, 27. 10. 2010 moze li netko rijesiti zadatak 1,8 ili 1,9 iz skripte? a moze i oba
#4: Autor/ica: pbakic, Postano: 11:04 sri, 27. 10. 2010 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
#5: Autor/ica: miam, Postano: 11:11 sri, 27. 10. 2010 e puuuno ti hvala
#6: Autor/ica: Tomy007, Postano: 0:06 sri, 5. 1. 2011 Može li netko riješiti zadatak 2.3 iz skripte iz predavanja, to je onaj zadatak sa (2n-1)!!.
#9: Autor/ica: .anchy., Lokacija: ZgbPostano: 12:00 pet, 7. 1. 2011 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?
Ne znam zaista na koji nacin djeluju, sasvim su mi nejasno napisani. :S
#12: Autor/ica: krcko, Postano: 16:20 sri, 26. 10. 2011 @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!
#13: Autor/ica: frutabella, Postano: 17:30 sri, 26. 10. 2011 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 ???
#14: Autor/ica: krcko, Postano: 17:52 sri, 26. 10. 2011 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?
Popločavanja (n + 1)–ploče kod kojeg koristimo barem jednu dominu
tako da zadnja domina pokriva mjesta (k+1) i (k+2) ima točno Jk.
oke, domina treba zauzeti dva mjesta k+1 i k+2, ali zašto onda ima točno Jk popločavanja??
#19: Autor/ica: Phoenix, Postano: 12:09 uto, 1. 11. 2011 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.
#20: Autor/ica: Lepi91, Postano: 16:38 čet, 3. 11. 2011 znam da je vjerojatno svima dosta ovih pitanja o algoritmima i generiranju,ali jos jedno...
hocemo li mi u kolokviju trebati napisati svoj algoritam i onda po njemu odrediti kako bi isao poredak koji on generira ili cemo mi dobiti zdani algoritam pa cemo trebat odredit kako on generira jer ako sam ja shvatio postoje dvije vrste algoritma za podskupove i k-clane podskupove koji rade drugacijim redoslijedom...pa recimo u kolkviju 2007. ako se ne varam ima jedan zadatak sa generiranjem i sad jel tamo mi biramo koji algoritam koristimo? jesam to dobro shvatio,mi odaberemo koji cemo algoritam i njega napisemo i po njemu radimo