Grundkurs Theoretische Informatik

Theoretische Informatik - der Vorlesungsbegleiter. Berechenbarkeit, formale Sprachen, Algorithmik und Komplexitätstheorie sind theoretische Themen mit praktischer Relevanz, zu denen es ebenso praktische Zugänge gibt. Freuen Sie sich auf eine moderene Didaktik, die streng Formales mit Ihrer Intuition verknüpft, lernfreundlich ausarbeitet und schließlich zu jedem Thema Anwendungsfelder der Informatik vorstellt. Stefan Neubert hat nicht nur selbst Freude an der theoretischen Informatik, sondern widmet sich auch mit Leidenschaft ihrer Vermittlung zu Beginn und im Laufe des Bachelorstudiums. Eine Einführung mit vielen Aufgaben und Beispielen, auch zum Selbststudium geeignet.

Aus dem Inhalt:

• Grundlegende mathematische Notation


• Modelle und Grenzen der Berechenbarkeit


• Formale Sprachen: Endliche Automaten, kontextfreie Grammatiken, Pumping Lemmata und mehr


• Beweisverfahren für Korrektheit und Laufzeit von Algorithmen


• Paradigmen für den Algorithmenentwurf


• Amortisierte Analyse und untere Schranke für Laufzeiten


• NP-Vollständigkeit und Reduktion

  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