In der theoretischen Informatik und Mathematik beschäftigt sich die -Theorie mit der Frage, wie effizient Probleme auf einem Rechenmodell gelöst werden können ein Algorithmus. Das Feld ist in drei Hauptzweige unterteilt: Automatentheorie und -sprachen, Berechenbarkeitstheorie und Rechenkomplexitätstheorie, die mit der Frage verknüpft sind: "Was sind die grundlegenden Fähigkeiten und Einschränkungen von Computern?". [1]
In Reihenfolge Um eine gründliche Studie über Berechnungen durchzuführen, arbeiten Computerwissenschaftler mit einer mathematischen Abstraktion von Computern, die als Berechnungsmodell bezeichnet wird. Es werden mehrere Modelle verwendet, am häufigsten wird jedoch die Turing-Maschine untersucht. [2] Informatiker untersuchen die Turing-Maschine, weil sie einfach zu formulieren ist, analysiert werden kann und zum Nachweis der Ergebnisse verwendet werden kann und weil sie das darstellt, was viele davon berücksichtigen Möglichstes "vernünftiges" Berechnungsmodell (siehe Church-Turing-These). [3] Es scheint, dass die potenziell unendliche Speicherkapazität ein nicht realisierbares Attribut ist, aber jedes entscheidbare Problem [4] das von einer Turing-Maschine gelöst wird, wird immer nur erforderlich sein eine endliche Menge an Speicher. Im Prinzip kann jedes Problem, das von einer Turing-Maschine gelöst (entschieden) werden kann, von einem Computer gelöst werden, der über eine begrenzte Menge an Speicher verfügt.
Geschichte [ edit ]
Die Theorie der Berechnung kann als die Schaffung von Modellen aller Art auf dem Gebiet der Informatik betrachtet werden. Daher werden Mathematik und Logik verwendet. Im letzten Jahrhundert wurde sie zu einer unabhängigen akademischen Disziplin und wurde von der Mathematik getrennt.
Einige Pioniere der Rechentheorie waren die Alonzo-Kirche, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann und Claude Shannon.
Zweige [ edit ]
Automata-Theorie [ edit ]
Automaten-Theorie ist das Studium abstrakter Maschinen (oder besser geeignet, abstrakt.) "mathematische" Maschinen oder Systeme) und die Rechenprobleme, die mit diesen Maschinen gelöst werden können. Diese abstrakten Maschinen werden Automaten genannt. Automaten stammen aus dem griechischen Wort (Αυτόματα), was bedeutet, dass etwas von sich aus etwas tut. Die Automatentheorie ist auch eng mit der formalen Sprachtheorie verbunden, [5] da die Automaten häufig nach der Klasse der formalen Sprachen klassifiziert werden, die sie erkennen können. Ein Automat kann eine endliche Repräsentation einer Formsprache sein, die eine unendliche Menge sein kann. Automaten werden als theoretische Modelle für Rechenmaschinen und für Nachweise zur Berechenbarkeit verwendet.
Theorie der formalen Sprache [ edit ]
Die Sprachtheorie ist ein Zweig der Mathematik, der sich mit der Beschreibung von Sprachen befasst Satz von Operationen über einem Alphabet. Es ist eng mit der Automatentheorie verbunden, da Automaten zur Generierung und Erkennung von formalen Sprachen verwendet werden. Es gibt mehrere Klassen formaler Sprachen, von denen jede eine komplexere Sprachspezifikation als die vorhergehende zulässt, d. H. Die Chomsky-Hierarchie [6] und jede entspricht einer Klasse von Automaten, die sie erkennt. Da Automaten als Modelle für die Berechnung verwendet werden, sind formale Sprachen die bevorzugte Art der Spezifikation für jedes Problem, das berechnet werden muss.
Berechenbarkeitstheorie [ edit ]
Die Berechenbarkeitstheorie beschäftigt sich hauptsächlich mit der Frage, inwieweit ein Problem auf einem Computer lösbar ist. Die Aussage, dass das Halteproblem nicht mit einer Turing-Maschine [7] gelöst werden kann, ist eines der wichtigsten Ergebnisse in der Theorie der Berechenbarkeit, da es ein Beispiel für ein konkretes Problem ist, das sowohl leicht zu formulieren als auch mit einer Turing-Maschine nicht zu lösen ist . Ein großer Teil der Theorie der Berechenbarkeit baut auf dem Ergebnis des Anhaltens des Problems auf.
Ein weiterer wichtiger Schritt in der Theorie der Berechenbarkeit war der Satz von Rice, der besagt, dass es für alle nicht trivialen Eigenschaften von Teilfunktionen unerheblich ist, ob eine Turing-Maschine eine Teilfunktion mit dieser Eigenschaft berechnet. [8] [edit]
Die Berechenbarkeitstheorie ist eng verwandt mit dem Zweig der mathematischen Logik, der Rekursionstheorie, der die Einschränkung des Studierens von nur auf das Turing-Modell reduzierbaren Berechnungsmodellen aufhebt. [9] Viele Mathematiker und Computertheoretiker, die sich auf Rekursionstheorie beziehen, werden sich darauf beziehen um es als Berechenbarkeitstheorie.
Rechnerische Komplexitätstheorie [ edit ]
Die Komplexitätstheorie berücksichtigt nicht nur, ob ein Problem überhaupt auf einem Computer gelöst werden kann, sondern auch wie effizient das problem gelöst werden kann. Es werden zwei Hauptaspekte betrachtet: Zeitkomplexität und Raumkomplexität. Dies ist jeweils die Anzahl der Schritte, die zur Durchführung einer Berechnung erforderlich sind, und wie viel Speicherplatz zur Ausführung dieser Berechnung erforderlich ist.
Um zu analysieren, wie viel Zeit und Raum ein bestimmter Algorithmus benötigt, geben die Informatiker die zur Lösung des Problems erforderliche Zeit oder den erforderlichen Raum als Funktion der Größe des Eingangsproblems an. Das Auffinden einer bestimmten Nummer in einer langen Liste von Nummern wird beispielsweise schwieriger, wenn die Liste der Nummern größer wird. Wenn wir sagen, dass es n Zahlen in der Liste gibt, dann müssen wir, wenn die Liste auf keine Weise sortiert oder indiziert ist, jede Zahl betrachten, um die gesuchte Zahl zu finden. Wir sagen also, dass der Computer zur Lösung dieses Problems eine Reihe von Schritten ausführen muss, die mit der Größe des Problems linear wachsen.
Um dieses Problem zu vereinfachen, haben die Informatiker die Big-O-Notation verwendet, mit der Funktionen so verglichen werden können, dass bestimmte Aspekte der Konstruktion einer Maschine nicht berücksichtigt werden müssen, sondern nur das asymptotische Verhalten, wenn Probleme auftreten groß In unserem vorherigen Beispiel könnten wir also sagen, dass das Problem Schritte erfordert lösen.
Das vielleicht wichtigste offene Problem in der gesamten Informatik ist die Frage, ob eine bestimmte breite Klasse von Problemen, die als NP bezeichnet werden, effizient gelöst werden kann. Dies wird in den Komplexitätsklassen P und NP ausführlicher besprochen. Das P versus NP-Problem ist eines der sieben Millennium-Preisprobleme, die das Clay Mathematics Institute im Jahr 2000 feststellte. Die offizielle Problembeschreibung wurde vom Turing-Preisträger Stephen Cook gegeben.
Berechnungsmodelle [ edit ]
Abgesehen von einer Turing-Maschine werden andere gleichwertige (Siehe: Church-Turing-These) Berechnungsmodelle verwendet.
- Lambda-Kalkül
- Eine Berechnung besteht aus einem anfänglichen Lambda-Ausdruck (oder zwei, wenn Sie die Funktion und ihre Eingabe trennen möchten) plus einer endlichen Folge von Lambda-Termen, die jeweils durch eine Anwendung der Beta-Reduktion aus dem vorhergehenden Term abgeleitet werden
- Kombinatorik
- ist ein Konzept, das viele Ähnlichkeiten mit hat, aber es gibt auch wichtige Unterschiede (z. B. Fixpunkt) Kombinator Y hat eine normale Form in der Kombinationslogik, aber nicht in -calculus). Die kombinatorische Logik wurde mit großem Ehrgeiz entwickelt: das Verständnis der Natur von Paradoxien, die ökonomischere (konzeptionelle) Grundlagen der Mathematik, die Beseitigung des Begriffs der Variablen (wodurch ihre Rolle in der Mathematik geklärt wird).
- μ-rekursive Funktionen
- eine Berechnung besteht aus einer mu-rekursiven Funktion, dh seine definierende Reihenfolge, beliebige Eingabewerte und eine Folge von rekursiven Funktionen, die in der definierenden Reihenfolge mit Eingängen und Ausgängen erscheinen. Wenn also in der Definitionssequenz einer rekursiven Funktion die Funktionen funktionieren und erscheint, dann sind Formeln mit der Form 'g (5) = 7 'oder' h (3,2) = 10 'können erscheinen. Jeder Eintrag in dieser Sequenz muss eine Anwendung einer Basisfunktion sein oder aus den obigen Einträgen unter Verwendung von Zusammensetzung, primitiver Rekursion oder μ-Rekursion folgen. Wenn zum Beispiel Damit 'f (5) = 3' erscheint, müssen oben Begriffe wie 'g (5) = 6' und 'h (5,6) = 3' auftreten. Die Berechnung wird nur dann beendet, wenn der letzte Term den Wert der auf die Eingaben angewendeten rekursiven Funktion angibt.
- Markov-Algorithmus
- Ein Zeichenfolgenumschreibungssystem, das grammatikenähnliche Regeln für die Verarbeitung von Zeichenfolgen verwendet.
- Register machine
- ist eine theoretisch interessante Idealisierung eines Computers. Es gibt verschiedene Varianten. In den meisten von ihnen kann jedes Register eine natürliche Zahl (von unbegrenzter Größe) enthalten, und die Befehle sind einfach (und nur wenige), z. es besteht nur eine Dekrementierung (kombiniert mit einem bedingten Sprung) und eine Inkrementierung (und Anhalten). Das Fehlen des unendlichen (oder dynamisch wachsenden) externen Speichers (bei Turing-Maschinen zu erkennen) kann durch Ersetzen seiner Rolle durch Gödel-Nummerierungstechniken verstanden werden: Die Tatsache, dass jedes Register eine natürliche Zahl enthält, ermöglicht die Darstellung einer komplizierten Sache (z. B. a Sequenz oder eine Matrix usw.) durch eine entsprechend große natürliche Zahl - die Eindeutigkeit von Repräsentation und Interpretation kann durch zahlentheoretische Grundlagen dieser Techniken festgelegt werden.
Zusätzlich zu den allgemeinen Rechenmodellen sind einige einfachere Rechenmodelle nützlich spezielle, eingeschränkte Anwendungen. Reguläre Ausdrücke spezifizieren zum Beispiel Zeichenkettenmuster in vielen Zusammenhängen, von Office-Produktivitätssoftware bis zu Programmiersprachen. Ein weiterer Formalismus, der mathematischen Ausdrücken mathematisch äquivalent ist, werden finite Automaten beim Schaltungsdesign und bei einigen Arten der Problemlösung verwendet. Kontextfreie Grammatiken geben die Syntax der Programmiersprache an. Nicht-deterministische Pushdown-Automaten sind ein weiterer Formalismus, der kontextfreien Grammatiken entspricht. Primitive rekursive Funktionen sind eine definierte Unterklasse der rekursiven Funktionen.
Verschiedene Berechnungsmodelle haben die Fähigkeit, verschiedene Aufgaben zu erledigen. Eine Möglichkeit, die Leistungsfähigkeit eines Rechenmodells zu messen, besteht darin, die Klasse formaler Sprachen zu studieren, die das Modell generieren kann. auf diese Weise wird die Chomsky-Hierarchie der Sprachen erhalten.
Referenzen [ edit ]
- ^ Michael Sipser (2013). Einführung in die Theorie der Berechnung 3. . Lernen lernen. ISBN 978-1-133-18779-0.
zentrale Bereiche der Rechentheorie: Automaten, Berechenbarkeit und Komplexität. (Seite 1)
- ^ Hodges, Andrew (2012). Alan Turing: The Enigma (Die Hundertjährige Ausgabe) . Princeton University Press. ISBN 978-0-691-15564-7.
- ^ Rabin, Michael O. (Juni 2012). Turing, Church, Gödel, Berechenbarkeit, Komplexität und Randomisierung: Eine persönliche Sicht .
- Donald Monk (1976). Mathematische Logik . Springer-Verlag. ISBN 9780387901701.
- ^ Hopcroft, John E. und Jeffrey D. Ullman (2006). Einführung in die Theorie, Sprachen und Berechnungen von Automaten. 3. Auflage . Lesen, MA: Addison-Wesley. ISBN 978-0-321-45536-9.
- ^ Chomsky-Hierarchie (1956). Msgstr "Drei Modelle zur Beschreibung der Sprache". Informationstheorie, IRE-Transaktionen am . IEEE. 2 (3): 113–124. doi: 10.1109 / TIT.1956.1056813 . 6. Januar 2015 .
- Alan Turing (1937). Msgstr "Auf berechenbaren Nummern, mit einer Anwendung auf das Entscheidungsproblem". Verfahren der London Mathematical Society . IEEE. 2 (42): 230–265. doi: 10.1112 / plms / s2-42.1.230 . 6. Januar 2015 .
- Henry Gordon Rice (1953). Msgstr "Klassen rekursiv aufzählbarer Mengen und ihre Entscheidungsprobleme". Transaktionen der American Mathematical Society . Amerikanische Mathematische Gesellschaft. 74 (2): 358–366. doi: 10.2307 / 1990888. JSTOR 1990888.
- Martin Davis (2004). Das Unentscheidbare: Grundlagenpapiere zu unentscheidbaren Vorschlägen, unlösbaren Problemen und berechenbaren Funktionen (Dover Ed) . Dover-Publikationen. ISBN 978-0486432281.
Weiterführende Literatur [ edit ]
- Lehrbücher für Informatiker
(Es gibt viele Lehrbücher in diesem Bereich; diese Liste ist zwangsläufig unvollständig.)
- Hopcroft, John E. und Jeffrey D. Ullman (2006). Einführung in die Theorie, Sprachen und Berechnungen von Automaten. 3. Auflage Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9 Eine der Standardangaben in diesem Bereich
- Linz P. Eine Einführung in die Formsprache und Automaten . Narosa Publishing. ISBN 9788173197819.
- Michael Sipser (2013). Einführung in die Theorie der Berechnung (3. Aufl.). Lernen lernen. ISBN 978-1-133-18779-0
- Eitan Gurari (1989). Eine Einführung in die Theorie der Berechnung . Informatikpresse. ISBN 0-7167-8182-4. Archiviert aus dem Original am 07.01.2007.
- Hein, James L. (1996) Theorie der Berechnung. Sudbury, MA: Jones und Bartlett. ISBN 978-0-86720-497-1 Eine sanfte Einführung in das Fachgebiet, geeignet für Studenten der Informatikstudenten im zweiten Studienjahr.
- Taylor, R. Gregory (1998). Berechnungsmodelle und formale Sprachen. New York: Oxford University Press. ISBN 978-0-19-510983-2 Ein ungewöhnlich lesbares Lehrbuch für Hochschulabsolventen oder Studienanfänger.
- Lewis, F. D. (2007). Grundlagen der theoretischen Informatik Ein Lehrbuch zu den Themen formale Sprachen, Automaten und Grammatiken. Der Schwerpunkt scheint darauf zu liegen, einen Überblick über die Ergebnisse und ihre Anwendungen zu geben, anstatt Beweise für die Ergebnisse zu liefern.
- Martin Davis, Ron Sigal, Elaine J. Weyuker, Berechenbarkeit, Komplexität und Sprachen: Grundlagen des theoretischen Informatik 2. Auflage, Academic Press, 1994, ISBN 0-12-206382-1. Umfasst ein breiteres Themenspektrum als die meisten anderen Einführungsbücher, einschließlich Semantik des Programms und Quantifizierungstheorie. An Doktoranden gerichtet.
- Bücher zur Berechenbarkeitstheorie aus (breiterer) mathematischer Perspektive
- Historische Perspektive
No comments:
Post a Comment