| Universität Rostock | Fakultät für Informatik und Elektrotechnik | Institut für Informatik | Wissenschaftsbereich Theoretische Informatik |
Das vorliegende Skript mit Übungsaufgaben zur Vorlesung Theoretische Grundlagen der Informatik entspricht den Inhalten der entsprechenden Vorlesung in Rostock im SS 1999 und WS 1999/2000. Es ist noch nicht vollständig; insbesondere fehlen einige längere Beweise wie z.B. der des Satzes von Cook zur NP-Vollständigkeit von SAT. Andererseits enthält es einige Ergänzungen, die die Darstellung abrunden wie z.B. die algebraische Beschreibung der berechenbaren Funktionen. Ausserdem sind die Übungsaufgaben mit Musterlösungen zu ausgewählten Aufgaben aufgenommen worden. Um Bemerkungen zu Fehlern bzw. zur Darstellung wird gebeten.