Ich suche nach Beispielen für Ergebnisse, die gegen die Intuition der Menschen für ein allgemeines Publikumsgespräch verstoßen. Ergebnisse, die, wenn Sie von Nicht-Experten gefragt werden, "Was sagt Ihnen Ihre Intuition?", Fast alle falsch machen würden. Die Aussage der Ergebnisse sollte für Studierende in cs / math leicht zu erklären sein. Ich suche hauptsächlich Ergebnisse in der Informatik.
Was sind die intuitivsten / unerwartetsten Ergebnisse (von allgemeinem Interesse) in Ihrer Region?
Antworten:
Für ein allgemeines Publikum muss man die Dinge bleiben , dass sie sehen . Sobald Sie anfangen zu theoretisieren, starten sie ihre Handys.
Hier sind einige Ideen, die ausgearbeitet werden könnten, um Beispiele zu vervollständigen:
Wenn Sie sich auf ein wenig mathematisches Wissen verlassen können, können Sie mehr tun:
Für Programmierer können Sie versuchen:
Die unmöglich Funktionalen : Es ist ein Programm , das ein Prädikat nimmt
p : stream → bool
, wostream
der Datentyp der unendlichen binärer Sequenzen ist, und kehrt ,true
wenn und nur wennp α
isttrue
für alle Strömeα
(das ist unzählbar viele), und ausfalse
anderen Gründen .Es ist möglich, Poker auf vertrauenswürdige Weise telefonisch zu spielen, um Betrug zu verhindern.
Eine Gruppe von Personen kann ihr Durchschnittsgehalt berechnen, ohne dass jemand das Gehalt einer anderen Person herausfindet.
Es ist ein Programm , das einen Konstrukt binären BaumT mit den folgenden Eigenschaften:
quelle
Eine Idee ist etwas Einfaches aus Streaming-Algorithmen . Der wahrscheinlich beste Kandidat ist der Mehrheitsalgorithmus. Angenommen, Sie sehen einen Strom von Zahlen , einer nach dem anderen, und Sie wissen, dass eine Zahl mehr als die Hälfte der Zeit vorkommt, aber Sie wissen nicht, welche. Wie können Sie die Mehrheitszahl finden, wenn Sie sich nur an zwei Zahlen gleichzeitig erinnern können ? Die Antwort ist der Misra-Gries-Algorithmus.s1,…,sn
In jedem Zeitschritt speichern Sie eine Zahl aus dem Stream und einen Frequenzzähler f . Zu Beginn setzen Sie x auf die erste Nummer des Streams und initialisieren die Frequenz f auf 1. Wenn Sie dann eine neue Nummer s i sehen , überprüfen Sie, ob x = s i ist . Wenn x = s i , Erhöhung f zu f + 1 , verringert sonst f bis f - 1 . Wenn f = 0 , setze x auf s ix f x f si x=si x=si f f+1 f f- 1 f= 0 x sich und zurück zu 1 . Wenn nach dem letzten Element des Streams ein Mehrheitselement vorhanden war, ist es gleich x .f 1 x
Eine weitere Idee ist das bekannte Spiel zur Veranschaulichung von wissensfreien Beweisen . Ich denke, es liegt an Oded Goldreich und ist ähnlich wie der wissensfreie Beweis für die Graphisomorphie.
Um die Antwort in sich geschlossen zu machen, hier ist das Spiel. Angenommen, Sie möchten Ihren farbenblinden Freund davon überzeugen, dass Sie Rot von Grün unterscheiden können. Ihr Freund hat zwei Kartenspiele und weiß, dass ein Stapel grün und der andere rot ist. Er macht Folgendes, ohne dass Sie ihn sehen: Mit Wahrscheinlichkeit 1/2 zieht er eine Karte aus jedem Stapel, mit Wahrscheinlichkeit 1/4 zieht er zwei Karten aus dem linken Stapel und mit Wahrscheinlichkeit 1/4 zieht er zwei Karten aus dem rechten Stapel . Dann zeigt er Ihnen die Karten und fragt Sie, ob sie die gleiche Farbe haben. Wenn Sie nicht farbenblind sind, können Sie natürlich jedes Mal richtig antworten. Wenn Sie farbenblind sind, werden Sie mit der Wahrscheinlichkeit 1/2 scheitern. Wenn das Spiel nun 10 Mal gespielt wird, ist die Wahrscheinlichkeit, dass Sie jedes Mal gewinnen können, wenn Sie farbenblind sind, äußerst gering.
Der Kicker ist, wenn dein Freund wüsste, dass die beiden Kartenspiele zwei verschiedene Farben haben, aber nicht wüsste, welches rot und welches grün ist, wird er es am Ende immer noch nicht wissen! Also zusammenfassend:
quelle
Das Volumen einer Einheitskugel der Dimension wächst zuerst mit n ( 2 , π , 4 π / 3 , … ), nimmt jedoch für n = 6 ab und konvergiert schließlich gegen 0, wenn n → ∞ .n n 2,π,4π/3,… n=6 0 n→∞
quelle
Ein kontraintuitives Ergebnis der Komplexitätstheorie ist der PCP-Satz:
Informell heißt es , dass für jeden Problem A , gibt es eine effiziente randomisierte Turing - Maschine , den Beweis Korrektheit (Nachweis der Mitgliedschaft in verifizieren kann A ) unter Verwendung von logarithmisch Anzahl von Zufallsbits und nur konstante Anzahl von Bits aus dem Beweis zu lesen. Die Konstante kann auf 3 Bit reduziert werden. Daher muss der randomisierte Prüfer nur drei Bits aus dem proklamierten Beweis lesen.NP A A
quelle
Eine Sache, die sich für CS-Studenten als nicht intuitiv erweist, ist die Tatsache, dass man die auswählen kannich -te Ordnung Statistik aus einem unsortierten Array von n Elemente in O ( n ) Zeit. Alle Schüler denken, dass sie zuerst das Array sortieren müssen (inO(n lg n) time).
quelle
building on MdBs answer/ angle, a classic result of something counterintuitive at the time of discovery in TCS at its foundations is the existence of (un)decidability itself. at the turn of the 20th century Hilbert, mirroring the thinking of other leading mathematicians of the time, thought that mathematics could be systematized (somewhat in the form of what we now recognize as algorithmic) & somewhat via the concept of "finitism" (which has rough parallels to the idea of an algorithm as a finite sequence of steps). he proposed famous open problems along these lines. his (and others) intuition turned out to be wrong in a sort of spectacular way. the counterproof is Godels theorem and Turings Halting problem. both were initially extremely abstract concepts/ results and long, highly technical papers/ arguments only understandable to leading mathematicians of the time, but now are refined to simpler conceptual structures and taught to undergraduates. these were not initially seen as two aspects/face of the same phenomenon but now they are.
also it took close to ~¾ of a century to prove that integer Diophantine equations are undecidable, Hilberts 10th problem. this is counterintuitive in the sense that it was always known that number theory was extremely difficult but the concept that some specific/ identifiable problems in it may actually be "impossible to resolve" was nearly shocking at the time to some. undecidability continues to be a deep challenge in math/ TCS even as we have decades of exponential increases in hardware due to Moores law and yet massive supercomputers that are in a sense still "powerless against it". some aspects of the surprise of undecidability can be found in the book Mathematics, Loss of Certainty by Klein.
quelle
It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a little too technical, you can always convert it into a statement about polls an elections (you need 1300 people to get a sample with 3% error, regardless of the population size).
Related to this is the birthday paradox of course.
quelle
Ein gutes Beispiel (das nicht in direktem Zusammenhang mit der Komplexität von Berechnungen steht) ist vielleicht die Turing-Universalität einfacher Rechenmodelle.
Zum Beispiel ist die Regel 110 effizient (schwach) universell:
Wenn ein (unendliches) Array von 0-1 (weiß-schwarzen) Zellen richtig initialisiert ist und die einfachen Substitutionsregeln gelten:
Wir haben einen "funktionierenden Computer"! :-)
Für die Definition von "schwach" und "effizient" und für andere Beispiele einfacher universeller Turingmaschinen siehe: Turlough Neary, Damien Woods; Die Komplexität kleiner Universal-Turingmaschinen: eine Übersicht .
Another puzzling example is the Turing completeness of the FRACTRAN "programming language":
With a suitable encoding of the inputn , FRACTRAN can simulate any Turing machine.
You can also use other models, like cyclic tag systems, ant-automata, ....
The not-so-intuitive idea is that "computation" is hidden almost everywhere ... Wolfram wrote 1192 pages filled with figures and text to better express that idea in his A New Kind of Science (yes... yes... despite some critical reviews I finally bought a hard-copy of it :-)
quelle
A few good candidates off the top of my head:
Every NFA has an equivalent DFA
There exists a finite field of sizep or pi where i∈N and i>0 .
Public key cryptography
Calling to a function with encrypted arguments and receiving the desired result without revealing information about your inputs
RSA encrpytion
Reed-Solomon codes
Countability
The set of elements in the language{0,1}∗ is countable, but R is uncountable (Cantor's diagonalization)
Cantor's Theorem:|S|<|P(S)|
On a more philosophical level, it astonished me that Turing machines accurately define computation
quelle