Forum I Roku Informatyki UW

Ok, zaliczmy w końcu ten szajs

Go down

Ok, zaliczmy w końcu ten szajs

Post by juho on Wed Feb 29, 2012 11:36 pm

Czy ktoś wie jak zrobić test z I terminu? Może jakaś wzorcówka, cokolwiek?
avatar
juho

Liczba postów : 177
Join date : 2010-10-13
Age : 27
Skąd : Krępiec / Lublin

View user profile http://juho-the-panda.xt.pl

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by pawel14 on Fri Mar 02, 2012 11:55 pm

Mógłby ktoś napisać jak dojść do zwartego wzoru w zadaniu 2 z tegorocznego egzaminu? A przy okazji jak policzyć wariancję w zad. 3 b).

pawel14

Liczba postów : 118
Join date : 2010-10-12

View user profile

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by gromo on Sat Mar 03, 2012 2:48 am

Moglby ktos wrzucic egzamin z tego roku? Czesc II, dzieki z gory:)

gromo

Liczba postów : 73
Join date : 2010-10-22

View user profile

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by Ciszek on Sat Mar 03, 2012 2:21 pm

avatar
Ciszek

Liczba postów : 13
Join date : 2010-10-20

View user profile

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by juho on Sat Mar 03, 2012 11:25 pm

Hej,
Czy ktoś może wie jak rozwiązać z zadania 2 podpunkt 3 (egzamin 2010 / 2011)
Chodzi o nierówność Czernofa


@pawel14
Licząc wariancję trzeba policzyć E(X^2) i można to zrobić z definicji:
E(X^2) = Suma po każdym liściu v : (P(algorytm doszedł do v) * D(v)^2)
Znamy prawdopodobieństwo, że doszliśmy do danego liścia -> 1/D(v)
Dlatego: E(X^2) = Suma po każdym liściu (D(v))
avatar
juho

Liczba postów : 177
Join date : 2010-10-13
Age : 27
Skąd : Krępiec / Lublin

View user profile http://juho-the-panda.xt.pl

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by pawel14 on Sun Mar 04, 2012 12:10 am

Ok, wielkie dzięki. A ktoś doszedł do zwartej postaci w drugim, bo ja nie ma pojęcia jak to zwinąć.

pawel14

Liczba postów : 118
Join date : 2010-10-12

View user profile

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by pawel14 on Sun Mar 04, 2012 12:54 am

Filip co do trzeciego punktu to mi wyszło coś takiego:
Wiemy, że wartość kursu po n dniach jest postaci: \[Q(1+ \epsilon)^k (1 - \epsilon)^{n - k} = W\]
Badamy kiedy (dla wartości podanych w treści zadania): $$W > Q$$
Wychodzi, że: $$k > nlog_32$$
Weźmy nierówność Chernoffa dla zmiennych 0/1 - kowych (pierwsza ze ściągi). Jako X_i = 1 bierzemy, że kurs wzrósł i-tego dnia. EX = n/2.
Wtedy mamy:
$$P(X > \frac{n}{2} \cdot 2log_3 2) \leq P(X \geq \frac{n}{2} \cdot 2log_3 2) \leq e^{-\frac{(2log_32 - 1)^2 \frac{n}{2}}{3}}$$
No i biorąc $$c = \frac{(2log_32 - 1)^2}{6}$$ dostajemy tezę.

Mam nadzieję, że nie ma nigdzie jakiś fałszywych przejść.

pawel14

Liczba postów : 118
Join date : 2010-10-12

View user profile

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by marcinek on Sun Mar 04, 2012 2:05 pm

Chce przekazac tresc a latexa bym musial sobie przypomniec jak sie wszystkie komendy robi i niespecjalnie mi sie chce to robic...

2 z tego egzaminu

N kanalow wrzucamy 0
A - w pierwszym nienastapilo przeklamanie
B - na koncu zero

binom(n,k) - liczba sposob na wybranie podzbioru o mocy k ze zbioru n elementowego

Jak policzyc A? musi byc parzysta liczba przeklaman
P(A)= x=(suma po k parzystych)( binom(n,k)p^k(1-p)^(1-k))


I idea jest taka ze X = (p+q)^n = suma po wszystkich k dodatnie wszystkie wyrazy
Y = (p-q)^n = suma po wszystkich k tak ze nieparzyste wyrazy sa dodatnie a parzyste ujemne
i teraz:

X+Y= 2x ( suma po k nieparzystych)
X-Y = 2x (suma po k parzystych)
(p-(1-p))^n = Y, X = 1

czyli nasza p(A) = (X-Y)/2
P(A^B) - na opczatku nie bylo zmiany to potem musi w n-1 przejsciach byc nieparzysta.. to trzeba X1 - Y1 ale z (n-1)
wiec P(A^B) = (1-p) * (X1-Y1)
P(A^B)/P(B) = (1-p)(X1-Y1)/(X-Y)

no i chyba tak powinno byc;p w kazdym razie idea jest

marcinek

Liczba postów : 35
Join date : 2010-10-15

View user profile

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by pawel14 on Mon Mar 19, 2012 8:55 pm

Macie już może wpisaną ocenę?

pawel14

Liczba postów : 118
Join date : 2010-10-12

View user profile

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by juho on Mon Mar 19, 2012 9:23 pm

Tej nowej jeszcze nie mam.
avatar
juho

Liczba postów : 177
Join date : 2010-10-13
Age : 27
Skąd : Krępiec / Lublin

View user profile http://juho-the-panda.xt.pl

Back to top Go down

Re: Ok, zaliczmy w końcu ten szajs

Post by Sponsored content


Sponsored content


Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum