nach oben

2024 | Buch

Automaten und Sprachen: Theoretische Informatik für die Praxis

Mathematik, Anwendung, Intuition

verfasst von: Andreas Müller

Verlag: Springer Berlin Heidelberg

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Inhaltsverzeichnis

Über dieses Buch

Dieses Lehrbuch entwickelt die theoretischen Grundlagen der Informatik mit möglichst direktem Anwendungsbezug: Es versteht die theoretische Informatik als einen Werkzeugkasten, der es Softwareingenieuren und -entwicklern erlaubt, informierte Designentscheidungen in ihren Entwicklungsprojekten zu fällen und eine entsprechende Intuition dafür zu entwickeln.

Das Buch richtet sich insbesondere an Studierende an Fachhochschulen bzw. Hochschulen für angewandte Wissenschaften, kann aber auch beim Quereinstieg oder zur Wissensauffrischung wertvolle Dienste leisten. Behandelt werden endliche Automaten und reguläre Ausdrücke, kontextfreie Grammatiken und Stackautomaten, Turing-Maschinen und Turing-Vollständigkeit, Entscheidbarkeit, Komplexität und NP-Vollständigkeit sowie Quantencomputer. Innerhalb der Kapitel sind Aufgaben zur Verständniskontrolle und am Ende jedes Kapitels abschließende Übungsaufgaben bereitgestellt – die Lösungen dazu sind jeweils per QR-Code verlinkt und online verfügbar. Letzteres gilt außerdem für den Anki-Lernkartenstapel, den der Autor als digitale Ergänzung zum Buch anbietet.

Inhaltsverzeichnis

Frontmatter

Kapitel 1. Reguläre Sprachen

Zusammenfassung

Deterministische endliche Automaten sind die einfachsten Arten von abstrakten Maschinen. Sie definieren aber bereits eine wichtige und praktisch nützliche Klasse von Sprachen, die sogenannten regulären Sprachen. Eine Vielzahl von Algorithmen stehen zur Konstruktion und Optimierung der endlichen Automaten für reguläre Sprachen zur Verfügung.

Andreas Müller

Kapitel 2. Nicht reguläre Sprachen

Zusammenfassung

Nicht jede Sprache ist regulär. Das Pumping-Lemma für reguläre Sprachen ist ein praktisch nützliches Werkzeug, welches erlaubt zu erkennen, wenn man den Bereich der regulären Sprachen verlässt.

Andreas Müller

Kapitel 3. Nichtdeterministische endliche Automaten

Zusammenfassung

Nichtdeterminismus ist ein mächtiges Werkzeug, mit dem die Konstruktion und das Studium von endlichen Automaten vereinfacht werden kann.

Andreas Müller

Kapitel 4. Reguläre Operationen und reguläre Ausdrücke

Zusammenfassung

Reguläre Operationen sind die natürlicheren Operationen als die Mengenoperationen von Kapitel 3. Aus ihnen lässt sich mit den regulären Ausdrücken auch eine sehr effiziente und intuitive Spezifikationssprache für reguläre Sprachen entwickeln, die vielfältige Anwendungen hat.

Andreas Müller

Kapitel 5. Kontextfreie Grammatiken und Sprachen

Zusammenfassung

Grammatiken ermöglichen viele Sprachelemente zu spezifizieren, für die reguläre Sprachen nicht reichen. Der daraus abgeleitete Syntaxbaum eines Sprachausdrucks ermöglicht die Auswertung.

Andreas Müller

Kapitel 6. Parsing

Zusammenfassung

Grammatiken sind das naheliegende Werkzeug zur Spezifikation einer formalen Sprache. Damit wird die Syntaxanalyse auf der Basis einer Grammatik die wichtigste Aufgabe des Parsers einer Programmiersprache.

Andreas Müller

Kapitel 7. Stackautomaten

Zusammenfassung

Der CYK-Algorithmus zur Syntaxanalyse ist viel zu langsam und daher nicht sinnvoll praktisch einsetzbar. Stackautomaten bilden die Basis für ein erfolgreicheres Konzept, den LR-Parser. Fast alle modernen Programmiersprachen können mit einem solchen Parser analysiert werden.

Andreas Müller

Kapitel 8. Nicht kontextfreie Sprachen

Zusammenfassung

