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

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

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

Autorentext
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.

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

  Zusammenfassung
  »Ein anspruchsvolles Buch für Informatikstudenten und für alle, die sich für das theoretische Fundament der Informatik interessieren.« LINUX MAGAZIN 202108

  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-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

  …