• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • XIVFestiwal Nauki/ Matematycy rzucają losy

    21.09.2010. 00:53
    opublikowane przez: Redakcja Naukowy.pl

    Po co komputerom liczby losowe i jak można korzystać z przypadkowości, mogli dowiedzieć się uczestnicy XIV Festiwalu Nauki w Warszawie podczas wykładu "Algorytmy losowe" Marcina Muchy. Granica między tym, co ma swój porządek, a tym co jest przypadkowe często jest trudna do określenia. Liczby "losowane" przez maszyny często tak na prawdę nie są losowe. Zazwyczaj są generowane w wyniku tak skomplikowanych algorytmów, że rzeczywiście mogą wydawać się przypadkowe. Aby podać przypadkowe liczby, komputer musi korzystać z danych zewnętrznych. A generowanie liczb losowych staje się coraz bardziej potrzebne w matematyce i informatyce.

    Ale do czego mogą służyć komputerom liczby losowe? Marcin Mucha opowiadał, że pole nawet bardzo skomplikowanej figury można policzyć, rozmieszczając w wyznaczonym polu przypadkowe punkty i sprawdzając czy leżą w obrębie tej figury czy poza nią. Stosunek liczby punktów wewnątrz figury do wszystkich punktów jest zbliżony do proporcji pola danej figury do całego pola. "Im więcej naniesionych punktów, tym wynik powinien być dokładniejszy" - powiedział naukowiec.

    Losowość jest też wykorzystywana np. przy badaniu prawdopodobieństwa, że rozpadnie się dana sieć komputerowa. Jeśli znamy prawdopodobieństwo zepsucia się każdego z połączeń sieci, komputery - uwzględniając to prawdopodobieństwo - losują zdarzenia i symulują te zdarzenia. Po odpowiednio dużej liczbie symulacji można zobaczyć, jak duże jest prawdopodobieństwo rozpadu sieci na kilka części.

    Komputery za pomocą losowości mogą też redukować czynnik ludzki i wyeliminować standardowe odpowiedzi tam, gdzie mogą one przeszkodzić, np. przy wyborze przypadkowych liczb w sprawdzaniu prawdziwości wielomianów czy sprawdzaniu wyznaczników macierzy albo nawet przy wyborze drzwi, za którymi ukryta jest nagroda w teleturnieju czy w wyborze kolejnych ruchów w grze np. w szachy lub kółko i krzyżyk.

    Losowość wyboru ma też znaczenie przy porównywaniu np. ogromnych baz danych. Z wszystkich plików komputer może przyrządzić skrót, tzw. hash. Jeśli skróty dwóch dokumentów są takie same, świadczy to o identyczności porównywanych baz danych.

    Jak zaznaczył Mucha, warto przy sporządzaniu algorytmu hasha wykorzystywać liczby przypadkowe. "Zwykle stosowany jest algorytm nielosowy. A nie jest jasne, czy jest to algorytm bezpieczny" - powiedział. Każdorazowe posługiwanie się nową liczbą losową miałoby, jego zdaniem, poprawić bezpieczeństwo przy sporządzaniu komputerowego "odcisku palca".

    PAP - Nauka w Polsce, Ludwika Tomala

    agt/bsz


    Czy wiesz ĹĽe...? (beta)
    Prawdopodobieństwo obiektywne to interpretacja teorii prawdopodobieństwa, według której wartość prawdopodobieństwa danego zdarzenia jest granicą stosunku liczby "sukcesów" do liczby "losowań". 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. W badaniach prawdopodobieństwa, wspólny rozkład prawdopodobieństwa (ang. joint probability distribution) dla zmiennych losowych X, Y, ... to jeden z rodzajów rozkładu prawdopodobieństwa, który daje prawdopodobieństwo, że każda ze zmiennych losowych X, Y, ... wchodzi w konkretny zakres lub dyskretny zbiór wartości określonych dla tej zmiennej. Jeśli w taki zakres lub zbiór wartości wchodzą tylko dwie zmienne losowe, to rozkład ten nosi nazwę „rozkład dwuwymiarowy”, natomiast jeśli koncepcja uogólni się do dowolnej liczby zmiennych losowych, to rozkład ten będzie nosił nazwę „rozkład wielowymiarowy”.

    Wiara - nadawanie dużego prawdopodobieństwa prawdziwości twierdzenia, w warunkach braku wystarczającej wiedzy. Owo subiektywne prawdopodobieństwo nigdy nie osiąga wartości 100%, gdyż wtedy wiara staje się wiedzą. Jeśli subiektywne prawdopodobieństwo jest małe, to potocznie taką wiarę nazywamy przypuszczeniem, a przy znikomym prawdopodobieństwie mówimy, że czegoś nie wykluczamy. Twierdzenie, które jest przedmiotem wiary nie musi być do końca (lub w ogóle) zwerbalizowane - np. roczne dziecko też może w coś wierzyć. Dotyczy to również bardziej inteligentnych zwierząt. W zwierzęcej "wierze" także dochodzi do subiektywnej oceny prawdopodobieństwa, która jest istotą każdej wiary. Wiara jest także ważnym składnikiem nadziei. Twierdzenie Poissona dostarcza dobrego przybliżenia uzyskania konkretnej liczby sukcesów w schemacie Bernoulliego w przypadku, gdy prawdopodobieństwo sukcesu jest małe oraz iloczyn prawdopodobieństwa sukcesu i liczby prób dąży do pewnej stałej.

    Twierdzenie o nieskończonej liczbie małp stwierdza, że małpa naciskająca losowo klawisze maszyny do pisania przez nieskończenie długi czas, prawie na pewno napisze dowolnie wybrany tekst, taki jak na przykład kompletny dorobek Williama Szekspira. W tym kontekście „prawie na pewno” należy traktować ściśle z matematycznego punktu widzenia (zdarzenie przeciwne ma prawdopodobieństwo równe zeru, jednak nie jest zdarzeniem niemożliwym), a „małpa” jest jedynie metaforą dla abstrakcyjnego urządzenia generującego nieskończony losowy ciąg liter. Twierdzenie ilustruje zagrożenia płynące z postrzegania nieskończoności jako olbrzymiej, ale skończonej liczby, a także z rozumowania odwrotnego – postrzegania dużej liczby jako nieskończoności. Prawdopodobieństwo napisania przez małpę zadanego tekstu, złożonego z dużej liczby znaków, jak na przykład Hamlet, jest tak małe, że szansa wystąpienia zadanego ciągu znaków nawet w czasie rzędu wieku wszechświata jest znikoma. Nierówność Czebyszewa podaje górne ograniczenie prawdopodobieństwa zdarzenia, że wartość nieujemnej zmiennej losowej jest większa lub równa od z góry ustalonej dodatniej liczby.

    Prawdopodobieństwo – ogólne określenie jednego z wielu pojęć służących modelowaniu doświadczenia losowego poprzez przypisanie poszczególnym zdarzeniom losowym liczb, zwykle z przedziału jednostkowego (w zastosowaniach często wyrażanych procentowo), wskazujących szanse ich zajścia. W rozumieniu potocznym wyraz „prawdopodobieństwo” odnosi się do oczekiwania względem rezultatu zdarzenia, którego wynik nie jest znany (niezależnie od tego, czy jest ono w jakimś sensie zdeterminowane, miało miejsce w przeszłości, czy dopiero się wydarzy); w ogólności należy je rozumieć jako pewną miarę przewidywalności bądź pewności względem zjawiska (przy danej o nim wiedzy), co umożliwia ocenę potencjalnie związanego z nim ryzyka. Język zagrożony wymarciem – język wykazujący spadek liczby użytkowników, zwłaszcza wśród młodego pokolenia, co w bliższej lub dalszej przyszłości grozi jego zaniknięciem. Język jest uważany za "bezpieczny", jeżeli istnieje duże prawdopodobieństwo, że dzieci społeczności mówiącej nim będą się nim posługiwały za 100 lat, "zagrożony" jeżeli prawdopodobieństwo to jest niewielkie, i "wymierający", jeżeli młode pokolenie użytkowników języka aktualnie się nim nie posługuje.

    Prawdopodobieństwo subiektywne to interpretacja prawdopodobieństwa, według której prawdopodobieństwo nie musi być wielkością obiektywną, lecz może być określone na podstawie subiektywnej opinii osoby, zależnie od dostępnych jej aktualnie danych.

    Prawdopodobieństwo – ogólne określenie jednego z wielu pojęć służących modelowaniu doświadczenia losowego poprzez przypisanie poszczególnym zdarzeniom losowym liczb, zwykle z przedziału jednostkowego (w zastosowaniach często wyrażanych procentowo), wskazujących szanse ich zajścia. W rozumieniu potocznym wyraz „prawdopodobieństwo” odnosi się do oczekiwania względem rezultatu zdarzenia, którego wynik nie jest znany (niezależnie od tego, czy jest ono w jakimś sensie zdeterminowane, miało miejsce w przeszłości, czy dopiero się wydarzy); w ogólności należy je rozumieć jako pewną miarę nieprzewidywalności.

    Intuicyjnie, zdarzenie losowe to pewien zbiór możliwych wyników danego eksperymentu. Może to być zarówno zbiór składający się z pojedynczego wyniku, jak i zbiór złożony z większej ilości elementów. Zdarzenia losowe rozważa się w rachunku prawdopodobieństwa. Liczby niewymierne – liczby rzeczywiste nie będące liczbami wymiernymi, czyli takie liczby rzeczywiste których nie można zapisać w postaci ilorazu dwóch liczb: liczby całkowitej przez liczbę naturalną różną od zera.

    Malowanie liczbami to łamigłówka polegająca na zaczernianiu pól diagramu. Zaczernione pola utworzą rysunek. To, które pola trzeba zaczernić, wskazują liczby obok diagramu. Liczby z lewej strony każdego wiersza określają, ile grup czarnych pól jest w danym rzędzie i ile czarnych pól jest w każdej grupie. Dla przykładu liczby „1,4,2” oznaczają trzy grupy: pierwsza jest złożona z jednego, druga z czterech, a trzecia z dwóch czarnych pól. Wyodrębnienie 3 kolejnych liczb świadczy o tym, że pomiędzy grupami czarnych pól występuje przynajmniej jedno wolne (białe) pole. Analogicznie jest z liczbami u góry diagramu. Obrazki czarno białe są klasyczną wersją ale czasami można spotkać wersję z wieloma kolorami, w której pola diagramu koloruje się zgodnie z kolorem liczb. Pola z dwoma różnymi kolorami nie muszą mieć białego pola pomiędzy sobą. Występuje również inna wersja (triddler), w której diagram składa się z równobocznych trójkątów.

    Dodano: 21.09.2010. 00:53  


    Najnowsze