Grammatiken und Stackautomaten sind nur anwendbar auf kontextfreie Sprachen. Das Pumping-Lemma für kontextfreie Sprachen ist ein handliches Werkzeug, um Sprachen als nicht kontextfrei zu erkennen.

Andreas Müller

Kapitel 9. Abzählbar und überabzählbar unendlich

Zusammenfassung

Sprachen basieren immer auf einem endlichen Alphabet und setzen sich aus endlichen Wörtern zusammen. Trotzdem können Sprachen unendlich viele Wörter haben. Es ist daher wichtig zu verstehen, was unendlich genau heißt. Die Menge aller Wörter ist abzählbar unendlich, die Menge aller Sprachen dagegen überabzählbar.

Andreas Müller

Kapitel 10. Turing-Maschinen

Zusammenfassung

Die Turing-Maschine ist die mathematische Abstraktion eines Computers. Es zeigt sich, dass die vielen Varianten von Turing-Maschinen alle im Wesentlichen die gleichen Fähigkeiten haben und damit ein gutes Modell sind, um mathematische Aussagen über reale Computerprogramme zu erhalten.

Andreas Müller

Kapitel 11. Entscheidbarkeit

Zusammenfassung

Nicht jede Aufgabe lässt sich mit einem Computer lösen. Das von Alan Turing entdeckte Halteproblem ist wahrscheinlich das berühmteste solche Problem. Es steht aber nicht alleine, eine ganze Familie von Problemen sind nicht entscheidbar.

Andreas Müller

Kapitel 12. Komplexität

Zusammenfassung

Zu lange Laufzeit ist der häufigste Grund für unbefriedigende Leistung einer Anwendung in der Praxis. Oft ist nicht die Hardware schuld, sondern das Problem ist grundsätzlich schwierig. Die Komplexitätstheorie untersucht hardwareunabhängige Eigenschaften von Algorithmen, deren Performance nicht skalieren wird und gibt dem Praktiker damit ein Entscheidungswerkzeug in die Hand, wie er problematische Anwendungsteile von vornherein so gestalten, kann dass er diesen Schwierigkeiten aus dem Weg gehen kann.

Andreas Müller

Kapitel 13. NP-Vollständigkeit

Zusammenfassung

Unter den NP-Problemen sind jene besonders interessant, auf die sich alle anderen polynomiell reduzieren lassen. Dass es solche Probleme überhaupt gibt, ist die überraschende Aussage des Satzes von Cook-Levin. Eine große Zahl von NP-vollständigen Problemen gibt dem Praktiker die Möglichkeit, durch Vergleich Skalierungsprobleme in Aufgabenstellung in der Praxis rechtzeitig zu erkennen.

Andreas Müller

Kapitel 14. Programmiersprachen und Turing-Vollständigkeit

Zusammenfassung

In der Praxis werden Turing-Maschinen mit höheren Programmiersprachen programmiert. Dabei besteht die Gefahr, dass wichtige Fähigkeiten der Turing-Maschine durch die verwendete Sprache eingeschränkt werden. Durch sorgfältig konstruierte primitive Programmiersprachen kann man herausfinden, welche Sprachelemente notwendig sind, um die Fähigkeiten einer Turing-Maschine zu erlangen.

Andreas Müller

Kapitel 15. Quantencomputer

Zusammenfassung

Quantencomputer versprechen die Lösung gewisser besonders schwieriger Probleme. So wie klassische Computer eine physikalische Realisierung des mathematischen Konzepts der Turing-Maschine mit Hilfe der klassischen Physik sind, versucht ein Quantencomputer eine nach den Gesetzen dar mathematischen Theorie der Quantenberechnung ablaufende Berechnung mit quantenphysikalischen Messungen zu realisieren. Die Überlagerung von Teilchenzuständen ist dabei das zentrale Werkzeug, welches exponentielle Beschleunigung in gewissen Problemen ermöglichen könnte.

Andreas Müller

Kapitel 16. Grundlagen und Bezeichnungen

Zusammenfassung

Die theoretische Informatik braucht die elementare mathematische Logik und die Mengenlehre als Grundlage. Im Anhang werden die im Buch benötigten Grundlagen zusammengestellt und die verwendete Schreibweise festgelegt.

Andreas Müller

Backmatter

Titel: Automaten und Sprachen: Theoretische Informatik für die Praxis
verfasst von: Andreas Müller
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-70146-1
Print ISBN: 978-3-662-70145-4
DOI: https://doi.org/10.1007/978-3-662-70146-1