Grundkurs Theoretische Informatik

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 Methoden- Kreativ knobeln, Probleme lösen und Beweise finden- Ideal zum Selbststudium und als Vorlesungsbegleiter 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*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.

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