Uwe Schöning Bücher

Dieses Buch beschreitet einen neuen Weg. Inhalte vor allem der Theoretischen Informatik werden hier für ein breiteres Publikum aufbereitet und verfügbar gemacht. Der Autor verdeutlicht, dass der Zugang zur Informatik über die formale Methode, die Grundideen und die Algorithmik viel Spaß machen kann. Effiziente, praxisrelevante Lösungsansätze stehen im Vordergrund, was Verständlichkeit und Anwendbarkeit der Ideen fördert.

Das Buch macht den Leser in kompakter Form mit den wesentlichen GrundzA1/4gen der Theoretischen Informatik vertraut. Es fA1/4hrt in die Thematik Formale Sprachen, Grammatiken und Automaten ein. An eine Diskussion des Berechenbarkeitsbegriffs und unentscheidbarer Probleme schlieAt sich eine EinfA1/4hrung in die Komplexi-tAtstheorie, speziell die Theorie der NP-VollstAndigkeit, an. QuerbezA1/4ge zwischen den Fachgebieten werden aufgezeigt. In der 3. Auflage wurden Erweiterungen eingearbeitet, wie zum Beispiel der KomplementabschluA der kontext-sensitiven Sprachen, die Greibach- und Kuroda-Normalform, weitere Unentscheidbarkeitsergebnisse fA1/4r kontextfreie Sprachen, ein Beweis fA1/4r die A"quivalenz von LOOP-Berechenbarkeit und primitiver RekursivitAt, ein Hinweis auf das 10. Hilbertsche Problem, weitere NP-VollstAndigkeitsresultate, sowie eine etwas anders gestaltete Darstellung der Ackermann-Funktion.