Witam,

mam problem z dwoma zadaniami, prowadząca powiedziała że ich nie przyjmie bo są źle ale nie powiedziała co jest źle.

Pierwsze:

Przedstawiony algorytm wykorzystywany jest w turniejach ewolucyjnych do wyboru lepiej przystosowanych osobników (zamiast stałej 3 może być inny rozmiar „turnieju”)

Kod:
select(n)
P:= [1,2,...,n]
for i:= 1 to n do
for j:= 1 to 3 do
tj:= wylosowana liczba ze zbioru P
wybrany:= max(t1, t2, t3)

Jaka jest wartość oczekiwana liczby elementów zbioru P, które ani razu nie zostaną wybrane?

Chciałem wykorzystać wzór Bernoulliego
Pn(k )=(nk)∗p^k∗q^(n−k)
gdzie:
n- reprezentuję liczbę turniejów
k- reprezentuje liczba sukcesów – nie wylosowania liczby
i doszedłem do wniosku że wzór się skróci
Pn=p^k

Później obliczłem ilość wariacji
V =n^k

I podstawiam to wszystko pod wzór wartości oczekiwanej:
EX=Σxi pi
wynik:
EX=Σxi∗(1−(pi^k/n^k))^n

i drugi:
Załóżmy, że zbudowano drzewo BST dla kluczy 1,2,...,n w sposób następujący. Wygeneruj losową permutację π zbioru
{1,2,...,n}, a następnie wstaw do początkowo pustego drzewa wszystkie klucze w kolejności: π(1),π(2),...,π(n).
Oszacuj wartość oczekiwaną wysokości takiego losowego drzewa.

jako wynik podałem log2n gdyż taka jest wysokość drzewa zrównoważonego ale wydaje mi się że miałem uwzględnić również niezrównoważone ale nie wiem jak się do tego zabrać.

Gdyby ktoś mógł jakoś pomóc byłbym bardzo wdzięczny.