Stefan Neubert hat zahlreiche Informatik-Workshops und -Camps für Schüler entwickelt und durchgeführt. Er unterstützt seit Jahren die Bachelor-Lehrveranstaltung "Theoretische Informatik" als Tutor und arbeitet mit Leidenschaft dafür, komplexe Themen verständlich zu machen. Der PhD-Student am Hasso-Plattner-Institut schätzt sein Fach auch dafür, dass es Kreativität und Teamfähigkeit erfordert, obwohl das vielleicht oft nicht vermutet wird. Schüler wie Leser schätzen seine verständliche Sprache und anschaulichen Beispiele - vor allem dann, wenn es anspruchsvoller wird.

Ideal zum Selbststudium und als Vorlesungsbegleiter

1. Einführung ... 15

1.1 ... Kompetenzen für die theoretische Arbeit ... 16

1.2 ... Themen der theoretischen Informatik ... 18

1.3 ... Anleitung fürs Buch ... 20

1.4 ... Danksagungen ... 21

2. Mathematische Notation ... 23

2.1 ... Logische Aussagen ... 24

2.2 ... Mengen ... 27

2.3 ... Relationen und Funktionen ... 32

2.4 ... Graphen ... 37

2.5 ... Unendlichkeiten und Abzählbarkeit ... 40

2.6 ... Beweistechniken ... 42

2.7 ... Aufgaben ... 57

2.8 ... Lösungen ... 58

TEIL I. Berechenbarkeit und formale Sprachen ... 65

3. Einführung in die Berechenbarkeitstheorie ... 67

3.1 ... Algorithmus ... 68

3.2 ... Zu viele Funktionen ... 69

3.3 ... Das Halteproblem ... 70

3.4 ... Kontrollfragen ... 72

3.5 ... Antworten ... 72

4. Problemtypen ... 73

4.1 ... Formalisierung von Problemen ... 73

4.2 ... Funktionen berechnen ... 75

4.3 ... Datencodierung ... 75

4.4 ... Sprachen entscheiden ... 78

4.5 ... Problemklassen der Berechenbarkeitstheorie ... 79

4.6 ... Aufgaben ... 82

4.7 ... Lösungen ... 83

5. Einführung in formale Sprachen ... 85

5.1 ... Definition ... 85

5.2 ... Die Chomsky-Hierarchie ... 88

5.3 ... Aufgaben ... 89

5.4 ... Lösungen ... 90

6. Reguläre Sprachen ... 91

6.1 ... Deterministische endliche Automaten ... 92

6.2 ... Nichtdeterministische endliche Automaten ... 103

6.3 ... Grammatiken ... 111

6.4 ... Reguläre Ausdrücke ... 120

6.5 ... Abschlusseigenschaften ... 127

6.6 ... Entscheidungsprobleme auf regulären Sprachen ... 132

6.7 ... Äquivalenzklassenzerlegung ... 134

6.8 ... Nichtreguläre Sprachen ... 139

6.9 ... Ausblick ... 144

6.10 ... Aufgaben ... 144

6.11 ... Lösungen ... 149

7. Kontextfreie Sprachen ... 161

7.1 ... Kontextfreie Grammatiken ... 162

7.2 ... Eindeutige Ableitungsbäume ... 164

7.3 ... Chomsky-Normalform ... 166

7.4 ... Exkurs: Kellerautomaten ... 170

7.5 ... Abschlusseigenschaften ... 175

7.6 ... Entscheidungsprobleme auf kontextfreien Sprachen ... 176

7.7 ... Nicht-kontextfreie Sprachen ... 181

7.8 ... Ausblick ... 183

7.9 ... Aufgaben ... 184

7.10 ... Lösungen ... 186

8. Kontextsensitive Sprachen ... 193

8.1 ... Kontextsensitive und monotone Grammatiken ... 194

8.2 ... Das Wortproblem auf kontextsensitiven Sprachen ... 195

9. Aufzählbare Sprachen ... 197

9.1 ... Turingmaschinen ... 199

9.2 ... While-Programme ... 202

9.3 ... Gödelnummern ... 218

9.4 ... Das universelle While-Programm ... 220

9.5 ... Das schrittbeschränkte universelle While-Programm ... 223

