Neubert Grundkurs Theoretische Informatik

1. Auflage 2021
ISBN: 978-3-8362-7590-3
Verlag: Rheinwerk
Format: EPUB
Kopierschutz: 0 - No protection

E-Book, Deutsch, 416 Seiten

Reihe: Rheinwerk Computing

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

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.

Autoren/Hrsg.

Neubert, Stefan

Inhaltsverzeichnis

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

Über Autor(innen)

Neubert, Stefan
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.