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


Das "Beyond-Pages"-Environment ist für die Messe ins Kongresszentrum verlagert worden. Worum geht’s? Durch Berührung einer virtuellen Buchseite kann frau das Blättern simulieren:

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:
An manchen Tagen fällt das Gehen etwas schwerer. "Heute ist so ein Tag", denkt sich Else Meier. Erleichtert lässt sich die Siebzigjährige auf ihr Sofa sinken. Etwas zu Trinken wäre nicht schlecht: "Care-O-bot: Bring mir bitte Orangensaft!"
Care-O-bot® II kann ziemlich viel:
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.
Wie angekündigt, traf sich das Programmkomitee im Januar, um die nächste informatica feminale zu organisieren. Wir haben getagt, gesichtet, sortiert und diskutiert (s. Foto am Ende). Hoffnung besteht, dass das nächste Sportprogramm von verantwortungsvollen Bevollmächtigten übernommen wird. Dann werden nicht nur unsere geistigen, sondern auch unsere physischen Talente gefördert. Sabine stimmte für Fußball, Rike für Tanzen. Mal sehen, was es wirklich wird… Wichtigste Erkenntnis: Das nächste Programm wird spannend, anspruchsvoll und sehr abwechslungsreich.
Am 24. Januar trifft sich das Programmkomitee in Bremen. Wir werden die Vorschläge sichten, die Organisation planen und Eure Wünsche berücksichtigen.
Eine anfangs sachliche Diskussion von Brigitte, Maria und Rike ist mit der Zeit

Auch wenn noch über all die Schoko-Nikoläuse und Lebkuchen herumstehen… die nächste informatica feminale ist schon in Planung. Der
Gemeinsame Angebote mehrerer Dozentinnen haben sich sehr bewährt. Das bietet sich insbesondere für interdisziplinäre Themen an. Für umfangreiche Veranstaltungen erhalten die Dozentinnen Lehraufträge der Universität Bremen oder der Fachhochschule Furtwangen.
1. Klebe D auf C.