• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Złożoność algorytmu z prawdopodobieństwem

Object Storage Arubacloud
0 głosów
303 wizyt
pytanie zadane 20 kwietnia 2020 w Matematyka, fizyka, logika przez Aisekai Nałogowiec (42,190 p.)
edycja 3 maja 2020 przez Aisekai

Cześć.
Dzięki za naprowadzenie z poprzednim problemem, jednakże znów muszę prosić o pomoc w innym zadaniu. Nie proszę o rozwiązanie, a raczej o jakieś wskazówki. Potrzebuję pomocy z obliczeniem złożoności algorytmu z zmienną losową. Doszedłem do tego, jak można zobrazować problem za pomocą grafu lecz nic poza tym. W wierzchołkach znajdują się wartości, natomiast krawędzie symbolizują prawdopodobieństwo z jakim może zostać wybrany następny wierzchołek:

Problem pojawia się, ponieważ istnieje prawdopodobieństwo, że algorytm "cofnie" się o 1, gdyby tego nie było, obliczenie złożoności obliczeniowej tego algorytmu byłoby w miarę proste. Nie pytam też o odpowiedź, a raczej o jakieś wskazówki jak do niej dojść.

 

Edit: myślałem też, zeby przedstawić to jako przeszukiwanie stringa i znajdowanie podciągu w którym będzie o n więcej 1 niż 0. Tylko to też niezbyt mi pomaga. 

komentarz 20 kwietnia 2020 przez tkz Nałogowiec (42,000 p.)

https://en.wikipedia.org/wiki/Probabilistic_Turing_machine

https://en.wikipedia.org/wiki/Randomized_algorithm#Computational_complexity

W mojej ocenie problem podchodzi pod klasę Probabilistic Polynomial. Co daje średni czas wielomianowy od n. 

komentarz 3 maja 2020 przez Aisekai Nałogowiec (42,190 p.)
Mógłbym prosić o jeszcze jakieś Wskazówki, nie jestem wstanie tylko z tym rozwiązać problem (ze względu na zmianę wartości losowej).

2 odpowiedzi

+1 głos
odpowiedź 5 maja 2020 przez vector Dyskutant (9,200 p.)
wybrane 21 maja 2020 przez Aisekai
 
Najlepsza

To jest klasyczny przykład na łańcuch markowa, w szczególności popatrz na twierdzenia 8.11 i 8.12. Obliczenie wartości oczekiwanej liczby kroków wykonanych podczas przejścia z stanu i do stanu n da się sprowadzić do poniższego układu równań:

  1. x(n) =0
  2. x(1) = x(2) + 1
  3. x(i) = 0.5(x(i-1) + x(i+1)) + 1 dla i {\displaystyle \in } {2, 3, .., n-1}

 

0 głosów
odpowiedź 20 kwietnia 2020 przez VirtualMember Pasjonat (15,790 p.)
W przypadku algorytmów z rachunkiem prawdopodobieństwa liczy się wartość oczekiwaną zmiennej losowej.

Zobacz na dowód złożoności oczekiwanej QuickSorta w Cormenie (co prawda tam nie ma explicit zmiennej losowej ale problem lustrzany)
komentarz 3 maja 2020 przez Aisekai Nałogowiec (42,190 p.)
No właśnie jestem wstanie sobie poradzić z Algorytmami z prawdopodobieństwem, gdy nie zmienia się zmienna losowa. Mógłbym prosić o jeszcze jakieś wskazówki?

Podobne pytania

0 głosów
1 odpowiedź 662 wizyt
0 głosów
0 odpowiedzi 512 wizyt
0 głosów
1 odpowiedź 938 wizyt

92,654 zapytań

141,543 odpowiedzi

319,952 komentarzy

62,022 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...