Theoretische Informatik (TCS) ist eine Abteilung oder Teilmenge der allgemeinen Informatik und Mathematik, die sich auf abstraktere oder mathematische Aspekte der Computerwissenschaft konzentriert.

Diese Abteilungen und Teilmengen schließen Analyse von Algorithmen und formelle Semantik von Programmiersprachen ein. Technisch gibt es Hunderte von Abteilungen und Teilmengen außer diesen zwei. Jeder der vielfachen Teile hat ihre eigenen individuellen persönlichen Führer (der Beliebtheit), und es gibt viele Vereinigungen und soziale Berufsgruppen und Veröffentlichungen der Unterscheidung.

Spielraum

Es ist nicht leicht, die Theorie-Gebiete genau und Special Interest Group des ACM auf Algorithmen zu umschreiben, und Berechnungstheorie (SIGACT) beschreibt seine Mission als die Promotion der theoretischen Informatik und Zeichen:

Zu dieser Liste fügt die Zeitschrift des ACM Transaktionen auf der Berechnungstheorie Codiertheorie, rechenbetonte Lerntheorie und theoretische Informatik-Aspekte von Gebieten wie Datenbanken, Informationsgewinnung, Wirtschaftsmodelle und Netze hinzu. Trotz dieses breiten Spielraums selbstidentifizieren sich die "Theorie-Leute" in der Informatik als verschieden von den "angewandten Leuten." Einige charakterisieren sich als das Tun der" (grundsätzlicheren) 'Wissenschaft (En)', die dem Feld der Computerwissenschaft unterliegt." Andere "Theorie-angewandte Leute" schlagen vor, dass es unmöglich ist, Theorie und Anwendung zu trennen. Das bedeutet, die so genannten "Theorie-Leute" verwenden regelmäßig experimentelle Wissenschaft (En), die darin getan ist, weniger - theoretische Gebiete wie Softwaresystemforschung. Das bedeutet auch, es gibt mehr Zusammenarbeit als gegenseitig exklusive Konkurrenz zwischen Theorie und Anwendung.

Geschichte

Während formelle Algorithmen seit Millennien bestanden haben (der Algorithmus von Euklid für zu beschließen, dass der größte allgemeine Teiler von zwei Zahlen noch in der Berechnung verwendet wird), erst als 1936, dass Alan Turing, Kirche von Alonzo und Stephen Kleene die Definition eines Algorithmus in Bezug auf die Berechnung formalisiert haben. Während binäre und logische Systeme der Mathematik vor 1703 bestanden hatten, als Gottfried Leibniz Logik mit binären Werten für den wahren und das falsche formalisiert hat. Während logische Schlussfolgerung und mathematischer Beweis in alten Zeiten bestanden hatten, 1931 hat Kurt Gödel mit seinem Unvollständigkeitslehrsatz bewiesen, dass es grundsätzliche Beschränkungen darauf gab, welche Behauptungen, selbst wenn wahr, bewiesen werden konnten.

Diese Entwicklungen haben zur modernen Studie der Logik und Berechenbarkeit, und tatsächlich des Feldes der theoretischen Informatik als Ganzes geführt. Informationstheorie wurde zum Feld mit 1948 mathematische Theorie der Kommunikation von Claude Shannon hinzugefügt. In demselben Jahrzehnt hat Donald Hebb ein mathematisches Modell des Lernens im Gehirn eingeführt. Mit dem Besteigen biologischer Daten, die diese Hypothese mit etwas Modifizierung unterstützen, wurden die Felder von Nervennetzen und verteilter Verarbeitung der Parallele gegründet.

