Computer science. A basical introduction. System structure and theoretical computer science

DOI10.1007/978-3-642-58911-9MaRDI QIDQ4220562zbMATH OpenOpenAlexFDO

Publication date 24 November 1998

Published in Springer-Lehrbuch (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-58911-9

computer science distributed systems operating systems theoretical computer science

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) General topics in the theory of software (68N01)

Review text

Dieser zweite Band der Informatik-Einführung von Manfred Broy ersetzt die Bände drei und vier der ersten Ausgabe. Die gesamte Einführung in nunmehr zwei Bänden behandelt die fundamentalen Modelle, Formalismen und sprachlichen Konstruktionen sowie die wichtigsten Anwendungsgebiete und technischen Konzepte der Informatik. Sie ist Grundlage der Informatik-Vorlesungen des Autors und anderer Hochschullehrer im Grundstudium an der Technischen Universität München und weiteren Universitäten. Der vorliegende Band umfaßt die Teile `Systemnahe Programmierung` und `Formale Sprachen, Berechenbarkeit, Komplexität, Logikprogrammierung`. In einem ersten ausführlichen Kapitel wird auf Prozesse und ihre Koordination und Kommunikation in verteilten Systemen eingegangen. Die Darstellung ist formal, es werden unterschiedliche Formalismen eingeführt, wie z.B. halbgeordnete Ereignisstrukturen, Petrinetze und Prozeßalgebren. Die Anwendung dieser Konzepte auf Fragestellungen bei Betriebssystemen und Systemprogrammierung erfolgt im zweiten Kapitel. Hier werden zunächst Aufgaben und Prinzipien von Betriebssystemen mit Hilfe von vereinfachten Beispielsystemen eingeführt. Die zentralen Begriffe wie z.B. Betriebsmittelvergabe werden ausführlich besprochen. Das dritte Kapitel des ersten Teils ist der Interpretation und der Übersetzung von Programmen gewidmet. Die klassischen Komponenten des Übersetzerbaus wie lexikalische, syntaktische und semantische Analyse werden vorgestellt. Der zweite Teil des Buches gliedert sich in sechs Kapitel: Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, effiziente Algorithmen und Datenstrukturen, Beschreibungstechniken in der Programmierung und abschließende Bemerkungen zur Entwicklung und Anwendungsgebieten der Informatik. Die Inhalte der Kapitel sind jeweils das im Grundstudium übliche Material aus dem Bereich. So werden im ersten Kapitel die Sprachen der Chomsky-Hierarchie eingeführt, mit einem starken Schwerpunkt auf reguläre Sprachen und endlichen Automaten sowie auf kontextfreie Sprachen und Kellerautomaten. Die Untersuchungen zur Berechenbarkeit basieren auf Turingmaschinen, Registermaschinen und primitiv rekursiven Funktionen. Bei der Komplexitätstheorie liegt der Schwerpunkt neben einer Einführung von Zeit- und Bandkomplexität deterministischer und nichtdeterministischer Maschinenmodelle auf NP-vollständigen Problemen. Das Kapitel zu effizienten Algorithmen und Datenstrukturen konzentriert sich auf Graphalgorithmen und Algorithmen auf speziellen Bäumen zum effizienten Zugriff auf große Datenmengen. Schließlich werden Beschreibungstechniken angegeben, wie sie beim Datenbankentwurf und in der Logikprogrammierung Verwendung finden. Diese kurze Darstellung der wesentlichen Inhalte macht bereits deutlich, welche Fülle unterschiedlicher Themen in diesem Band angesprochen werden. Trotzdem bleibt er stets formal und zugleich klar und verständlich. Naturgemäß kann es aber kein Einzelthema vertieft betrachten. Dieser Band eignet sich als Grundlage einer Vorlesung, vierstündig über zwei Semester. Aber auch bei diesem Umfang ist zu erwägen, das Buch als Angebot einer Vielzahl von Konzepten zu verwenden, aus denen einige ausgewählt und noch vertiefter dargestellt werden während andere auf Lehrveranstaltungen des Hauptstudiums verschoben werden.

Recommendations

Cited in

(11)

This page was built for publication: Computer science. A basical introduction. System structure and theoretical computer science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4220562)