Logo
Unionpedia
Kommunikation
Jetzt bei Google Play
Neu! Laden Sie Unionpedia auf Ihrem Android™-Gerät herunter!
Frei
Schneller Zugriff als Browser!
 

Theoretische Informatik

Index Theoretische Informatik

Mind-Map zu einem Teilbereich der theoretischen Informatik Die theoretische Informatik beschäftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Übertragung und Wiedergabe von Informationen in Zusammenhang stehen.

310 Beziehungen: Abelpreis, Ableitung (Informatik), AC, Ackermannfunktion, Akzeptieren (Automaten- und Komplexitätstheorie), Akzeptor (Informatik), Alan Turing, Alexandra Silva, Algebraische Linguistik, Algebraische Rechenmodelle, Algorithmische Informationstheorie, Algorithmus, Alonzo Church, Alternierende Turingmaschine, Amortisierte Laufzeitanalyse, Andrew Yao, Approximationsalgorithmus, AtoCC, Aufzählungsoperator, Automat (Informatik), Automatentheorie, Äquivalenzproblem, Bandmaschine, Barbara König (Informatikerin), Berechenbare Folge, Berechenbare Ordinalzahl, Berechenbare Ordnung, Berechenbarer Operator, Berechenbarkeitstheorie, Bernard Chazelle, Bernd Mahr, Bernhard Thalheim, Bewertungsfunktion (Formale Sprachen), Bisimulation, Boolescher Schaltkreis, BQP, Britta Schinzel, Cantorsche Paarungsfunktion, Chomsky-Hierarchie, Chomsky-Normalform, Christel Baier, Christoph Meinel (Informatiker), Circuit Value Problem, Cocke-Younger-Kasami-Algorithmus, Computer Pioneer Award, Computervirus, Constraint, Continuation, Conways Spiel des Lebens, Corrado Böhm, ..., Crew-Pairing, Determinismus (Algorithmus), Deterministischer azyklischer endlicher Automat, Deterministischer endlicher Automat, Deutsche Vereinigung für mathematische Logik und für Grundlagenforschung der exakten Wissenschaften, Deutscher IT-Sicherheitspreis, Diagonalsprache, Diamond Lemma, Diskrete Mathematik, Doktor der Naturwissenschaften, Dorothea Wagner, Dyck-Sprache, Effizienz (Informatik), Eigenschaft T, Eike Kiltz, Einzelwissenschaft, Electronic Notes in Theoretical Computer Science, Endlichkeitsproblem, Energieeffiziente Algorithmen, Entscheidbar, Erfüllbarkeitsproblem der Aussagenlogik, Erfüllbarkeitsproblem für Schaltkreise, Ernst Mayr (Informatiker), Ernst-Rüdiger Olderog, Externspeichermodell, Faktorisierungsverfahren, Fields-Medaille, Fitch-Kalkül, Fleißiger Biber, Formale Grammatik, Formale Methode, Formale Semantik, Formale Sprache, Formalwissenschaft, Friedrich Otto (Informatiker), Gerd Wechsung, Gesellschaft für Informatik, Gewichteter Automat, Gewissheit, Gilles Brassard, GOTO-Programm, Graphentheorie, Graphersetzungssystem, Greibach-Normalform, Halbgruppe, Halteproblem, Hans-Jörg Kreowski, Hartmut Ehrig, Heinrich Scholz (Logiker), Henry Gordon Rice, Heribert Vollmer, Hidden Markov Model, Horst Reichel (Mathematiker), IMU-Abakus-Medaille, Indeterminismus, Informatik, Informatikstudium, Informatikunterricht, Ingo Wegener, Internationaler Mathematikerkongress, Μ-Rekursion, Ω-reguläre Sprache, John-von-Neumann-Medaille, Joost-Pieter Katoen, Julius Richard Büchi, Juraj Hromkovič, Kachelproblem, Karl Heinz Böhling, Karl-Heinz Zimmermann, Kategorientheorie, Kellerautomat, Klaus Indermark, Klaus Peter Jantke, Klaus Weihrauch, Kombinatorik auf Wörtern, Kommunikationskomplexität, Komplexität, Komplexitätstheorie, Konfluenz (Informatik), Konstruierte Sprache, Kontextfreie Sprache, Kontextsensitive Sprache, Kuroda-Normalform, Kurt-Ulrich Witt, Lambda, Lambda-Kalkül, Längster Pfad, Lückensatz von Borodin, Leeres Wort, Leerheitsproblem, Lemma von Arden, Leslie Lamport, LF(k)-Grammatik, Lindenmayer-System, Linear beschränkte Turingmaschine, Lineare Sprache, Liste bedeutender Mathematiker, Liste bedeutender Personen für die Informatik, Liste von Informatikerinnen, LL(k)-Grammatik, Logik, LOOP-Programm, Louise Hay (Mathematikerin), LR(k)-Grammatik, Ludwig Staiger, Manfred Paul (Informatiker), Marian Kogler, Marta Kwiatkowska, Martin Ziegler (Mathematiker), Maschinensemantik, Mathematische Logik, Matroids Matheplanet, Maut, Mautproblem, Medwedew-Automat, Mehrband-Turingmaschine, Mehrspuren-Turingmaschine, Mercateo, Mereologie, Mereotopologie, Michael Huber (Mathematiker), Monadische Prädikatenlogik zweiter Stufe, Moses S. Charikar, Mutex, Neil Immerman, Nerode-Relation, Netzwerkökonomik, Nichtdeterminismus, Nichtdeterministische Turingmaschine, Nick Pippenger, Nicole Megow, Noam Chomsky, Norbert Blum, Normalform, NP-Schwere, NP-Vollständigkeit, NSPACE, Ogdens Lemma, Orakel-Turingmaschine, Otto-von-Guericke-Universität Magdeburg, P-NP-Problem, P/poly, Palindrom, Paralleler Algorithmus, Parametrisierter Algorithmus, Partielle Funktion, Patricia Bouyer-Decitre, PCP-Theorem, Peter Rossmanith, Peter van Emde Boas, Petri-Netz, Pfannkuchen-Sortierproblem, Philosophenproblem, Philosophische Logik, Phrasenstrukturgrammatik, Polynomialzeitreduktion, Postsches Korrespondenzproblem, Potenzautomat, Praktische Informatik, Presburger Award, Primitiv-rekursive Funktion, Probabilistische Turingmaschine, Problem, Problem des Handlungsreisenden, Problemkern, Produktionsregel, Programmäquivalenz, Pumping-Lemma, Q (Komplexitätsklasse), Quadratfreies Wort, Quantencomputer, Rechtsableitung, Rechtsreduktion, Reduktion (theoretische Informatik), Reduktionssystem, Registermaschine, Reguläre Sprache, Regulärer Ausdruck, Rekursion, Rekursionssatz, Rekursiv aufzählbare Sprache, Rekursive Sprache, René Heinzl, Retraceable Menge, Robert Fano, Robin Milner, Ronen Eldan, Rudolf Freund (Informatiker), SameGame, Satz von Ladner, Satz von Myhill-Nerode, Satz von Rice, Schnittproblem, Schwere und Vollständigkeit (theoretische Informatik), Scott-Topologie, Semantik (Logik), Semi-Thue-System, Seymour Ginsburg, Shafrira Goldwasser, Sheila A. Greibach, Sigma, Simons Foundation, Software, Sprache, Spursprache, Stephen A. Cook, Stephen Cole Kleene, Sternhöhe (Informatik), Stirling-Zahl, Strukturelle Induktion, Strukturwissenschaft, Suchproblem, Susanne Albers, Syntaxbaum, Syntaxdiagramm, Tadao Kasami, TC, Termersetzungssystem, Terminiertheit, TGI, Thomas Bruderer, Thomas Schwentick, TI, Transduktor (Informatik), Transitionssystem, Transitive Hülle (Relation), TUM Department of Computer Science, Turing Award, Turingmaschine, Turingmaschine mit Zusatzeingabe, Typentheorie, Ulrike Meyer, Ulrike von Luxburg, Unärsystem, Universität Paderborn, Uwe Nestmann, Uwe Schöning, Vasco Brattka, Verfeinerung (Informatik), Verifizierung, Verkettungszeichen, Verzögerte Initialisierung, Volker Claus, Wachsend kontextsensitive Sprache, Walter Savitch, Władysław Matwin, WHILE-Programm, Wilfried Brauer, Wilhelm Ackermann (Mathematiker), Wirkung (Informatik), Wolfgang Ertel (Informatiker), Wolfram Menzel, Wort (theoretische Informatik), Wortfunktion, Wortproblem (Berechenbarkeitstheorie), Zahlenfunktion, Zeichenkette, Zustandsraum (Informatik), Zweikellerautomat, 2020. Erweitern Sie Index (260 mehr) »

Abelpreis

Der Abelpreis ist eine seit 2003 jährlich durch die Norwegische Akademie der Wissenschaften verliehene internationale Auszeichnung für wissenschaftliche Arbeiten von außergewöhnlicher Tiefe und Einfluss auf dem Gebiet der Mathematik.

Neu!!: Theoretische Informatik und Abelpreis · Mehr sehen »

Ableitung (Informatik)

Als Ableitung wird in der theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen.

Neu!!: Theoretische Informatik und Ableitung (Informatik) · Mehr sehen »

AC

AC bzw.

Neu!!: Theoretische Informatik und AC · Mehr sehen »

Ackermannfunktion

Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der theoretischen Informatik Grenzen von Computer- und Berechnungsmodellen aufgezeigt werden können.

Neu!!: Theoretische Informatik und Ackermannfunktion · Mehr sehen »

Akzeptieren (Automaten- und Komplexitätstheorie)

Akzeptieren ist ein Begriff aus der Automaten- und Komplexitätstheorie, Teilgebieten der theoretischen Informatik.

Neu!!: Theoretische Informatik und Akzeptieren (Automaten- und Komplexitätstheorie) · Mehr sehen »

Akzeptor (Informatik)

Ein Akzeptor ist in der theoretischen Informatik ein spezieller endlicher Automat.

Neu!!: Theoretische Informatik und Akzeptor (Informatik) · 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 »

Alexandra Silva

Alexandra Martins da Silva (* 11. Februar 1984) ist eine portugiesische Informatikerin und Mathematikerin.

Neu!!: Theoretische Informatik und Alexandra Silva · Mehr sehen »

Algebraische Linguistik

Die Algebraische Linguistik ist ein Teilbereich der mathematischen Linguistik, der sich unter Verwendung formaler Methoden (Algebra, theoretische Informatik, formale Logik/ mathematische Logik, Mengenlehre) um die Formalisierung von Grammatiken bemüht: „Die algebraische Linguistik hat die Aufgabe, die Grammatik zu formalisieren“.

Neu!!: Theoretische Informatik und Algebraische Linguistik · Mehr sehen »

Algebraische Rechenmodelle

Algebraische Rechenmodelle sind in der theoretischen Informatik, insbesondere in der Komplexitätstheorie, solche Versuche, den Begriff des Berechenbaren formell zu fassen, die davon ausgehen, dass exakte Operationen auf den reellen oder auch den komplexen Zahlen durchführbar sind.

