Diese Vorlesungsallsarbeitung beruht auf der Vorlesung Theoretische Grundlagen der Informatik, die ich im Wintersemester 1998/1999 an der Universität Konstanz gehalten habe. Im Sonimersemester 1993 und im Wintersemester 1995/1996 habe ich in Halle bzw. Konstanz Vorlesungen etwa gleichen Inhalts angeboten. Inhaltlich habe ich mich dabei sehr stark auf das Buch Theoretische Informatik von Ingo Wegener (erschienen 1993 bei Teubner) und ''den Garey & Johnson", also das Buch Computers and Intraclability: A Guide to the Theory of NP-Completeness von Michael R. Garey und David S. Johnson, gestützt.