Wichtige Themen in der Theorie der Berechnung

Question

Während meines Studiums an der Universität musste ich viel über die Theorie der Berechnung lernen. Ich habe das Thema für drei Semester studiert. Ich hatte eine schwere Zeit und muss zugeben, dass ich viel vergessen habe.

Ich frage mich, ob das ein persönliches Problem ist, oder ob wir einfach viel (mehr oder weniger) nutzloses Zeug lernen müssen.

Also meine Frage ist: Welche Themen auf dem Gebiet der Theorie der Berechnung sind Ihrer Meinung nach am wichtigsten, welche Teile sind es wert, darüber zu lernen, und welche Themen verwenden Sie während Ihrer normalen Arbeit?

Ich persönlich bin froh, dass ich über die theory of languages gehört (vor allem die regulären Sprachen => reguläre Ausdrücke - wenn sie angewendet und wenn nicht werden) die verschiedenen time (and space) complexities und über, insbesondere die O (n) Notationen.

Aber wir hatten viel mehr zu studieren, einschließlich:

• Berechenbarkeit Theorie
  • Halteproblem
  • semidecidable Probleme
• Theorie der Komplexität
  • p = np?
• Theorie der Logik
  • Aussagenlogik
  • Pr¨adikatenlogik

Es war interessant, über diese Themen zu hören, aber ich bin nicht sicher, wie notwendig es ist, studiere sie gründlich.

Ich weiß, diese Frage ist subjektiv und die Antworten werden sich sehr unterscheiden abhängig von Ihrer täglichen Arbeit und persönliche Erfahrung. Aber ich hätte gerne über Themen, die interessanter sein könnten, als ich mich erinnere.

Answer 1

Ich bin mir nicht sicher, ob ich direkt bei der Arbeit alles nutze, was ich in der Theorie der Rechenklassen gelernt habe. Aber ich denke nicht, dass das wirklich der Punkt ist. Ich benutze auch nichts, was ich in der euklidischen Geometrie in der High School des Lebens gelernt habe. Aber das war der wichtigste Kurs, den ich in der Grundschule belegt habe.

Die Theorie der Berechnung ist ein wirklich interessantes Thema, und es gut zu wissen kann Ihnen nur im Leben helfen. Ich kann das nicht beweisen, aber ich weiß, dass es wahr ist.

Tut mir leid, wenn das keine große Antwort ist.

Answer 2

Welche Themen auf dem Gebiet der Theorie der Berechnung denken Sie, sind die wichtigsten

Die Frage ist vage. Wichtig zu wer?

Welche Teile sind es wert, darüber zu lernen?

Alle von ihnen sind es wert, darüber zu lernen. Dies ist ein Sonderfall der Tatsache, dass alle menschlichen Anstrengungen von Natur aus lohnenswert sind.

Wenn Ihre Frage lautet: "Welche Themen bieten mir Vorteile, die größer sind als die Kosten meiner Zeit und Mühe, sie zu studieren?" Dann ist das eine Frage, die nur Sie selbst beantworten können. Der Vorteil für mich, etwa die Geschichte der alten Griechen zu studieren, hat nichts damit zu tun, wie es meine Fähigkeit beeinflusst, meine Arbeit zu erledigen.

Welche Themen verwenden Sie bei Ihrer normalen Arbeit?

Ich benutze alle Themen, die Sie aufgelistet haben - Sprachtheorie, asymptotische Ordnungsanalyse, Entscheidbarkeit, Komplexitätstheorie, Theorem-Prüfsysteme und so weiter.

Ich verwende sie nicht in einer formalen Sinn; Ich sitze nicht mit dem Hauptsatz an meinem Schreibtisch, um eine Ordnungsanalyse für bestimmte Algorithmen abzuleiten. Ich benutze sie in dem Sinne, dass es sehr praktisch ist, ein vorgeschlagenes Sprachmerkmal zu verwenden und schnell herauszufinden, ob die Implementierung des Compilers ein Problem lösen muss, das linear, polynom, exponentiell, NP-hart oder äquivalent ist das Halteproblem.

Zum Beispiel ist es ziemlich einfach zu erarbeiten, dass die Überladungsauflösung in C# 3 auf verschachtelten Lambdas NP-hart ist, aber nicht dem Halteproblem entspricht. Wir wissen daher, dass es (1) eine Verschwendung unserer Zeit ist, sogar zu versuchen, das Problem in polynomieller Zeit zu lösen, und (2) zumindest wissen wir, dass eine Lösung in einer gewissen Zeit gefunden werden kann, und (3) wir könnten mit einfachen Heuristiken aufwarten, um die schlechten Szenarien zu erkennen und schnell zu versagen, wenn es nötig wäre.

Ich persönlich verwende keine Proofsysteme, obwohl es hilfreich ist, über Probleme als Sonderfall eines Theorembeweisers nachzudenken. Es gibt alle Arten von Sprachmerkmalen, die den Problemen entsprechen, die Sie bei einem Theorembeweiser werfen, insbesondere im Bereich der Typinferenz und der Flussanalyse. Glücklicherweise keine der Funktionen von C# tatsächlich erfordern Implementierung eines Theorembeweisers; Andere Sprachen, die in diesem Gebäude implementiert sind, haben diese Eigenschaft, wie F #.