Ok, zaliczmy w końcu ten szajs

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

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).

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

Jest tu: http://students.mimuw.edu.pl/~mc305195/RPiS

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))

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

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ść.

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

Macie już może wpisaną ocenę?

Tej nowej jeszcze nie mam.