Neu!!: Theoretische Informatik und Algebraische Rechenmodelle · Mehr sehen »

Algorithmische Informationstheorie

Die algorithmische Informationstheorie ist eine Theorie aus der theoretischen Informatik, die im Gegensatz zur klassischen Informationstheorie die Kolmogorow-Komplexität zur Bestimmung des Informationsgehalts verwendet.

Neu!!: Theoretische Informatik und Algorithmische Informationstheorie · 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 »

Alternierende Turingmaschine

In der theoretischen Informatik ist eine alternierende Turingmaschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert.

Neu!!: Theoretische Informatik und Alternierende Turingmaschine · Mehr sehen »

Amortisierte Laufzeitanalyse

In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die Kosten von Operationen in Abfolgen («sequences») dieser Operation.

Neu!!: Theoretische Informatik und Amortisierte Laufzeitanalyse · Mehr sehen »

Andrew Yao

Andrew Yao 2005 Andrew Chi-Chih Yao (* 24. Dezember 1946 in Shanghai, Republik China) ist ein chinesischer Informatiker an der Tsinghua-Universität, China.

Neu!!: Theoretische Informatik und Andrew Yao · Mehr sehen »

Approximationsalgorithmus

Ein Approximationsalgorithmus (oder auch Näherungsalgorithmus) ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst.

Neu!!: Theoretische Informatik und Approximationsalgorithmus · Mehr sehen »

AtoCC

AtoCC (von engl. from Automaton to Compiler Construction) ist eine Lernumgebung im Bereich der theoretischen Informatik, speziell der Automatentheorie und der formalen Sprachen und deren Anwendung im Compilerbau.

Neu!!: Theoretische Informatik und AtoCC · Mehr sehen »

Aufzählungsoperator

Aufzählungsoperatoren (engl.: enumeration operator) sind in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, bestimmte berechenbare Abbildungen zwischen Mengen natürlicher Zahlen.

Neu!!: Theoretische Informatik und Aufzählungsoperator · 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 »

Äquivalenzproblem

Als Äquivalenzproblem bezeichnet man in der Theoretischen Informatik das Problem, zu entscheiden, ob zwei formale Definitionen von zwei Sprachen L_1 und L_2 äquivalent sind, also L_1.

Neu!!: Theoretische Informatik und Äquivalenzproblem · Mehr sehen »

Bandmaschine

Bandmaschine steht für.

Neu!!: Theoretische Informatik und Bandmaschine · Mehr sehen »

Barbara König (Informatikerin)

Barbara König ist eine deutsche Informatikerin.

Neu!!: Theoretische Informatik und Barbara König (Informatikerin) · Mehr sehen »

Berechenbare Folge

In der Berechenbarkeitstheorie, einem Teilgebiet der theoretischen Informatik und der mathematischen Logik, gibt es berechenbare Folgen.

Neu!!: Theoretische Informatik und Berechenbare Folge · Mehr sehen »

Berechenbare Ordinalzahl

Berechenbare Ordinalzahlen sind die Ordnungstypen berechenbarer Wohlordnungen.

Neu!!: Theoretische Informatik und Berechenbare Ordinalzahl · Mehr sehen »

Berechenbare Ordnung

Berechenbare Ordnungen bezeichnen in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, bestimmte entscheidbare Relationen.

Neu!!: Theoretische Informatik und Berechenbare Ordnung · Mehr sehen »

Berechenbarer Operator

Berechenbare Operatoren (auch: effektive Operatoren; engl.: recursive operator, effective operator) sind in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, Manipulationen partieller Funktionen, die durch Turing-Maschinen realisiert werden.

Neu!!: Theoretische Informatik und Berechenbarer Operator · 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 »

Bernard Chazelle

Bernard Chazelle Bernard Chazelle (* 1955 in Paris) ist ein französisch-amerikanischer Informatiker und Mathematiker.

Neu!!: Theoretische Informatik und Bernard Chazelle · Mehr sehen »

Bernd Mahr

Bernd Mahr (* 18. Juni 1945 in Thannhausen; † 12. April 2015) war ein deutscher Mathematiker, der unter anderem eine Professur für Theoretische Informatik an der TU Berlin innegehabt hat.

Neu!!: Theoretische Informatik und Bernd Mahr · Mehr sehen »

Bernhard Thalheim

Bernhard Thalheim Bernhard Thalheim (* 10. März 1952 in Radebeul) ist ein deutscher Informatiker und Universitätsprofessor.

Neu!!: Theoretische Informatik und Bernhard Thalheim · Mehr sehen »

Bewertungsfunktion (Formale Sprachen)

In der Theorie der Formalen Sprachen, einem Teilgebiet der theoretischen Informatik, bildet eine Bewertungsfunktion die Zeichen eines Alphabets auf natürliche Zahlen ab.

Neu!!: Theoretische Informatik und Bewertungsfunktion (Formale Sprachen) · Mehr sehen »

Bisimulation

Die Theoretische Informatik definiert Bisimulation als Relation zwischen den Zuständen eines Transitionssystems, die solche Zustände miteinander in Beziehung setzt, die sich gleich verhalten.

Neu!!: Theoretische Informatik und Bisimulation · Mehr sehen »

Boolescher Schaltkreis

In der theoretischen Informatik (insbesondere in der Komplexitätstheorie) ist ein boolescher Schaltkreis ein mathematisches Modell für digitale Schaltungen.

Neu!!: Theoretische Informatik und Boolescher Schaltkreis · Mehr sehen »

BQP

Die Lage von BQP relativ zu anderen ProblemklassenMichael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. Die Komplexitätsklasse BQP (von) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik.

Neu!!: Theoretische Informatik und BQP · Mehr sehen »

Britta Schinzel

Britta Schinzel (* 1943) ist eine Professorin der Mathematik und Informatik im Ruhestand.

Neu!!: Theoretische Informatik und Britta Schinzel · Mehr sehen »

Cantorsche Paarungsfunktion

Die Cantorsche Paarungsfunktion, manchmal auch Nummerierungsfunktion genannt, ist eine unter anderem in der theoretischen Informatik verwendete Abbildung, die auf dem Diagonalargument von Cantor basiert.

Neu!!: Theoretische Informatik und Cantorsche Paarungsfunktion · 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 »

Chomsky-Normalform

Die Chomsky-Normalform (Abk.: CNF) ist in der theoretischen Informatik eine Normalform für kontextfreie Grammatiken.

Neu!!: Theoretische Informatik und Chomsky-Normalform · Mehr sehen »

Christel Baier

Christel Baier (* 26. September 1965 in Karlsruhe) ist eine deutsche theoretische Informatikerin.

Neu!!: Theoretische Informatik und Christel Baier · Mehr sehen »

Christoph Meinel (Informatiker)

Christoph Meinel (2004) Christoph Meinel (* 14. April 1954 in Meißen) ist ein deutscher Informatiker und Professor für Internet-Technologien und Systeme zuletzt am Hasso-Plattner-Institut (HPI) und an der Universität Potsdam.

Neu!!: Theoretische Informatik und Christoph Meinel (Informatiker) · Mehr sehen »

Circuit Value Problem

Das Circuit Value Problem (engl., CVP, dt. etwa: Schaltkreis-Auswertungsproblem) ist in der theoretischen Informatik ein P-vollständiges Problem.

Neu!!: Theoretische Informatik und Circuit Value Problem · Mehr sehen »

Cocke-Younger-Kasami-Algorithmus

Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der theoretischen Informatik.

Neu!!: Theoretische Informatik und Cocke-Younger-Kasami-Algorithmus · Mehr sehen »

Computer Pioneer Award

Der Computer Pioneer Award (eigentlich IEEE Computer Society Women of ENIAC Computer Pioneer Award) wird seit 1981 für herausragende Leistungen im Bereich Computer vergeben, die mindestens 15 Jahre zurückliegen.

Neu!!: Theoretische Informatik und Computer Pioneer Award · Mehr sehen »

Computervirus

Blaster-Wurms, zeigt eine Nachricht des Wurm-Programmierers an den damaligen Microsoft-CEO Bill Gates Ein Computervirus (‚Gift, Schleim‘; Plural -viren) ist ein sich selbst verbreitendes Computerprogramm, welches sich in andere Computerprogramme, einen Bootsektor oder den RAM einschleust, und sich damit reproduziert.

Neu!!: Theoretische Informatik und Computervirus · Mehr sehen »

Constraint

Mit Constraints (deutsch „Einschränkung“) werden in diversen Programmiersprachen Bedingungen definiert, die zwingend vom Wert einer Variablen erfüllt werden müssen, damit der Wert ins System übernommen werden kann.

Neu!!: Theoretische Informatik und Constraint · Mehr sehen »

Continuation

Die Continuation ist ein abstraktes Konzept höherer, insbesondere funktionaler Programmiersprachen.

Neu!!: Theoretische Informatik und Continuation · Mehr sehen »

Conways Spiel des Lebens

Die Figur „Gleiter“ bildet anhand der Regeln alle vier Generationen eine verschobene Kopie ihrer selbst, wodurch sie sich „fortbewegt“. Das Spiel des Lebens ist ein vom Mathematiker John Horton Conway 1970 entworfenes Spiel, basierend auf einem zweidimensionalen zellulären Automaten.

Neu!!: Theoretische Informatik und Conways Spiel des Lebens · Mehr sehen »

Corrado Böhm

Corrado Böhm an seinem 90. Geburtstag auf der ETAPS-Konferenz in Rom (2013) Corrado Böhm (* 17. Januar 1923 in Mailand; † 23. Oktober 2017) war ein italienischer theoretischer Informatiker und Computerpionier.

Neu!!: Theoretische Informatik und Corrado Böhm · Mehr sehen »

Crew-Pairing

Das Problem des Crew-Pairings (CPP) ist ein kombinatorisches Optimierungsproblem des Operations Research und der theoretischen Informatik.

Neu!!: Theoretische Informatik und Crew-Pairing · Mehr sehen »

Determinismus (Algorithmus)

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.

Neu!!: Theoretische Informatik und Determinismus (Algorithmus) · Mehr sehen »

Deterministischer azyklischer endlicher Automat

Präfixbaum (links) und als DAEA (rechts), ''EOW'' steht für End-of-word (Ende des Wortes). Ein deterministischer azyklischer endlicher Automat (DAEA; Jan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000). Incremental construction of minimal acyclic finite state automata. Computational Linguistics 26(1):3-16. oder directed acyclic word graph, DAWG) ist in der theoretischen Informatik eine Datenstruktur, die eine Menge von Zeichenketten darstellt und eine Abfrageoperation ermöglicht, die prüft, ob eine gegebene Zeichenkette in einer Zeit, die proportional zu ihrer Länge ist, zu dieser Menge gehört.

Neu!!: Theoretische Informatik und Deterministischer azyklischer endlicher Automat · Mehr sehen »

Deterministischer endlicher Automat

Ein deterministischer endlicher Automat (DEA; oder deterministic finite automaton, DFA) ist in der theoretischen Informatik ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt.

Neu!!: Theoretische Informatik und Deterministischer endlicher Automat · Mehr sehen »

Deutsche Vereinigung für mathematische Logik und für Grundlagenforschung der exakten Wissenschaften

