zalozmy, ze p-stwo zwrocenia rozwiazania optymalnego (o minimalnym koszcie) przez pewien algorytm wynosi 0.05.
algorytm tez zostal wykonany 100 krotnie, a nastepnie jako wynik podano rozwiazanie o najmniejszym koszcie sposrod
100 uzyskanych rozwiazan.
jakie jest prawdopodobienstwo, ze tak uzyskany wynik jest optymalny?
rozwiazanie optymalne
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
rozwiazanie optymalne
Uzyskany wynik będzie optymalny, jeśli w trakcie stu wykonań algorytmu przynajmniej raz dostaniemy wynik optymalny. Prawdopodobieństwo zdarzenia przeciwnego, tzn. takiego, że za każdym razem dostaniemy wynik nieoptymalny wynosi \(\displaystyle{ 0,95^{100}}\), zatem nasze szukane prawdopodobieństwo to \(\displaystyle{ 1 - 0,95^{100} 1- \frac{1}{e^5}}\) czyli dość dużo.
Q.
Q.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
rozwiazanie optymalne
Pytasz o szacowanie rzędu wielkości wyniku? Mamy:
\(\displaystyle{ 0,95^{100}= ft( ft( 1 - \frac{1}{20} \right)^{20} \right)^5 ft(\frac{1}{e} \right)^5}\)
(z uwagi na to, że \(\displaystyle{ \lim_{n \to } ft(1- \frac{1}{n} \right)^n = \frac{1}{e}}\) i jest to zbieżność dość szybka)
Q.
\(\displaystyle{ 0,95^{100}= ft( ft( 1 - \frac{1}{20} \right)^{20} \right)^5 ft(\frac{1}{e} \right)^5}\)
(z uwagi na to, że \(\displaystyle{ \lim_{n \to } ft(1- \frac{1}{n} \right)^n = \frac{1}{e}}\) i jest to zbieżność dość szybka)
Q.