• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algorytm probabilistyczny

    Przeczytaj także...
    Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie "dziel i zwyciężaj".Bezpieczeństwo teleinformatyczne – zbiór zagadnień z dziedziny telekomunikacji i informatyki związany z szacowaniem i kontrolą ryzyka wynikającego z korzystania z komputerów, sieci komputerowych i przesyłania danych do zdalnych lokalizacji, rozpatrywany z perspektywy poufności, integralności i dostępności.
    Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.

    Algorytm probabilistyczny albo randomizowany to algorytm który do swojego działania używa losowości. W praktyce oznacza to, że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie zawsze w „średnim przypadku”, dzięki czemu „złośliwe" dane wejściowe nie wydłużają jego działania. Formalnie efektywność takiego algorytmu jest zmienną losową określoną na przestrzeni możliwych losowych ciągów. Wartość oczekiwana takiej zmiennej nazywana jest oczekiwanym czasem działania. Przypadek pesymistyczny jest zwykle na tyle mało prawdopodobny, że można go pominąć w analizie.

    Tablica w informatyce to kontener danych dostępnych, w którym poszczególne komórki dostępne są za pomocą kluczy, które najczęściej przyjmują wartości numeryczne. Rozmiar tablicy jest albo ustalony z góry (tablice statyczne), albo może się zmieniać w trakcie wykonywania programu (tablice dynamiczne).W informatyce, algorytm deterministyczny to algorytm, którego działanie jest całkowicie zdeterminowane przez warunki początkowe (wejście). Oznacza to, że kilkukrotne uruchomienie takiego algorytmu doprowadzi za każdym razem do takiego samego wyniku. Algorytmy deterministyczne stanowią główny obszar badań informatycznych i są najczęściej stosowane, ponieważ mogą być łatwo realizowane na współczesnych komputerach.

    Motywacja[edytuj kod]

    Załóżmy że mamy znaleźć literę „a" w tablicy o n elementach, z których połowa jest literami „a", a połowa literami „b". Zwyczajne przeglądanie tablicy może spowodować, że znajdziemy „a" dopiero po sprawdzeniu połowy (½n) elementów, jeśli cały początek tablicy jest wypełniony literami „b". Podobnie przeglądanie tablicy od końca będzie czasochłonne, jeśli cały koniec tablicy jest wypełniony literami „b" itp. Faktycznie dla dowolnej strategii przeglądania tablicy w ustalonym porządku istnieją „złośliwe" przypadki, dla których algorytm działa długo. Z drugiej strony, jeśli będziemy sprawdzać losowe elementy, dla dowolnej tablicy z dużym prawdopodobieństwem trafimy bardzo szybko na literę „a".

    Test Millera-Rabina jest testem pierwszości, czyli algorytmem określającym czy dana liczba jest pierwsza. Podobnie jak test Fermata i test Solovaya-Strassena jest testem probabilistycznym, wymagającym stosowania liczb losowych. Oryginalna wersja tego algorytmu (Millera) została zaprojektowana jako algorytm deterministyczny, jednak jej poprawność zależy od nieudowodnionej dotychczas uogólnionej hipotezy Riemanna. Michael O. Rabin zmodyfikował ten algorytm do postaci randomizacyjnej i dowiódł jego poprawności w tej postaci.Metoda Monte Carlo (MC) jest stosowana do modelowania matematycznego procesów zbyt złożonych (obliczania całek, łańcuchów procesów statystycznych), aby można było przewidzieć ich wyniki za pomocą podejścia analitycznego. Istotną rolę w metodzie MC odgrywa losowanie (wybór przypadkowy) wielkości charakteryzujących proces, przy czym losowanie dokonywane jest zgodnie z rozkładem, który musi być znany.

    Powyższy przykład opisuje algorytm, który zawsze zwraca prawidłową odpowiedź, ale jego czas działania nie jest z góry ustalony. Algorytmy tego typu nazywane są algorytmami Las Vegas. Drugim typem algorytmów są algorytmy Monte Carlo, które zawsze kończą się w ustalonym czasie, ale mogą z pewnym prawdopodobieństwem zwrócić zły wynik bądź zwracają wynik tylko z pewną dokładnością.

    Zmienna losowa – funkcja przypisująca zdarzeniom elementarnym liczby. Intuicyjnie: odwzorowanie przenoszące badania prawdopodobieństwa z niewygodnej przestrzeni probabilistycznej do dobrze znanej przestrzeni euklidesowej. Zmienne losowe to funkcje mierzalne względem przestrzeni probabilistycznych.Wartość oczekiwana (wartość średnia, przeciętna, dawniej nadzieja matematyczna) – w rachunku prawdopodobieństwa wartość określająca spodziewany wynik doświadczenia losowego. Wartość oczekiwana to inaczej pierwszy moment zwykły. Estymatorem wartości oczekiwanej rozkładu cechy w populacji jest średnia arytmetyczna.

    Algorytmy randomizowane są szczególnie użyteczne, jeśli rozważamy sytuację, w której jakiś „przeciwnik" próbuje zmusić algorytm do dłuższego działania. Ma to miejsce na przykład w kryptografii i bezpieczeństwie komputerowym

    Złożoność[edytuj kod]

    Teoria złożoności obliczeniowej Kołmogorowa definiuje algorytmy probabilistyczne przy użyciu pojęcia probabilistycznej maszyny Turinga. Model ten definiuje odpowiednie klasy złożoności obliczeniowej, analogicznie do klasycznej maszyny Turinga. Przykładowo do klasy złożoności RP należą problemy, dla których istnieje algorytm probabilistyczny działający w czasie wielomianowym, który negatywne przypadki zawsze odrzuca, a pozytywne akceptuje z prawdopodobieństwem co najmniej 50%. Dualną do tej klasy jest klasa Co-RP, a przecięcie tych dwóch klas nazywane jest klasą BPP. Problemy, dla których istnieją algorytmy probabilistyczne działające średnio w czasie wielomianowym, ale potencjalnie o dowolnie długim czasie działania, tworzą klasę ZPP.

    Złożoność Kołmogorowa – dla łańcucha symboli, skończonego lub nieskończonego, to długość najkrótszego programu, który generuje dany łańcuch. Nazwa pojęcia pochodzi od nazwiska Andrieja Kołmogorowa.Losowość - w potocznym znaczeniu brak celu, przyczyny, porządku lub przewidywalnego zachowania. Losowy proces to proces, którego wyniki nie dają się dokładnie przewidzieć, a jedynie można opisać ich rozkład.

    Derandomizacja[edytuj kod]

    Algorytmy probabilistyczne są zwykle prostsze i efektywniejsze od algorytmów deterministycznych dla tych samych problemów. Usuwanie wymagania losowości z algorytmów i tworzenie w ten sposób równie silnych algorytmów deterministycznych jest obecnie bardzo aktywnym obszarem badań.

    Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.Generator liczb losowych (ang. random number generator; czasem nazywany generatorem zdarzeń losowych (REG - Random Event Generator) lub generatorem przypadków) - program komputerowy lub układ elektroniczny, generujący stacjonarny i ergodyczny, losowy ciąg elementów binarnych, zorganizowanych zwykle jako ciąg liczb losowych. Generator liczb losowych jest urządzeniem, które nie produkuje przypadkowych liczb, lecz stany, które wyrażane są później jako liczby, stąd też określane są często poprawniejszą nazwą "generatora zdarzeń losowych" (REG - Random Event Generator).

    Zobacz też[edytuj kod]

  • Test Millera-Rabina
  • Sortowanie szybkie
  • Algorytm deterministyczny



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.03 sek.