Wyniki sprzeczne z intuicją dla studentów

Szukam przykładów wyników, które są sprzeczne z intuicją ludzi podczas ogólnej dyskusji publiczności. Wyniki, które na pytanie ekspertów niebędących ekspertami „co podpowiada ci intuicja?”, Prawie wszystko byłoby błędne. Oświadczenie o wynikach powinno być łatwe do wyjaśnienia studentom w cs / matematyce. Głównie szukam wyników w informatyce.

Jakie są najbardziej sprzeczne z intuicją / nieoczekiwane wyniki (ogólne zainteresowanie) w Twojej okolicy?

Dla ogółu odbiorców musisz trzymać się rzeczy, które mogą zobaczyć . Gdy tylko zaczniesz teoretyzować, uruchomią swoje telefony komórkowe.

Oto kilka pomysłów, które można wypracować w celu uzupełnienia przykładów:

1. Jest powierzchnia, która ma tylko jedną stronę .
2. Krzywa może wypełnić cały kwadrat .
3. Istnieją krzywe o stałej szerokości inne niż okrąg.
4. Możliwe jest pokolorowanie płaszczyzny trzema kolorami w taki sposób, że każdy punkt graniczny jest trójkątem .

Jeśli możesz polegać na odrobinie wiedzy matematycznej, możesz zrobić więcej:

1. Jest tyle nieparzystych liczb, ile jest liczb naturalnych.
2. Istnieje funkcja ciągła i nigdzie różna .
3. Istnieje funkcja która jest nieciągła dla wszystkich liczb wymiernych i różniczkowalna dla wszystkich liczb niewymiernych.$f : \mathbb{R} \to \mathbb{R}$
4. Banacha-Tarskiego „paradoks” .

Dla programistów możesz spróbować:

1. W niemożliwych Funkcjonały : jest to program, który wykonuje orzeczenie p : stream → bool, w którym streamjest typ danych nieskończonych ciągów binarnych i powraca truewtedy i tylko wtedy, gdy p αjest truedla wszystkich strumieni α(to uncountably wiele), a falseinaczej.

2. Można grać w pokera przez telefon w zaufany sposób, co zapobiega oszukiwaniu.

3. Grupa ludzi może obliczyć swoje przeciętne wynagrodzenie bez wiedzy o wynagrodzeniach innych osób.

4. Istnieje program, który konstruuje drzewo binarne$T$ o następujących właściwościach:

   • drzewo jest nieskończone$T$
   • nie ma programu, który śledziłby nieskończoną ścieżkę w$T$

Jeden pomysł to coś prostego z algorytmów przesyłania strumieniowego . Prawdopodobnie najlepszym kandydatem jest algorytm większościowy. Załóżmy, że widzisz strumień liczb , jeden po drugim, i wiesz, że jedna liczba występuje więcej niż w połowie przypadków, ale nie wiesz, która z nich. Jak znaleźć numer większości, jeśli pamiętasz tylko dwie liczby na raz ? Odpowiedzią jest algorytm Misra-Gries.$s_1, \ldots, s_n$

Na każdym kroku zapisujesz liczbę ze strumienia i licznik częstotliwości . Na początku ustawiasz na pierwszą liczbę strumienia i inicjujesz częstotliwość na 1. Następnie, gdy zobaczysz nową liczbę , sprawdzasz, czy . Jeśli , zwiększ do , w przeciwnym razie zmniejsz do . Jeśli , zestaw do i z powrotem do . Po ostatnim elemencie strumienia, jeśli był element większości, będzie on równyf x f s i x = s i x = s i f f + 1 f f - 1 f = 0 x s i f 1 $x$$f$$x$$f$$s_i$$x = s_i$$x=s_i$$f$$f+1$$f$$f-1$$f=0$$x$$s_i$$f$$1$$x$ .

Innym pomysłem jest dobrze znana gra ilustrująca zero dowodów wiedzy . Myślę, że wynika to z Oded Goldreich i jest podobny do zerowego dowodu wiedzy na temat izomorfizmu grafów.

Aby odpowiedź była samodzielna, oto gra. Załóżmy, że chcesz przekonać swojego niedowidzącego przyjaciela, że ​​możesz odróżnić czerwony od zielonego. Twój przyjaciel ma dwie talie kart i wie, że jeden stos jest zielony, a drugi czerwony. Robi to bez ciebie: z prawdopodobieństwem 1/2 losuje jedną kartę z każdej talii, z prawdopodobieństwem 1/4 losuje dwie karty z lewej talii, a z prawdopodobieństwem 1/4 losuje dwie karty z prawej talii . Następnie pokazuje ci karty i pyta, czy są tego samego koloru. Jeśli nie jesteś ślepy na kolory, możesz oczywiście odpowiedzieć poprawnie za każdym razem. Jeśli jesteś ślepy na kolory, zawiedziesz z prawdopodobieństwem 1/2. Jeśli teraz gra się 10 razy, prawdopodobieństwo, że wygrasz za każdym razem będąc ślepym na kolory, jest bardzo niskie.

Kick polega na tym, że jeśli twój znajomy wiedział, że dwie talie kart mają dwa różne kolory, ale nie wiedział, który z nich jest czerwony, a który zielony, nadal nie będzie wiedział na końcu! Podsumowując:

1. W dowodach jest miejsce na przypadkowość.
2. Możesz przekonać kogoś, że coś wiesz, nie przekazując mu żadnych informacji na ten temat.

