Theoretische Informatik: Eine umfassende Einführung

Description

Diese Einführung umfasst die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und einen Überblick über die Komplexitätstheorie. Alle Beweise werden ausführlich behandelt. Schwierige Beweise werden nicht etwa abgekürzt, sondern eingehender behandelt. Damit bietet dieses Buch zugleich eine Einführung in die Technik des Beweisens und ist somit sowohl für Anfänger als auch Dozenten geeignet. Ein größeres Kapitel behandelt alternative Rechenmodelle, unter anderem Zwei-Register-Maschinen, Tag-Systeme, Wang-Maschinen, Rödding-Netze, Splicing und reversible Rechnungen. Front Matter....Pages I-XV Einleitung....Pages 1-1 Begriffe und Notationen....Pages 3-34 Eine kurze Einführung in die Aussagenlogik....Pages 35-49 Front Matter....Pages 51-51 Grammatiken und formale Sprachen....Pages 53-61 Reguläre Sprachen und endliche Automaten....Pages 63-107 Kontextfreie Sprachen....Pages 109-163 Turing-Maschinen....Pages 165-193 Die Sprachklassen $$ \mathcal{L},\mathcal{L}_0 $$ und $$ \mathcal{L}_1 $$ ....Pages 195-214 Abschlußeigenschaften von Sprachklassen....Pages 215-223 Front Matter....Pages 225-225 Einleitung....Pages 227-231 Registermaschinen....Pages 233-251 Rekursive Funktionen....Pages 253-289 Unentscheidbare Probleme....Pages 291-325 Alternative Berechnungsmodelle....Pages 327-437 Komplexität....Pages 439-472 Back Matter....Pages 473-485