[Algorytmy] Zadania Selekcja turniejowa i losowe drzewo BST

henry900
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 22 cze 2014, o 15:49
Płeć: Mężczyzna
Lokalizacja: Tychy

[Algorytmy] Zadania Selekcja turniejowa i losowe drzewo BST

Post autor: henry900 »

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: Zaznacz cały

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
\(\displaystyle{ P_n \left( k \right) = {n \choose k} \cdot p^k \cdot q^ \left( n−k \right)}\)
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
\(\displaystyle{ P_n=p^k}\)

Później obliczłem ilość wariacji
\(\displaystyle{ V =n^k}\)

I podstawiam to wszystko pod wzór wartości oczekiwanej:
\(\displaystyle{ EX=\sum x_i p_i}\)
wynik:
\(\displaystyle{ EX=\sum x_i \cdot \left( 1-\frac{p_i^k}{n^k} \right) ^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 \(\displaystyle{ \log _2 n}\) 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.
Ostatnio zmieniony 23 cze 2014, o 07:55 przez Afish, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
ODPOWIEDZ