„Portal:Informatik/TheoretischeInformatik“ – Versionsunterschied
+Transduktor |
K -bkllinks |
||
| Zeile 35: | Zeile 35: | ||
'''[[Formale Sprache]]n und [[Automat (Informatik)|Automaten]]:'''<br/> |
'''[[Formale Sprache]]n und [[Automat (Informatik)|Automaten]]:'''<br/> |
||
[[Akzeptor]] |
[[Akzeptor (Informatik)|Akzeptor]] |
||
· [[Datei:Qsicon lesenswert.svg|12px]] [[Backus-Naur-Form]] |
· [[Datei:Qsicon lesenswert.svg|12px]] [[Backus-Naur-Form]] |
||
· [[Chomsky-Hierarchie]] |
· [[Chomsky-Hierarchie]] |
||
| Zeile 42: | Zeile 42: | ||
· [[Regulärer Ausdruck]] |
· [[Regulärer Ausdruck]] |
||
· [[Reguläre Sprache]] |
· [[Reguläre Sprache]] |
||
· [[Transduktor]] |
· [[Transduktor (Informatik)|Transduktor]] |
||
· [[Turingmaschine]] |
· [[Turingmaschine]] |
||
Version vom 14. Oktober 2012, 00:41 Uhr
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. Weiterlesen...
Grundlagen:
Bit
· Boolesche Algebra
· Boolesche Funktion
· Formale Semantik
· Gödelscher Unvollständigkeitssatz
· Informationsgehalt
· Informationstheorie
· Kodierungstheorie
· 
Logik
· 
Problem des Handlungsreisenden
Berechenbarkeitstheorie:
Ackermannfunktion
· Berechenbarkeit
· Church-Turing-These
· Entscheidbarkeit
· Halteproblem
· Lambda-Kalkül
· µ-Rekursion
· Satz von Rice
· Türme von Hanoi
Komplexitätstheorie:
Damenproblem
· Komplexitätsklasse
· NP-Vollständigkeit
· O-Notation
· P-NP-Problem
· Platzkomplexität
· Polynomialzeit
· Zeitkomplexität
Formale Sprachen und Automaten:
Akzeptor
· Backus-Naur-Form
· Chomsky-Hierarchie
· Formale Grammatik
· Pumping-Lemma
· Regulärer Ausdruck
· Reguläre Sprache
· Transduktor
· Turingmaschine