Informatik III

Informatik III Skript zur Vorlesung von Prof. Dr. Dorothea Wagner WS 04/05

ausgearbeitet von Marco Gaertler und Dagmar Handke uberarbeitet von ¨ Silke Wagner

ii

Vorwort

Diese Vorlesungsausarbeitung beruht auf der Vorlesung Informatik III, die ich im Wintersemester 2003/2004 an der Universit¨t Karlsruhe gehalten habe. Im a Sommersemester 1993 und in den Wintersemestern 1995/1996 und 1998/1999 habe ich bereit in Halle bzw. Konstanz Vorlesungen uber die theoretischen ¨ Grundlagen der Informatik angeboten. Die Vorlesung Informatik III ist aus diesen Vorlesungen weiterentwickelt worden. Inhaltlich habe ich mich dabei sehr stark auf das Buch Theoretische Informatik von Ingo Wegener (erschienen bei Teubner) und “den Garey & Johnson”, also das Buch Computers and Intractability: A Guide to the Theory of NP-Completeness von Michael R. Garey und David S. Johnson, gest¨tzt. u Das vorliegende Skript ist eine reine Vorlesungsausarbeitung, kein Lehrbuch. Entsprechend ist es sprachlich eher knapp gehalten und inhaltlich sicher an einigen Stellen weit weniger umfangreich, als es ein entsprechendes Lehrbuch sein sollte. Ich hoffe, dass es trotzdem den Studierenden bei der Nacharbeitung des Vorlesungsstoffs und der Pr¨fungsvorbereitung hilfreich sein wird. u Karlsruhe, im Oktober 2004 Dorothea Wagner

Inhaltsverzeichnis

1 Einf¨hrung u 1.1 Einf¨hrende Beispiele . . . . . . . . . . . . . . . . . . . . . . . . u 1 1 7 7 13 25 33 33 34 34 40 40 42 49 49 54 56 72 74 78 79 79 80 85

2 Endliche Automaten 2.1 2.2 2.3 Deterministische endliche Automaten . . . . . . . . . . . . . . . . Nichtdeterministische endliche Automaten . . . . . . . . . . . . . ¨ Aquivalenzklassenautomat . . . . . . . . . . . . . . . . . . . . . .

3 Turing-Maschine, Berechenbarkeit 3.1 3.2 Die Registermaschine . . . . . . . . . . . . . . . . . . . . . . . . . Die Turing-Maschine . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 3.2.2 3.2.3 3.3 Der Aufbau der Turing-Maschine . . . . . . . . . . . . . . Die Church’sche These . . . . . . . . . . . . . . . . . . . . Erweiterungen der Turing-Maschine . . . . . . . . . . . .

Die universelle Turing-Maschine . . . . . . . . . . . . . . . . . . .

4 Komplexit¨tsklassen a 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Sprachen, Probleme, eitkomplexit¨t . . . . . . . . . . . . . . . . a Nichtdeterministische Turing-Maschinen . . . . . . . . . . . . . . N P–vollst¨ndige Probleme . . . . . . . . . . . . . . . . . . . . . a Komplementsprachen . . . . . . . . . . . . . . . . . . . . . . . . . Weitere Komplexit¨tsklassen uber N P hinaus . . . . . . . . . . . a ¨ Pseudopolynomiale Algorithmen . . . . . . . . . . . . . . . . . . Approximationsalgorithmen . . . . . . . . . . . . . . . . . . . . . 4.7.1 4.7.2 4.7.3 Approximation mit Differenzengarantie . . . . . . . . . . Approximation mit relativer G¨tegarantie . . . . . . . . . u Approximationsschemata . . . . . . . . . . . . . . . . . .

i