Diese Einführung in die Theoretische Informatik zeichnet sich durch Verständlichkeit und gute Lesbarkeit aus. Sie umfasst 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.

Fundierte Einführung in die Theoretische Informatik Verständlich geschrieben und gut lesbar Ausführliche Darstellung aller Beweise Includes supplementary material: sn.pub/extras

Klappentext

Das Lehrbuch führt in verständlicher Sprache in die theoretische Informatik ein. Es umfasst die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und gibt einen Überblick zur Komplexitätstheorie. Das Buch eignet sich insbesondere für Einsteiger: Alle Beweise sind im Detail ausgeführt. Für Dozenten ist das Buch ebenfalls interessant, da auch Nicht-Standard-Berechnungsmodelle vorgestellt werden. Das Buch basiert auf Vorlesungen der letzten zehn Jahre für Studierende der Informatik im Grundstudium.

Inhalt
Begriffe und Notationen.- Begriffe und Notationen.- Eine kurze Einführung in die Aussagenlogik.- Eine kurze Einführung in die Aussagenlogik.- Formale Sprachen.- Grammatiken und formale Sprachen.- Reguläre Sprachen und endliche Automaten.- Kontextfreie Sprachen.- Turing-Maschinen.- Die Sprachklassen und .- Abschlußeigenschaften von Sprachklassen.- Berechenbarkeit.- Registermaschinen.- Rekursive Funktionen.- Unentscheidbare Probleme.- Alternative Berechnungsmodelle.- Komplexität.