Angenommen, Sie treffen sich mit Programmierern, die einige professionelle Programmierkurse besucht haben (/ self thought), aber kein Mathematikstudium auf Universitätsniveau absolviert haben.
Um ihnen die Schönheit von TCS zu zeigen, möchte ich einige nette Ergebnisse / offene Fragen von TCS sammeln, die leicht erklärt werden können.
Ein guter Kandidat für diesen Zweck (IMHO) wird zeigen, dass das Stopp-Problem nicht entscheidbar ist. Eine andere wird eine niedrigere Grenze für die Laufzeit der vergleichsbasierten Sortierung anzeigen (obwohl dies ein bisschen zu viel ist, als ich von ihnen erwartet habe).
Ich kann auch die Ideen vom Erklären des P = NP-Problems bis zum 10-Jährigen verwenden , vorausgesetzt, einige von ihnen sind damit nicht vertraut.
Fragen müssen also sein:
(0. Schön)
- Erklärbar mit (höchstens) High School Mathe.
- (vorzugsweise) nicht trivial genug, um in professionellen Programmierkursen (für C ++ / Java / Web / etc.) gezeigt zu werden.
Antworten:
Zusätzlich zum Problem des Anhaltens schlage ich vor, Folgendes zu diskutieren:
Reis-Theorem. Einige der Erklärungen in Wikipedia sind ein bisschen umgangssprachlich, aber es ist im Allgemeinen kein schwieriger Satz oder Beweis, den man anders verstehen kann. Es hat eine große Relevanz für reale Konzepte wie Antiviren-Software. Der Beweis ist ungefähr so umfangreich wie der Beweis des Halteproblems (und hängt tatsächlich von der Unentscheidbarkeit des Halteproblems ab). Verstehe einfach, dass eine "berechenbare Funktion" eine Turing-Maschine oder ein Computerprogramm ist.
quelle
Ich denke, dass das Cook-Levin-Theorem (und der damit verbundene Begriff der NP-Vollständigkeit) - unabhängig von der P-gegen-NP-Frage - ein weiterer sehr guter Kandidat ist; Wenn Sie einen (effizienten) Löser für SAT haben, dann haben Sie einen (effizienten) Löser für jedes Problem in NP.
sind in gewissem Sinne "gleichwertige Probleme"; Wenn dein Chef dich also bittet, ein Programm zum Verpacken von Kartons in einen Container zu erstellen, kannst du ihm einen Minesweeper-Solver geben ... :-)
quelle
Ein lustiges und unterhaltsames Beispiel ist die Unentscheidbarkeit des Kachelproblems von Wang-Kacheln. Das Ergebnis ergibt sich direkt aus der Unentscheidbarkeit des Halteproblems durch eine einfache Simulation von Turingmaschinen unter Verwendung von Wang-Kacheln. Interessanterweise führte die Unentscheidbarkeit des Kachelproblems für Wang-Kacheln zu dem schönen Ergebnis, dass es Kachelsets gibt, die das Flugzeug nur zeitweise kacheln.
Wang vermutete, dass jedes Plättchen, das auf das Flugzeug gelegt wurde, regelmäßig gekachelt werden musste. Daher implizierte die Vermutung, dass das Kachelproblem entscheidbar ist. Später bewies Burger die Unentscheidbarkeit des Kachelproblems, das die Existenz von Kachelsätzen implizierte, die das Flugzeug nur zeitweise kacheln.
quelle
Favoriten von hier und anderswo gesammelt
Kryptographie mit öffentlichem Schlüssel / RSA-Algorithmus , Trapdoor-Funktionen , Shannons Zählargument, das die meisten Schaltkreisfunktionen anzeigt, sind schwierig ; Ist dieses Rätsel:
AKS-Primalitätstest in P , relativ neuer TCS-Durchbruch leicht kommuniziert
P vs NP . Eine elementare Möglichkeit, NP-Funktionen in Beziehung zu setzen, sind Spiele, z. B. Schlachtschiff oder Soduku, beide mit vollständigen NP-Verallgemeinerungen. siehe auch zB Fortnows-Buch . Siehe auch Videospiele als NP komplett
Unentscheidbarkeit des Post-Korrespondenz-Problems
Tseitin Circuit Transformation & SAT (Reduktionen & NP Vollständigkeit)
(alter) euklidischer Algorithmus & Worst-Case-Analyse-Verbindung zur Fibonacci-Sequenz
Curry-Howard-Korrespondenz zwischen Proofs und Programmen . Ich habe noch keinen elementaren Hinweis dazu gesehen, aber im Grunde ist die Idee recht einfach und verständlich
Vier-Farben-Test via Auto-Test , ein Durchbruch für TCS
quelle