Grundzüge der Informatik I

In dieser Vorlesung soll die Basis für das Studium der Informatik gelegt werden. Dazu werden die Grundlagen von Programmiersprachen und Algorithmen behandelt.

Ein Programm soll ein gestelltes Problem korrekt und effizient lösen. Um Aussagen über die Korrektheit und die Effizienz eines Programms machen zu können, müssen sowohl die Syntax als auch die Semantik der verwendeten Programmiersprache exakt definiert sein. In dieser Vorlesung wird exemplarisch die Sprache PROSA behandelt, die der Sprache PASCAL sehr ähnlich ist, die aber in einigen Punkten aus didaktischen Gründen von PASCAL abweicht. Die Syntax von PROSA wird mittels attributierter Grammatiken (kontextfreie Grammatiken mit Attributen) beschrieben, und eine operationale Semantik wird mittels einer mathematischen Maschine (einem Interpretierer) erklärt. Aufgrund dieser formalen Definitionen wird es dann möglich sein, Korrektheitsbeweise und Laufzeitanalysen von Programmen durchzuführen.

Als Text für diese Vorlesung dient das folgende Buch:

J. Loeckx, K. Mehlhorn, R. Wilhelm:
Grundlagen der Programmiersprachen
Teubner, Stuttgart, 1986.

Ergänzende und weiterführende Literatur:

A. Aho, J.E. Hopcroft, J.D. Ullman:
The Design and Analysis of Computer Algorithms
Addison-Wesley, 1974.
H.J. Appelrath, J. Ludwig:
Skriptum Informatik - Eine konventionelle Einführung
Teubner, Stuttgartl, 1991.
F. Bauer, G. Goos:
Informatik
2-bändig, Springer, 1982 und 1984.
D.E. Knuth:
The Art of Computer Programming
Addison-Wesley, 1973.
K. Mehlhorn:
Data Structures and Algorithms
3-bändig, Springer, 1984.
E. Waldschmidt, H. Walter:
Grundzüge der Informatik
2-bändig, BI Wissenschaftsverlag, 1984.
N. Wirth:
Algorithmen und Datenstrukturen - Pascal Version
3. Auflage, Teubner, 1983.