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
Das 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.
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.)
Theoretische Informatik
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.)
![]() |
![]() |
Maria
von Maria




Die Autoren weisen darauf hin, dass sie „Aus Gründen der Lesbarkeit“ mal die männliche, mal die weibliche Form gewählt haben. Gut, aber mussten sie deswegen das Beispiel Pilot und Masseurin wählen…? Aber das nur nebenbei.
Das Tutorial ist ein englisch-sprachiges Buch für Datenbankadministratorinnen. Locker, aber fundiert geschrieben, macht es Spaß, sich damit schlau zu machen. Einsteigerinnen wie Profis können damit etwas anfangen. Denn der kompakte Band eignet sich sowohl zum Durchlesen als auch zum Nachschlagen.
Das Patent dieses „Fuschzettels“ ist Stadtplänen und Straßenkarten abgeguckt. Es ist sehr praktisch, die wichtigsten Befehle und Datentypen dabei zu haben, ohne sich gleich mit einem dicken Nachschlage-Wälzer abzuschleppen. Das Ding besteht aus 8 Spalten, die sich mit folgenden Themen befassen:
Sehr locker und doch fundiert führt Raymans
Thema verfehlt? Nein, so weit würde ich nicht gehen. Zielgruppe verfehlt? Die der Informatik-Studierenden sicher! Jarosch schreibt zwar über Datenbankentwurf, aber für meinen Geschmack zu… hm… ja, zu unwissenschaftlich. Und das sage ich, obwohl ich selbst Datenbanken mehr aus der praktischen als aus der wissenschaftlichen Sicht kenne. Das Buch beginnt mit einer seltsamen Grafik, die seinen Aufbau veranschaulichen soll. Schon hier trennen sich Anspruch und Wirklichkeit.



Für Mathematik-Interessierte gibt es ein Buch über Beweise. Und darauf kommen wir später vielleicht nochmal zurück… [Deswegen hier keine Rezension, sondern nur eine Erwähnung, Anm. d. Red.]
Ein Buch für die engagierte Linuxerin. Als Einstieg wählt Brian Ward das Thema „UNIX, Linux und Linux-Distributionen“. Danach werden Systemgrundlagen erklärt. Sehr interessant ist das Kapitel Netzwerkadministration, denn wer von uns hätte nicht gern ein eigenes Netz? NFS, NIS und RDIST und SAMBA sind nach der Lektüre keine böhmischen Dörfer mehr. Das große Thema Drucken wird ebenso behandelt wie die Installation von Software aus dem Quellcode.
Dieses Buch bietet einen ersten Überblick über einige gängige Websprachen. Es behandelt JavaScript und VBScript. Neben XML kommt auch SMIL vor. Als Einstieg ins Scripting ist das Buch brauchbar, aber sicher nicht der Weisheit letzter Schluss. Für SMIL ist leider nur das Abschlusskapitel reserviert. Hier wollte der Autor etwas Zukunftsweisendes in sein Werk einbetten. Nun gut. Mehr hat er damit auch nicht erreicht. Was fehlt noch? Die CD-Rom. Sie enthält die Beispiele, aber nichts an weltbewegender Software. Schade, bei diesem Buchtitel hätte frau da doch einiges erwartet.
Ein wirklich schwergewichtiges Werk hat frau mit diesem Buch (848 Seiten).
