Objętość sfery jednostkowej wymiaru najpierw rośnie wraz ze wzrostem ( ), ale zaczyna się zmniejszać dla i ostatecznie zbiega się do jako .n 2 , π , 4 π / 3 , … n = 6 0 n → $n$$n$$2,\pi,4\pi/3,\dots$$n=6$$0$$n\to\infty$

Przeciwnie intuicyjnym wynikiem teorii złożoności jest twierdzenie PCP:

$NP$$A$$A$

$i$$n$$O(n)$$O(n~lg ~n)$

bazując na odpowiedzi / kącie MdB, klasycznym rezultatem czegoś sprzecznego z intuicją w momencie odkrycia w TCS u jego podstaw jest samo istnienie (nie) rozstrzygalności . na przełomie ^{XIX i XX} wieku Hilbert, odzwierciedlając myśl innych czołowych matematyków tamtych czasów, pomyślał, że matematykę można usystematyzować (nieco w formie tego, co obecnie nazywamy algorytmem ) i nieco poprzez koncepcję „finityzmu” ( który ma przybliżone podobieństwa do idei algorytmu jako skończonej sekwencji kroków). zaproponował słynne otwarte problemy w tym zakresie. jego (i inni) intuicja okazała się błędna w pewien spektakularny sposób. kontroodporność jestTwierdzenie Godelsa i problem zatrzymania Turingsa . oba były początkowo niezwykle abstrakcyjnymi pojęciami / wynikami i długimi, wysoce technicznymi artykułami / argumentami zrozumiałymi tylko dla czołowych matematyków tamtych czasów, ale teraz są dopracowane do prostszych struktur koncepcyjnych i nauczane dla studentów. nie były one początkowo postrzegane jako dwa aspekty / oblicze tego samego zjawiska, ale teraz są.

również zajęło prawie ¾ wieku, aby udowodnić, że liczby całkowite Równania diofantyczne są nierozstrzygalne, dziesiąty problem Hilberta . jest to sprzeczne z intuicją w tym sensie, że zawsze wiadomo było, że teoria liczb jest niezwykle trudna, ale koncepcja, że ​​niektóre konkretne / możliwe do zidentyfikowania problemy mogą być „niemożliwe do rozwiązania”, była dla niektórych niemal szokująca. nierozstrzygalność nadal stanowi głębokie wyzwanie w matematyce / TCS, mimo że mamy dekady wykładniczego wzrostu sprzętu ze względu na prawo Mooresa, a jednak ogromne superkomputery, które są w pewnym sensie nadal „bezsilne”. niektóre aspekty niespodzianki nierozstrzygalności można znaleźć w książce Mathematics, Loss of Certainty autorstwa Kleina.

Wydaje się to oczywiste, ale z własnego doświadczenia pomysł, że można oszacować medianę zbioru przedmiotów przy użyciu stałej liczby operacji, jest nieco szokujący. A jeśli wydaje się to trochę zbyt techniczne, zawsze możesz przekonwertować je na stwierdzenie o wyborach wyborczych (potrzebujesz 1300 osób, aby uzyskać próbkę z 3% błędem, niezależnie od liczebności populacji).

Powiązany z tym jest oczywiście paradoks urodzinowy .

Być może dobrym przykładem (niezwiązanym bezpośrednio ze złożonością obliczeniową) jest uniwersalność prostych modeli obliczeniowych Turinga.

Na przykład reguła 110 jest wydajnie (słabo) uniwersalna:

Biorąc pod uwagę (nieskończoną) tablicę 0-1 (biało-czarnych) komórek właściwie zainicjowanych i proste zasady podstawiania:

mamy „działający komputer”! :-)

Definicję „słabo” i „wydajnie” oraz inne przykłady prostych uniwersalnych maszyn Turinga można znaleźć w: Turlough Neary, Damien Woods; Złożoność małych uniwersalnych maszyn Turinga: ankieta .

Innym zagadkowym przykładem jest kompletność Turinga „języka programowania” FRACTRAN :

• $(p_1/q_1, p_2/q_2,..., p_n/q_n)$
• $n$$q_i$$n$$n \leftarrow n \cdot \frac{p_i}{q_i}$
• $q_i$$n$

$n$

Możesz także użyć innych modeli, takich jak cykliczne systemy tagów, ant-automaty, ... Niezbyt
intuicyjny pomysł polega na tym, że „obliczenia” są ukryte prawie wszędzie ... Wolfram napisał 1192 strony wypełnione cyframi i tekstem, aby lepiej wyrazić ten pomysł w swoim A New Kind of Science (tak ... tak ... pomimo niektórych krytycznych recenzji w końcu kupiłem jego wersję papierową :-)

Kilku dobrych kandydatów z mojej głowy:

• Każdy NFA ma równoważny DFA

• $p$$p^i$$i \in \mathbb{N}$$i > 0$

• Kryptografia klucza publicznego

  • Wywołanie funkcji z zaszyfrowanymi argumentami i otrzymanie pożądanego wyniku bez ujawnienia informacji o danych wejściowych

  • Kodowanie RSA

• Kody Reeda-Solomona

• Policzalność

  • $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{N} \times \mathbb{N}| = |\mathbb{Q}|$

  • $\{0,1\}^*$$\mathbb{R}$

  • $|S| < |\mathcal{P}(S)|$

• Z bardziej filozoficznego punktu widzenia zadziwiło mnie, że maszyny Turinga precyzyjnie definiują obliczenia