Theoretische Informatik: Eine umfassende EinführungSpringer-Verlag, 17.04.2013 - 467 Seiten Diese Einführung in die Theoretische Informatik zeichnet sich durch Verständlichkeit und gute Lesbarkeit aus. Sie umfaßt die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und einen Überblick über die Komplexitätstheorie. Das Buch eignet sich insbesondere für Anfänger: Alle Beweise sind im Detail ausgeführt - insofern ist es auch eine Einführung in die Technik des Beweisens. Für Dozenten ist das Buch ebenfalls interessant, da die Beweise nicht nur wie vielfach üblich skizziert sind und auch Nicht-Standard-Berechnungsmodelle vorgestellt werden. Das Buch basiert auf Vorlesungen der letzten zehn Jahre für Studierende der Informatik im Grundstudium an den Universitäten Paderborn und Koblenz. Die Neuauflage wurde um theoretische Grundlagen für Quantenrechner ergänzt. |
Andere Ausgaben - Alle anzeigen
Theoretische Informatik: eine umfassende Einführung Katrin Erk,Lutz Priese Keine Leseprobe verfügbar - 2002 |
Häufige Begriffe und Wortgruppen
A₁ abgeschlossen Ableitungsbaum akzeptiert Algorithmus Alphabet äquivalent Äquivalenzklassen asynchrone b₁ Band Bandinhalt Baustein Befehl Beispiel beliebig berechenbar berechnen berechnet berechnungsuniversell Beweis Buchstaben cf-Grammatik chemisch reversible DCFL definieren definiert Definition determinierte Eingabe Eingabewort endlichen Automaten enthält ersten falls false true finalen Zustand folgenden Formel Funktion ƒ gibt gilt Gödelisierung Gödelnummer goto GOTO-Programm Grammatik Graphen hält Halteproblem Hamilton-Kreis heißt Homomorphismus i-te Input jeweils Knoten Konfiguration konstruieren kontextfreie kontextfreie Sprachen kontextsensitiven L₁ läßt Lemma links LOOP LOOP-Programm M₁ Maschine Mealy-Automaten Menge muß natürlichen Zahlen Netz NP-vollständig oben P₁ physikalisch reversible polynomieller Postsche primitiv rekursiv primitiv rekursive Funktionen Programm Pumping-Lemma Rechnung Regel Register Registermaschine reguläre reguläre Sprache Rekursion rekursiven Funktionen Rödding-Netze Satz Schritt Signal simulieren simuliert Sprache Sprachklassen surjektive TM-berechenbare totale Funktion true false true true Turing Turing-Maschine unendlich unentscheidbar unserer Variablen verwenden w₁ Wert WHILE-Programm Wort x₁ Zeichen zeigen Zustand q zwei