lehrerbibliothek.deDatenschutzerklärung
Theoretische Informatik Grundlagen mit Übungsaufgaben und Lösungen
Theoretische Informatik
Grundlagen mit Übungsaufgaben und Lösungen




Renate Winter

Oldenbourg Schulbuchverlag
EAN: 9783486258080 (ISBN: 3-486-25808-7)
231 Seiten, paperback, 17 x 24cm, 2002

EUR 19,00
alle Angaben ohne Gewähr

Umschlagtext
Dieses Lehrbuch enthält die wesentlichen Grundzüge der Theoretischen Informatik. Es gibt eine verständliche Einführung in die Gebiete Berechenbarkeits-, Automatentheorie, Formale Sprachen und Komplexitätstheorie.



Im Hauptsatz der Algorithmentheorie wird die Äquivalenz verschiedener Berechenbarkeitsbegriffe dargestellt. Einen weiteren Schwerpunkt bilden ausführliche Untersuchungen hierarchischer Beziehungen von Sprachklassen mit den zugehörigen Automatentypen zur Spracherkennung. Alle Zusammenhänge sind verständlich bewiesen und durch Beispiele untermauert. Von praktischer Bedeutung sind Untersuchungen zur Existenz von nicht entscheidbaren und nicht effizient lösbaren Problemen. Es erfolgt eine Einführung in die Theorie der NP-Vollständigkeit mit Beispielen.



Durch eine Vielzahl von Übungsaufgaben, sämtlich mit ausführlichen Lösungen, werden die dargestellten Sachverhalte der einzelnen Kapitel vertieft. Die Aufgaben sind zum Selbsttest des Lesers wie auch zur Vorbereitung auf den studentischen Übungsbetrieb geeignet.
Rezension
Dieses Buch richtet sich an Informatikstudenten mit Grundkenntnissen in der Theoretischen Informatik (und Höheren Mathematik). Es behandelt die einzelnen Themenkomplexe sehr kompakt und dient dank der vielen Übungsaufgaben und Lösungen hauptsächlich der Vorbereitung auf Klausuren und mündliche Prüfungen. Das sehr abstrakte Wissen läßt sich durch dieses Buch sinnvoll einarbeiten.

Florian Schimandl, lehrerbibliothek.de
Inhaltsverzeichnis
Vorwort

1 Einleitung - Wesen der Theoretischen Informatik

1.1 Aufgaben

2 Berechenbarkeitstheorie

2.1 Einführung zum Berechenbarkeitsbegriff
2.2 Arten von Nichtberechenbarkeit
2.3 Die Turingmaschine
2.3.1 Begriff und Arbeitsweise einer Turingmaschine
2.3.2 Modifizierte Definitionen von Turingmaschinen
2.4 Aufzählbarkeit, Entscheidbarkeit und Berechenbarkeit
2.5 Nichtdeterministische Turingmaschinen
2.6 Markow- und Post-Algorithmen
2.6.1 Vergleich: Markow-und Post-Algorithmus
2.7 Rekursive Funktionen
2.7.1 Primitiv rekursive Funktionen
2.7.2 Die Ackermann-Funktion
2.7.3 µ-rekursive Funktionen
2.8 Der Hauptsatz der Algorithmentheorie
2.9 Registermaschinen
2.10 Nichtentscheidbarkeit und Nichtberechenbarkeit
2.10.1 Nichtentscheidbare Probleme und der Satz von Rice
2.10.2 Die Fleißiger-Biber-Funktion
2.11 Zur Universalität von Turingmaschinen
2.12 Theorie der rekursiven Funktionen - Einführung
2.13 Aufgaben

3 Abstrakte Automaten

3.1 Der Begriff des abstrakten Automaten und Automatenarten
3.2 Die Arbeitsweise von Mealy-Automaten
3.3 Endliche Akzeptoren und Potenzmengenkonstruktion
3.4 Reguläre Mengen und Hauptsatz von Kleene
3.4.1 Verfahren von Gluschkow
3.5 Das Pumping-Lemma für reguläre Sprachen
3.6 Der Satz von Nerode
3.7 Minimierung endlicher Automaten
3.8 Anwendungen für endliche Automaten
3.9 Deterministische und nichtdeterministische Push-Down-Automaten
3.10 Linear-beschränkte Automaten
3.11 Hierarchie der Automatentypen
3.12 Aufgaben

4 Formale Sprachen

4.1 Sprachen und Grammatiken
4.2 Grammatiken zur Erzeugung formaler Sprachen
4.3 Chomsky-Normalform kontextfreier Grammatiken, Pumping-Lemma
4.4 Chomsky-Hierarchie formaler Sprachen
4.5 Sprachklassen und Automatentypen
4.6 Abgeschlossenheitseigenschaften von Sprachklassen
4.7 Deterministisch-kontextfreie Sprachen
4.8 Wortprobleme bei Sprachklassen. Der CYK-Algorithmus
4.9 Hierarchie von Sprachfamilien und Automatentypen
4.10 Aufgaben

5 Komplexitätstheorie

5.1 Einführung und Komplexitätsschranken
5.2 Zeit- und Bandkomplexität bei Turingmaschinen
5.3 Komplexität bei Mehrband-Turingmaschinen und bei RAM's
5.4 Die Klassen P und NP. NP-Vollständigkeit
5.5 Der Satz von Cook
5.6 NP-vollständige Probleme 3SAT und CLIQUE
5.7 Probleme jenseits von NP
5.8 Einordnung der Klassen P, NP und PSPACE in die Chomsky-Hierarchie
5.9 Aufgaben

6 Zusammenfassung und Schlussfolgerungen

7 Lösungsvorschläge

Literatur

Index