[es] - Zadatak iz kombinatorike

jovannk
student

Član broj: 188659
Poruke: 9
*.crnagora.net.

Profil

Zadatak iz kombinatorike

^{28.02.2011. u 08:51 - pre 160 meseci}

Zad:
Odrediti max broj

_{[Ovu poruku je menjao jovannk dana 02.03.2011. u 01:47 GMT+1]}

Odgovor na temu

Sini82

Član broj: 234605
Poruke: 479
62.101.141.*

Jabber: Sini82@elitesecurity.org

+33 Profil

Re: Zadatak iz kombinatorike

^{28.02.2011. u 17:05 - pre 159 meseci}

Prebroj koliko imaš kvadratnih matrica 1x1, 2x2, ... , mxm:

1x1 imaš

;
2x2 imaš

;
...
mxm imaš

.

Maksimalan broj kvadratnih matrica u matrici reda mxn (m<n) je

Odgovor na temu

jovannk
student

Član broj: 188659
Poruke: 9
62.4.33.*

Profil

Re: Zadatak iz kombinatorike

^{28.02.2011. u 22:34 - pre 159 meseci}

Hvala, Sini. I ja sam dosao do ove formule al sam slabo postavio pitanje..

_{[Ovu poruku je menjao jovannk dana 02.03.2011. u 01:40 GMT+1]}

_{[Ovu poruku je menjao jovannk dana 02.03.2011. u 01:45 GMT+1]}

Odgovor na temu

SrdjanR271
Srdjan Radosavljevic
dipl. inženjer informatike

Član broj: 174403
Poruke: 443
*.adsl.eunet.rs.

+88 Profil

Re: Zadatak iz kombinatorike

^{28.02.2011. u 22:45 - pre 159 meseci}

Mozda je ovako nisam siguran.

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Odgovor na temu

jovannk
student

Član broj: 188659
Poruke: 9
62.4.33.*

Profil

Re: Zadatak iz kombinatorike

^{01.03.2011. u 08:01 - pre 159 meseci}

Hvala. Ima li ko ideju moze li preko faktorijela, lici mi da moze al sam se zapetljao

Odgovor na temu

atomant
Beograd

Član broj: 47540
Poruke: 263
*.dynamic.isp.telekom.rs.

+34 Profil

Re: Zadatak iz kombinatorike

^{01.03.2011. u 08:35 - pre 159 meseci}

Pa ako je zadatak da napises program onda ti je ova formula sasvim dovoljna za iterativnu proceduru. Ako ga pakujes na faktorijel moze da se uradi i preko rekurzije, ali rekurzija je uvek sporija jer funkcija poziva sama sebe vise puta. Je l' mnogo bitno da bude u obliku faktorijela?

If you can't explain it simply, you don't understand it well enough. A. Einstein

Odgovor na temu

jovannk
student

Član broj: 188659
Poruke: 9
62.4.33.*

Profil

Re: Zadatak iz kombinatorike

^{01.03.2011. u 08:50 - pre 159 meseci}

Zbog -1/6 se moze dobiti negativan broj a broj kv. matrica bi valjda trebao da je cio pozitivan broj, i valjda k ide od 0 do m-1).

_{[Ovu poruku je menjao jovannk dana 02.03.2011. u 09:07 GMT+1]}

Odgovor na temu

SrdjanR271
Srdjan Radosavljevic
dipl. inženjer informatike

Član broj: 174403
Poruke: 443
*.adsl.eunet.rs.

+88 Profil

Re: Zadatak iz kombinatorike

^{01.03.2011. u 15:31 - pre 159 meseci}

Ja sam napisao sumu prema Sini82-evoj "formuli" i tamo ide do m+1.
Probao sam za kvadratne m=n i trebalo bi da suma ide do m.
Za m<n suma daje tacne rezultate.

A sumira se ovako

_{[Ovu poruku je menjao SrdjanR271 dana 01.03.2011. u 17:02 GMT+1]}

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Odgovor na temu

Sini82

Član broj: 234605
Poruke: 479
62.101.141.*

Jabber: Sini82@elitesecurity.org

+33 Profil

Re: Zadatak iz kombinatorike

^{01.03.2011. u 17:56 - pre 159 meseci}

Odgovor na temu

SrdjanR271
Srdjan Radosavljevic
dipl. inženjer informatike

Član broj: 174403
Poruke: 443
*.adsl.eunet.rs.

+88 Profil

Re: Zadatak iz kombinatorike

^{01.03.2011. u 19:29 - pre 159 meseci}

To je to sad sam skontao da je islo do m-1

Sad je ukupan broj

_{[Ovu poruku je menjao SrdjanR271 dana 02.03.2011. u 00:38 GMT+1]}

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Odgovor na temu

jovannk
student

Član broj: 188659
Poruke: 9
62.4.33.*

Profil

Re: Zadatak iz kombinatorike

^{01.03.2011. u 22:33 - pre 159 meseci}

Hvala momci. Srdjane, da li si ovaj rezultat dobio iz formule koju je sini iznad napisao

? Da li koristis da je

i da je

?

_{[Ovu poruku je menjao jovannk dana 02.03.2011. u 01:42 GMT+1]}

Odgovor na temu

SrdjanR271
Srdjan Radosavljevic
dipl. inženjer informatike

