Babylon – Viele Sprachen, Grammatiken und andere komplexe Theorien

Maria / / Rezension

Babylon – Viele Sprachen und andere Theorien

Buchrezensionen

Automatentheorie, Formale Sprachen und Komplexität
Theoretische Informatik

Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie

CoverDas Buch ist sehr ausführlich, es kommt mit über 500 Seiten daher. Eine nette Einführung ist die Geschichte der Automaten und eine Antwort auf die Frage: „Wozu eigentlich Automatentheorie?“ Wie Ihr seht, hat das Buch Zusatzinfos im Gepäck, nämlich jede Menge Hintergrundinformationen. Dazu gehört u.a. eine kurze, brauchbare Erklärung von Beweistechniken. „Wie formal müssen Beweise sein?“ wird ebenso beantwortet wie verschiedene Beweistypen erklärt, nicht nur deduktive und induktive. [Anm. der Redaktion: Zum Beweisen wird es auf der diesjährigen ditact in Salzburg auch einen Kurs geben.]

Mit Liebe gemacht sind auch die Zusammenfassungen und Literaturangaben zu jedem einzelnen Kapitel. Außerdem gibt es zu den Übungen im Buch (leider nur) teilweise Lösungen in der Website des (leider) englischen Originals. Naja, schließlich sollten Informatikstudierende sich mit dem Web und auch etwas im Englischen auskennen. Ein paar mehr Abbildungen mehr hätten allerdings nicht geschadet.

Voraussetzungen, um das Buch zu verstehen, nennen die Autoren auch: Ihr solltet schon mal ein bisschen gehört haben von Graphen, Bäumen, Logik, Datenstrukturen, Rekursion, Compilern und anderen Systemkomponenten. Aber das ist wirklich nicht die Welt; Reinschnuppern geht eigentlich auch einfach mit gesundem Informatik-Verstand.

Themen

  • Endliche Automaten
  • Reguläre Ausdrücke und Sprachen
  • Kontextfreie Grammatiken und Sprachen
  • Pushdown-Automaten und Turing-Maschinen
  • Pumping-Lemmata
  • (Un-) Entscheidbarkeit und andere Problemklassen

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: „Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie“.
Pearson Studium 2002. 34,95 EUR (D) / 41,10 EUR (A). ISBN 3-8273-7020-5.

Cover Und noch was zu dem Thema: Mit dem folgenden Buch hab ich mich auf verschiedene erfolgreiche Klausuren / Prüfungen vorbereitet. Es kann also nicht ganz schlecht sein ;-)

Peter Sander, Wolffried Stucky, Rudolf Herschel: „Automaten, Sprachen und Berechenbarkeit“.
Teubner 1992. ISBN 3-519-02937-5. (Nur noch als Liebhaberstück zu haben … aber vielleicht findet es die ein oder andere noch in den Weiten des Web oder den Tiefen ihrer Bib.)

nach oben

Theoretische Informatik

Cover Ich weiß ja nicht, wie Ihr zur theoretischen Informatik steht. Manche scheinen sie jedenfalls nicht sonderlich zu mögen… Nichtsdestotrotz sollte frau wenigstens etwas Ahnung von dem Gebiet haben. Und da habe ich mich mal umgesehen, welche literarische Unterstützung sich so besorgen lässt.

Alexander Asteroth und Christel Baier bieten mit ihrem mehr als vierhundert Seiten starken Buch eine gute Grundlage. Sie arbeiten beide an der Rheinischen Friedrich-Wilhelms-Universität in Bonn. Das Buch enthält neben der einführenden Theorie auch Übungen, was sich immer gut macht. Leider gibt es dazu keine Lösungen, was sich i.d.R. nicht ganz so gut macht. Besonders gelungen finde ich die Abbildungen. Sie sind anschaulich (z. B. beim Semi-Entscheidungsverfahren), teilweise sogar lustig, besonders beim Halteproblem musste ich schmunzeln (S. 100). Außerdem gibt es eine Übersicht für den Zusammenhang zwischen Sprachen und Automaten, was für Prüfungen sehr nützlich ist.

Themen

  • Register- und Turingmaschinen
  • Entscheidungsprobleme
  • Komplexitätsklassen
  • Grammatiken und Sprachen
  • Pumping-Lemmata
  • LR(0)- und LR(k)-Grammatiken

Der ultimative Vergleich

Anhand des Rucksackproblems habe ich mal die drei mir persönlich bekannten Titel zur theoretischen Informatik einander gegenüber gestellt:

Buch Bewertung Ausführlichkeit

Alexander Asteroth, Christel Baier: „Theoretische Informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen“.
Pearson Studium 2002. 29,95 EUR (D) / 30,80 EUR (A). ISBN 3-8273-7033-7.

Ingo Wegener: „Theoretische Informatik – eine algorithmische Einführung“.
Teubner 1999. 21,90 EUR. ISBN 3-519-12123-9.

Uwe Schöning: „Theoretische Informatik kurz gefasst“.
BI Wissenschaftsverlag 1992. ISBN 3-411-15641-4. (Diese Ausgabe gibt’s nur noch gebraucht.)

Cover Cover

nach oben

Maria

von Maria