Die Deutsche Vereinigung für mathematische Logik und für Grundlagenforschung der exakten Wissenschaften e.V. (DVMLG) ist die Fachvertretung von Forschern im interdisziplinären Forschungsgebiet der Logik (innerhalb der Fächer Mathematik, Philosophie, Informatik und Linguistik).

Neu!!: Theoretische Informatik und Deutsche Vereinigung für mathematische Logik und für Grundlagenforschung der exakten Wissenschaften · Mehr sehen »

Deutscher IT-Sicherheitspreis

Der Deutsche IT-Sicherheitspreis ist ein von der Horst Görtz Stiftung vergebener Geldpreis für innovative Sicherheitslösungen und -anwendungen im Bereich der IT-Sicherheit.

Neu!!: Theoretische Informatik und Deutscher IT-Sicherheitspreis · Mehr sehen »

Diagonalsprache

Die Diagonalsprache ist eine Formale Sprache aus der theoretischen Informatik aus dem Bereich der Entscheidungsprobleme.

Neu!!: Theoretische Informatik und Diagonalsprache · Mehr sehen »

Diamond Lemma

In der theoretischen Informatik besagt das Diamond Lemma (auch: der Satz von Newman, nach Max Newman), dass eine fundierte Relation genau dann konfluent ist, wenn sie lokal konfluent ist.

Neu!!: Theoretische Informatik und Diamond Lemma · Mehr sehen »

Diskrete Mathematik

Die Diskrete Mathematik als Teilgebiet der Mathematik befasst sich mit mathematischen Operationen auf endlichen oder höchstens abzählbar unendlichen Mengen, also mit diskreten mathematischen Fragestellungen.

Neu!!: Theoretische Informatik und Diskrete Mathematik · Mehr sehen »

Doktor der Naturwissenschaften

Doktor der Naturwissenschaften (Deutschland und Österreich: Dr. rer. nat. für lateinisch doctor rerum naturalium oder Dr. phil. nat. für lateinisch doctor philosophiae naturalis; in englischer Schreibung RNDr, nachgestellt; Schweiz: Dr. sc. nat. für lateinisch doctor scientiarum naturalium oder Dr. phil. nat. wie in Deutschland und Österreich) ist ein akademischer Grad.

Neu!!: Theoretische Informatik und Doktor der Naturwissenschaften · Mehr sehen »

Dorothea Wagner

Dorothea Maria Anna Wagner (* 22. Juni 1957 in Trier) ist eine deutsche Informatikerin, Hochschullehrerin am Karlsruher Institut für Technologie und vom 1.

Neu!!: Theoretische Informatik und Dorothea Wagner · Mehr sehen »

Dyck-Sprache

Die Dyck-Sprachen sind in der theoretischen Informatik bestimmte kontextfreie formale Sprachen, also Typ-2-Sprachen entsprechend der Chomsky-Hierarchie.

Neu!!: Theoretische Informatik und Dyck-Sprache · Mehr sehen »

Effizienz (Informatik)

Die Effizienz eines Algorithmus ist seine Sparsamkeit bezüglich Ressourcen, Rechenzeit und Speicherplatz, die jener zur Lösung eines festgelegten Problems beansprucht.

Neu!!: Theoretische Informatik und Effizienz (Informatik) · Mehr sehen »

Eigenschaft T

In der Mathematik ist Eigenschaft T (auch Kazhdans Eigenschaft T) eine Starrheitseigenschaft topologischer Gruppen, die zuerst von David Kazhdan in den 1960er Jahren betrachtet wurde.

Neu!!: Theoretische Informatik und Eigenschaft T · Mehr sehen »

Eike Kiltz

Eike Kiltz (* 1975) ist ein deutscher Mathematiker auf dem Gebiet der Kryptologie und derzeit Professor an der Ruhr-Universität Bochum.

Neu!!: Theoretische Informatik und Eike Kiltz · Mehr sehen »

Einzelwissenschaft

Einzelwissenschaft (auch: Disziplin, Fach, Fachwissenschaft) ist ein eigenes Fachgebiet in der akademischen Bildungslandschaft, insbesondere der Hochschulen.

Neu!!: Theoretische Informatik und Einzelwissenschaft · Mehr sehen »

Electronic Notes in Theoretical Computer Science

Electronic Notes in Theoretical Computer Science ist eine Sammlung von Magazinen, die seit 1995 von dem Verlag Elsevier in elektronischer Form veröffentlicht wurden.

Neu!!: Theoretische Informatik und Electronic Notes in Theoretical Computer Science · Mehr sehen »

Endlichkeitsproblem

Als Endlichkeitsproblem einer formalen Sprache L bezeichnet man in der theoretischen Informatik das Problem, zu entscheiden, ob die Sprache endlich ist.

Neu!!: Theoretische Informatik und Endlichkeitsproblem · Mehr sehen »

Energieeffiziente Algorithmen

Energieeffiziente Algorithmen sind ein Forschungsgebiet der theoretischen Informatik, welches sich mit der Minimierung der benötigten Energie zur Durchführung komplexer Berechnungen befasst.

Neu!!: Theoretische Informatik und Energieeffiziente Algorithmen · 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 »

Erfüllbarkeitsproblem der Aussagenlogik

Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von ‚ Erfüllbarkeit‘) ist ein Entscheidungsproblem der theoretischen Informatik.

Neu!!: Theoretische Informatik und Erfüllbarkeitsproblem der Aussagenlogik · Mehr sehen »

Erfüllbarkeitsproblem für Schaltkreise

In der theoretischen Informatik (insbesondere in der Komplexitätstheorie) ist das Erfüllbarkeitsproblem für Schaltkreise (CircuitSAT, CSAT) das Entscheidungsproblem, ob es für eine gegebene boolesche Schaltung eine Eingabe gibt, die den Ausgang wahr macht.

Neu!!: Theoretische Informatik und Erfüllbarkeitsproblem für Schaltkreise · Mehr sehen »

Ernst Mayr (Informatiker)

Ernst Wilhelm Mayr (* 18. Mai 1950 in Fürstenfeldbruck) ist ein deutscher Informatiker.

Neu!!: Theoretische Informatik und Ernst Mayr (Informatiker) · Mehr sehen »

Ernst-Rüdiger Olderog

Ernst-Rüdiger Olderog (* 1955) ist ein deutscher Informatiker.

Neu!!: Theoretische Informatik und Ernst-Rüdiger Olderog · Mehr sehen »

Externspeichermodell

Das Externspeichermodell ist ein Modell aus der theoretischen Informatik, welches die Komplexität von Algorithmen in Bezug auf die Verwendung von mehreren Speicherhierarchien beschreibt.

Neu!!: Theoretische Informatik und Externspeichermodell · Mehr sehen »

Faktorisierungsverfahren

Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie.

Neu!!: Theoretische Informatik und Faktorisierungsverfahren · Mehr sehen »

Fields-Medaille

Fields-Medaille, Vorderseite Die Fields-Medaille, offizieller Name International Medal for Outstanding Discoveries in Mathematics (deutsch: „Internationale Medaille für herausragende Entdeckungen in der Mathematik“), ist eine der höchsten Auszeichnungen, die ein Mathematiker erhalten kann.

Neu!!: Theoretische Informatik und Fields-Medaille · Mehr sehen »

Fitch-Kalkül

Der Fitch-Kalkül ist eine von dem amerikanischen Logiker Frederic Brenton Fitch erfundene Methode für Beweise in Prädikatenlogik erster Stufe.

Neu!!: Theoretische Informatik und Fitch-Kalkül · Mehr sehen »

Fleißiger Biber

Fleißige Biber (auch) sind spezielle Turingmaschinen, die möglichst viele Einsen auf das Band schreiben und die nach einer endlichen Anzahl Rechenschritte den Halt-Zustand einnehmen (also anhalten).

Neu!!: Theoretische Informatik und Fleißiger Biber · 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 Methode

Der Begriff Formale Methode bezeichnet in der Informatik eine Vielzahl von natur- und ingenieurswissenschaftlichen Techniken zur Modellierung und mathematisch rigorosen Überprüfung von Computersystemen.

Neu!!: Theoretische Informatik und Formale Methode · 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 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 »

Formalwissenschaft

Formalwissenschaften sind Wissenschaften, die sich der Analyse von formalen Systemen widmen.

Neu!!: Theoretische Informatik und Formalwissenschaft · Mehr sehen »

Friedrich Otto (Informatiker)

Friedrich Otto (* 21. Februar 1952 in Gadderbaum, heute Bielefeld) ist ein deutscher Informatiker.

Neu!!: Theoretische Informatik und Friedrich Otto (Informatiker) · Mehr sehen »

Gerd Wechsung

Gerd Wechsung, 1985 Gerd Wechsung als Prorektor der Universität Jena, 1991 Gerd Wechsung wird 1998 das Verdienstkreuz am Bande der Bundesrepublik Deutschland von Thüringens Ministerpräsident Bernhard Vogel verliehen V. l. n. r.: Boris Trakhtenbrot, Gerd Wechsung und Jörg Rothe, 1994 Gerd Wechsung und Ludwig Staiger, 2012 Gerd und Maria Wechsung, 2010 Gerd Wechsung (* 12. Februar 1939 in Berka) ist ein deutscher Mathematiker und Informatiker, der von 1980 bis 2004 als Professor für Theoretische Informatik an der Universität Jena wirkte.

Neu!!: Theoretische Informatik und Gerd Wechsung · Mehr sehen »

Gesellschaft für Informatik

Die Gesellschaft für Informatik e. V. (abgekürzt GI) ist die größte Interessenvertretung für Informatik im deutschsprachigen Raum.

Neu!!: Theoretische Informatik und Gesellschaft für Informatik · Mehr sehen »

Gewichteter Automat

Der gewichtete Automat ist ein mathematisches Konzept aus der theoretischen Informatik, speziell aus der Automatentheorie.

Neu!!: Theoretische Informatik und Gewichteter Automat · Mehr sehen »

Gewissheit

Der Ausdruck Gewissheit bezeichnet alltagssprachlich meist die subjektive Sicherheit bezüglich bestimmter, für gut gerechtfertigt gehaltener Überzeugungen, die sich z. B.

Neu!!: Theoretische Informatik und Gewissheit · Mehr sehen »

Gilles Brassard

Gilles Brassard (2019) Gilles Brassard (* 1955 in Montreal) ist ein kanadischer Informatiker und theoretischer Physiker, der sich mit Quanteninformationstheorie befasst.

Neu!!: Theoretische Informatik und Gilles Brassard · Mehr sehen »

GOTO-Programm

GOTO-Programme sind spezielle Programme mit einer sehr einfachen Syntax.

Neu!!: Theoretische Informatik und GOTO-Programm · Mehr sehen »

Graphentheorie

Ungerichteter Graph mit sechs Knoten. Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik.

Neu!!: Theoretische Informatik und Graphentheorie · Mehr sehen »

Graphersetzungssystem

Beispiel für Graphersetzungsregel (Optimierung aus dem Compilerbau: Multiplikation mit 2 durch Addition ersetzt) Graphersetzungssysteme dienen der formalen Beschreibung der Veränderung von Graphen.

