Schneller Zugriff als Browser!
128 Beziehungen: Abstraktion, Alan Turing, Algorithmus, Alonzo Church, Alphabet (Informatik), Amir Pnueli, Aussage (Logik), Aussagenlogik, Automat (Informatik), Automatentheorie, Axiomatische Semantik, Äquivalenzrelation, Backus-Naur-Form, Berechenbarkeit, Berechenbarkeitstheorie, Beweis (Logik), Beweis (Mathematik), Boolesche Algebra, Chomsky-Hierarchie, Church-Turing-These, Claude Shannon, Compiler, Compilerbau, Computerprogramm, Craig-Interpolation, Dana Scott, Datenbankmodell, David Hilbert, Definition, Denotationelle Semantik, Dialogische Logik, Dirk Hoffmann, Diskret, Donald E. Knuth, Eingabe (Computer), Emil Leon Post, Endlicher Automat, Entropie (Informationstheorie), Entscheidbar, Erweiterte Backus-Naur-Form, Formale Grammatik, Formale Semantik, Formale Spezifikation, Formale Sprache, Formales System, Formalisierung, Funktion (Mathematik), Funktionale Programmierung, Gödelscher Unvollständigkeitssatz, Gerhard Gentzen, ..., Grammatik, Graph (Graphentheorie), Halteproblem, Hans Hermes, Heinrich Scholz (Logiker), Imagination, Implementierung, Infimum und Supremum, Informatik, Information, Informationstheorie, Ingo Wegener, Integrierter Schaltkreis, John von Neumann, John W. Backus, Kanal (Informationstheorie), Kanalkapazität, Künstliche Intelligenz, Kellerautomat, Klaus Weihrauch, Kodierungstheorie, Kombinatorische Logik, Komplexitätsklasse, Komplexitätstheorie, Konstrukt, Kontextfreie Sprache, Kontextsensitive Sprache, Kriterium, Kryptologie, Kurt Gödel, Laufzeit (Informatik), Lösung (Mathematik), Leslie Lamport, Linear beschränkte Turingmaschine, Logik, Logische Programmierung, Maschinengestütztes Beweisen, Maschinensemantik, Mathematik, Mathematische Logik, Münster, Modallogik, Model Checking, Modell, Modula-2, Noam Chomsky, Notwendige und hinreichende Bedingung, NP (Komplexitätsklasse), NP-Vollständigkeit, One-Time-Pad, P (Komplexitätsklasse), Parametrisierter Algorithmus, Pascal (Programmiersprache), Peter Naur, Polynomialzeit, Prädikatenlogik, Problem, Programmiersprache, Pumping-Lemma, Reguläre Sprache, Rekursiv aufzählbare Menge, Richard M. Karp, Robin Milner, Satz (Mathematik), Satz von Rice, Speicherkapazität, Stephen A. Cook, Stephen Cole Kleene, Strukturwissenschaft, Syntax, Syntaxdiagramm, Temporale Logik, Terminiertheit, Turing-Vollständigkeit, Turingmaschine, Universität Münster, Uwe Schöning, Westfälische Nachrichten. Erweitern Sie Index (78 mehr) »
Abstraktion
Das Wort Abstraktion (‚abgezogen‘, Partizip Perfekt Passiv von abs-trahere ‚abziehen‘, ‚entfernen‘, ‚trennen‘) bezeichnet meist den induktiven Denkprozess des erforderlichen Weglassens von Einzelheiten und des Überführens auf etwas Allgemeineres oder Einfacheres.
Neu!!: Theoretische Informatik und Abstraktion · Mehr sehen »
Alan Turing
Alan Turing (ca. 1938)Andrew Hodges: ''http://www.turing.org.uk/scrapbook/ww2.html The Alan Turing Internet Scrapbook.'' In: ''turing.org'', (englisch), abgerufen am 19. August 2017. Seine Unterschrift Alan Mathison Turing OBE, FRS (* 23. Juni 1912 in London; † 7. Juni 1954 in Wilmslow, Cheshire) war ein britischer Logiker, Mathematiker, Kryptoanalytiker und Informatiker.
Neu!!: Theoretische Informatik und Alan Turing · Mehr sehen »
Algorithmus
sowjetischen Briefmarke anlässlich seines 1200-jährigen Geburtsjubiläums Ein Algorithmus (benannt nach al-Chwarizmi, von arabisch: Choresmier) ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen.
Neu!!: Theoretische Informatik und Algorithmus · Mehr sehen »
Alonzo Church
Alonzo Church (* 14. Juni 1903 in Washington, D.C.; † 11. August 1995 in Hudson, Ohio) war ein US-amerikanischer Mathematiker, Logiker und Philosoph und einer der Begründer der theoretischen Informatik.
Neu!!: Theoretische Informatik und Alonzo Church · Mehr sehen »
Alphabet (Informatik)
In der Informatik und der mathematischen Logik ist ein Alphabet eine endliche Menge voneinander unterscheidbarer Symbole, die auch Zeichen oder Buchstaben genannt werden.
Neu!!: Theoretische Informatik und Alphabet (Informatik) · Mehr sehen »
Amir Pnueli
Amir Pnueli (* 22. April 1941 in Nahalal, Palästina; † 2. November 2009 in New York City, New York) war ein israelischer Informatiker, der wegweisende Verdienste um die Einführung der temporalen Logik in die Informatik sowie die Verifizierung von Programmen und Systemen geleistet und dafür 1996 mit dem Turing Award ausgezeichnet wurde.
Neu!!: Theoretische Informatik und Amir Pnueli · Mehr sehen »
Aussage (Logik)
Eine Aussage im Sinn der aristotelischen Logik ist ein sprachliches Gebilde, von dem es sinnvoll ist, zu fragen, ob es wahr oder falsch ist (so genanntes Aristotelisches Zweiwertigkeitsprinzip).
Neu!!: Theoretische Informatik und Aussage (Logik) · Mehr sehen »
Aussagenlogik
Die Aussagenlogik ist ein Teilgebiet der Logik, das sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen ein Wahrheitswert zugeordnet wird.
Neu!!: Theoretische Informatik und Aussagenlogik · Mehr sehen »
Automat (Informatik)
Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners.
Neu!!: Theoretische Informatik und Automat (Informatik) · Mehr sehen »
Automatentheorie
Die Automatentheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit dem Studium von Automaten (Modellrechnern) und mit den von diesen Automaten lösbaren Problemen beschäftigt.
Neu!!: Theoretische Informatik und Automatentheorie · Mehr sehen »
Axiomatische Semantik
Die axiomatische Semantik der Informatik beschreibt die Bedeutung von Programmen durch Schlussregeln, die es erlauben, von einer gewünschten Eigenschaft der Eingabe auf Eigenschaften der Ausgabe zu schließen.
Neu!!: Theoretische Informatik und Axiomatische Semantik · Mehr sehen »
Äquivalenzrelation
Unter einer Äquivalenzrelation versteht man in der Mathematik eine zweistellige Relation, die reflexiv, symmetrisch und transitiv ist.
Neu!!: Theoretische Informatik und Äquivalenzrelation · Mehr sehen »
Backus-Naur-Form
Die Backus-Naur-Form oder Backus-Normalform (kurz BNF) ist eine kompakte formale Metasprache zur Darstellung kontextfreier Grammatiken (Typ-2-Grammatiken in der Chomsky-Hierarchie).
Neu!!: Theoretische Informatik und Backus-Naur-Form · Mehr sehen »
Berechenbarkeit
Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie).
Neu!!: Theoretische Informatik und Berechenbarkeit · Mehr sehen »
Berechenbarkeitstheorie
Die Berechenbarkeitstheorie (auch Rekursionstheorie) ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modells einer Maschine) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind.
Neu!!: Theoretische Informatik und Berechenbarkeitstheorie · Mehr sehen »
Beweis (Logik)
Ein Beweis ist eine Reihe von logischen Schlussfolgerungen, die die Wahrheit eines Satzes auf als wahr Angenommenes zurückführen soll.
Neu!!: Theoretische Informatik und Beweis (Logik) · Mehr sehen »
Beweis (Mathematik)
Beispielhafter, schematischer Aufbau eines Beweises Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit bzw.
Neu!!: Theoretische Informatik und Beweis (Mathematik) · Mehr sehen »
Boolesche Algebra
Venn-Diagramme für Konjunktion, Disjunktion und Ergänzung In der Mathematik ist eine boolesche Algebra (oder ein boolescher Verband) eine spezielle algebraische Struktur, die die Eigenschaften der logischen Operatoren UND, ODER, NICHT sowie die Eigenschaften der mengentheoretischen Verknüpfungen Durchschnitt, Vereinigung, Komplement verallgemeinert.
Neu!!: Theoretische Informatik und Boolesche Algebra · Mehr sehen »
Chomsky-Hierarchie
Chomsky-Hierarchie, gelegentlich Chomsky-Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der theoretischen Informatik.
Neu!!: Theoretische Informatik und Chomsky-Hierarchie · Mehr sehen »
Church-Turing-These
Die Church-Turing-These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine.
Neu!!: Theoretische Informatik und Church-Turing-These · Mehr sehen »
Claude Shannon
Claude Shannon (um 1963) Claude Elwood Shannon (* 30. April 1916 in Petoskey, Michigan; † 24. Februar 2001 in Medford, Massachusetts) war ein US-amerikanischer Mathematiker und Elektrotechniker.
Neu!!: Theoretische Informatik und Claude Shannon · Mehr sehen »
Compiler
Ein Compiler (auch Kompilierer; von ‚zusammentragen‘ bzw. ‚aufhäufen‘) ist ein Computerprogramm, das Quellcodes einer bestimmten Programmiersprache in eine Form übersetzt, die von einem Computer (direkter) ausgeführt werden kann.
Neu!!: Theoretische Informatik und Compiler · Mehr sehen »
Compilerbau
Compilerbau, deutsch Übersetzerbau, ist eine Disziplin der Informatik, die sich mit dem Entwurf und der Programmierung von Compilern, die einen Quelltext in einen Zielcode umsetzen, beschäftigt.
Neu!!: Theoretische Informatik und Compilerbau · Mehr sehen »
Computerprogramm
Ein Computerprogramm oder kurz Programm ist eine den Regeln einer bestimmten Programmiersprache genügende Folge von Anweisungen (bestehend aus Deklarationen und Instruktionen), um bestimmte Funktionen bzw.
Neu!!: Theoretische Informatik und Computerprogramm · Mehr sehen »
Craig-Interpolation
Die Craig-Interpolation ist ein Ausdruck der Logik.
Neu!!: Theoretische Informatik und Craig-Interpolation · Mehr sehen »
Dana Scott
Dana S. Scott Dana Stewart Scott (* 11. Oktober 1932 in Berkeley, Kalifornien) ist ein US-amerikanischer Mathematiker, Logiker, Informatiker und Philosoph, der bedeutende Beiträge zur Automatentheorie, Modelltheorie, axiomatischen Mengenlehre und Semantik der Programmiersprachen geleistet hat.
Neu!!: Theoretische Informatik und Dana Scott · Mehr sehen »
Datenbankmodell
Fünf Beispiele für Datenbankmodelle Ein Datenbankmodell ist die theoretische Grundlage für eine Datenbank und bestimmt, in welcher Struktur Daten in einem Datenbanksystem gespeichert werden.
Neu!!: Theoretische Informatik und Datenbankmodell · Mehr sehen »
David Hilbert
David Hilbert (1912) David Hilbert (* 23. Januar 1862 in Königsberg; † 14. Februar 1943 in Göttingen) war ein deutscher Mathematiker und Hochschullehrer.
Neu!!: Theoretische Informatik und David Hilbert · Mehr sehen »
Definition
Unter einer Definition („Abgrenzung“, aus, „(von etwas) herab/weg“ und, „Grenze“) versteht man in Logik und Wissenschaftstheorie die Bestimmung eines Begriffs (Begriffsbestimmung) oder die Erklärung des Wesens einer Sache.
Neu!!: Theoretische Informatik und Definition · Mehr sehen »
Denotationelle Semantik
Die denotationelle Semantik (Funktionensemantik; englisch: denotational semantics) ist in der Theoretischen Informatik eine von mehreren Möglichkeiten, eine formale Semantik für eine formale Sprache zu definieren.
Neu!!: Theoretische Informatik und Denotationelle Semantik · Mehr sehen »
Dialogische Logik
Die dialogische Logik (engl.: dialogical logic auch: game semantics) ist ein von den deutschen Logikern und Philosophen Kuno Lorenz und Paul Lorenzen entwickelter spieltheoretischer, semantiknaher Ansatz zur Logik.
Neu!!: Theoretische Informatik und Dialogische Logik · Mehr sehen »
Dirk Hoffmann
Dirk Hoffmann Dirk W. Hoffmann (* 1972 in Frankenthal) ist ein deutscher Informatiker.
Neu!!: Theoretische Informatik und Dirk Hoffmann · Mehr sehen »
Diskret
Das Adjektiv diskret (lat. discernere ‚trennen‘, ‚unterscheiden‘) wurde im 16.
Neu!!: Theoretische Informatik und Diskret · Mehr sehen »
Donald E. Knuth
Donald Knuth (2005) Donald Ervin „Don“ Knuth (* 10. Januar 1938 in Milwaukee, Wisconsin) ist ein US-amerikanischer Informatiker.
Neu!!: Theoretische Informatik und Donald E. Knuth · Mehr sehen »
Eingabe (Computer)
Die Eingabe (englisch input) eines Computerprogramms ist das, was es zu seiner Ausführung benötigt.
Neu!!: Theoretische Informatik und Eingabe (Computer) · Mehr sehen »
Emil Leon Post
Emil Leon Post Emil Leon Post (* 11. Februar 1897 in Augustów, Kongresspolen; † 21. April 1954 in New York, USA) war ein polnisch-US-amerikanischer Mathematiker und Logiker.
Neu!!: Theoretische Informatik und Emil Leon Post · Mehr sehen »
Endlicher Automat
Abbildung 1: Beispiel eines EA, der eine Tür beschreibt Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat;, FSM) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen.
Neu!!: Theoretische Informatik und Endlicher Automat · Mehr sehen »
Entropie (Informationstheorie)
Entropie (nach dem Kunstwort ἐντροπία)Kulturgeschichte der Physik, Károly Simonyi, Urania-Verlag, Leipzig 1990, ISBN 3-332-00254-6, S. 372.
Neu!!: Theoretische Informatik und Entropie (Informationstheorie) · Mehr sehen »
Entscheidbar
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt.
Neu!!: Theoretische Informatik und Entscheidbar · Mehr sehen »
Erweiterte Backus-Naur-Form
Die Erweiterte Backus-Naur-Form, kurz EBNF, ist eine Erweiterung der Backus-Naur-Form (BNF), die ursprünglich von Niklaus Wirth zur Darstellung der Syntax der Programmiersprache Pascal eingeführt wurde.
Neu!!: Theoretische Informatik und Erweiterte Backus-Naur-Form · Mehr sehen »
Formale Grammatik
Formale Grammatiken sind mathematische Modelle von Grammatiken, die zur eindeutigen Erzeugung und Beschreibung formaler Sprachen dienen.
Neu!!: Theoretische Informatik und Formale Grammatik · Mehr sehen »
Formale Semantik
Formale Semantik beschäftigt sich mit der exakten Bedeutung von Termen in künstlichen oder natürlichen Sprachen.
Neu!!: Theoretische Informatik und Formale Semantik · Mehr sehen »
Formale Spezifikation
Eine formale Spezifikation ist die Beschreibung eines Computerprogramms mittels einer Notation, deren Semantik eindeutig definiert ist (einer sogenannten formalen Sprache).
Neu!!: Theoretische Informatik und Formale Spezifikation · Mehr sehen »
Formale Sprache
Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die Definition und Anwendung formaler Systeme im engeren Sinn und der Logik im weiteren, allgemeinen Sinn.
Neu!!: Theoretische Informatik und Formale Sprache · Mehr sehen »
Formales System
Ein formales System ist ein System von Symbolketten und Regeln.
Neu!!: Theoretische Informatik und Formales System · Mehr sehen »
Formalisierung
Formalisierung bedeutet den Vorgang oder das Ergebnis des Formalisierens einer Sache.
Neu!!: Theoretische Informatik und Formalisierung · Mehr sehen »
Funktion (Mathematik)
In der Mathematik ist eine Funktion oder Abbildung eine Beziehung (Relation) zwischen zwei Mengen, die jedem Element der einen Menge (Funktionsargument, unabhängige Variable, x-Wert) genau ein Element der anderen Menge (Funktionswert, abhängige Variable, y-Wert) zuordnet.
Neu!!: Theoretische Informatik und Funktion (Mathematik) · Mehr sehen »
Funktionale Programmierung
Funktionale Programmierung ist ein Programmierparadigma, in dem Funktionen nicht nur definiert und angewendet werden können, sondern auch wie Daten miteinander verknüpft, als Parameter verwendet und als Funktionsergebnisse auftreten können.
Neu!!: Theoretische Informatik und Funktionale Programmierung · Mehr sehen »
Gödelscher Unvollständigkeitssatz
Der Gödelsche Unvollständigkeitssatz ist einer der wichtigsten Sätze der modernen Logik.
Neu!!: Theoretische Informatik und Gödelscher Unvollständigkeitssatz · Mehr sehen »
Gerhard Gentzen
Gerhard Gentzen Gerhard Karl Erich Gentzen (* 24. November 1909 in Greifswald; † 4. August 1945 in Prag) war ein deutscher Mathematiker und Logiker.
Neu!!: Theoretische Informatik und Gerhard Gentzen · Mehr sehen »
Grammatik
allegorisch dargestellt als Gärtnerin, Gemälde von Laurent de La Hyre (1650) Die Grammatik oder auch Sprachlehre (von, ‚Buchstabe‘) bezeichnet in der Sprachwissenschaft (Linguistik) jede Form einer systematischen Sprachbeschreibung.
Neu!!: Theoretische Informatik und Grammatik · Mehr sehen »
Graph (Graphentheorie)
Ein Graph ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert.
Neu!!: Theoretische Informatik und Graph (Graphentheorie) · Mehr sehen »
Halteproblem
Das Halteproblem beschreibt eine Frage aus der theoretischen Informatik.
Neu!!: Theoretische Informatik und Halteproblem · Mehr sehen »
Hans Hermes
Mathematischen Forschungsinstitut Oberwolfach 1970 Hans Hermes (* 12. Februar 1912 in Neunkirchen (Saar); † 10. November 2003 in Freiburg im Breisgau) war ein deutscher Mathematiker, der bedeutende Beiträge zu den Grundlagen der mathematischen Logik geleistet hat.
Neu!!: Theoretische Informatik und Hans Hermes · Mehr sehen »
Heinrich Scholz (Logiker)
Mathematischen Forschungsinstitut Oberwolfach Heinrich Scholz (* 17. Dezember 1884 in Berlin; † 30. Dezember 1956 in Münster, Westfalen) war ein deutscher Logiker, Philosoph und evangelischer Theologe.
Neu!!: Theoretische Informatik und Heinrich Scholz (Logiker) · Mehr sehen »
Imagination
Imagination („Bild“) ist synonym mit Einbildung, Einbildungskraft, Phantasie.
Neu!!: Theoretische Informatik und Imagination · Mehr sehen »
Implementierung
Eine Implementierung – auch Implementation (über ‚Ausführung‘, ‚Durchführung‘; von spätlateinisch implementum ‚Gerät‘ zu ‚anfüllen‘, ‚erfüllen‘) genannt – ist das Implementieren oder das Implementiertwerden, also die Realisierung oder Umsetzung von festgelegten Strukturen und Prozessabläufen in einem System unter Berücksichtigung von Rahmenbedingungen, Regeln und Zielvorgaben, im Sinne einer Spezifikation.
Neu!!: Theoretische Informatik und Implementierung · Mehr sehen »
Infimum und Supremum
Die Bildmenge der abgebildeten Funktion ist beschränkt, damit ist auch die Funktion beschränkt. In der Mathematik treten die Begriffe Supremum und Infimum sowie kleinste obere Schranke bzw.
Neu!!: Theoretische Informatik und Infimum und Supremum · Mehr sehen »
Informatik
Lambda lc.svg Sorting quicksort anim frame.svg Utah teapot simple 2.png 3-Tasten-Maus Microsoft.jpg Bei der Informatik handelt es sich um die Wissenschaft von der systematischen Darstellung, Speicherung, Verarbeitung und Übertragung von Daten, wobei besonders die automatische Verarbeitung mit Computern betrachtet wird.
Neu!!: Theoretische Informatik und Informatik · Mehr sehen »
Information
Das „i“ ist international ein Symbol für Information im Tourismus und verwandten Gebieten Information ist in der Informationstheorie das Wissen, das ein Absender einem Empfänger über einen Informationskanal vermittelt.
Neu!!: Theoretische Informatik und Information · Mehr sehen »
Informationstheorie
Die Informationstheorie ist eine mathematische Theorie aus dem Bereich der Wahrscheinlichkeitstheorie und Statistik, die auf den US-amerikanischen Mathematiker Claude Shannon zurückgeht.
Neu!!: Theoretische Informatik und Informationstheorie · Mehr sehen »
Ingo Wegener
Ingo Wegener (vollständiger Name Ingo Werner Wegener; * 4. Dezember 1950 in Bremen; † 27. November 2008 in Bielefeld) war ein deutscher Informatiker, der auf dem Gebiet der theoretischen Informatik arbeitete.
Neu!!: Theoretische Informatik und Ingo Wegener · Mehr sehen »
Integrierter Schaltkreis
Funktionseinheiten wie Rechenwerk und Cache des Prozessors zu erkennen. Aktuelle Prozessor-Chips umfassen bei ähnlichen Abmessungen mittlerweile etwa 4000 Mal so viele Transistoren. Ein integrierter Schaltkreis, auch integrierte Schaltung (kurz IC; die Buchstaben werden einzeln gesprochen: bzw. veraltet IS) ist eine auf einem dünnen, meist einige Millimeter großen Plättchen aus Halbleiter-Material aufgebrachte elektronische Schaltung.
Neu!!: Theoretische Informatik und Integrierter Schaltkreis · Mehr sehen »
John von Neumann
John von Neumann (um 1940) John von Neumann (* 28. Dezember 1903 in Budapest, Österreich-Ungarn als Neumann János Lajos; † 8. Februar 1957 in Washington, D.C., Vereinigte Staaten) war ein ungarisch-US-amerikanischer Mathematiker.
Neu!!: Theoretische Informatik und John von Neumann · Mehr sehen »
John W. Backus
John Backus John Warner Backus (* 3. Dezember 1924 in Philadelphia; † 17. März 2007 in Ashland, Oregon) war ein US-amerikanischer Informatiker und einer der Pioniere der Informatik.
Neu!!: Theoretische Informatik und John W. Backus · Mehr sehen »
Kanal (Informationstheorie)
Ein Kanal (oder Informationskanal, Übertragungskanal, Übertragungsweg; auch Shannon’sches Kanalmodell) ist in der Informationstheorie ein Medium, durch das Daten und Informationen vom Absender zum Empfänger über einen Übertragungsweg geleitet werden.
Neu!!: Theoretische Informatik und Kanal (Informationstheorie) · Mehr sehen »
Kanalkapazität
Die Kanalkapazität ist Teil der informationstheoretischen Beschreibung eines Übertragungskanals.
Neu!!: Theoretische Informatik und Kanalkapazität · Mehr sehen »
Künstliche Intelligenz
Künstliche Intelligenz (KI), auch artifizielle Intelligenz (AI), englisch artificial intelligence, ist ein Teilgebiet der Informatik, es umfasst alle Anstrengungen, deren Ziel es ist, Maschinen intelligent zu machen.
Neu!!: Theoretische Informatik und Künstliche Intelligenz · Mehr sehen »
Kellerautomat
Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen.
Neu!!: Theoretische Informatik und Kellerautomat · Mehr sehen »
Klaus Weihrauch
Klaus Weihrauch, Oberwolfach 2012 Klaus Weihrauch (* 1943 in Frankfurt (Oder)) ist ein deutscher Informatiker, der sich mit Berechenbarkeitstheorie und insbesondere Berechenbarer Analysis befasst.
Neu!!: Theoretische Informatik und Klaus Weihrauch · Mehr sehen »
Kodierungstheorie
Die Kodierungstheorie ist die mathematische Theorie der fehlererkennenden und -korrigierenden Codes.
Neu!!: Theoretische Informatik und Kodierungstheorie · Mehr sehen »
Kombinatorische Logik
Kombinatorische Logik (Abgekürzt CL für engl. Combinatory Logic) ist eine Notation, die von Moses Schönfinkel und Haskell Brooks Curry eingeführt wurde, um die Verwendung von Variablen in der Mathematischen Logik zu vermeiden.
Neu!!: Theoretische Informatik und Kombinatorische Logik · Mehr sehen »
Komplexitätsklasse
Komplexitätsklassen In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands.
Neu!!: Theoretische Informatik und Komplexitätsklasse · Mehr sehen »
Komplexitätstheorie
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen.
Neu!!: Theoretische Informatik und Komplexitätstheorie · Mehr sehen »
Konstrukt
Ein Konstrukt ist ein nicht empirisch erkennbarer Sachverhalt innerhalb einer wissenschaftlichen Theorie.
Neu!!: Theoretische Informatik und Konstrukt · Mehr sehen »
Kontextfreie Sprache
In der Theoretischen Informatik ist eine kontextfreie Sprache (CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann.
Neu!!: Theoretische Informatik und Kontextfreie Sprache · Mehr sehen »
Kontextsensitive Sprache
Die kontextsensitiven Sprachen (englisch context-sensitive languages, abgekürzt durch CSL) sind eine Klasse der formalen Sprachen, einem Teilgebiet der Theoretischen Informatik.
Neu!!: Theoretische Informatik und Kontextsensitive Sprache · Mehr sehen »
Kriterium
Ein Kriterium (von griechisch κριτήριον, „Gerichtshof; Rechtssache; Richtmaß“) ist ein Merkmal, das relevant für eine Unterscheidung, Bewertung oder Entscheidung ist, beispielsweise bei einer Auswahl zwischen Personen, Objekten, Eigenschaften oder Themen.
Neu!!: Theoretische Informatik und Kriterium · Mehr sehen »
Kryptologie
Mit Zufallstexten aus Ziffern beschriftetes Kryptologen-Denkmal vor dem Residenzschloss Posen Die Kryptologie („versteckt, verborgen, geheim“ und -logie) ist eine Wissenschaft, die sich mit der Verschlüsselung und Entschlüsselung von Informationen und somit mit der Informationssicherheit beschäftigt.
Neu!!: Theoretische Informatik und Kryptologie · Mehr sehen »
Kurt Gödel
rahmenlos Kurt Friedrich Gödel (* 28. April 1906 in Brünn, Österreich-Ungarn, heute Tschechien; † 14. Januar 1978 in Princeton, New Jersey, Vereinigte Staaten) war ein österreichischer und später US-amerikanischer Mathematiker, Philosoph und einer der bedeutendsten Logiker des 20. Jahrhunderts.
Neu!!: Theoretische Informatik und Kurt Gödel · Mehr sehen »
Laufzeit (Informatik)
Der Begriff Laufzeit beschreibt in der Informatik einerseits die Zeitdauer, die ein Programm, ausgeführt durch einen Rechner, zur Bewältigung einer Aufgabe benötigt.
Neu!!: Theoretische Informatik und Laufzeit (Informatik) · Mehr sehen »
Lösung (Mathematik)
Als Lösung bezeichnet man in der Mathematik ein mathematisches Objekt, zum Beispiel eine Zahl oder eine Funktion, das den Vorgaben eines wohldefinierten mathematischen Problems genügt.
Neu!!: Theoretische Informatik und Lösung (Mathematik) · Mehr sehen »
Leslie Lamport
Leslie Lamport Leslie Lamport (* 7. Februar 1941 in New York) ist ein US-amerikanischer Mathematiker, Informatiker und Programmierer.
Neu!!: Theoretische Informatik und Leslie Lamport · Mehr sehen »
Linear beschränkte Turingmaschine
Eine linear beschränkte Turingmaschine (auch LBA.
Neu!!: Theoretische Informatik und Linear beschränkte Turingmaschine · Mehr sehen »
Logik
Mit Logik (von logikè téchnē ‚Kunst des Denkens‘, ‚Kunst des Argumentierens‘) wird im Allgemeinen das vernünftige Schlussfolgern und im Besonderen dessen Lehre – die Schlussfolgerungslehre oder auch Denklehre – bezeichnet.
Neu!!: Theoretische Informatik und Logik · Mehr sehen »
Logische Programmierung
Logische Programmierung (Prädikative Programmierung, Logikprogrammierung) ist ein Programmierparadigma, das auf der mathematischen Logik beruht.
Neu!!: Theoretische Informatik und Logische Programmierung · Mehr sehen »
Maschinengestütztes Beweisen
Maschinengestütztes Beweisen (oder missverständlicher: automatisches Beweisen; ein Teilgebiet der automatischen Deduktion) basiert auf der Verwendung von Computerprogrammen zur Erzeugung und Überprüfung von mathematischen Beweisen logischer Theoreme.
Neu!!: Theoretische Informatik und Maschinengestütztes Beweisen · Mehr sehen »
Maschinensemantik
Unter der Semantik einer Maschine versteht man das Zusammenspiel der operationellen Semantik mit der Ein- und Ausgabecodierung einer realen oder abstrakten Rechenmaschine, so dass sich das Ergebnis einer Berechnung zweifelsfrei bestimmen lässt.
Neu!!: Theoretische Informatik und Maschinensemantik · Mehr sehen »
Mathematik
Die Mathematik (bundesdeutsches Hochdeutsch:,; österreichisches Hochdeutsch:; mathēmatikē téchnē ‚die Kunst des Lernens‘) ist eine Formalwissenschaft, die aus der Untersuchung von geometrischen Figuren und dem Rechnen mit Zahlen entstand.
Neu!!: Theoretische Informatik und Mathematik · Mehr sehen »
Mathematische Logik
Die mathematische Logik, auch symbolische Logik oder veraltet Logistik, ist ein Teilgebiet der Mathematik, insbesondere als Methode der Metamathematik und eine Anwendung der modernen formalen Logik.
Neu!!: Theoretische Informatik und Mathematische Logik · Mehr sehen »
Münster
Luftaufnahme der Innenstadt von Münster, 2009 Domplatz und Prinzipalmarkt im Modell für Blinde Die kreisfreie Stadt Münster (münsterländisch Mönster,,, altsächsisch Mimigernaford) in Westfalen ist Sitz des nach ihr benannten Regierungsbezirks in Nordrhein-Westfalen.
Neu!!: Theoretische Informatik und Münster · Mehr sehen »
Modallogik
Die Modallogik ist derjenige Zweig der Logik, der sich mit den Folgerungen um die Modalbegriffe möglich und notwendig befasst.
Neu!!: Theoretische Informatik und Modallogik · Mehr sehen »
Model Checking
Model Checking (deutsch auch Modellprüfung) ist ein Verfahren zur vollautomatischen Verifikation einer Systembeschreibung (Modell) gegen eine Spezifikation (Formel).
Neu!!: Theoretische Informatik und Model Checking · Mehr sehen »
Modell
Ein Modell (modello (italienisch), modulus (lateinisch), wörtlich: Maß, Maßstab) ist „eine Nachbildung (Darstellung, Wiedergabe oder Reproduktion) eines Gegenstands, bei dem die für wesentlich erachteten Eigenschaften hervorgehoben werden.
Neu!!: Theoretische Informatik und Modell · Mehr sehen »
Modula-2
Modula-2 ist eine 1978 entstandene Weiterentwicklung der Programmiersprache Pascal und wurde wie diese von Niklaus Wirth entwickelt.
Neu!!: Theoretische Informatik und Modula-2 · Mehr sehen »
Noam Chomsky
Noam Chomsky, 2017 220px Avram Noam Chomsky (* 7. Dezember 1928 in Philadelphia, Pennsylvania, USA) ist ein US-amerikanischer Sprachwissenschaftler sowie politischer Publizist und Aktivist.
Neu!!: Theoretische Informatik und Noam Chomsky · Mehr sehen »
Notwendige und hinreichende Bedingung
Notwendige Bedingung und hinreichende Bedingung sind Begriffe aus der mathematischen Beweisführung, die Bedingungen in zwei verschiedene Typen unterteilt.
Neu!!: Theoretische Informatik und Notwendige und hinreichende Bedingung · Mehr sehen »
NP (Komplexitätsklasse)
In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie.
Neu!!: Theoretische Informatik und NP (Komplexitätsklasse) · Mehr sehen »
NP-Vollständigkeit
NP-schweren und NP-vollständigen Probleme. In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist.
Neu!!: Theoretische Informatik und NP-Vollständigkeit · Mehr sehen »
One-Time-Pad
Beispiel eines One-Time-Pads (mit den 26 Großbuchstaben des lateinischen Alphabets) Das One-Time-Pad (Abkürzung: OTP, deutsch: Einmalverschlüsselung oder Einmalschlüssel-Verfahren, wörtlich Einmal-Block, nicht zu verwechseln mit dem Einmalkennwort) ist ein symmetrisches Verschlüsselungsverfahren zur geheimen Kommunikation.
Neu!!: Theoretische Informatik und One-Time-Pad · Mehr sehen »
P (Komplexitätsklasse)
In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, die alle Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind.
Neu!!: Theoretische Informatik und P (Komplexitätsklasse) · Mehr sehen »
Parametrisierter Algorithmus
Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP-vollständigen Problemen effizient zu lösen sind.
Neu!!: Theoretische Informatik und Parametrisierter Algorithmus · Mehr sehen »
Pascal (Programmiersprache)
Niklaus Wirth (2009), der Entwickler von Pascal Pascal ist eine Anfang der 1970er Jahre entwickelte imperative Programmiersprache.
Neu!!: Theoretische Informatik und Pascal (Programmiersprache) · Mehr sehen »
Peter Naur
Peter Naur (2008) Peter Naur (* 25. Oktober 1928 in Frederiksberg bei Kopenhagen; † 3. Januar 2016 in Herlev, Dänemark) war ein dänischer Informatik-Pionier und Träger des Turing Awards.
Neu!!: Theoretische Informatik und Peter Naur · Mehr sehen »
Polynomialzeit
In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn es mit einer deterministischen Rechenmaschine in einer Rechenzeit lösbar ist, die mit der Problemgröße nicht stärker als gemäß einer Polynomfunktion wächst.
Neu!!: Theoretische Informatik und Polynomialzeit · Mehr sehen »
Prädikatenlogik
Die Prädikatenlogiken (auch Quantorenlogiken) bilden eine Familie logischer Systeme, die es erlauben, in der Praxis und in der Theorie vieler Wissenschaften wichtige Bereiche durch Argumente zu formalisieren und sie auf ihre Gültigkeit zu überprüfen.
Neu!!: Theoretische Informatik und Prädikatenlogik · Mehr sehen »
Problem
Ein Problem („Vorsprung, Klippe, Hindernis; das, was vorgelegt wurde“) entsteht in einer Situation, in der ein oder mehrere Ziele erreicht werden müssen, wobei nicht unmittelbar sicher ist, welche Maßnahmen ergriffen oder welche Mittel eingesetzt werden müssen, um diese Ziele zu erreichen.
Neu!!: Theoretische Informatik und Problem · Mehr sehen »
Programmiersprache
Quelltext eines Programms in der Programmiersprache C++. Scratch. Eine Programmiersprache ist eine formale Sprache zur Formulierung von Datenstrukturen und Algorithmen, d. h.
Neu!!: Theoretische Informatik und Programmiersprache · Mehr sehen »
Pumping-Lemma
Das Pumping-Lemma bzw.
Neu!!: Theoretische Informatik und Pumping-Lemma · Mehr sehen »
Reguläre Sprache
In der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge oder erkennbare Sprache eine formale Sprache, die einigen Einschränkungen unterliegt.
Neu!!: Theoretische Informatik und Reguläre Sprache · Mehr sehen »
Rekursiv aufzählbare Menge
Als rekursiv aufzählbare Menge (auch semi-entscheidbare Menge, positiv semi-entscheidbare Menge, halb-entscheidbare Menge, berechenbar aufzählbare Menge, kurz r.e., c.e.) wird in der Berechenbarkeitstheorie eine Menge von natürlichen Zahlen bezeichnet, wenn es einen Algorithmus gibt, der die Elemente dieser Menge aufzählt.
Neu!!: Theoretische Informatik und Rekursiv aufzählbare Menge · Mehr sehen »
Richard M. Karp
Richard Karp 2009 Richard Manning Karp (* 3. Januar 1935 in Boston) ist ein amerikanischer Informatiker.
Neu!!: Theoretische Informatik und Richard M. Karp · Mehr sehen »
Robin Milner
Arthur John Robin Gorell Milner FRS FRSE (* 13. Januar 1934 in Yealmpton bei Plymouth; † 20. März 2010 in Cambridge) war ein britischer Professor für Informatik und Turingpreisträger.
Neu!!: Theoretische Informatik und Robin Milner · Mehr sehen »
Satz (Mathematik)
Ein Satz oder Theorem ist in der Mathematik eine widerspruchsfreie logische Aussage, die mittels eines Beweises als wahr erkannt, das heißt, aus Axiomen, Definitionen und bereits bekannten Sätzen hergeleitet werden kann.
Neu!!: Theoretische Informatik und Satz (Mathematik) · Mehr sehen »
Satz von Rice
Der Satz von Rice ist ein Ergebnis der Theoretischen Informatik.
Neu!!: Theoretische Informatik und Satz von Rice · Mehr sehen »
Speicherkapazität
Die Speicherkapazität bezeichnet die maximale Datenmenge, die in einer Datenstruktur oder in einem Datenspeicher gespeichert werden kann.
Neu!!: Theoretische Informatik und Speicherkapazität · Mehr sehen »
Stephen A. Cook
Stephen Arthur Cook OOnt (* 14. Dezember 1939 in Buffalo, New York) ist Professor der Informatik an der University of Toronto in Kanada.
Neu!!: Theoretische Informatik und Stephen A. Cook · Mehr sehen »
Stephen Cole Kleene
Kleene 1978 Stephen Cole Kleene (* 5. Januar 1909 in Hartford, Connecticut; † 25. Januar 1994 in Madison, Wisconsin) war ein US-amerikanischer Mathematiker und Logiker.
Neu!!: Theoretische Informatik und Stephen Cole Kleene · Mehr sehen »
Strukturwissenschaft
Mit dem Begriff Strukturwissenschaften werden Wissensgebiete zusammengefasst, die allgemein funktional wirksame Formen betrachten und weder im Allgemeinen noch im Speziellen Gegenstände der Natur oder der sozialen Wirklichkeit zum Gegenstand haben.
Neu!!: Theoretische Informatik und Strukturwissenschaft · Mehr sehen »
Syntax
Unter Syntax (von syn ‚zusammen‘ und taxis ‚Ordnung, Reihenfolge‘) versteht man allgemein ein Regelsystem zur Kombination elementarer Zeichen zu zusammengesetzten Zeichen in natürlichen oder künstlichen Zeichensystemen.
Neu!!: Theoretische Informatik und Syntax · Mehr sehen »
Syntaxdiagramm
Ein Syntaxdiagramm wird in der theoretischen Informatik benutzt, um die Syntax einer Regelmenge graphisch darzustellen.
Neu!!: Theoretische Informatik und Syntaxdiagramm · Mehr sehen »
Temporale Logik
Temporale Logiken oder Zeitlogiken sind Erweiterungen der Logik, durch die zeitliche Abläufe erfasst werden können.
Neu!!: Theoretische Informatik und Temporale Logik · Mehr sehen »
Terminiertheit
Terminiertheit ist ein Begriff aus der Berechenbarkeitstheorie, einem Teilgebiet der theoretischen Informatik.
Neu!!: Theoretische Informatik und Terminiertheit · Mehr sehen »
Turing-Vollständigkeit
Mit Turing-Vollständigkeit (engl. turing completeness) eines Systems wird seine universelle Programmierbarkeit beschrieben.
Neu!!: Theoretische Informatik und Turing-Vollständigkeit · Mehr sehen »
Turingmaschine
Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.
Neu!!: Theoretische Informatik und Turingmaschine · Mehr sehen »
Universität Münster
Sitz der Universität Münster im Schlossgebäude Die Universität Münster (bis 30. September 2023 Westfälische Wilhelms-Universität Münster, kurz WWU) ist mit 44.585 Studenten (Stand: WS 2022/23) und rund 280 Studiengängen in 15 Fachbereichen eine der größten deutschen Universitäten.
Neu!!: Theoretische Informatik und Universität Münster · Mehr sehen »
Uwe Schöning
Uwe Schöning (* 28. Dezember 1955 in Ulm) ist ein deutscher Informatiker.
Neu!!: Theoretische Informatik und Uwe Schöning · Mehr sehen »
Westfälische Nachrichten
alternatives Logo Westfälische Nachrichten (WN) ist eine regionale Tageszeitung für den Raum Münster, das Münsterland und das Tecklenburger Land.
Neu!!: Theoretische Informatik und Westfälische Nachrichten · Mehr sehen »
Leitet hier um:
Theoretische Informationswissenschaft, Theoretische informatik.