Mit der Entwicklung der Quant-Mechanik am Anfang des 20. Jahrhunderts ist das Konzept gekommen, dass mathematische Operationen auf einer kompletten Partikel wavefunction durchgeführt werden konnten. Mit anderen Worten konnte man Funktionen auf vielfachen Staaten gleichzeitig schätzen. Das hat zum Konzept eines Quant-Computers in der letzten Hälfte des 20. Jahrhunderts geführt, das sich in den 1990er Jahren entfernt hat, als Peter Shor gezeigt hat, dass solche Methoden an die große Faktor-Anzahl in der polynomischen Zeit gewöhnt sein konnten, die, wenn durchgeführt, die meisten modernen öffentlichen nutzlos unsicheren Schlüsselgeheimschrift-Systeme machen würde.

Moderne theoretische Informatik-Forschung basiert auf diesen grundlegenden Entwicklungen, aber schließt viele andere mathematische und zwischendisziplinarische Probleme ein, die aufgestellt worden sind.

Organisationen

• Europäische Vereinigung für die theoretische Informatik
• SIGACT

Zeitschriften und Rundschreiben

• Information und Berechnung
• Theorie Zu rechnen (öffnen Zugriffszeitschrift)
• Formelle Aspekte, zu schätzen
• Zeitschrift des ACM
• SIAM Zeitschrift bei der Computerwissenschaft (SICOMP)
• SIGACT Nachrichten
• Theoretische Informatik
• Theorie von Computings Systemen
• Internationale Zeitschrift von Fundamenten der Informatik
• Die Chikagoer Zeitschrift der Theoretischen Informatik (öffnen Zugriffszeitschrift)
• Fundamente und Tendenzen in der theoretischen Informatik
• Zeitschrift von Automaten, Languages und Combinatorics
• Acta Informatica
• Fundamenta Informaticae
• ACM Transaktionen auf der Berechnungstheorie
• ACM Transaktionen auf Algorithmen
• Informationsverarbeitungsbriefe

Konferenzen

• Jährliches ACM Symposium auf der Theorie, (STOC) zu rechnen
• Jährliches IEEE Symposium auf Fundamenten der Informatik (FOCS)
• ACM-SIAM Symposium Auf Getrennten Algorithmen (SODA)
• Jährliche ACM Symposium on Computational Geometry (SoCG)
• Internationales Kolloquium auf Automaten, Sprachen und (ICALP) programmierend
• Symposium auf theoretischen Aspekten der Informatik (STACS)
• Europäisches Symposium auf Algorithmen (ESA)
• IEEE Symposium auf der Logik In der Informatik (LICS)
• Internationales Symposium auf Algorithmen und Berechnung (ISAAC)
• Werkstatt auf Annäherungsalgorithmen für kombinatorische Optimierungsprobleme (UNGEFÄHR)
• Werkstatt auf Randomization und Computation (ZUFÄLLIGER)
• Computational Complexity Conference (CCC)
• ACM Symposium auf dem Parallelismus in Algorithmen und den Architekturen (SPAA)
• ACM Symposium auf Grundsätzen der Verteilten Computerwissenschaft (PODC)

Siehe auch

• Formelle Wissenschaft
• Ungelöste Probleme in der Informatik
• Liste von wichtigen Veröffentlichungen in der theoretischen Informatik

Referenzen

Weiterführende Literatur

• Martin Davis, Ron Sigal, Elaine J. Weyuker, Berechenbarkeit, Kompliziertheit und Sprachen: Grundlagen der theoretischen Informatik, 2. Hrsg., Akademischen Presse, 1994, internationale Standardbuchnummer 0122063821. Deckel-Theorie der Berechnung, sondern auch Programm-Semantik und Quantifizierungstheorie. Gerichtet auf Studenten im Aufbaustudium.

Außenverbindungen

• Das SIGACT Verzeichnis der zusätzlichen Theorie verbindet
• Theorie-Sachen Wiki Befürwortung von Theoretical Computer Science (TCS) Wiki
• [news://comp.theory Usenet comp.theory]
• Liste von akademischen Konferenzen im Gebiet der theoretischen Informatik an confsearch
• Theoretische Informatik - StackExchange, eine Frage- und Antwort-Seite für Forscher in der theoretischen Informatik
• Informatik belebter
• http://theory.csail.mit.edu/ Institut von Massachusetts für die Technologie