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.

[Quelle (Text und Bild): Oldenbourg-Wissenschaftsverlag]

 

Eine Leseprobe findet ihr unter: Theoretische Informatik (google books)

Autoren: Renate Winter
Erscheinungsdatum: Auflage: 1 (Januar 2002)
ISBN: 978-3-486-25808-0
Preis: 19,80 EUR
Verlag (inkl. Bestellmöglichkeit): Oldenbourg-Wissenschaftsverlag

 

Rezension von Adrian Klinger (17 Jahre):

Viele Jugendliche und auch ein paar Studenten denken immer das Informatik nur etwas mit Computer zu tun hat und Informatiker den ganzen lieben langen Tag vor dem Bildschirm hocken und programmieren. Jedoch besteht die Informatik nicht nur aus dem praktischen Teil sondern auch aus einem großen Teil Theorie

Ein paar wichtige Bereiche der theoretischen Informatik beschreibt Renate Winter in ihrem Buch „Theoretische Informatik“. Das Buch enthält die Bereiche Berechenbarkeit, Automatentheorie, Formale Sprachen und Komplexitätstheorie. Schon nach den ersten beiden Seiten kommen einem 4 Aufgaben entgegen, die wahrscheinlich als Einstieg dienen sollen. An diesen Aufgaben habe ich dann schon gemerkt, dass dieses Buch nichts für Anfänger ist. Da es gleich mit vollständiger Induktion als Einstimmung anfing und nicht gerade leicht zu lösen war, auch wenn man die Induktion beherrscht. Jedoch besitzt das Buch einen sehr guten Schreibstil und ist nicht zu formal aber auch nicht zu schwierig gestaltet.

Der größte Vorteil an diesem Buch ist, dass der Leser nach jeder Lektion ein paar Aufgaben lösen kann, welche gerade zu dem Thema passen was auch gerade behandelt wurde. Die vollständigen und ausführlichen Lösungen befinden sich dann auf den hinteren Seiten des Buches, diese sind meistens auch sehr gut erklärt und plausibel dargestellt worden. Das ist wirklich ein sehr positiver Aspekt für das Buch.

Ich schätze mal für Studenten ist das Buch eine ideale Vorbereitung auf Klausuren zum Beispiel der Berechenbarkeit oder der formalen Sprachen, hierbei kann ich auch erwähnen, dass der Schwerpunkt nämlich rund 68 Seiten von 175 Seiten auf der Berechenbarkeit liegt. Jedoch finde ich, dass der Leser eine großes Vorwissen an informatischen Themen haben muss, um das Buch und die Aufgabe zu lösen.
Deshalb denke ich, dass dieses Buch eher eine Erweiterung des Buches „Ideen der Informatik“ von Uwe Schöning ist. Dort werden nämlich Themen zwar ohne Aufgaben erklärt, aber dafür mit sehr viel Verständnis und kann somit jedem Nicht-Informatiker zur Verfügung gestellt werden. Was bei dem Buch von Renate Winter nicht der Fall ist.

Ich finde aber insgesamt dieses Buch für Leser die ein großes Vorwissen haben sehr hilfreich und es bietet eine Reihe von Beweisen und Übungen mit Lösungen. Also ich würde das Buch für 13. Klässler bis Studenten empfehlen, da es doch ziemlich schwierig zu lesen war.