Kilka ciekawostek, z którymi zetknąłem się na studiach i w życiu.
Problem P != NP to chyba najważniejszy otwarty problem informatyki teoretycznej. Problemy klasy P to problemy, dla których rozwiązanie można znaleźć w czasie wielomianowym. Z kolei problemy klasy NP to problemy, których rozwiązanie można zweryfikować w czasie wielomianowym. Czy da się każdy problem, którego rozwiązanie można zweryfikować w czasie wielomianowym, rozwiązać również w tym samym czasie? Za dowiedzenie, że P=NP lub P!=NP można dostać 1 mln $.
Paradoks urodzinowy dotyczy prawdopodobieństwa zdarzenia, że w grupie k osób znajdują się co najmniej dwie osoby urodzone tego samego dnia (z oczywistych względów pomijamy rok). Zaskakujące może wydać się to, że w grupie 23 osób prawdopodobieństwo jest nieco wyższe niż 50%. Zastosowany wzór w WolframAlpha można znaleźć tu. Będzie to dopełnienie zbioru zdarzeń takich, że każda osoba (k – liczba osób) urodziła się w innym dniu (n/n * (n-1)/n * … * (n-k+1)/n = (n!/(n-k)!)/(n^k)). Zmienna n to liczba pudełek (dni w roku), do których trafiają kule (ludzie). Paradoks urodzinowy ma swoje zastosowanie w kryptografii (ataki urodzinowe).
Problem Collatza zwany również Problemem 3n+1. Hipoteza zakłada, że rozpoczynając algorytm od początkowej wartości będącej liczbą naturalną dodatnią zawsze zakończymy jego działanie na liczbie 1. Dla liczby parzystej dzielimy ją na dwa, dla nieparzystej potrajamy i dodajemy 1. Czy istnieje liczba n (należąca do zbioru liczb naturalnych bez zera), dla której algorytm nie będzie miał końca? Rozwiązanie tego problemu przyniesie odkrywcy sławę i duże pieniądze.Przykład działania: 5 ->; 16 ->; 8 -> 4 -> 2 -> 1
Paradoks kłamcy to następujący problem logiczny: Turysta ma do wyboru dwie drogi, ale tylko jedna z nich prowadzi do stolicy. W okolicy mieszkają dwie osoby, o których turysta słyszał, że jedna zawsze mówi prawdę, a druga zawsze kłamie. Turysta spotyka losową z tych dwóch osób. Jakie pytanie ma zadać, aby wybrać właściwą drogę?
Odpowiedź: Należy zadać pytanie "Którą drogę wskaże mi twój kolega?" i odpowiedź zanegować. Kłamca wie, że jego kolega mówi prawdę, więc poda fałszywą drogę. Z kolei prawdomówny wiedząc, że kłamca skłamie, poda drogę fałszywą.
Paradoks Russela polega na skonstruowaniu zbioru: S = { X : X nie należy do X }. Dlaczego jest to paradoks?
Odpowiedź: W przypadku takiego zbioru mamy: x należy do X wtedy i tylko wtedy gdy x nie należy do X. Na chłopski rozum: Należysz do zbioru ludzi wtedy i tylko wtedy kiedy nie należysz do zbioru ludzi. Jeżeli cię to zaciekawiło polecam poszukać informacji o Paradoksie Fryzjera.
Trójkąt Pascala jest przydatny do badania pierwszości liczb jest to jeden z wniosków wypływających z algorytmu AKS. Jeżeli każda kolumna (poza 0 i n) w n-tym wierszu jest podzielna przez n to liczba n jest liczbą pierwszą. Zresztą jest to równoważność, a implikację w drugą stronę bardzo prosto udowodnić.
Star Wars w Ascii-Art możesz zobaczyć wpisując w konsoli/trybie poleceń „telnet towel.blinkenlights.nl”. Trzeba przyznać, że ciekawy pomysł holenderskiego programisty.
Nyan-cat w konsoli możesz zobaczyć wpisując w konsoli/trybie poleceń „telnet miku.acm.uiuc.edu”. Ile wytrzymacie?
Wolne filmy oraz wszelkie inne wolne dzieła kultury istnieją podobnie jak wolne oprogramowanie. Najczęściej dystrybuowane są na licencji Creative Commons. Takimi filmami są na przykład Sintel, Big Buck Bunny, Valkaama (współtworzona przez Polaków).
Dzielenie sekretów (ang. secret sharing) to technika kryptograficzna mająca na celu podzielenie dostępu do informacji w ten sposób, że tylko dowolna grupa N osób spośród M osób może uzyskać do niej dostęp. Najprostszym pomysłem jest rozdanie uczestnikom węzłów wykresu wielomianu. Użyteczne tu jest twierdzenie, że dla wielomianu stopnia n potrzebne do odtworzenia wykresu jest n+1 punktów. Aby podzielić sekret w ten sposób żeby wszyscy z grupy M osób byli potrzebni do odczytania informacji (N=M) należy stowrzyć wielomian N-1 stopnia. Jeżeli chcemy, aby N było mniejsze niż M to tworzymy wielomian N-1 stopnia i rozdajemy M punktów tego wielomianu. Jak mając te wszystkie informacje odczytać prawidłowy wielomian? Tutaj pomocna może być Interpolacja (przykłady w dziale „Moje TeXty”).
Strona z otwartymi problemami matematyki i nagrodami pieniężnymi za ich rozwiązaniu znajduje się tutaj