9.6 ... Diagonalisierung und min-Suche ... 224

9.7 ... Prädikate für semi-entscheidbare Sprachen ... 226

9.8 ... Semi-Entscheidbarkeit vs. Aufzählbarkeit ... 227

9.9 ... Das S-m-n-Theorem ... 228

9.10 ... Das kleenesche Rekursionstheorem ... 230

9.11 ... Weitere Modelle und Charakterisierungen ... 233

9.12 ... Aufgaben ... 233

9.13 ... Lösungen ... 235

10. Nicht Berechenbares ... 241

10.1 ... Beweise mit KRT ... 243

10.2 ... Der Satz von Rice ... 244

10.3 ... Reduktionen ... 246

10.4 ... RE-Vollständigkeit ... 250

10.5 ... Ausblick: Die arithmetische Hierarchie ... 251

10.6 ... Aufgaben ... 252

10.7 ... Lösungen ... 254

TEIL II. Algorithmik ... 259

11. Einführung in Algorithmik ... 261

12. Obere Schranken für Laufzeiten ... 263

12.1 ... Das Maschinenmodell ... 264

12.2 ... Die Laufzeit eines Algorithmus ... 267

12.3 ... Die Größe einer Eingabe ... 268

12.4 ... Die Landau-Notation ... 268

12.5 ... Aufgaben ... 271

12.6 ... Lösungen ... 272

13. Laufzeiten von Datenstrukturen ... 275

13.1 ... Arrays ... 275

13.2 ... Listen ... 277

13.3 ... Verschachtelte Datenstrukturen und Graphen ... 279

13.4 ... Aufgaben ... 281

13.5 ... Lösungen ... 282

14. Brute-Force-Algorithmen ... 285

14.1 ... Lineare Suche ... 286

14.2 ... Backtracking/Tiefensuche ... 288

14.3 ... Aufgaben ... 292

14.4 ... Lösungen ... 293

15. Greedy-Algorithmen ... 295

15.1 ... Beweis mit Austauschargument ... 296

15.2 ... Greedy stays ahead ... 302

15.3 ... Aufgaben ... 304

15.4 ... Lösungen ... 306

16. Divide and Conquer ... 313

16.1 ... Mergesort ... 314

16.2 ... Binäre Suche ... 319

16.3 ... Multiplikation großer Zahlen ... 321

16.4 ... Das Mastertheorem ... 325

16.5 ... Ausblick ... 326

16.6 ... Aufgaben ... 327

16.7 ... Lösungen ... 329

17. Dynamische Programmierung ... 335

17.1 ... Fibonacci-Zahlen ... 336

17.2 ... Rückgeld geben ... 337

17.3 ... Der Algorithmus von Dijkstra ... 341

17.4 ... Aufgaben ... 344

17.5 ... Lösungen ... 346

18. Amortisierte Analyse ... 351

18.1 ... Dynamische Arrays ... 351

18.2 ... Guthabenmethode ... 353

18.3 ... Ausblick ... 353

TEIL III. Komplexitätstheorie ... 355

19. Einführung in die Komplexitätstheorie ... 357

19.1 ... Die Komplexität eines Problems ... 358

19.2 ... Bedingte Schranken ... 358

19.3 ... Auswege für schwierige Probleme ... 359

20. Beweistechniken für untere Schranken ... 361

20.1 ... Die Ausgabegröße ... 362

20.2 ... Das informationstheoretische Argument ... 363

20.3 ... Das Adversary-Argument ... 367

20.4 ... Reduktionen ... 370

20.5 ... Aufgaben ... 372

20.6 ... Lösungen ... 374

21. P vs. NP: Bedingte untere Schranken ... 377

21.1 ... Die Komplexitätsklasse P ... 378

21.2 ... Die Komplexitätsklasse NP ... 380

21.3 ... Polynomialzeitreduktionen ... 388

21.4 ... NP-schwere und NP-vollständige Probleme ... 392

21.5 ... Ausblick: Mehr NP-vollständige Probleme ... 404

21.6 ... Aufgaben ... 405

21.7 ... Lösungen ... 406

22. Ausblick: Parametrisierte Analyse ... 408

Index ... 410