Neu!!: Theoretische Informatik und Graphersetzungssystem · Mehr sehen »

Greibach-Normalform

Die Greibach-Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist.

Neu!!: Theoretische Informatik und Greibach-Normalform · Mehr sehen »

Halbgruppe

In der Mathematik ist eine Halbgruppe eine algebraische Struktur bestehend aus einer Menge mit einer inneren zweistelligen Verknüpfung, die dem Assoziativgesetz genügt (also ein assoziatives Magma).

Neu!!: Theoretische Informatik und Halbgruppe · Mehr sehen »

Halteproblem

Das Halteproblem beschreibt eine Frage aus der theoretischen Informatik.

Neu!!: Theoretische Informatik und Halteproblem · Mehr sehen »

Hans-Jörg Kreowski

Hans-Jörg Kreowski (* 10. August 1949) ist ein deutscher Informatiker und Professor an der Universität Bremen.

Neu!!: Theoretische Informatik und Hans-Jörg Kreowski · Mehr sehen »

Hartmut Ehrig

Hartmut Ehrig (* 6. Dezember 1944 in Angermünde; † 17. März 2016) war ein deutscher Informatiker und Professor für theoretische Informatik und formale Spezifikation.

Neu!!: Theoretische Informatik und Hartmut Ehrig · 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 »

Henry Gordon Rice

Henry Gordon Rice (* 18. Juli 1920; † 14. April 2003) war ein Mathematiker und Logiker.

Neu!!: Theoretische Informatik und Henry Gordon Rice · Mehr sehen »

Heribert Vollmer

Heribert Vollmer (* 15. Oktober 1964 in Schmallenberg-Bad Fredeburg) ist ein deutscher Informatiker und Hochschullehrer.

Neu!!: Theoretische Informatik und Heribert Vollmer · Mehr sehen »

Hidden Markov Model

Das Hidden Markov Model, kurz HMM (verdecktes Markowmodell, oder verborgenes Markowmodell) ist ein stochastisches Modell, in dem ein System durch eine Markowkette – benannt nach dem russischen Mathematiker A. A. Markow – mit unbeobachteten Zuständen modelliert wird.

Neu!!: Theoretische Informatik und Hidden Markov Model · Mehr sehen »

Horst Reichel (Mathematiker)

Horst Reichel (* 30. März 1941 in Freiwaldau, Reichsgau Sudetenland) ist ein deutscher Mathematiker, Informatiker und Hochschullehrer.

Neu!!: Theoretische Informatik und Horst Reichel (Mathematiker) · Mehr sehen »

IMU-Abakus-Medaille

