Theoretische Informatik: Eine umfassende Einführung

✍ Scribed by Katrin Erk, Prof. Dr. Lutz Priese (auth.)

• Publisher: Springer Berlin Heidelberg
• Year: 2000
• Tongue: German
• Leaves: 427
• Series: Springer-Lehrbuch
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Front Matter....Pages I-X
Einleitung....Pages 1-1
Begriffe und Notationen....Pages 3-33
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 ℒ, ℒ 0 und ℒ 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-324
Alternative Berechnungsmodelle....Pages 325-386
Komplexität....Pages 387-420
Back Matter....Pages 421-433

✦ Subjects

Mathematical Logic and Formal Languages; Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Mathematics of Computing; Mathematical Logic and Foundations; Combinatorics