Berechnungstheorie für Informatiker

Der Inhalt dieses Buches entspricht weitgehend dem Stoff, den die beiden Autoren seit mehreren Jahren in einem zweisemestrigen Kurs fur Informatiker an der ETH Z rich vermitteln. Vieles davon ist bereits fr her in der Form von provisorischen Notizen von E. Engeler als "Kleines Repetitorium der Berechnungstheorie" an die Stu- denten abgegeben worden. Bei der Niederschrift des nun vorliegenden Textes hat sich immer deutlicher gezeigt, dass sich eine weitgehend unabh ngige Redaktion der beiden, jetzt auch im Inhaltsverzeichnis abgegrenzten Teile, sowohl arbeitstechnisch als auch von der Stoffbehandlung her, als durchaus nat rlich aufdr ngte. So hat denn P. L uchli den ersten, E. Engeier den zweiten Teil selbst ndig betreut. Wir haben uns zwar punkto Notation weitgehend abgesprochen, nehmen jedoch eine gewisse Verschiedenheit im Stil bewusst in Kauf. F r die Lekt re des Buches wird vorausgesetzt, dass der Leser ber das mathema- tische R stzeug verfugt, welches etwa in einem elementaren Kurs "Diskrete Mathema- tik" in den unteren Semestern eines Hochschulstudiums, Richtung Informatik oder Elek- trotechnik, angeboten wird. Dazu geh ren jedenfalls Grundbegriffe bez glich Mengen, Funktionen, Relationen etc. Der erste Teil, im allgemeinen elementarer formuliert, entspricht ungefahr der oben erw hnten ersten Vorlesung ("Berechnungstheorie," 4. Semester), in welcher vor allem der Berechenbarkeitsbegriff herausgearbeitet und eine erste Bekanntschaft mit der Erzeu- gung, bzw. Erkennung von formalen Sprachen anhand der ausf hrlich diskutierten regul ren Sprachen vermittelt wird. Die anschliessend eingefuhrte Fixpunkttheorie soll dem Studenten ein theoretisches Werkzeug in die Hand geben, welches ihm erlaubt, ver- schiedene Gegenst nde von einem einheitlichen Standpunkt aus zu betrachten.