Theoretische Informatik
Theoretical Informatik (TCS) ist eine Untergruppe von General Informatik und Mathematik Das konzentriert sich auf mathematische Aspekte von Informatik so wie die Theorie der Berechnung, Lambda -Kalkül, und Typentheorie.
Es ist schwierig, die theoretischen Bereiche genau zu umschreiben. Das ACM's Spezialinteressensgruppe für Algorithmen und Berechnungstheorie (Sigact) enthält die folgende Beschreibung:[1]
TCS deckt eine Vielzahl von Themen ab, einschließlich Algorithmen, Datenstrukturen, Rechenkomplexität, parallel und verteilt Berechnung, Probabilistische Berechnung, Quantenberechnung, Automatenheorie, Informationstheorie, Kryptographie, Programmsemantik und Überprüfung, Algorithmische Spieltheorie,maschinelles Lernen, Computerbiologie, Computerökonomie, Computergeometrie, und Rechenzahltheorie und Algebra. Die Arbeit in diesem Bereich unterscheidet sich oft durch ihre Betonung der mathematischen Technik und Strenge.
Geschichte
Während logischer Inferenz und mathematischer Beweise bereits 1931 existierten, Kurt Gödel bewiesen mit seinem Unvollständigkeitstheorem dass es grundlegende Einschränkungen dafür gibt, welche Aussagen nachgewiesen oder widerlegt werden können.
Informationstheorie wurde mit einer mathematischen Kommunikationstheorie von 1948 auf das Feld hinzugefügt Claude Shannon. Im selben Jahrzehnt, Donald Hebb stellte ein mathematisches Modell von vor Lernen im Gehirn. Mit der Montage biologischer Daten, die diese Hypothese mit einiger Modifikation unterstützen, die Felder von Neuronale Netze und Parallele verteilte Verarbeitung wurden Eingeführt. 1971,, Stephen Cook und Arbeiten unabhängig, Leonid Levin, bewiesen, dass es praktisch relevante Probleme gibt, die es sind NP-Complete - Ein Wahrzeichen führt dazu Computerkomplexitätstheorie.
Mit der Entwicklung von Quantenmechanik Zu Beginn des 20. Jahrhunderts kam das Konzept, dass mathematische Operationen bei einer gesamten Partikelwellenfunktion durchgeführt werden konnten. Mit anderen Worten, man könnte Funktionen in mehreren Zuständen gleichzeitig berechnen. Dies führte zum Konzept von a Quantencomputer in der zweiten Hälfte des 20. Jahrhunderts, das in den neunziger Jahren abfuhr, als Peter Shor zeigten, dass solche Methoden verwendet werden konnten, um große Zahlen zu berücksichtigen Polynomzeit, was, wenn es umgesetzt würde, einige modern machen würde öffentliche Schlüsselkryptographie Algorithmen mögen RSA_ (Cryptosystem) unsicher.
Die moderne theoretische Informatikforschung basiert auf diesen grundlegenden Entwicklungen, umfasst jedoch viele andere mathematische und interdisziplinäre Probleme, die wie unten gezeigt wurden:
Themen
Algorithmen
Ein Algorithmus ist ein Schritt-für-Schritt-Verfahren für Berechnungen. Algorithmen werden für verwendet Berechnung, Datenverarbeitung, und automatisierte Argumentation.
Ein Algorithmus ist ein Effektive Methode ausgedrückt als endliche Liste[2] von gut definierten Anweisungen[3] zur Berechnung a Funktion.[4] Ausgehend von einem Anfangszustand und anfänglichen Eingaben (vielleicht leer),[5] Die Anweisungen beschreiben a Berechnung das, wann hingerichtet, fährt durch eine endliche[6] Anzahl der gut definierten aufeinanderfolgenden Zustände, die schließlich "Output" erzeugen[7] und in einem endgültigen Endzustand enden. Der Übergang von einem Zustand zum nächsten ist nicht unbedingt deterministisch; Einige Algorithmen, bekannt als Randomisierte Algorithmen, integrieren Sie zufällige Eingabe.[8]
Automatenheorie
Automatenheorie ist das Studium von Abstrakte Maschinen und Automatensowie die Rechenprobleme, die mit ihnen gelöst werden können. Es ist eine Theorie in der theoretischen Informatik, unter Diskrete Mathematik (ein Teil von Mathematik und auch von Informatik). Automaten Kommt aus dem griechischen Wort αὐτόματα, was "selbstwirksam" bedeutet.
Die Automatenheorie ist die Untersuchung selbstoperativer virtueller Maschinen, um das logische Verständnis des Eingabe- und Ausgangsprozesses ohne oder mit Zwischenstufe (n) von (en) von zu unterstützen Berechnung (oder irgendein Funktion/Prozess).
Codierungstheorie
Codierungstheorie ist die Untersuchung der Eigenschaften von Codes und ihrer Fitness für eine bestimmte Anwendung. Codes werden für verwendet Datenkompression, Kryptographie, fehler Korrektur und in jüngerer Zeit auch für Netzwerkcodierung. Codes werden von verschiedenen wissenschaftlichen Disziplinen untersucht - z. B. als Informationstheorie, Elektrotechnik, Mathematik, und Informatik- zum Zweck der Gestaltung effizienter und zuverlässig Datenübertragung Methoden. Dies beinhaltet typischerweise die Entfernung der Redundanz und die Korrektur (oder den Nachweis) von Fehlern in den übertragenen Daten.
Computerbiologie
Computerbiologie beinhaltet die Entwicklung und Anwendung von datenanalytischen und theoretischen Methoden, mathematischen Modellierungs- und Rechensimulationstechniken zur Untersuchung biologischer, verhaltensbezogener und sozialer Systeme.[9] Das Feld ist weitgehend definiert und umfasst Fundamente in der Informatik. angewandte Mathematik, Animation, Statistiken, Biochemie, Chemie, Biophysik, Molekularbiologie, Genetik, Genomik, Ökologie, Evolution, Anatomie, Neurowissenschaften, und Visualisierung.[10]
Computerbiologie unterscheidet sich von Biologische Berechnung, was ein Unterfeld der Informatik ist und Technische Informatik Verwendung Biotechnik und Biologie bauen Computers, ist aber ähnlich wie Bioinformatik, eine interdisziplinäre Wissenschaft, die Computer verwendet, um biologische Daten zu speichern und zu verarbeiten.
Computerkomplexitätstheorie
Computerkomplexitätstheorie ist ein Zweig der Theorie der Berechnung Das konzentriert sich auf die Klassifizierung Rechenprobleme nach ihrer inhärenten Schwierigkeit und in Bezug auf diese in Beziehung Klassen zueinander. Ein rechtzeitiges Problem wird als eine Aufgabe verstanden, die grundsätzlich für einen Computer gelöst werden kann, was der Angabe entspricht, dass das Problem durch mechanische Anwendung mathematischer Schritte wie ein gelöst werden kann Algorithmus.
Ein Problem wird als von Natur aus schwierig angesehen, wenn seine Lösung erhebliche Ressourcen erfordert, was auch immer die Algorithmus Gebraucht. Die Theorie formalisiert diese Intuition, indem sie mathematisch vorstellt Berechnungsmodelle Diese Probleme zu untersuchen und die Anzahl der Ressourcen zu quantifizieren, die zur Lösung dieser Zeit erforderlich sind, z. B. Zeit und Speicher. Sonstiges Komplexität Es werden auch Maßnahmen verwendet, wie z. B. die Kommunikationsmenge (verwendet in Kommunikationskomplexität), die Anzahl der Anzahl von Tore in einer Schaltung (verwendet in Komplexität der Schaltung) und die Anzahl der Prozessoren (verwendet in Parallele Computing). Eine der Rollen der Rechenkomplexitätstheorie besteht darin, die praktischen Grenzen für was zu bestimmen, was Computers kann und kann nicht tun.
Computergeometrie
Computergeometrie ist ein Zweig der Informatik, der sich der Untersuchung von Algorithmen widmet, die in Bezug auf angegeben werden können Geometrie. Einige rein geometrische Probleme entstehen aus der Untersuchung von rechnerischen geometrischen Algorithmen, und solche Probleme werden auch als Teil der Computergeometrie angesehen.
Der Hauptantrieb für die Entwicklung der Computergeometrie als Disziplin war der Fortschritt in Computergrafik und computergestütztes Design und Fertigung (CAD/NOCKEN), aber viele Probleme in der Computergeometrie sind klassischer Natur und können von kommen Mathematische Visualisierung.
Andere wichtige Anwendungen der Computergeometrie umfassen Robotik (Problemplanung und Sichtbarkeitsprobleme), Geografisches Informationssystem (GIS) (geometrischer Standort und Suche, Routenplanung), Integrierter Schaltkreis Design (IC -Geometrie -Design und -überprüfung), computergestütztes Ingenieurwesen (CAE) (Maschengenerierung), Computer Vision (3D -Rekonstruktion).
Computerlerntheorie
Theoretische Ergebnisse in maschinellem Lernen richten sich hauptsächlich mit einer Art induktivem Lernen, das als überwachtes Lernen bezeichnet wird. Beim überwachten Lernen erhält ein Algorithmus Muster, die auf nützliche Weise gekennzeichnet sind. Zum Beispiel könnten die Proben Beschreibungen von Pilzen sein, und die Etiketten könnten sein, ob die Pilze essbar sind oder nicht. Der Algorithmus nimmt diese zuvor beschrifteten Proben auf und induziert sie, um einen Klassifikator zu induzieren. Dieser Klassifizierer ist eine Funktion, die Proben, einschließlich der Proben, die vom Algorithmus noch nie gesehen wurden, Beschriftungen zugewiesen. Das Ziel des überwachten Lernalgorithmus ist es, ein gewisses Maß an Leistung zu optimieren, z.
Rechenzahltheorie
Rechenzahltheorie, auch bekannt als Algorithmische Zahlentheorie, ist das Studium von Algorithmen zum Ausführen Zahlen -theoretisch Berechnungen. Das bekannteste Problem auf diesem Gebiet ist Ganzzahlfaktorisierung.
Kryptographie
Kryptographie ist die Praxis und Studium von Techniken für Sichere Kommunikation in Gegenwart Dritter (genannt Gegner).[11] Allgemeiner geht es darum, zu konstruieren und zu analysieren Protokolle das überwindet den Einfluss von Gegnern[12] und das bezieht sich auf verschiedene Aspekte in Informationssicherheit wie Daten Vertraulichkeit, Datenintegrität, Authentifizierung, und Nicht-Repudiation.[13] Die moderne Kryptographie schneidet die Disziplinen von Mathematik, Informatik, und Elektrotechnik. Anwendungen der Kryptographie umfassen ATM -Karten, Computerkennwörter, und elektronischer Handel.
Die moderne Kryptographie basiert stark auf mathematischer Theorie und Informatikpraxis. Kryptografische Algorithmen sind darum entwickelt Berechnungshärtenannahmen, solche Algorithmen, in der Praxis durch jeden Gegner schwer zu brechen. Es ist theoretisch möglich, ein solches System zu brechen, aber es ist nicht durch bekannte praktische Mittel zu tun. Diese Schemata werden daher rechnerisch sicher bezeichnet. theoretische Fortschritte, z. B. Verbesserungen in Ganzzahlfaktorisierung Algorithmen und eine schnellere Computertechnologie erfordern, dass diese Lösungen kontinuierlich angepasst werden. Es gibt Informationstheoretisch sicher Schemata, die nachdenklich nicht gebrochen werden können, selbst bei unbegrenzter Rechenleistung - ein Beispiel ist das einmalige Pad- Aber diese Systeme sind schwieriger zu implementieren als die am besten theoretisch brechen, aber rechenversichernden Mechanismen.
Datenstrukturen
A Datenstruktur ist eine besondere Art zu organisieren Daten in einem Computer, damit es verwendet werden kann effizient.[14][15]
Verschiedene Arten von Datenstrukturen sind für verschiedene Arten von Anwendungen geeignet, einige sind auf bestimmte Aufgaben hochspezialisiert. Zum Beispiel verwenden Datenbanken B-Baum Indizes für kleine Prozentsätze des Datenabrufs und Compiler und Datenbanken verwenden dynamisch Hash -Tische als Aussichtstische.
Datenstrukturen bieten ein Mittel, um große Datenmengen effizient für Verwendungen wie groß zu verwalten Datenbanken und Internet -Indexierungsdienste. Normalerweise sind effiziente Datenstrukturen für effizientes Entwerfen von entscheidender Bedeutung Algorithmen. Einige formale Designmethoden und Programmiersprachen Betonen Sie eher Datenstrukturen als Algorithmen als wichtiger Organisationsfaktor für das Softwaredesign. Das Speichern und Abrufen kann an Daten durchgeführt werden, die in beiden gespeichert sind Haupterinnerung und in Sekundärspeicher.
Verteilte Berechnung
Verteiltes Computer Studien verteilte Systeme. Ein verteiltes System ist ein Softwaresystem, in dem sich Komponenten befinden vernetzte Computer kommunizieren und koordinieren ihre Handlungen durch Nachrichten übergeben.[16] Die Komponenten interagieren miteinander, um ein gemeinsames Ziel zu erreichen. Drei signifikante Merkmale verteilter Systeme sind: Parallelität von Komponenten, Mangel an globaler Uhr und unabhängiges Versagen von Komponenten.[16] Beispiele für verteilte Systeme variieren von SOA-basierte Systeme zu Massiv Multiplayer Online -Spiele zu Peer-to-Peer-Anwendungenund Blockchain -Netzwerke wie Bitcoin.
A Computer Programm Das in einem verteilten System läuft a verteiltes Programmund verteilte Programmierung ist der Prozess des Schreibens solcher Programme.[17] Es gibt viele Alternativen für den Mechanismus zur Nachrichtenübergabe, einschließlich RPC-ähnlich Anschlüsse und Nachrichtenwarteschlangen. Ein wichtiges Ziel und eine wichtige Herausforderung verteilter Systeme ist Standorttransparenz.
Informationsbasierte Komplexität
Informationsbasierte Komplexität (IBC) Studien optimale Algorithmen und rechnerische Komplexität für kontinuierliche Probleme. IBC hat kontinuierliche Probleme als Pfadintegration, partielle Differentialgleichungen, Systeme gewöhnlicher Differentialgleichungen, nichtlineare Gleichungen, Integralgleichungen, feste Punkte und sehr hohe dimensionale Integration untersucht.
Formale Methoden
Formale Methoden sind eine bestimmte Art von Mathematik basierte Techniken für die Spezifikation, Entwicklung und Überprüfung von Software und Hardware- Systeme.[18] Die Verwendung formaler Methoden für Software und Hardwaredesign wird durch die Erwartung motiviert, dass die Durchführung einer geeigneten mathematischen Analyse wie in anderen technischen Disziplinen zur Zuverlässigkeit und Robustheit eines Designs beitragen kann.[19]
Formale Methoden werden am besten als Anwendung einer ziemlich breiten Vielfalt theoretischer Informatik -Grundlagen beschrieben, insbesondere als Anwendung Logik Kalkül, formelle Sprachen, Automatenheorie, und Programmsemantik, aber auch Typsysteme und Algebraische Datentypen zu Problemen in der Software- und Hardwarespezifikation und -überprüfung.[20]
Informationstheorie
Informationstheorie ist ein Zweig von angewandte Mathematik, Elektrotechnik, und Informatik mit dem Quantifizierung von Information. Die Informationstheorie wurde von entwickelt von Claude E. Shannon grundlegende Grenzen finden Signalverarbeitung Operationen wie Druckdaten und zuverlässig Speicherung und kommunizieren Daten. Seit seiner Gründung hat es sich erweitert, um Anwendungen in vielen anderen Bereichen zu finden, einschließlich statistische Inferenz, Verarbeitung natürlicher Sprache, Kryptographie, Neurobiologie,[21] die Evolution[22] und Funktion[23] von molekularen Codes,, Modellauswahl in Statistiken,[24] Wärmephysik,[25] Quanten-Computing, Linguistik, Plagiaterkennung,[26] Mustererkennung, Anomalieerkennung und andere Formen von Datenanalyse.[27]
Anwendungen grundlegender Themen der Informationstheorie umfassen Verlustlose Datenkomprimierung (z.B. Zip -Dateien), Verlustige Datenkomprimierung (z.B. MP3s und Jpegs), und Kanalcodierung (z. B. für Digitale Abonnentenlinie (DSL)). Das Feld befindet sich an der Kreuzung von Mathematik, Statistiken, Informatik, Physik, Neurobiologie, und Elektrotechnik. Seine Auswirkungen waren entscheidend für den Erfolg der Voyager Missionen zum Deep Space, die Erfindung der Kompaktscheibe, die Machbarkeit von Mobiltelefonen, die Entwicklung der Internet, das Studium der Linguistik und der menschlichen Wahrnehmung das Verständnis von Schwarze Löcherund zahlreiche andere Felder. Wichtige Unterfelder der Informationstheorie sind Quellcodierung, Kanalcodierung, Algorithmische Komplexitätstheorie, Algorithmische Informationstheorie, Informationstheoretische Sicherheitund Informationsmaße.
Maschinelles Lernen
Maschinelles Lernen ist ein wissenschaftliche Disziplin Das befasst sich mit dem Bau und dem Studium von Algorithmen das kann lernen aus Daten.[28] Solche Algorithmen werden mit dem Bau a betrieben Modell basierend auf Eingaben[29]: 2 und diese verwenden, um Vorhersagen oder Entscheidungen zu treffen, anstatt nur explizit programmierte Anweisungen zu befolgen.
Maschinelles Lernen kann als Unterfeld der Informatik betrachtet werden und Statistiken. Es hat starke Beziehungen zu künstliche Intelligenz und Optimierung, die Methoden, Theorie und Anwendungsdomänen an das Feld liefern. Maschinelles Lernen wird in einer Reihe von Rechenaufgaben verwendet, bei denen explizite, regelbasierte Entwerfen und Programme explizites, regelbasierte Aufgaben verwendet werden Algorithmen ist unmöglich. Beispielanwendungen umfassen Spamfilterung, optische Zeichenerkennung (OCR),[30] Suchmaschinen und Computer Vision. Maschinelles Lernen wird manchmal mit miteinander verbunden Data Mining,[31] Dies konzentriert sich zwar mehr auf explorative Datenanalysen.[32] Maschinelles Lernen und Mustererkennung "Kann als zwei Facetten desselben Feldes angesehen werden."[29]: Vii
Parallele Berechnung
Parallele Computing ist eine Form von Berechnung in denen viele Berechnungen gleichzeitig durchgeführt werden,[33] Betrieb nach dem Prinzip, dass große Probleme oft in kleinere unterteilt werden können, die dann gelöst werden "parallel zu". Es gibt verschiedene Formen des parallelen Computers: Bit-Level, Anleitung, Daten, und Aufgabe Parallelität. Parallelität ist seit vielen Jahren, hauptsächlich in High Performance Computing, aber das Interesse daran hat in letzter Zeit aufgrund der vorbeugungen physischen Einschränkungen gewachsen Frequenzskalierung.[34] Da der Stromverbrauch (und folglich Wärmeerzeugung) durch Computer in den letzten Jahren zu einem Problem geworden ist,[35] Parallele Computing ist das dominierende Paradigma in geworden Rechnerarchitekturhauptsächlich in Form von Multi-Core-Prozessoren.[36]
Parallele Computerprogramme sind schwieriger zu schreiben als sequentielle,[37] Weil die Parallelität mehrere neue Potenzialklassen einführt Software -Fehler, von welchem Rennbedingungen sind die häufigsten. Kommunikation und Synchronisation Zwischen den verschiedenen Unteraufnehmern befinden sich in der Regel einige der größten Hindernisse für eine gute parallele Programmleistung.
Das maximal mögliche beschleunigen eines einzelnen Programms als Ergebnis einer Parallelisierung ist als bekannt als Amdahls Gesetz.
Programmsemantik
Im Programmiersprache Theorie, Semantik befasst sich das Feld mit der strengen mathematischen Untersuchung der Bedeutung von Programmiersprachen. Dies geschieht, indem es die Bedeutung von bewertet syntaktisch legal Saiten definiert durch eine bestimmte Programmiersprache und zeigt die damit verbundene Berechnung. In einem solchen Fall, dass die Bewertung syntaktisch illegaler Zeichenfolgen wäre, wäre das Ergebnis eine Nichtüberwachung. Semantik beschreibt die Prozesse, die einem Computer folgt, wenn ein Programm in dieser spezifischen Sprache ausgeführt wird. Dies kann gezeigt werden, indem die Beziehung zwischen Eingabe und Ausgabe eines Programms beschrieben wird, oder einer Erklärung, wie das Programm auf einem bestimmten Ausführen ausgeführt wird Plattform, damit ein Schaffung a Berechnungsmodell.
Quantenberechnung
A Quantencomputer ist ein Berechnung System, das direkt verwendet wird von quantum-mechanical Phänomene, wie zum Beispiel Überlagerung und Verstrickung, aufführen Operationen an Daten.[38] Quantencomputer unterscheiden sich von digitalen Computern basierend auf Transistoren. Während digitale Computer benötigt werden, um Daten in binäre Ziffern zu codieren ((Bits), von denen jeder immer in einem von zwei bestimmten Zuständen ist (0 oder 1), Quantenberechnung verwendet Qubits (Quantenbits), die in sein können Überlagerungen von Staaten. Ein theoretisches Modell ist das Quanten -Turing -Maschineauch als universeller Quantencomputer bekannt. Quantencomputer teilen theoretische Ähnlichkeiten mit nicht deterministisch und Probabilistische Computer; Ein Beispiel ist die Fähigkeit, gleichzeitig in mehr als einem Zustand zu sein. Das Feld des Quantencomputers wurde zuerst von eingeführt von Yuri Manin 1980[39] und Richard Feynman 1982.[40][41] Ein Quantencomputer mit Spins als Quantenbits wurde auch zur Verwendung als Quantum formuliert Freizeit 1968.[42]
Ab 2014[aktualisieren]Das Quantum Computing steckt noch in den Kinderschuhen, es wurden jedoch Experimente durchgeführt, bei denen Quantenberechnungspunkte auf einer sehr geringen Anzahl von Qubits ausgeführt wurden.[43] Sowohl die praktische als auch die theoretische Forschung werden fortgesetzt, und viele nationale Regierungen und militärische Finanzierungsagenturen unterstützen die Quantum Computing -Forschung, um Quantenentwicklung zu entwickeln Computers sowohl für zivile als auch für nationale Sicherheitszwecke wie z. Kryptanalyse.[44]
Symbolische Berechnung
Computeralgebra, auch als symbolische Berechnung oder algebraische Berechnung bezeichnet, ist ein wissenschaftlicher Bereich, der sich auf die Studie und Entwicklung von bezieht Algorithmen und Software zum Manipulieren Mathematische Ausdrücke und andere mathematische Objekte. Die Computeralgebra sollte jedoch ein Unterfeld von sein Wissenschaftliches rechnen, sie werden allgemein als unterschiedliche Felder angesehen, da wissenschaftliche Computing normalerweise auf Numerische Berechnung mit ungefähren Gleitkommazahlen, während die symbolische Berechnung betont genau Berechnung mit Ausdrücken, die enthalten Variablen die keinen bestimmten Wert haben und daher als Symbole manipuliert werden (daher der Name von Symbolische Berechnung).
Software Anwendungen, die symbolische Berechnungen durchführen Computeralgebra -Systememit dem Begriff System Anspielung auf die Komplexität der Hauptanwendungen, die zumindest eine Methode zur Darstellung mathematischer Daten in einem Computer enthalten, einer Benutzerprogrammiersprache (normalerweise von der für die Implementierung verwendeten Sprache), einem speziellen Speichermanager, a Benutzeroberfläche Für die Eingabe/Ausgabe von mathematischen Ausdrücken, ein großer Satz von Routinen übliche Operationen auszuführen, wie die Vereinfachung von Ausdrücken, Unterscheidung Verwendung Kettenregel, Polynomfaktorisierung, Unbestimmte Integration, etc.
Sehr große Integration
Sehr große Integration (VLSI) ist der Prozess des Erstellens eines Integrierter Schaltkreis (IC) durch Kombination von Tausenden von Transistoren in einen einzelnen Chip. VLSI begann in den 1970er Jahren, als es komplex ist Halbleiter und Kommunikation Es wurden Technologien entwickelt. Das Mikroprozessor ist ein VLSI -Gerät. Vor der Einführung der VLSI -Technologie hatten die meisten ICs eine begrenzte Reihe von Funktionen, die sie ausführen konnten. Ein elektronische Schaltung könnte aus a bestehen Zentralprozessor, Rom, RAM und andere Logik Kleber. Mit VLSI können IC -Hersteller alle diese Schaltkreise in einen Chip hinzufügen.
Organisationen
- Europäische Vereinigung für theoretische Informatik
- Sigakt
- Simons Institute für die Theorie des Computers
Zeitschriften und Newsletter
- “Diskrete Mathematik und theoretische Informatik”
- Informationen und Berechnung
- Theorie des Computers (uneingeschränkter Zugang Tagebuch)
- Formale Aspekte des Computers
- Journal of the ACM
- Siam Journal über Computing (Sicomp)
- Sigact News
- Theoretische Informatik
- Theorie der Computersysteme
- Internationales Journal of Foundations of Computer Science
- Chicago Journal of Theoretical Informatik (uneingeschränkter Zugang Tagebuch)
- Grundlagen und Trends in der theoretischen Informatik
- Journal of Automata, Sprachen und Kombinatorik
- Acta Informatica
- Fundamenta Informaticae
- ACM -Transaktionen zur Berechnungstheorie
- Rechenkomplexität
- Journal of Complexity
- ACM -Transaktionen auf Algorithmen
- Informationsverarbeitungsbriefe
- Öffnen Sie die Informatik (uneingeschränkter Zugang Tagebuch)
Konferenzen
- Jährliche ACM Symposium über die Computertheorie (STOC)[45]
- Jährliches IEEE Symposium über Fundamente der Informatik (Fokus)[45]
- Innovationen in der theoretischen Informatik (ITCS)
- Mathematische Grundlagen der Informatik (MFCS)[46]
- Internationales Informatik -Symposium in Russland (CSR)[47]
- ACM -SIAM Symposium an diskreten Algorithmen (SPRUDEL)[45]
- IEEE Symposium über Logik in der Informatik (LICs)[45]
- Konferenz für Computerkomplexität (CCC)[48]
- Internationales Kolloquium über Automaten, Sprachen und Programmierung (ICICP)[48]
- Jährlich Symposium on Computational Geometry (SOCG)[48]
- ACM Symposium über Prinzipien des verteilten Computers (PODC)[45]
- ACM Symposium über Parallelität in Algorithmen und Architekturen (Spaa)[48]
- Jahreskonferenz über Lerntheorie (Colt)[48]
- Symposium über theoretische Aspekte der Informatik (STACS)[48]
- European Symposium on Algorithms (ESA)[48]
- Workshop zu Approximationsalgorithmen für kombinatorische Optimierungsprobleme (ca.)[48]
- Workshop über Randomisierung und Berechnung (zufällig)[48]
- Internationales Symposium für Algorithmen und Berechnung (Isaac)[48]
- Internationales Symposium für Grundlagen der Berechnungstheorie (FCT)[49]
- Internationaler Workshop zu graphentheoretischen Konzepten in Informatik (WG)
Siehe auch
- Formale Wissenschaft
- Ungelöste Probleme in der Informatik
- Liste wichtiger Veröffentlichungen in der theoretischen Informatik
- Sonne -Ni -Gesetz
Anmerkungen
- ^ "Sigakt". Abgerufen 2017-01-19.
- ^ "Jeder klassische mathematische Algorithmus kann beispielsweise in einer endlichen Anzahl englischer Wörter beschrieben werden". Rogers, Hartley Jr. (1967). Theorie der rekursiven Funktionen und effektiver Berechnbarkeit. McGraw-Hill. Seite 2.
- ^ Gut definiert in Bezug auf den Agenten, der den Algorithmus ausführt: "Es gibt einen Computermittel, der normalerweise menschlich ist und auf die Anweisungen reagieren und die Berechnungen ausführen kann" ((Rogers 1967, p. 2).
- ^ "Ein Algorithmus ist ein Verfahren zum Berechnen a Funktion (In Bezug auf einige ausgewählte Notation für Ganzzahlen) ... diese Einschränkung (auf numerische Funktionen) führt zu keinem Verlust der Allgemeinheit "((Rogers 1967, p. 1).
- ^ "Ein Algorithmus hat Null oder mehr Eingaben, d. H., Mengen die zunächst vor Beginn des Algorithmus gegeben werden "(Knuth 1973: 5).
- ^ "Ein Verfahren, das alle Merkmale eines Algorithmus aufweist, außer dass es möglicherweise keine Finanzheit fehlt, kann als" Rechenmethode "bezeichnet werden" (Knuth 1973: 5).
- ^ "Ein Algorithmus hat einen oder mehrere Ausgänge, d. H. Mengen, die eine bestimmte Beziehung zu den Eingängen haben" (Knuth 1973: 5).
- ^ Ob ein Prozess mit zufälligen inneren Prozessen (ohne Eingabe der Eingabe) ist, ist ein Algorithmus. Rogers meint: "Eine Berechnung wird diskret schrittweise durchgeführt, ohne kontinuierliche Methoden oder analoge Geräte zu verwenden.Rogers 1967, p. 2).
- ^ "NIH Arbeitsdefinition von Bioinformatik und Computerbiologie" (PDF). Initiative für biomedizinische Informationswissenschaft und Technologie. 17. Juli 2000. archiviert von das Original (PDF) am 5. September 2012. Abgerufen 18. August 2012.
- ^ "Über die CCMB". Zentrum für Computermolekularbiologie. Abgerufen 18. August 2012.
- ^ Rivest, Ronald L. (1990). "Kryptologie". In J. van Leeuwen (Hrsg.). Handbuch der theoretischen Informatik. Vol. 1. Elsevier.
- ^ Bellare, Mihir; Rogaway, Phillip (21. September 2005). "Einführung". Einführung in die moderne Kryptographie. p. 10.
- ^ Menezes, A. J.; Van Oorschot, P. C.; Vanstone, S. A. (1997). Handbuch der angewandten Kryptographie. ISBN 978-0-8493-8523-0.
- ^ Paul E. Black (Hrsg.), Eintrag für Datenstruktur in Wörterbuch von Algorithmen und Datenstrukturen. UNS. Nationales Institut für Standards und Technologie. 15. Dezember 2004. Online Version Zugriff am 21. Mai 2009.
- ^ Eintrag Datenstruktur in dem Encyclopædia Britannica (2009) Online -Eintrag Zugriff am 21. Mai 2009.
- ^ a b Coulouris, George; Jean Dollimore; Tim Kindberg; Gordon Blair (2011). Verteilte Systeme: Konzepte und Design (5. Aufl.). Boston: Addison-Wesley. ISBN 978-0-132-14301-1.
- ^ Andrews (2000) . Dolev (2000) . Ghosh (2007) , p. 10.
- ^ R. W. Butler (2001-08-06). "Was sind formale Methoden?". Abgerufen 2006-11-16.
- ^ C. Michael Holloway. "Warum Ingenieure formelle Methoden berücksichtigen sollten" (PDF). 16. Konferenz für digitale Avioniksysteme (27. bis 30. Oktober 1997). Archiviert von das Original (PDF) am 16. November 2006. Abgerufen 2006-11-16.
{{}}
: Journal zitieren erfordert|journal=
(Hilfe) - ^ Monin, S. 3-4
- ^ F. Rieke; D. Kriegsland; R Ruyter van Steveninck; W Bialek (1997). Spikes: Erforschen des neuronalen Code. Die MIT -Presse. ISBN 978-0262681087.
- ^ Huelsenbeck, J. P.; Ronquist, F.; Nielsen, R.; Bollback, J. P. (2001-12-14). "Bayes'sche Inferenz der Phylogenie und ihre Auswirkungen auf die Evolutionsbiologie". Wissenschaft. American Association for the Advancement of Science (AAAS). 294 (5550): 2310–2314. Bibcode:2001Sci ... 294.2310h. doi:10.1126/Science.1065889. ISSN 0036-8075. PMID 11743192. S2CID 2138288.
- ^ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider, Michael Dean (1998) Organisation des ABCR -Gens: Analyse von Promotor- und Splice Junction -Sequenzen, Gen 215: 1, 111-122
- ^ Burnham, K. P. und Anderson D. R. (2002) Modellauswahl und Multimodel-Inferenz: Ein praktischer informationstheoretischer Ansatz, zweite Ausgabe (Springer Science, New York) ISBN978-0-387-95364-9.
- ^ Jaynes, E. T. (1957-05-15). "Informationstheorie und statistische Mechanik". Physische Bewertung. American Physical Society (APS). 106 (4): 620–630. Bibcode:1957PHRV..106..620J. doi:10.1103/PhysRev.106.620. ISSN 0031-899X.
- ^ Charles H. Bennett, Ming Li und bin Ma (2003) Kettenbuchstaben und Evolutionsgeschichten, Wissenschaftlicher Amerikaner 288: 6, 76-81
- ^ David R. Anderson (1. November 2003). "Einige Hintergrundinformationen darüber, warum Menschen in den empirischen Wissenschaften die Informations-theoretischen Methoden besser verstehen möchten" (PDF). Archiviert von das Original (PDF) am 23. Juli 2011. Abgerufen 2010-06-23.
- ^ Ron Kovahi; Foster Provost (1998). "Glossar der Begriffe". Maschinelles Lernen. 30: 271–274. doi:10.1023/a: 1007411609915.
- ^ a b C. M. Bishop (2006). Mustererkennung und maschinelles Lernen. Springer. ISBN 978-0-387-31073-2.
- ^ Wernick, Yang, Brankov, Yourganov und Strother, maschinelles Lernen in der medizinischen Bildgebung, IEEE Signal Processing Magazine, vol. 27, nein. 4, Juli 2010, S. 25-38
- ^ Mannila, Heikki (1996). Data Mining: maschinelles Lernen, Statistiken und Datenbanken. Int'l Conf. Wissenschaftlicher und statistischer Datenbankmanagement. IEEE Computer Society.
- ^ Friedman, Jerome H. (1998). "Data Mining und Statistik: Was ist die Verbindung?" Computerwissenschaft und Statistik. 29 (1): 3–9.
- ^ Gottlieb, Allan; Almasi, George S. (1989). Hoch parallele Computer. Redwood City, Kalifornien: Benjamin/Cummings. ISBN 978-0-8053-0177-9.
- ^ S.V. Adve et al. (November 2008). "Parallel Computing Research bei Illinois: Die UPCRC -Agenda" Archiviert 2008-12-09 bei der Wayback -Maschine (PDF). Parallel@Illinois, Universität von Illinois in Urbana-Champaign. "Die Haupttechniken für diese Leistungsvorteile-erhöhte Taktfrequenz und intelligentere, aber immer komplexere Architekturen-treffen jetzt die sogenannte Power-Wand. Die Computerindustrie hat akzeptiert, dass zukünftige Leistungserhöhungen weitgehend durch die Erhöhung der Anzahl der Prozessoren (oder Kerne" herrühren müssen ) auf einem Würfel, anstatt einen einzelnen Kern schneller zu machen. "
- ^ Asanovic et al. Alte [konventionelle Weisheit]: Macht ist frei, aber Transistoren sind teuer. Neue [konventionelle Weisheit] ist [diese] Macht ist teuer, aber Transistoren sind "frei".
- ^ Asanovic, Krste et al. (18. Dezember 2006). "Die Landschaft der parallelen Computerforschung: Eine Ansicht aus Berkeley" (PDF). Universität von Kalifornien, Berkeley. Technischer Bericht Nr. UCB/EECS-2006-183. "Alt [konventionelle Weisheit]: Erhöhte Taktfrequenz ist die Hauptmethode zur Verbesserung der Prozessorleistung. Neue [konventionelle Weisheit]: Erhöhung der Parallelität ist die Hauptmethode zur Verbesserung der Prozessorleistung ... sogar Vertreter von Intel, ein Unternehmen, das im Allgemeinen mit dem" verbunden ist " Eine höhere Uhrspeed ist eine bessere Position und warnte, dass traditionelle Ansätze zur Maximierung der Leistung durch Maximierung der Taktrate an ihre Grenze gedrückt wurden. "
- ^ Hennessy, John L.; Patterson, David A.; Larus, James R. (1999). Computerorganisation und Design: Die Hardware-/Software -Oberfläche (2. ed., 3. print. Ed.). San Francisco: Kaufmann. ISBN 978-1-55860-428-5.
- ^ "Quantencomputer mit Molekülen"Artikel in Wissenschaftlicher Amerikaner durch Neil Gershenfeld und Isaac L. Chuang
- ^ Manin, Yu. I. (1980). Vychislimoe I Nevychislimoe [Berechnbar und nicht kompetent] (auf Russisch). Sov.radio. S. 13–15. Archiviert von das Original am 10. Mai 2013. Abgerufen 4. März 2013.
- ^ Feynman, R. P. (1982). "Physik mit Computern simulieren". Internationales Journal of Theoretical Physics. 21 (6): 467–488. Bibcode:1982ijtp ... 21..467f. Citeseerx 10.1.1.45.9310. doi:10.1007/bf02650179. S2CID 124545445.
- ^ Deutsch, David (1992-01-06). "Quantenberechnung". Physikwelt. 5 (6): 57–61. doi:10.1088/2058-7058/5/6/38.
- ^ Finkelstein, David (1968). "Raumzeitstruktur in energiegeladenen Wechselwirkungen". In Gudehus, T.; Kaiser, G. (Hrsg.). Grundlegende Wechselwirkungen bei hoher Energie. New York: Gordon & Breach.
- ^ "Neue Qubit -Kontrolle ist gut für die Zukunft des Quantencomputers". Abgerufen 26. Oktober 2014.
- ^ Quanteninformationswissenschaft und Technologie -Roadmap für ein Gefühl, wohin die Forschung führt.
- ^ a b c d e Das 2007 Australische Rangliste von IKT -Konferenzen Archiviert 2009-10-02 bei der Wayback -Maschine: Tier A+.
- ^ MFCS 2017
- ^ CSR 2018
- ^ a b c d e f g h i j Das 2007 Australische Rangliste von IKT -Konferenzen Archiviert 2009-10-02 bei der Wayback -Maschine: Tier A.
- ^ FCT 2011 (Abgerufen 2013-06-03)
Weitere Lektüre
- Martin Davis, Ron Sigal, Elaine J. Weyuker, Berechnbarkeit, Komplexität und Sprachen: Grundlagen der theoretischen Informatik, 2. Aufl., Academic Press, 1994, ISBN0-12-206382-1. Abdeckungen Theorie der Berechnung, aber auch Programmsemantik und Quantifizierungstheorie. Ziel an Doktoranden.
Externe Links
- Sigact -Verzeichnis zusätzlicher Theorieverbindungen
- Theorie ist wichtig wiki Theoretische Informatik (TCS) Interessenvertretung Wiki
- Liste der akademischen Konferenzen im Bereich der theoretischen Informatik bei Bekenntnissearch
- Theoretische Informatik - Stackexchange, eine Frage- und Antwortstelle für Forscher in der theoretischen Informatik
- Informatik animiert
- Theorie der Berechnung @ Massachusetts Institute of Technology