Theoretische Informatik - kurz gefasst

Autoren-Porträt von Uwe Schöning

Prof. Dr. Uwe Schöning ist Leiter der Abteilung Theoretische Informatik der Universität Ulm.

Inhaltsverzeichnis zu „Theoretische Informatik - kurz gefasst “

Einleitung.- 1 Automatentheorie und Formale Sprachen.- 1.1 Allgemeines. 1.2 Reguläre Sprachen. 1.3 Kontextfreie Sprachen. 1.4 Kontextsensitive und Typ 0-Sprachen. 1.5 Tabellarischer Überblick.- 2 Berechenbarkeitstheorie.- 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These. 2.2 Turing-Berechenbarkeit. 2.3 LOOP-, WHILE- und GOTO-Berechenbarkeit. 2.4 Primitiv rekursive und mü-rekursive Funktionen. 2.5 Die Ackermannfunktion. 2.6 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit. 2.7 Das Postsche Korrespondenzprinzip. 2.8 Unentscheidbare Grammatik-Probleme. 2.9 Der Gödelsche Satz.- 3 Komplexitätstheorie.- 3.1 Komplexitätsklassen und P-NP-Problem. 3.2 NP-Vollständigkeit. 3.3 Weitere NP-vollständige Probleme.- Anhang: Mathematische Grundlagen.- Literaturverzeichnis.- Index

Rezension zu „Theoretische Informatik - kurz gefasst “

Nach wie vor eines der besten Bücher zum Themenbereich; kurz und knapp, dennoch klar strukturiert und verständlich; insbesondere sehr gut für Prüfungsvorbereitung geeignet. Prof. Dr. Kurt-Ulrich Witt, Fachhochschule Bonn-Rhein-Sieg Das Buch hat sich zum kompakten Klassiker entwickelt. Prof. Dr. Jörg Weimar, Fachhochschule Brandenburg Eine sehr schöne und gut aufgebaute Zusammenfassung der Theoretischen Informatik , die einen guten Überblick über das Gebiet gibt und hervorragend zur Prüfungsvorbereitung geeignet ist. Prof. Dr. Peer Ueberholz, Hochschule Niederrhein, Krefeld