Basics of theoretical computer science with applications. An introduction for students of computer science, business informatics and technical computer science (Q2715629)

Das Buch behandelt zum einen die Gebiete der theoretischen Informatik, die üblicherweise in einer entsprechenden Grundvorlesung behandelt werden, ergänzt diese aber zum anderen durch einige nicht allgemein übliche Gebiete und legt vor allem sehr viel Wert auf Motivation der Konzepte und deren Anwendung. Der letzte Aspekt dürfte das größte Interesse finden und macht den Reiz dieses Buches aus. Das inhaltliche Hauptaugenmerk des Buches liegt bei endlichen Automaten und regulären Sprachen, die fast die Hälfte des Buches ausmachen. Den zentralen Teil bilden hierbei die endlichen Automaten ohne Ausgabe zur Akzeptanz von regulären Sprachen und deren Erzeugung durch reguläre Grammatiken bzw. reguläre Ausdrücke. Ausführlich werden auch kontextfreie Sprachen und Kellerautomaten und ihre Eigenschaften untersucht. Typ-0- und Typ-1-Sprachen und Turing-Maschinen bzw. linear beschränkte Automaten als deren Akzeptoren werden relativ kurz behandelt. In allen Fällen werden verschiedene Varianten der Automatentypen und Grammatiken und die zugehörigen äquivalenzen sowie Normalformen, Pumping-Lemmata und Abschlusseigenschaften angegeben. Im Gegensatz zu vielen herkömmlichen Lehrbüchern werden aber auch Automaten mit Ausgabe und endliche Transducer als deren Verallgemeinerung ausführlich betrachtet. Darüberhinaus werden auch den endlichen Automaten nahestehende Netzwerke wie zellulare Automaten und Petri-Netze behandelt. NEWLINENEWLINENEWLINEGroßes Interesse dürften die motivierenden Beispiele in den einleitenden Teilen finden. Hier werden sowohl Objekte der Praxis (wie der Automat zur Einlasskontrolle im Schwimmbad) als der Informatik (Automat zur Addition bzw. Paritätsprüfung) finden. Diese Beispiele werden je nach Bedarf modifiziert und verallgemeinert (z. B. von Abfertigung einzelner Personen zu Folgen von Personen). Aus diesen Beispielen entwickelt sich die Theorie in einer relativ natürlichen Weise. Diese Teile sind auch didaktisch sehr gelungen. Ergänzt werden die einführenden Beispiele durch Abschnitte, die vollständig Anwendungen der Konzepte gewidmet sind. So erfolgt z. B. bei den regulären bzw. kontextfreien Sprachen ein Ausblick auf Suchmaschinen bzw. auf den Compilerbau und auf ihre Bedeutung im Zusammenhang mit XML-Sprachen. Leider werden nicht alle behandelt, wie es wünschenswert wäre; so ist der elektronische Handel als Anwendungsfeld der regulären Sprachen eigentlich nur durch ein einfaches Beispiel skizziert. Auf der anderen Seite lassen die Autoren einige Beweise (für teilweise wichtige Aussagen) fort oder geben nur die Konstruktion an, die sie noch durch ein Beispiel illustrieren, überlassen aber dem Leser den eigentlichen Beweis bzw. verweisen auf andere Lehrbücher. Das letzte Viertel des Buches machen drei Abschnitte zur Berechenbarkeit (auf der Basis von Turing-Maschinen bzw. Loop-, While- und Goto-Konstrukten), Entscheidbarkeit (Existenz und Beispiele von unentscheidbaren Mengen) und Komplexität (Klassen P und NP, Existenz NP-vollständiger Probleme, Beispiele dafür und Heuristiken zu ihrer approximativen Lösung) aus.