Wolf Zimmermann

Dieses Lehrbuch bietet eine fundierte Einführung in die grundlegenden Begriffe und Methoden der Informatik. Die Autoren stellen dabei die Prinzipien der System-Modellierung und der Entwicklung von Software in den Mittelpunkt der Darstellung. Der hier vorliegende Band baut auf dem ersten Band auf und vermittelt die wesentlichen Kenntnisse im Entwurf und in der Programmierung mittels imperativer und objektorientierter Programmiersprachen. Schwerpunkte bilden dabei das zustandsorientierte Programmiermodell und das strukturierte Programmieren, worauf die modulare und objektorientierte Programmierung und deren Entwurfsprinzipien aufbauen. Ferner werden die Grundlagen der Umsetzung von Programmen aus höheren Programmiersprachen in solche auf Maschinenebene behandelt und zentrale Methoden zur systematischen Konstruktion von Algorithmen vorgestellt. Die vierte Auflage des bewährten Lehrbuches ist grundlegend überarbeitet und aktualisiert worden.

Dieses Lehrbuch bietet eine fundierte Einführung in die grundlegenden Begriffe und Methoden der Informatik. Die Autoren stellen dabei die Prinzipien der System-Modellierung und der Entwicklung von Software in den Mittelpunkt der Darstellung. Der hier vorliegende Band vermittelt die wesentlichen Grundbegriffe und theoretischen Grundlagen der Informatik, wie z. B. Algebren, Relationen, elementare Logik, funktionales Programmieren, abstrakte Datentypen. Die vierte Auflage des bewährten Lehrbuches ist grundlegend überarbeitet und aktualisiert worden. Der Text richtet sich an Studierende im Grundstudium an Universitäten und Fachhochschulen und basiert auf der langjährigen Erfahrung der Autoren in der Ausbildung angehender Informatiker.

Es gibt im Bereich der Softwaretechnik viele Werkzeuge, die den Programmentwicklungsprozeß unterstützen. Sie stellen die Korrektheit der Implementierung sicher, nicht aber ihre Effizienz. Die vorliegende Arbeit führt daher eine Methode ein, die es erlaubt, die Zeitkomplexität funktionaler Programme automatisch zu ermitteln. Die Grundidee dieser Methode besteht darin, ein funktionales Programm in ein System von Rekurrenzgleichungen zu übersetzen, dessen Lösung das Zeitverhalten des Programms angibt. Durch Einführung von bedingten Rekurrenzen und Rekurrenzfamilien ist es möglich, obere und untere Schranken für die Zeitkomplexität zu finden. Um die mittlere Zeitkomplexität zu bestimmen, müssen Wahrscheinlichkeiten dafür berechnet werden, daß im Programm vorkommende Bedingungen wahr bzw. falsch werden. Diese Wahrscheinlichkeiten werden anhand einer probabilistischen Semantik des Programms berechnet. Um möglichst genaue Schranken für die Zeitkomplexität zu erhalten, muß eine Abhängigkeitsanalyse durchgeführt werden. Dies ermöglicht eine genaue Analyse von Divide-and-Conquer-Programmen.