Mam do zrealizowania zadanie z następującą treścią:
Załóżmy, że prawdopodobieństwo zwrócenia rozwiązania optymalnego (o minimalnym koszcie) przez pewien algorytm wynosi 0.05. Algorytm ten został wykonany 100krotnie, a następnie jako wynik podano rozwiązanie o najmniejszym koszcie spośród 100 uzyskanych rozwiązań. Jakie jest prawdopodobieństwo, że tak uzyskany wynik jest optymalny?.
Zastanawiam się z jakiej strony mógłbym je ugryźć. Słyszałem o twierdzeniu de Moivre'a-Laplace'a które mogłoby znaleźć tutaj zastosowanie. Pytanie brzmi w jaki sposób mógłbym zastosować tutaj wzór żeby otrzymać poprawny rezultat?
Niezależne wykonania algorytmu [twierdzenie de Moivre'a-Laplace'a?]
-
- Użytkownik
- Posty: 1
- Rejestracja: 11 maja 2022, o 19:59
- Płeć: Mężczyzna
- wiek: 26
- Dasio11
- Moderator
- Posty: 10255
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 41 razy
- Pomógł: 2376 razy
Re: Niezależne wykonania algorytmu [twierdzenie de Moivre'a-Laplace'a?]
Jeśli wolno założyć, że zdarzenia polegające na zwróceniu optymalnego wyniku w \(\displaystyle{ i}\)-tym przebiegu są niezależne dla \(\displaystyle{ i = 1, 2, \ldots, 100}\), to odpowiedzią jest \(\displaystyle{ 1-(1-0.05)^{100}}\) - aby bowiem ostatecznie uzyskany wynik był nieoptymalny, wszystkie sto przebiegów musi zwrócić nieoptymalne wyniki.