Die IMU-Abakus-Medaille (bis 2021 Nevanlinna-Preis (offiziell „Rolf-Nevanlinna-Preis in mathematischen Bereichen der Informatik“; englisch Rolf Nevanlinna Prize in Mathematical Aspects of Information Sciences), wird von der Internationalen Mathematischen Union (IMU) für herausragende Arbeiten auf dem Gebiet der theoretischen Informatik verliehen.

Neu!!: Theoretische Informatik und IMU-Abakus-Medaille · Mehr sehen »

Indeterminismus

Indeterminismus ist die Auffassung, dass nicht alle Ereignisse durch Vorbedingungen eindeutig festgelegt sind, es also bestimmte Ereignisse gibt, die nicht oder nicht eindeutig durch Ursachen determiniert, sondern indeterminiert (unbestimmt) sind.

Neu!!: Theoretische Informatik und Indeterminismus · 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 »

Informatikstudium

Das Informatikstudium ist das Studium der Fachrichtung Informatik.

Neu!!: Theoretische Informatik und Informatikstudium · Mehr sehen »

Informatikunterricht

Im Informatikunterricht erlernen die Schüler die Grundlagen der Informationstechnik (IT) und der Elektronischen Datenverarbeitung (EDV) und den sachgemäßen Umgang mit dem Computer.

Neu!!: Theoretische Informatik und Informatikunterricht · 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 »

Internationaler Mathematikerkongress

Der Internationale Mathematikerkongress (kurz ICM) ist der größte Kongress auf dem Gebiet der Mathematik.

Neu!!: Theoretische Informatik und Internationaler Mathematikerkongress · Mehr sehen »

Μ-Rekursion

Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle (µ für ‚das kleinste‘).

Neu!!: Theoretische Informatik und Μ-Rekursion · Mehr sehen »

Ω-reguläre Sprache

In der theoretischen Informatik bezeichnet die Klasse der ω-regulären Sprachen eine bestimmte Menge formaler Sprachen aus unendlichen Wörtern.

Neu!!: Theoretische Informatik und Ω-reguläre Sprache · Mehr sehen »

John-von-Neumann-Medaille

Die IEEE John von Neumann Medaille (benannt nach John von Neumann) wurde 1990 vom IEEE ins Leben gerufen und wird jährlich für „besondere Leistungen in Computer-bezogener Wissenschaft und Technologie“ verliehen, die nicht notwendigerweise zeitnah zur Verleihung stattgefunden haben müssen.

Neu!!: Theoretische Informatik und John-von-Neumann-Medaille · Mehr sehen »

Joost-Pieter Katoen

Joost-Pieter Katoen in der Logic Lane, Oxford Joost-Pieter Katoen (* 6. Oktober 1964 in Krimpen aan den IJssel) ist ein niederländischer theoretischer Informatiker.

Neu!!: Theoretische Informatik und Joost-Pieter Katoen · Mehr sehen »

Julius Richard Büchi

Julius Richard Büchi (* 1924; † 1984) war ein Schweizer Logiker und Mathematiker.

Neu!!: Theoretische Informatik und Julius Richard Büchi · Mehr sehen »

Juraj Hromkovič

Juraj Hromkovič (* 24. August 1958 in Bratislava) ist ein slowakischer Informatiker und Professor an der ETH Zürich.

Neu!!: Theoretische Informatik und Juraj Hromkovič · Mehr sehen »

Kachelproblem

Ein Kachelproblem ist die Aufgabe, eine Menge von Teilen zu einem Gesamten anzuordnen, so dass bestimmte Regeln eingehalten werden.

Neu!!: Theoretische Informatik und Kachelproblem · Mehr sehen »

Karl Heinz Böhling

Karl Heinz Böhling (* 13. Mai 1930 in Leer; † 23. März 2016) war ein deutscher Mathematiker, Informatiker und Hochschullehrer.

Neu!!: Theoretische Informatik und Karl Heinz Böhling · Mehr sehen »

Karl-Heinz Zimmermann

Karl-Heinz Zimmermann (* 31. Dezember 1956 in Bayreuth; † 21. August 2023) war Informatikprofessor an der Technischen Universität Hamburg.

Neu!!: Theoretische Informatik und Karl-Heinz Zimmermann · Mehr sehen »

Kategorientheorie

Die Kategorientheorie oder die kategorielle Algebra ist ein Zweig der Mathematik, der Anfang der 1940er Jahre zuerst im Rahmen der Topologie entwickelt wurde; Saunders MacLane nennt seine 1945 in Zusammenarbeit mit Samuel Eilenberg entstandene „General Theory of Natural Equivalences“ (in Trans. Amer. Math. Soc. 58, 1945) die erste explizit kategorientheoretische Arbeit.

Neu!!: Theoretische Informatik und Kategorientheorie · 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 Indermark

Klaus Indermark (* 21. September 1940) ist ein deutscher Informatiker und Hochschullehrer.

Neu!!: Theoretische Informatik und Klaus Indermark · Mehr sehen »

Klaus Peter Jantke

Klaus Peter Jantke (auch Klaus-Peter Jantke; * 1951 in Berlin) ist ein deutscher Mathematiker, Informatiker, Hochschullehrer und Spielforscher.

Neu!!: Theoretische Informatik und Klaus Peter Jantke · 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 »

Kombinatorik auf Wörtern

Die Kombinatorik auf Wörtern ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik, das Struktur und Eigenschaften von Wörtern einer Gruppe (wie z. B. Wörtern einer formalen Sprache) untersucht.

Neu!!: Theoretische Informatik und Kombinatorik auf Wörtern · Mehr sehen »

Kommunikationskomplexität

Die Kommunikationskomplexität ist ein Teilgebiet der Komplexitätstheorie und wird angewendet um die Frage zu untersuchen, wie viel Kommunikation zum Lösen bestimmter Aufgaben nötig ist, wobei die Eingabe auf mehrere Rechner verteilt ist.

Neu!!: Theoretische Informatik und Kommunikationskomplexität · Mehr sehen »

Komplexität

Komplexität bezieht sich vor allem auf die veränderlichen Verknüpfungen zwischen Elementen: beispielsweise den 100 Billionen Synapsen im Gehirn eines erwachsenen Menschen, die sich etwa durch Lernprozesse ständig auf-, ab- und umbauen (Neuronale Plastizität) Komplexität (Partizip Perfekt Passiv von complecti „umschlingen“, „umfassen“ oder „zusammenfassen“) bezeichnet eine große Anzahl von Elementen, vielfältigen Wechselwirkungen, Strukturen und Prozessen in einem Zusammenhang.

Neu!!: Theoretische Informatik und Komplexität · 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 »

Konfluenz (Informatik)

Konfluenz in einem Termersetzungssystem Konfluenz ist ein Begriff aus der Theoretischen Informatik und bezeichnet die Eigenschaft eines Transitionssystems, jedem Element höchstens eine Normalform zuzuordnen.

Neu!!: Theoretische Informatik und Konfluenz (Informatik) · Mehr sehen »

Konstruierte Sprache

Konstruierte Sprachen, auch Kunstsprachen oder künstliche Sprachen, sind Sprachen, die von einer Person oder einer Gruppe aus verschiedenen Gründen und zu verschiedenen Zwecken neu entwickelt wurden.

Neu!!: Theoretische Informatik und Konstruierte Sprache · 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 »

Kuroda-Normalform

Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist.

Neu!!: Theoretische Informatik und Kuroda-Normalform · Mehr sehen »

Kurt-Ulrich Witt

Kurt-Ulrich Witt (* 1953) ist ein deutscher Mathematiker und theoretischer Informatiker.

Neu!!: Theoretische Informatik und Kurt-Ulrich Witt · Mehr sehen »

Lambda

Das Lambda (auch Lamda, Lanta oder Labda; griechisches Neutrum λάβδα lábda, λάμβδα lámbda, neugriechisches Neutrum Λάμδα; Majuskel Λ, Minuskel λ) ist der elfte Buchstabe des griechischen Alphabets und hat nach dem milesischen System den Zahlwert 30.

Neu!!: Theoretische Informatik und Lambda · Mehr sehen »

Lambda-Kalkül

griechischen Alphabets, benutzt. Der Lambda-Kalkül ist eine formale Sprache zur Untersuchung von Funktionen.

Neu!!: Theoretische Informatik und Lambda-Kalkül · Mehr sehen »

Längster Pfad

Durch Entfernen einer beliebigen roten Kante erhält man aus diesem Hamiltonkreis einen einfachen Weg maximaler Länge. Die Aufgabe, den einfachen Weg maximaler Länge in einem gegebenen Graphen zu finden, bezeichnet man in der Graphentheorie und der theoretischen Informatik als longest path problem (englisch für Problem des längsten Weges).

Neu!!: Theoretische Informatik und Längster Pfad · Mehr sehen »

Lückensatz von Borodin

Der Lückensatz von Borodin ist ein 1972 von Allan Borodin veröffentlichter Satz der Komplexitätstheorie in der theoretischen Informatik.

Neu!!: Theoretische Informatik und Lückensatz von Borodin · Mehr sehen »

Leeres Wort

Das leere Wort ist in der Theoretischen und in der Praktischen Informatik ein Wort, das aus keinem einzigen Zeichen besteht, also die Länge 0 hat.

Neu!!: Theoretische Informatik und Leeres Wort · Mehr sehen »

Leerheitsproblem

Als Leerheitsproblem bezeichnet man in der theoretischen Informatik das Problem, zu entscheiden, ob eine in Form einer formalen Grammatik gegebene formale Sprache L leer ist, also L.

Neu!!: Theoretische Informatik und Leerheitsproblem · Mehr sehen »

Lemma von Arden

Das Lemma von Arden trifft eine Aussage über Mengen von Zeichenreihen, welche im Rahmen der formalen Sprachen Gegenstand der theoretischen Informatik, spezieller der Automatentheorie sind.

Neu!!: Theoretische Informatik und Lemma von Arden · 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 »

LF(k)-Grammatik

Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. ---- Eine LF(k)-Grammatik ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LF(k)-Parsers bildet.

Neu!!: Theoretische Informatik und LF(k)-Grammatik · Mehr sehen »

Lindenmayer-System

Künstliche Pflanzen, die durch 3D-L-Systeme generiert wurden Bei den Lindenmayer- oder L-Systemen handelt es sich um einen mathematischen Formalismus, der 1968 von dem ungarischen theoretischen Biologen Aristid Lindenmayer als Grundlage einer axiomatischen Theorie biologischer Entwicklung vorgeschlagen wurde.

Neu!!: Theoretische Informatik und Lindenmayer-System · Mehr sehen »

Linear beschränkte Turingmaschine

Eine linear beschränkte Turingmaschine (auch LBA.

Neu!!: Theoretische Informatik und Linear beschränkte Turingmaschine · Mehr sehen »

Lineare Sprache

Die Linearen Sprachen (englisch linear languages, LIN) sind ein Fachbegriff aus der Theoretischen Informatik.

Neu!!: Theoretische Informatik und Lineare Sprache · Mehr sehen »

Liste bedeutender Mathematiker

Diese Liste bedeutender Mathematiker stellt eine Auswahl von Mathematikern von der Antike bis zur Gegenwart dar.

Neu!!: Theoretische Informatik und Liste bedeutender Mathematiker · Mehr sehen »

Liste bedeutender Personen für die Informatik

Die Informatik ist eine junge, aber sehr breit gefächerte Wissenschaft, deren Entwicklung von unüberschaubar vielen Menschen vorangetrieben wurde.

Neu!!: Theoretische Informatik und Liste bedeutender Personen für die Informatik · Mehr sehen »

Liste von Informatikerinnen

Die Liste von Informatikerinnen enthält Informatikerinnen sowie Mathematikerinnen mit Schwerpunkt Informatik.

Neu!!: Theoretische Informatik und Liste von Informatikerinnen · Mehr sehen »

LL(k)-Grammatik

Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. ---- Eine LL(k)-Grammatik (im Gegensatz zu LF(k)-Grammatik auch schwache LL(k)-Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LL(k)-Parsers bildet.

Neu!!: Theoretische Informatik und LL(k)-Grammatik · 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 »

LOOP-Programm

LOOP-Programme sind Programme in der Programmiersprache LOOP, einer stark eingeschränkten, modellhaften Sprache, die nur die Formulierung von Additionen, Wertzuweisungen und endlich oft durchlaufende Schleifen erlaubt.

Neu!!: Theoretische Informatik und LOOP-Programm · Mehr sehen »

Louise Hay (Mathematikerin)

Louise Hay, um 1987 Louise Szmir Hay (* 14. Juni 1935 in Metz, Frankreich; † 28. Oktober 1989 in Oak Park (Illinois), USA) war eine französisch-amerikanische Mathematikerin und Hochschullehrerin.

Neu!!: Theoretische Informatik und Louise Hay (Mathematikerin) · Mehr sehen »

LR(k)-Grammatik

In der theoretischen Informatik und dem Compilerbau bezeichnet LR(k)-Grammatik eine spezielle kontextfreie Grammatik, welche die Grundlage eines LR-Parsers bildet.

Neu!!: Theoretische Informatik und LR(k)-Grammatik · Mehr sehen »

Ludwig Staiger

Ludwig Staiger (* 26. Februar 1948 in Jena) ist ein deutscher Mathematiker und Informatiker und emeritierter Professor an der Martin-Luther-Universität Halle-Wittenberg.

Neu!!: Theoretische Informatik und Ludwig Staiger · Mehr sehen »

Manfred Paul (Informatiker)

Manfred Paul (* 25. April 1932 in Berlin; † 18. September 2021 in Füssen) war ein deutscher Pionier der Informatik und erster ordentlicher Professor für Informatik an einer deutschen Universität.

Neu!!: Theoretische Informatik und Manfred Paul (Informatiker) · Mehr sehen »

Marian Kogler

Marian Kogler (* 19. Dezember 1991 in Wien) ist ein österreichischer Informatiker.

Neu!!: Theoretische Informatik und Marian Kogler · Mehr sehen »

Marta Kwiatkowska

Marta Kwiatkowska, 2018 Marta Zofia Kwiatkowska (* 26. Februar 1957) ist eine polnische theoretische Informatikerin wohnhaft im Vereinigten Königreich.

Neu!!: Theoretische Informatik und Marta Kwiatkowska · Mehr sehen »

Martin Ziegler (Mathematiker)

Martin Ziegler (* 1968) ist ein deutscher Mathematiker.

Neu!!: Theoretische Informatik und Martin Ziegler (Mathematiker) · 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 »

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 »

Matroids Matheplanet

Matroids Matheplanet ist eine deutschsprachige Internetplattform zum Austausch über Mathematik und angrenzende Gebiete wie Informatik und Physik.

Neu!!: Theoretische Informatik und Matroids Matheplanet · Mehr sehen »

Maut

Maut ist ein aus dem Althochdeutschen mūta (vgl. gotisch mōta) abgeleiteter Begriff für eine Zollabgabe im Sinne eines Wegzolls.

Neu!!: Theoretische Informatik und Maut · Mehr sehen »

Mautproblem

Das Mautproblem (englisch: Turnpike problem) ist ein Problem in der theoretischen Informatik.

Neu!!: Theoretische Informatik und Mautproblem · Mehr sehen »

Medwedew-Automat

In der theoretischen Informatik versteht man unter einem Medwedew-Automaten einen endlichen Automaten, dessen Ausgabe direkt der Zustand ist (während sie beim Moore-Automat mit einem eigenen Schaltwerk auf der Basis des Speicherzustandes generiert wird).

Neu!!: Theoretische Informatik und Medwedew-Automat · Mehr sehen »

Mehrband-Turingmaschine

Eine Mehrband-Turingmaschine ist eine abstrakte Maschine in der theoretischen Informatik und eine Erweiterung der klassischen Turingmaschine.

Neu!!: Theoretische Informatik und Mehrband-Turingmaschine · Mehr sehen »

Mehrspuren-Turingmaschine

Eine Mehrspuren-Turingmaschine ist eine abstrakte Maschine in der theoretischen Informatik und eine Erweiterung der klassischen Turingmaschine.

Neu!!: Theoretische Informatik und Mehrspuren-Turingmaschine · Mehr sehen »

Mercateo

Mercateo Deutschland AG (von ‚Kaufmann‘; bis September 2018 Mercateo AG) betreibt eine offene B2B-Handelsplattform im Internet.

Neu!!: Theoretische Informatik und Mercateo · Mehr sehen »

Mereologie

Die Mereologie (griech. μέρος meros ‚Teil‘) ist ein Teilgebiet der Ontologie und der angewandten Logik und befasst sich mit dem Verhältnis zwischen Teil und Ganzem.

Neu!!: Theoretische Informatik und Mereologie · Mehr sehen »

Mereotopologie

Die Mereotopologie ist eine formale Theorie, die Mereologie und Topologie miteinander verbindet.

Neu!!: Theoretische Informatik und Mereotopologie · Mehr sehen »

Michael Huber (Mathematiker)

Michael Huber (* 22. Dezember 1972 in Geislingen/Steige) ist ein deutscher Mathematiker und Informatiker.

Neu!!: Theoretische Informatik und Michael Huber (Mathematiker) · Mehr sehen »

Monadische Prädikatenlogik zweiter Stufe

Die monadische Prädikatenlogik zweiter Stufe, nach dem englischen monadic second order logic auch kurz MSO genannt, ist ein Begriff aus dem Bereich der mathematischen Logik.

Neu!!: Theoretische Informatik und Monadische Prädikatenlogik zweiter Stufe · Mehr sehen »

Moses S. Charikar

Moses S. Charikar (* in Mumbai) ist ein indisch-US-amerikanischer theoretischer Informatiker.

Neu!!: Theoretische Informatik und Moses S. Charikar · Mehr sehen »

Mutex

Der Begriff wechselseitiger Ausschluss bzw.

Neu!!: Theoretische Informatik und Mutex · Mehr sehen »

Neil Immerman

Neil Immerman (2010) Neil Immerman (* 24. November 1953 in Manhasset, New York) ist ein amerikanischer Wissenschaftler im Bereich der theoretischen Informatik und Professor an der University of Massachusetts Amherst.

Neu!!: Theoretische Informatik und Neil Immerman · Mehr sehen »

Nerode-Relation

Die Nerode-Relation (auch: Nerode-Kongruenz oder Nerode-Rechtskongruenz) ist eine Äquivalenzrelation auf den Präfixen einer formalen Sprache, die in der Theoretischen Informatik untersucht wird.

Neu!!: Theoretische Informatik und Nerode-Relation · Mehr sehen »

Netzwerkökonomik

Als Netzwerkökonomik (auch Netz(werk)ökonomie) wird eine interdisziplinäre Wissenschaft bezeichnet, die sich mit wirtschaftlichen Aspekten von Netzwerken befasst.

Neu!!: Theoretische Informatik und Netzwerkökonomik · Mehr sehen »

Nichtdeterminismus

Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem Algorithmen oder Maschinen (meist Turingmaschinen oder endliche Automaten) nicht nur genau eine Berechnung zu einer bestimmten Eingabe durchlaufen können (deterministisch), sondern es bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand gibt.

Neu!!: Theoretische Informatik und Nichtdeterminismus · Mehr sehen »

Nichtdeterministische Turingmaschine

Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.

Neu!!: Theoretische Informatik und Nichtdeterministische Turingmaschine · Mehr sehen »

Nick Pippenger

Nicholas „Nick“ Pippenger (* 1947) ist ein US-amerikanischer Forscher im Bereich der theoretischen Informatik.

Neu!!: Theoretische Informatik und Nick Pippenger · Mehr sehen »

Nicole Megow

Nicole Megow (* 25. Dezember 1976 in Dessau) ist eine deutsche Mathematikerin und Theoretische Informatikerin.

Neu!!: Theoretische Informatik und Nicole Megow · 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 »

Norbert Blum

Norbert Blum (* 1954 in Neustadt an der Weinstraße) ist ein deutscher theoretischer Informatiker und Hochschullehrer an der Universität Bonn.

Neu!!: Theoretische Informatik und Norbert Blum · Mehr sehen »

Normalform

Eine Normalform (auch kanonische Form) ist eine mathematische Darstellung mit bestimmten von der Art der Normalform vorgegebenen Eigenschaften.

Neu!!: Theoretische Informatik und Normalform · Mehr sehen »

NP-Schwere

NP-vollständigen Probleme. Zu beachten ist, dass auf der rechten Seite die leere Sprache und ihr Komplement außen vor gelassen werden (beide sind zwar in P und NP, aber nicht NP-schwer). NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer lösbar zu sein wie die Probleme der Klasse NP.

Neu!!: Theoretische Informatik und NP-Schwere · 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 »

NSPACE

NSPACE (selten auch NTAPE, von englisch: Non-deterministic Turing machine tape) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der theoretischen Informatik.

Neu!!: Theoretische Informatik und NSPACE · Mehr sehen »

Ogdens Lemma

Ogdens Lemma, benannt nach William Ogden, ist eine Methode der theoretischen Informatik, mit der gezeigt werden kann, dass eine formale Sprache keine kontextfreie Sprache ist, da sie Eigenschaften beschreibt, die für alle kontextfreien Sprachen gelten müssen.

Neu!!: Theoretische Informatik und Ogdens Lemma · Mehr sehen »

Orakel-Turingmaschine

Eine Orakel-Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist.

Neu!!: Theoretische Informatik und Orakel-Turingmaschine · Mehr sehen »

Otto-von-Guericke-Universität Magdeburg

Luftbild des Hauptcampus der Universität Die Otto-von-Guericke-Universität Magdeburg (kurz: OVGU) ist eine öffentliche Universität in Sachsen-Anhalt.

Neu!!: Theoretische Informatik und Otto-von-Guericke-Universität Magdeburg · Mehr sehen »

P-NP-Problem

Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Komplexitätstheorie in der theoretischen Informatik.

Neu!!: Theoretische Informatik und P-NP-Problem · Mehr sehen »

P/poly

In der Komplexitätstheorie ist P/poly die Komplexitätsklasse von Sprachen die von polynomzeit-beschränkten Turing-Maschinen mit polynomiell beschränkter Hinweisfunktion erkannt werden.

Neu!!: Theoretische Informatik und P/poly · Mehr sehen »

Palindrom

Als Palindrom („rückwärts laufend“) werden in der Sprachwissenschaft Wörter, Wortreihen oder Sätze bezeichnet, die rückwärts gelesen genau denselben Text oder zumindest einen Sinn ergeben.

Neu!!: Theoretische Informatik und Palindrom · Mehr sehen »

Paralleler Algorithmus

Ein paralleler Algorithmus ist ein Algorithmus, welcher zum Beispiel ein Problem der Komplexitätsklasse NC (Nick’s Class nach Nick Pippenger) in polynomieller Zeit lösen bzw.

Neu!!: Theoretische Informatik und Paralleler Algorithmus · 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 »

Partielle Funktion

Eine partielle Funktion von der Menge X nach der Menge Y ist eine binäre, rechtseindeutige Relation, das heißt eine Relation, in der jedem Element der Menge X höchstens ein Element der Menge Y zugeordnet wird.

Neu!!: Theoretische Informatik und Partielle Funktion · Mehr sehen »

Patricia Bouyer-Decitre

Patricia Bouyer-Decitre Patricia Bouyer-Decitre (* 18. Oktober 1976) ist eine französische Informatikerin.

Neu!!: Theoretische Informatik und Patricia Bouyer-Decitre · Mehr sehen »

PCP-Theorem

Das PCP-Theorem ist ein Satz aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik.

Neu!!: Theoretische Informatik und PCP-Theorem · Mehr sehen »

Peter Rossmanith

Peter Rossmanith (* 31. Oktober 1965 in Turnov, Tschechoslowakei) ist ein tschechisch-deutscher Informatiker und Hochschullehrer, der 1969 als Kind von der damaligen Tschechoslowakei nach Deutschland kam.

Neu!!: Theoretische Informatik und Peter Rossmanith · Mehr sehen »

Peter van Emde Boas

Peter van Emde Boas (* um 1944) ist ein niederländischer Informatiker.

Neu!!: Theoretische Informatik und Peter van Emde Boas · Mehr sehen »

Petri-Netz

Als Petri-Netze werden Modelle diskreter, vorwiegend verteilter Systeme bezeichnet.

Neu!!: Theoretische Informatik und Petri-Netz · Mehr sehen »

Pfannkuchen-Sortierproblem

Das Pfannkuchen-Sortierproblem ist ein Problem aus dem Bereich der diskreten Mathematik bzw.

Neu!!: Theoretische Informatik und Pfannkuchen-Sortierproblem · Mehr sehen »

Philosophenproblem

Aufbau des Philosophenproblems Beim Philosophenproblem handelt es sich um ein Fallbeispiel aus dem Bereich der theoretischen Informatik.

Neu!!: Theoretische Informatik und Philosophenproblem · Mehr sehen »

Philosophische Logik

Der Ausdruck philosophische Logik wird auf mehrfache Weise verwendet.

Neu!!: Theoretische Informatik und Philosophische Logik · Mehr sehen »

Phrasenstrukturgrammatik

Der Begriff Phrasenstrukturgrammatik (englisch phrase structure grammar) bezeichnet formale Grammatiken, die nach dem Konstituenten-Prinzip einen Satz schrittweise in kleinere Einheiten zerlegen.

Neu!!: Theoretische Informatik und Phrasenstrukturgrammatik · Mehr sehen »

Polynomialzeitreduktion

Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik.

Neu!!: Theoretische Informatik und Polynomialzeitreduktion · Mehr sehen »

Postsches Korrespondenzproblem

Das Postsche Korrespondenzproblem (nach Emil Leon Post, abgekürzt auch PKP oder englisch PCP) ist ein Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik.

Neu!!: Theoretische Informatik und Postsches Korrespondenzproblem · Mehr sehen »

Potenzautomat

Ein Potenzautomat ist ein Begriff der theoretischen Informatik.

Neu!!: Theoretische Informatik und Potenzautomat · Mehr sehen »

Praktische Informatik

Die Praktische Informatik (PI) ist eines der Hauptgebiete der Informatik.

Neu!!: Theoretische Informatik und Praktische Informatik · Mehr sehen »

Presburger Award

Der Presburger Award ist eine Auszeichnung, die seit 2010 jährlich von der European Association for Theoretical Computer Science (EATCS) an einen jungen Nachwuchswissenschaftler für außergewöhnliche Beiträge auf dem Gebiet der theoretischen Informatik verliehen wird.

Neu!!: Theoretische Informatik und Presburger Award · Mehr sehen »

Primitiv-rekursive Funktion

Primitiv-rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können.

Neu!!: Theoretische Informatik und Primitiv-rekursive Funktion · Mehr sehen »

Probabilistische Turingmaschine

Eine probabilistische Turingmaschine, abgekürzt PTM, ist ein Konzept aus der theoretischen Informatik.

Neu!!: Theoretische Informatik und Probabilistische Turingmaschine · 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 »

Problem des Handlungsreisenden

größten Städte Deutschlands. Die angegebene Route ist die kürzeste von formatnum:43589145600 möglichen. Das Problem des Handlungsreisenden (auch Problem des Handelsreisenden, Botenproblem, Rundreiseproblem, engl. Traveling Salesman Problem oder Traveling Salesperson Problem (TSP)) ist ein kombinatorisches Optimierungsproblem des Operations Research und der theoretischen Informatik.

Neu!!: Theoretische Informatik und Problem des Handlungsreisenden · Mehr sehen »

Problemkern

In der theoretischen Informatik bezeichnet der Problemkern (engl. problemkernel) den algorithmisch „schwierig“ entscheidbaren Teil einer Instanz eines NP-Schweren Problems.

Neu!!: Theoretische Informatik und Problemkern · Mehr sehen »

Produktionsregel

Eine Produktionsregel (auch Regel, Produktion oder Ersetzungsregel genannt) ist in der Theorie formaler Grammatiken eine Regel, die angibt, wie aus Wörtern durch eine Grammatik neue Wörter bzw.

Neu!!: Theoretische Informatik und Produktionsregel · Mehr sehen »

Programmäquivalenz

Programmäquivalenz besagt, dass zwei Computerprogramme (oder zwei Algorithmen) dieselbe Funktion berechnen.

Neu!!: Theoretische Informatik und Programmäquivalenz · Mehr sehen »

Pumping-Lemma

Das Pumping-Lemma bzw.

Neu!!: Theoretische Informatik und Pumping-Lemma · Mehr sehen »

Q (Komplexitätsklasse)

Die Klasse Q, auch bekannt unter dem Namen Quasi-Realzeit-Sprachen, ist ein Begriff der Theoretischen Informatik, speziell der Komplexitätstheorie.

Neu!!: Theoretische Informatik und Q (Komplexitätsklasse) · Mehr sehen »

Quadratfreies Wort

Unter einem quadratfreien Wort (englisch squarefree word) versteht man in der Theoretischen Informatik ein Wort, das kein (nicht-leeres) Quadrat eines anderen Wortes enthält.

Neu!!: Theoretische Informatik und Quadratfreies Wort · Mehr sehen »

Quantencomputer

Ein Quantenprozessor bzw.

Neu!!: Theoretische Informatik und Quantencomputer · Mehr sehen »

Rechtsableitung

Eine Rechtsableitung (auch rechtskanonische Ableitung) ist in der Theoretischen Informatik eine Folge von Ableitungsschritten, bei der stets das am weitesten rechts stehende sogenannte Nichtterminalsymbol durch Anwendung einer Produktionsregel ersetzt wird.

Neu!!: Theoretische Informatik und Rechtsableitung · Mehr sehen »

Rechtsreduktion

Rechtsreduktion ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine umgedrehte Rechtsableitung.

Neu!!: Theoretische Informatik und Rechtsreduktion · Mehr sehen »

Reduktion (theoretische Informatik)

Die Reduktion ist eine Methode der theoretischen Informatik, bei der ein Problem auf ein anderes zurückgeführt wird.

Neu!!: Theoretische Informatik und Reduktion (theoretische Informatik) · Mehr sehen »

Reduktionssystem

In der Mathematischen Logik und der Theoretischen Informatik steht die Bezeichnung Reduktionssystem, oder abstraktes Reduktionssystem, abgekürzt ARS, für eine Verallgemeinerung von Termersetzungssystemen.

Neu!!: Theoretische Informatik und Reduktionssystem · Mehr sehen »

Registermaschine

Die Registermaschine (RM) ist eine abstrakte Maschine der theoretischen Informatik.

Neu!!: Theoretische Informatik und Registermaschine · 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 »

Regulärer Ausdruck

Ein regulärer Ausdruck (Abkürzung RegExp oder Regex) ist in der theoretischen Informatik eine Zeichenkette, die der Beschreibung von Mengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient.

Neu!!: Theoretische Informatik und Regulärer Ausdruck · Mehr sehen »

Rekursion

Unendlichfache Spiegelung als Beispiel für '''Rekursion''': Die Person sitzt mit vorgehaltenem Spiegel einem größeren Wandspiegel gegenüber. Das jeweils folgende Spiegelbild enthält sich selbst als Teil. Als Rekursion wird ein prinzipiell unendlicher Vorgang, der sich selbst als Teil enthält oder mithilfe von sich selbst definierbar ist, bezeichnet.

Neu!!: Theoretische Informatik und Rekursion · Mehr sehen »

Rekursionssatz

Die Rekursionssätze sind drei Resultate der Theoretischen Informatik, genauer der Berechenbarkeitstheorie, von Kleene, Rogers und Case.

Neu!!: Theoretische Informatik und Rekursionssatz · Mehr sehen »

Rekursiv aufzählbare Sprache

In der theoretischen Informatik ist eine rekursiv aufzählbare Sprache (auch bekannt als semientscheidbare oder erkennbare Sprache) L dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen.

Neu!!: Theoretische Informatik und Rekursiv aufzählbare Sprache · Mehr sehen »

Rekursive Sprache

In der theoretischen Informatik heißt eine formale Sprache L über einem Alphabet \Sigma rekursiv (entscheidbar), wenn eine Turingmaschine M existiert, die auf allen Eingaben w \in \Sigma^* hält und jede Eingabe w \in \Sigma^* genau dann akzeptiert, wenn w \in L ist.

Neu!!: Theoretische Informatik und Rekursive Sprache · Mehr sehen »

René Heinzl

René Heinzl als Speaker bei A1 Keynote René Heinzl (* 6. September 1977 in Wien) ist ein österreichischer Unternehmer mit einem Hintergrund in Technologieberatung und Industrieautomatisierung.

Neu!!: Theoretische Informatik und René Heinzl · Mehr sehen »

Retraceable Menge

Eine Menge natürlicher Zahlen heißt retraceable (engl.: zurückverfolgbar), wenn zu jedem Element der Menge das nächstkleinere Element berechnet werden kann.

Neu!!: Theoretische Informatik und Retraceable Menge · Mehr sehen »

Robert Fano

Robert Mario Fano (* 11. November 1917 in Turin, Italien als Roberto Mario Fano; † 13. Juli 2016 in Naples, Florida) war ein italienisch-US-amerikanischer Informatiker.

Neu!!: Theoretische Informatik und Robert Fano · 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 »

Ronen Eldan

Ronen Eldan 2020 Ronen Eldan (* 1980 in Tel Aviv) ist ein israelischer Mathematiker, der sich mit Wahrscheinlichkeitstheorie, geometrischer Funktionalanalysis, metrischer, konvexer und algorithmischer Geometrie, Optimierung, Kombinatorik, mathematischer Physik, theoretischer Informatik und Maschinenlernen befasst.

Neu!!: Theoretische Informatik und Ronen Eldan · Mehr sehen »

Rudolf Freund (Informatiker)

Rudolf Freund (geboren am 15. Jänner 1956 in Wien) ist ein österreichischer Informatiker und Mathematiker.

Neu!!: Theoretische Informatik und Rudolf Freund (Informatiker) · Mehr sehen »

SameGame

SameGame, auch The Same Game ist ein populäres Computer-Puzzlespiel, das in verschiedensten Varianten auf einer Vielzahl von Plattformen implementiert wurde.

Neu!!: Theoretische Informatik und SameGame · Mehr sehen »

Satz von Ladner

Der Satz von Ladner ist ein Satz aus der theoretischen Informatik, der sich mit der Struktur der Komplexitätsklasse NP in Bezug auf P befasst.

Neu!!: Theoretische Informatik und Satz von Ladner · Mehr sehen »

Satz von Myhill-Nerode

Der Satz von Myhill-Nerode gibt im Fachgebiet Formale Sprachen der Theoretischen Informatik ein notwendiges und hinreichendes Kriterium dafür an, dass eine formale Sprache regulär ist.

Neu!!: Theoretische Informatik und Satz von Myhill-Nerode · Mehr sehen »

Satz von Rice

Der Satz von Rice ist ein Ergebnis der Theoretischen Informatik.

Neu!!: Theoretische Informatik und Satz von Rice · Mehr sehen »

Schnittproblem

Das Schnittproblem ist ein Problem der theoretischen Informatik.

Neu!!: Theoretische Informatik und Schnittproblem · Mehr sehen »

Schwere und Vollständigkeit (theoretische Informatik)

In der theoretischen Informatik – insbesondere in der Berechenbarkeits- und der Komplexitätstheorie – bezeichnet die Schwere (Übersetzung von engl. hardness dt. „Schwierigkeit“) eines Problems dessen Eigenschaft, mindestens so schwierig lösbar zu sein wie alle Probleme einer betrachteten Klasse.

Neu!!: Theoretische Informatik und Schwere und Vollständigkeit (theoretische Informatik) · Mehr sehen »

Scott-Topologie

Die Scott-Topologie, benannt nach Dana Scott, ist eine Topologie, die sich aus der Halbordnung auf einer halbgeordneten Menge ergibt.

Neu!!: Theoretische Informatik und Scott-Topologie · Mehr sehen »

Semantik (Logik)

In der Logik beschäftigt sich die Semantik mit der exakten Bedeutung von Termen in Sprachen.

Neu!!: Theoretische Informatik und Semantik (Logik) · Mehr sehen »

Semi-Thue-System

Semi-Thue-System (oder auch Umformungssystem, Wortersetzungssystem oder Stringersetzungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Transformation von Wörtern.

Neu!!: Theoretische Informatik und Semi-Thue-System · Mehr sehen »

Seymour Ginsburg

Seymour Ginsburg (* 12. Dezember 1927 in Brooklyn; † 5. Dezember 2004) war ein US-amerikanischer Informatiker.

Neu!!: Theoretische Informatik und Seymour Ginsburg · Mehr sehen »

Shafrira Goldwasser

Shafrira Goldwasser Shafrira „Shafi“ Goldwasser (* 1958 in New York City) ist eine US-amerikanische Informatikerin.

Neu!!: Theoretische Informatik und Shafrira Goldwasser · Mehr sehen »

Sheila A. Greibach

Sheila Adele Greibach (* 6. Oktober 1939 in New York City) ist eine Mathematikerin und arbeitet hauptsächlich in der theoretischen Informatik.

Neu!!: Theoretische Informatik und Sheila A. Greibach · Mehr sehen »

Sigma

Der griechische Buchstabe Sigma (griechisches Neutrum σίγμα oder σῖγμα, neugriechisches Neutrum Σίγμα; Majuskel Σ, Minuskel im Wort σ, Minuskel am Wortende ς) ist der 18. Buchstabe des griechischen Alphabets und hat nach dem milesischen System den Zahlwert 200.

Neu!!: Theoretische Informatik und Sigma · Mehr sehen »

Simons Foundation

Die Simons Foundation ist eine von dem Mathematiker und Hedge-Fonds-Manager James Simons und seiner Frau Marilyn Simons gegründete Stiftung.

Neu!!: Theoretische Informatik und Simons Foundation · Mehr sehen »

Software

Software (dt.

Neu!!: Theoretische Informatik und Software · Mehr sehen »

Sprache

Unter Sprache versteht man im allgemeinen Sinn alle komplexen Systeme der Kommunikation.

Neu!!: Theoretische Informatik und Sprache · Mehr sehen »

Spursprache

In der Theoretischen Informatik versteht man unter einer Spursprache eine Formale Sprache, die parallel ausführbare Prozesse modelliert.

Neu!!: Theoretische Informatik und Spursprache · 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 »

Sternhöhe (Informatik)

Die Sternhöhe ist ein Begriff aus der Theoretischen Informatik.

Neu!!: Theoretische Informatik und Sternhöhe (Informatik) · Mehr sehen »

Stirling-Zahl

Die Stirling-Zahlen erster und zweiter Art, benannt nach James Stirling, werden in der Kombinatorik und der theoretischen Informatik verwendet.

Neu!!: Theoretische Informatik und Stirling-Zahl · Mehr sehen »

Strukturelle Induktion

Die strukturelle Induktion ist ein Beweisverfahren, das unter anderem in der Logik, der theoretischen Informatik und der Graphentheorie eingesetzt wird.

Neu!!: Theoretische Informatik und Strukturelle Induktion · 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 »

Suchproblem

Als Suchproblem bezeichnet man in der theoretischen Informatik ein Problem, bei dem zu einer gegebenen Eingabe eine bestmögliche Lösung gesucht ist.

Neu!!: Theoretische Informatik und Suchproblem · Mehr sehen »

Susanne Albers

Von links: Torben Hagerup, Susanne Albers, David P. Williamson, Kurt Mehlhorn, Oberwolfach 2003 Susanne Albers (* 10. Juni 1965 in Georgsmarienhütte) ist eine deutsche Informatikerin und Inhaberin des Lehrstuhl XIV Theoretische Informatik an der Fakultät für Informatik der Technischen Universität München.

Neu!!: Theoretische Informatik und Susanne Albers · Mehr sehen »

Syntaxbaum

Ein Syntax-, Ableitungs- oder Parsebaum ist ein Begriff aus der theoretischen Informatik und der Linguistik.

Neu!!: Theoretische Informatik und Syntaxbaum · 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 »

Tadao Kasami

Tadao Kasami (jap. 嵩忠雄, Kasami Tadao; * 12. April 1930 in Kōbe, Japan; † 18. März 2007) war ein japanischer Informatiker und Elektrotechniker mit Arbeiten auf dem Gebiet der Fehlerkorrekturverfahren, einem Teilgebiet der Codierungstheorie und der Informationstheorie.

Neu!!: Theoretische Informatik und Tadao Kasami · Mehr sehen »

TC

Die Abkürzung TC steht für.

Neu!!: Theoretische Informatik und TC · Mehr sehen »

Termersetzungssystem

Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik.

Neu!!: Theoretische Informatik und Termersetzungssystem · Mehr sehen »

Terminiertheit

Terminiertheit ist ein Begriff aus der Berechenbarkeitstheorie, einem Teilgebiet der theoretischen Informatik.

Neu!!: Theoretische Informatik und Terminiertheit · Mehr sehen »

TGI

TGI steht als Abkürzung für.

Neu!!: Theoretische Informatik und TGI · Mehr sehen »

Thomas Bruderer

Thomas Bruderer (* 26. Februar 1982) ist ein Schweizer Softwareingenieur und war in der Zeit vom 1.

Neu!!: Theoretische Informatik und Thomas Bruderer · Mehr sehen »

Thomas Schwentick

Thomas Schwentick (* 1963) ist ein deutscher Informatiker und Hochschullehrer.

Neu!!: Theoretische Informatik und Thomas Schwentick · Mehr sehen »

TI

TI steht für.

Neu!!: Theoretische Informatik und TI · Mehr sehen »

Transduktor (Informatik)

Ein Transduktor ist in der theoretischen Informatik ein spezieller endlicher Automat.

Neu!!: Theoretische Informatik und Transduktor (Informatik) · Mehr sehen »

Transitionssystem

Ein Transitionssystem (englisch transition system) beschreibt in der Automatentheorie die möglichen Zustände eines zustandsbasierten Systems und die möglichen Übergänge (Transitionen) zwischen diesen Zuständen.

Neu!!: Theoretische Informatik und Transitionssystem · Mehr sehen »

Transitive Hülle (Relation)

Die transitive Hülle bzw.

Neu!!: Theoretische Informatik und Transitive Hülle (Relation) · Mehr sehen »

TUM Department of Computer Science

Außenansicht des Fakultätsgebäudes für Mathematik und Informatik in Garching Innenansicht des Fakultätsgebäudes für Mathematik und Informatik in Garching Das Department of Computer Science der Technischen Universität München (TUM) ist eine der führenden Informatikfakultäten in Deutschland.

Neu!!: Theoretische Informatik und TUM Department of Computer Science · Mehr sehen »

Turing Award

Der nach Alan Turing benannte A. M. Turing Award wird jährlich von der Association for Computing Machinery (ACM) an Personen verliehen, die sich besonders um die Entwicklung der Informatik verdient gemacht haben.

Neu!!: Theoretische Informatik und Turing Award · Mehr sehen »

Turingmaschine

Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.

Neu!!: Theoretische Informatik und Turingmaschine · Mehr sehen »

Turingmaschine mit Zusatzeingabe

Eine Turingmaschine mit Zusatzeingabe ist ein zu nichtdeterministischen Turingmaschinen äquivalentes Berechnungsmodell der theoretischen Informatik.

Neu!!: Theoretische Informatik und Turingmaschine mit Zusatzeingabe · Mehr sehen »

Typentheorie

In mathematischer Logik und theoretischer Informatik sind Typentheorien formale Systeme, in denen jeder Term einen Typ hat und Operationen auf bestimmte Typen beschränkt sind.

Neu!!: Theoretische Informatik und Typentheorie · Mehr sehen »

Ulrike Meyer

Ulrike Meyer (* 23. Januar 1973 in Leutkirch im Allgäu) ist eine deutsche Informatikerin und leitet seit Mitte August 2008 als Universitätsprofessorin das Lehr- und Forschungsgebiet IT-Security in der Fakultät für Mathematik, Informatik und Naturwissenschaften der RWTH Aachen.

Neu!!: Theoretische Informatik und Ulrike Meyer · Mehr sehen »

Ulrike von Luxburg

Ulrike von Luxburg (* 1975 in Regensburg) ist eine deutsche Informatikerin und Leiterin der Arbeitsgruppe Theory of Machine Learning am Wilhelm-Schickard-Institut der Mathematisch-Naturwissenschaftlichen Fakultät der Eberhard Karls Universität Tübingen.

Neu!!: Theoretische Informatik und Ulrike von Luxburg · Mehr sehen »

Unärsystem

Bierdeckel mit Strichliste Das Unärsystem, umgangssprachlich auch Bierdeckelnotation genannt, ist ein Additionssystem, das nur ein Symbol mit der Wertigkeit 1 besitzt.

Neu!!: Theoretische Informatik und Unärsystem · Mehr sehen »

Universität Paderborn

306x306px Die Universität Paderborn in Paderborn, Deutschland, ist eine 1972 gegründete Universität in Nordrhein-Westfalen.

Neu!!: Theoretische Informatik und Universität Paderborn · Mehr sehen »

Uwe Nestmann

Uwe Nestmann (* 1967 in Coburg) ist ein deutscher Informatiker und Hochschullehrer.

Neu!!: Theoretische Informatik und Uwe Nestmann · 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 »

Vasco Brattka

Vasco Brattka ist ein deutscher Mathematiker und Informatiker und Professor für Theoretische Informatik und Mathematische Logik an der Universität der Bundeswehr München.

Neu!!: Theoretische Informatik und Vasco Brattka · Mehr sehen »

Verfeinerung (Informatik)

Unter Verfeinerung versteht man in der Informatik ein Verfahren, bei dem aus einer abstrakten Beschreibung (z. B. Registermaschine, formale Spezifikation mittels Z-Notation) eine konkretere Beschreibung abgeleitet wird.

Neu!!: Theoretische Informatik und Verfeinerung (Informatik) · Mehr sehen »

Verifizierung

Verifizierung oder Verifikation (von und facere ‚machen‘) ist der Nachweis, dass ein vermuteter oder behaupteter Sachverhalt wahr ist.

Neu!!: Theoretische Informatik und Verifizierung · Mehr sehen »

Verkettungszeichen

Das Verkettungszeichen (\circ), auch als Kreisoperator bezeichnet, ist ein mathematisches Zeichen, das die Verkettung zweier Funktionen, Relationen oder Wörter ausdrückt.

Neu!!: Theoretische Informatik und Verkettungszeichen · Mehr sehen »

Verzögerte Initialisierung

In der Computer-Programmierung ist eine verzögerte Initialisierung ein Entwurfsmuster, das die Erstellung eines Objekts, die Berechnung eines Werts oder eines anderen teuren Prozesses erst dann erstellt, wenn es erstmals benötigt wird.

Neu!!: Theoretische Informatik und Verzögerte Initialisierung · Mehr sehen »

Volker Claus

Volker Claus (* 22. Juni 1944 bei Berlin) ist ein deutscher Informatiker und ehemaliger Hochschullehrer.

Neu!!: Theoretische Informatik und Volker Claus · Mehr sehen »

Wachsend kontextsensitive Sprache

Wachsend kontextsensitive Sprachen (abgekürzt: GCSL) sind ein Begriff aus der Theorie der Formalen Sprachen, einem Teilgebiet der Theoretischen Informatik.

Neu!!: Theoretische Informatik und Wachsend kontextsensitive Sprache · Mehr sehen »

Walter Savitch

Walter John Savitch (* 21. Februar 1943; † 1. Februar 2021) war Professor für Informatik an der University of California, San Diego.

Neu!!: Theoretische Informatik und Walter Savitch · Mehr sehen »

Władysław Matwin

Władysław Matwin (1959) Władysław Wojciech Matwin (* 17. Juli 1916 in Grodziec, heute: Będzin; † 22. Oktober 2012 in Warschau) war ein Politiker der Polnischen Vereinigten Arbeiterpartei PZPR (Polska Zjednoczona Partia Robotnicza), Mathematiker und Informatiker in der Volksrepublik Polen, der unter anderem zwischen 1952 und 1965 Mitglied des Sejm, von 1953 bis 1957 Chefredakteur der Parteizeitung Trybuna Ludu sowie zugleich zwischen 1955 und 1963 Sekretär des Zentralkomitees (ZK) der PZPR war.

Neu!!: Theoretische Informatik und Władysław Matwin · Mehr sehen »

WHILE-Programm

WHILE-Programme spielen in der Theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit.

Neu!!: Theoretische Informatik und WHILE-Programm · Mehr sehen »

Wilfried Brauer

Wilfried Brauer 1995 Wilfried Brauer (* 8. August 1937 in Berlin; † 25. Februar 2014 in Bonn) war ein deutscher Informatiker.

Neu!!: Theoretische Informatik und Wilfried Brauer · Mehr sehen »

Wilhelm Ackermann (Mathematiker)

Wilhelm Ackermann (ca. 1935) Wilhelm Friedrich Ackermann (* 29. März 1896 in Schönebecke (Herscheid); † 24. Dezember 1962 in Lüdenscheid) war ein deutscher Mathematiker.

Neu!!: Theoretische Informatik und Wilhelm Ackermann (Mathematiker) · Mehr sehen »

Wirkung (Informatik)

In der theoretischen Informatik bezeichnet eine (spezifizierte) Wirkung die Veränderung des Zustands, in dem sich eine abstrakte Maschine befindet.

Neu!!: Theoretische Informatik und Wirkung (Informatik) · Mehr sehen »

Wolfgang Ertel (Informatiker)

Wolfgang Ertel (* 1959 in Laufenburg) ist ein deutscher Informatiker und Hochschullehrer.

Neu!!: Theoretische Informatik und Wolfgang Ertel (Informatiker) · Mehr sehen »

Wolfram Menzel

Wolfram Menzel Wolfram Menzel (* 6. Juli 1933 in Marienbad; † 5. Oktober 2022 in Karlsruhe) war ein Informatiker und Mathematiker, der bis zu seiner Emeritierung im Jahr 2001 an der Universität Karlsruhe im Bereich der Theoretischen Informatik tätig war.

Neu!!: Theoretische Informatik und Wolfram Menzel · Mehr sehen »

Wort (theoretische Informatik)

In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets.

Neu!!: Theoretische Informatik und Wort (theoretische Informatik) · Mehr sehen »

Wortfunktion

Eine Wortfunktion ist eine Funktion, die von einer k-stelligen Wortmenge in eine Wortmenge führt.

Neu!!: Theoretische Informatik und Wortfunktion · Mehr sehen »

Wortproblem (Berechenbarkeitstheorie)

Als Wortproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort festzustellen, ob dieses zur Sprache gehört oder nicht.

Neu!!: Theoretische Informatik und Wortproblem (Berechenbarkeitstheorie) · Mehr sehen »

Zahlenfunktion

Eine Zahlenfunktion ist eine Funktion, die Tupel von natürlichen Zahlen auf natürliche Zahlen abbildet.

Neu!!: Theoretische Informatik und Zahlenfunktion · Mehr sehen »

Zeichenkette

Eine Zeichenkette, Zeichenfolge, Zeichenreihe oder ein String (aus dem Englischen) ist in der Informatik eine endliche Folge von Zeichen (z. B. Buchstaben, Ziffern, Sonderzeichen und Steuerzeichen) aus einem definierten Zeichensatz.

Neu!!: Theoretische Informatik und Zeichenkette · Mehr sehen »

Zustandsraum (Informatik)

In der theoretischen Informatik ist ein Zustandsraum eine Beschreibung von diskreten Zuständen, um sie als einfaches Modell von Maschinen zu verwenden (z. B. Endliche Automaten) (nicht zu verwechseln mit dem Zustandsraum (Neuronales Netz) in der Neuroinformatik).

Neu!!: Theoretische Informatik und Zustandsraum (Informatik) · Mehr sehen »

Zweikellerautomat

Der Begriff Zweikellerautomat (TPDA – engl. Two-stack Push Down Automaton) steht in der Theoretischen Informatik für ein besonderes Automatenmodell.

Neu!!: Theoretische Informatik und Zweikellerautomat · Mehr sehen »

2020

Das Jahr 2020 war durch die COVID-19-Pandemie geprägt, die zahlreiche Einschränkungen im gesellschaftlichen und wirtschaftlichen Bereich zur Folge hatte.

Neu!!: Theoretische Informatik und 2020 · Mehr sehen »

Leitet hier um:

Theoretische Informationswissenschaft, Theoretische informatik.

AusgehendeEingehende
Hallo! Wir sind auf Facebook! »