Član broj: 174403
Poruke: 443
*.adsl.eunet.rs.

+88 Profil

Re: Zadatak iz kombinatorike

^{02.03.2011. u 00:01 - pre 159 meseci}

Da ono je formula za Sinijevu sumu do m-1.
Ja sam to izracunao u Mathematici nisam rucno.

A mozes (moras) da koristis te sume za sumu kvadrata i sumu prirodnih brojeva.
Kad primenis te formule, jel dobijes ovako nesto

Kad sve izmnozis i izvuces m (ili prvo izvuces m) dobices kao ja.

Mozda te je bunilo ovo

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Odgovor na temu

jovannk
student

Član broj: 188659
Poruke: 9
62.4.33.*

Profil

Re: Zadatak iz kombinatorike

^{02.03.2011. u 00:13 - pre 159 meseci}

Da, upravo to. Ja sam uzimao da je

.

_{[Ovu poruku je menjao jovannk dana 02.03.2011. u 09:10 GMT+1]}

Odgovor na temu

miki069

Član broj: 161528
Poruke: 1951
212.200.34.*

+370 Profil

Re: Zadatak iz kombinatorike

^{02.03.2011. u 00:28 - pre 159 meseci}

Konkretno za m=10.
Koliko je

?

1+1+1+1+1+1+1+1+1+1 = 10.
Odnosno m u opštem slučaju.

Zadatak ti je urađen ispravno ako je glasio: "Odrediti max broj kvadratnih matrica u matrici reda mxn (m-kolone, n-redovi i n>m)."
Bez onog čudnog dela dela: "gdje se kvadratnom matricom smatra i jedinični član uz krajnju ivicu".
Računati su i svi elementi (1X1) koji i nisu uz krajnu ivicu, što je i normalno i tako je Sini82 i uradio.

_{[Ovu poruku je menjao miki069 dana 02.03.2011. u 01:41 GMT+1]}

_{[Ovu poruku je menjao miki069 dana 02.03.2011. u 01:56 GMT+1]}

Odgovor na temu

jovannk
student

Član broj: 188659
Poruke: 9
62.4.33.*

Profil

Re: Zadatak iz kombinatorike

^{02.03.2011. u 00:37 - pre 159 meseci}

Hvala, Srdjane. Miko takodje. Sad sam se malo zamislio i vidio da je

.

_{[Ovu poruku je menjao jovannk dana 02.03.2011. u 09:12 GMT+1]}

Odgovor na temu

miki069

Član broj: 161528
Poruke: 1951
212.200.34.*

+370 Profil

Re: Zadatak iz kombinatorike

^{02.03.2011. u 01:08 - pre 159 meseci}

Kada bi se od ovih tvojih kvadratnih podmatrica tipa 1X1, 2X2, 3X3... izračunale determinante one se zovu Minori.
Ali ovu su samo minori nastali ukrštanjem susednih vrsta i susednih kolona.

Definicija:
Minor reda k matrice AmXn je vrednost determinante kvadratne podmatrice tipa kXk, nastale iz matrice A ukrštanjem bilo kojih njenih k vrsta i k kolona.
k=1,2,3...min(m,n).

Dakle minori tipa 2 nisu samo od kvadratnih podmatrica nastalih ukrštanjem 2 susedne vrse i 2 susedne kolone, već bilo koje 2 vrste i 2 kolone.
Recimo može (1 i 3) vrsta ukrštene sa (2 i 5) kolonom i broj minora je daleko veći od ovog što su tebi izračunali.
Ti si dobio broj minora u "komadu".

Jedino se ne menja kod minora tipa 1X1.

Zadatak se generalizuju na: "Koliko ima minora tipa 2, tipa 3.... do tipa min(m,n)".
Možemo uzeti da je min(m,n) = m.

Znao bih da napišem program da ih sve izgeneriše, ali mi prebrojavanje zapinje.

Odgovor na temu

SrdjanR271
Srdjan Radosavljevic
dipl. inženjer informatike

Član broj: 174403
Poruke: 443
*.adsl.eunet.rs.

+88 Profil

Re: Zadatak iz kombinatorike

^{02.03.2011. u 02:42 - pre 159 meseci}

@Miki069
Jesi na ovo mislio?

Citat:

Let A be an m × n matrix and k an integer with 0 < k ≤ m, and k ≤ n. A k × k minor of A is the determinant
of a k × k matrix obtained from A by deleting m − k rows and n − k columns.

Since there are:

ways to choose k rows from m rows, and there are

ways to choose k columns from n columns, there are a total of

minors of size k × k.

Izvor
http://en.wikipedia.org/wiki/Minor_%28linear_algebra%29

A mathematician is a blind man in a dark room looking for a black cat which isn't there.

Odgovor na temu

miki069

Član broj: 161528
Poruke: 1951
212.200.34.*

+370 Profil

Re: Zadatak iz kombinatorike

^{02.03.2011. u 08:37 - pre 159 meseci}

To je to.

Toliko je jasno iz dela definicije "...ukrštanjem bilo kojih njenih k vrsta i k kolona.." da mi sad nije jasno šta sam ja muljao i komplikovao.
U programu i koristim generator kombinacija, a u prebrojavanju nisam ukapirao da su kombinacije.

Hvala Srdjane.

Odgovor na temu