In der Praxis stellt sich selbst für Probleme, die die von einem Rechner gelöst werden können, noch die Frage, ob eine Lösung effizient möglich ist. Wir werden sehen, wie man den Begriff "Effizienz" präzise fassen kann und Probleme danach klassifiziern, ob sie effizient lösbar sind oder nicht. Dabei zeigt es sich, daß sehr viele wichtige Probleme in diesem Sinne sehr wahrscheinlich nicht effizient lösbar sind. Dazu gehören zum Beispiel Stundenplanenrwurf, Tourenplanung von Transportunternemen, Auswahl eines optimalen Aktienpaketes, optimale Beladung eines Containers, Auswahl einer möglichst kleinen Testmenge zur Fehlererkennung und so weiter. Wenn man weiß, daß ein Problem nicht effizient lösbar ist, so muß man keine Zeit auf die Suche nach effizienten Lösungsalgorithmen verschwenden. Wir werden verschiedene Techniken zum Nachweis dieser Tatsache kennenlernen.
Die "Endlichen Automaten" stellen eine einfache Modellierung für Schaltwerke, Rechnerkomponenten und Rechner mit beschränktem Speicher dar. Sie erlauben in diesen Bereichen die Synthese, Analyse und Verifikation der Korrektheit. In der Vorlesung werden die grundlegenden Eigenschaften von Endlichen Automaten untersucht. Auch ihre nichtdeterministische Variante wird behandelt.
Schließlich untersuchen wir Grammatiken, die die Grundlage für Programmiersprachen bilden. Anforderungen an solche Grammatiken sind, daß ausreichend mächtig sind, um die gewünschten Konstrukte der Programmiersprache zu unterstützen, und andererseites einfach genug, um von einem Compiler schnell geprüft werden zu können. Es wird gezeigt, daß die sogenannten kontextfreien Grammatiken diese Anforderungen erfüllen.
In der Vorlesung wird eine Reihe von neuen und zum Teil ungewohnten Denkweisen vermittelt. Insbesondere trifft dies auf den Umgang mit negativen Resultaten und die Untersuchung von abstrakten Rechnertypen zu. Eine erfolgreiche Teilnahme erfordert daher die regelmäßige Nachbearbeitung der Vorlesung ebenso wie das regelmäßige Bearbeiten der Übungsaufgaben und die Diskussion der Ergebnisse in den Übungsgruppen.