Aus der Buchreihe »Informatik verstehen«. Ideal zum Studium als Vorlesungsbegleiter

Theoretische Informatik: Lernen mit Spaß und Erfolg!Theoretische Informatik der Vorlesungsbegleiter. Berechenbarkeit, formale Sprachen, Algorithmik, Komplexitätstheorie: All das sind theoretische Themen mit praktischer Relevanz, zu denen es ebenso praktische Zugänge gibt. Und die finden Sie in diesem neuen Grundkurs aus der Reihe »Informatik verstehen«.Freuen Sie sich auf moderne Didaktik, die streng Formales mit Ihrer eigenen Intuition verknüpft. Die einzelnen Kapitel des Buches sind lernfreundlich ausgearbeitet und stellen zu jedem Thema die Verbindung zu den Aufgabenfeldern der Informatik her.Stefan Neubert hat nicht nur selbst Freude an der theoretischen Informatik, sondern widmet sich auch mit Leidenschaft der Aufgabe, sie zu Beginn und im Laufe des Bachelorstudiums zu vermitteln. Mit diesem Buch legt er eine erhellende Einführung in die Theoretische Informatik vor, die Sie mit vielen anschaulichen Aufgaben und Beispiele beim Lernen unterstützt. Auch zum Selbststudium geeignet.Intuitive Zugänge, praktische Anwendungen, formale MethodenKreativ knobeln, Probleme lösen und Beweise findenIdeal zum Selbststudium und als Vorlesungsbegleiter Aus dem Inhalt:Grundlegende mathematische NotationModelle und Grenzen der BerechenbarkeitFormale Sprachen: Endliche Automaten, kontextfreie Grammatiken, Pumping Lemmata und mehrBeweisverfahren für Korrektheit und Laufzeit von AlgorithmenParadigmen für den AlgorithmenentwurfAmortisierte Analyse und untere Schranke für LaufzeitenNP-Vollständigkeit und Reduktion

»Das Buch hier bietet einen guten, intuitiven Zugang zu diesem Fach und eignet sich hervorragend als Vorlesungsbegleiter und auch zum Selbststudium.«

Vorwort
Aus der Buchreihe »Informatik verstehen«. Ideal zum Studium als Vorlesungsbegleiter

Autorentext
Stefan Neubert hat zahlreiche Informatik-Workshops und -Camps für Schüler*innen entwickelt und durchgeführt. Studierende im Bachelor-Studiengang haben seine langjährige Tätigkeit in der Lehrveranstaltung "Theoretische Informatik" mit einem Lehrpreis belohnt, weil er mit Leidenschaft dafür arbeitet, komplexe Themen verständlich zu machen. Inzwischen arbeitet er als Program Manager für den Bachelor-Studiengang am Hasso-Plattner-Institut, wo er zuvor auch studiert, unterrichtet und geforscht hat. An der Informatik schätzt er besonders, dass sie Kreativität und Teamfähigkeit erfordert, obwohl das vielleicht oft nicht vermutet wird. Lernende schätzen seine verständliche Sprache und anschaulichen Beispiele vor allem dann, wenn es anspruchsvoller wird.

Klappentext

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

  Inhalt

  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…