Infotext:
Diese Einfhrung in die Theoretische Informatik zeichnet sich durch Verstndlichkeit und gute Lesbarkeit aus. Sie umfat die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und einen berblick ber die Komplexittstheorie. Das Buch eignet sich insbesondere fr Anfnger: Alle Beweise sind im Detail ausgefhrt - insofern ist es auch eine Einfhrung in die Technik des Beweisens. Fr 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 fr Studierende der Informatik im Grundstudium an den Universitten Paderborn und Koblenz.Die Neuauflage wurde um theoretische Grundlagen fr Quantenrechner ergnzt.
Inhaltsverzeichnis:
Einleitung.- Begriffe und Notationen.- Eine kurze Einfhrung in die Aussagenlogik.I. Formale Sprachen: Grammatiken und formale Sprachen. Regulre Sprachen und endliche Automaten. Kontextfreie Sprachen. Turing-Maschinen. Die Sprachklassen L, L0 und L1. Abschlueigenschaften von Sprachklassen.-II. Berechenbarkeit: Einleitung. Registermaschinen. Rekursive Funktionen. Unentscheidbare Probleme. Alternative Berechnungsmodelle. Komplexitt.-Bibliographische Hinweise.- Literaturverzeichnis.- Sachverzeichnis.
Diese Einfhrung in die Theoretische Informatik zeichnet sich durch Verstndlichkeit und gute Lesbarkeit aus. Sie umfat die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und einen berblick ber die Komplexittstheorie. Das Buch eignet sich insbesondere fr Anfnger: Alle Beweise sind im Detail ausgefhrt - insofern ist es auch eine Einfhrung in die Technik des Beweisens. Fr 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 fr Studierende der Informatik im Grundstudium an den Universitten Paderborn und Koblenz.Die Neuauflage wurde um theoretische Grundlagen fr Quantenrechner ergnzt.
Inhaltsverzeichnis:
Einleitung.- Begriffe und Notationen.- Eine kurze Einfhrung in die Aussagenlogik.I. Formale Sprachen: Grammatiken und formale Sprachen. Regulre Sprachen und endliche Automaten. Kontextfreie Sprachen. Turing-Maschinen. Die Sprachklassen L, L0 und L1. Abschlueigenschaften von Sprachklassen.-II. Berechenbarkeit: Einleitung. Registermaschinen. Rekursive Funktionen. Unentscheidbare Probleme. Alternative Berechnungsmodelle. Komplexitt.-Bibliographische Hinweise.- Literaturverzeichnis.- Sachverzeichnis.