Lectures on computer science. Vol. 3: Computability, formal languages, specifications (Q1360183)

Dieses ist der 3. Band in der Buchreihe Vorlesungen über Informatik von Prof. Goos. Der vorliegende Band behandelt die eher theoretischen Aspekte der Informatik in ihren Grundzügen, wie es für das Niveau einer Grundstudiumsvorlesung angemessen ist. Es wird mit den Themen der klassischen Berechenbarkeitstheorie begonnen: im Anschluß an eine Diskussion des Algorithmenbegriffs und der Churchschen These werden nachfolgend verschiedene Formalismen zur Spezifikation des Berechenbarkeitsbegriffs besprochen: verschiedene Formen von Programmen (auf abstrakten Maschinen), die Turingmaschine, rekursive Funktionen, und als Paradebeispiel für ein unterscheidbares Problem, das Postsche Korrespondenzproblem. Auf diesen Berechenbarkeitsteil schließt sich in natürlicher Weise ein Abschnitt über Komplexitätstheorie an, wobei der Fokus auf den Klassen P und NP und verschiedenen NP-Vollständigkeitsbeweisen liegt. Die Diskussion formaler Sprachen geht den Weg von den einfachen (sprich: regulären Sprachen) zu den schwierigen (kontextfreien und kontextsensitiven), wobei jeweils die entsprechenden Grammatikarten und Automatentypen angegeben werden. Eine Besonderheit dieses Buches, im Vergleich zu anderen mit ähnlichem Anliegen und ähnlicher Zielgruppe, ist die Behandlung von Programmtransformationen (Einsetzen, Falten, Entrekursivieren), und ferner auch die Behandlung der Oxforder Z-Notation zur Spezifikation von Eigenschaften objektorientierter Modelle, wobei der zentrale Begriff der des Schemas ist. Das letzte Kapitel befaßt sich mit Ablaufspezifikationen, Synchronisierung und Kommunikation. Mittels Zustandsdiagrammen (Statecharts) können Konzepte wie Ereignisse, Bedingungen, Aktionen in ihrem zeitlichen Ablauf in einem nebenläufigen, parallelen System modelliert werden. Probleme der Kooperation und Synchronisation zwischen Prozessen mittels geeigneten Kommunikationsprotokollen werden exemplarisch besprochen. Zusammenfassung: ein sehr breit angelegtes Lehrbuch, das sehr viele, auch moderne Aspekte der Informatik behandelt. Hierbei kann (und soll) natürlich nicht jedes Thema mit seiner gesamten theoretischen Tiefe behandelt werden.