Skip to main content
main-content

2022 | Buch

Grundlagen der Theoretischen Informatik

share
TEILEN
insite
SUCHEN

Über dieses Buch

Dieses Lehrbuch liefert eine verständliche, aber dennoch kompakte Einführung in die Theoretische Informatik. Die behandelten Themen bilden das Fundament für weiterführende Themen in der Theoretischen Informatik und sind zudem grundlegend für das formale Arbeiten in der gesamten Informatik. Durch eine Vielzahl von Aufgaben mit Lösungen eignet sich dieses Buch sehr gut zum Selbststudium.​

Inhaltsverzeichnis

Frontmatter
1. Einführung und formale Sprachen
Zusammenfassung
In diesem ersten Kapitel beschäftigen wir uns mit den Grundlagen, die notwendig sind, um die Inhalte dieses Buches verstehen zu können. Insbesondere wollen wir uns damit beschäftigen, wie wir algorithmische Probleme so aufschreiben können, dass wir sie mit einem Berechnungsmodell bearbeiten können. Für diesen Umgang benötigen wir einen formalen Kalkül, welchen wir in erster Linie über die formalen Sprachen festlegen werden. Eine formale Beschreibung hat nicht nur den Vorteil, dass wir die Sachen, über die wir reden, klar benennen können, sie hilft uns auch weiter, wenn unsere Vorstellungskraft nicht mehr ausreicht, um bestimmte Sachverhalte gänzlich zu überblicken.
André Schulz
2. Reguläre Sprachen
Zusammenfassung
In diesem Kapitel lernen wir mit den endlichen Automaten ein erstes Berechnungsmodell kennen. Dieses Modell orientiert sich am Rechnen mit begrenztem Speicher. Wir werden sehen, dass wir nur sehr einfache Probleme mit einem endlichen Automaten lösen können. Trotzdem ist der endliche Automat ein sehr wichtiges Modell, denn er bildet die Grundlage für weitere Modelle und findet als Modellierungswerkzeug in der gesamten Informatik vielfältige Anwendungen.
André Schulz
3. Kontextfreie Sprachen
Zusammenfassung
Wir haben im letzten Kapitel gesehen, dass bereits sehr einfache Sprachen wie L = {anbnn ≥ 0} nicht regulär sind. Das mag nicht überraschend sein, da wir mit begrenztem Speicher nicht das Wortproblem für diese Sprache entscheiden können. Dennoch steht wohl außer Frage, dass es sich bei L um keine komplizierte Sprache handelt. Wir können problemlos einen Algorithmus angeben, der das Wortproblem für L löst. Dafür müssen wir nur alle as am Anfang zusammenzählen und dann kontrollieren, ob nur bs folgen, und zwar genauso viele, wie wir as gezählt hatten. Diesen Algorithmus kann man nicht durch einen endlichen Automaten ausführen lassen, da in diesem Modell nicht unbeschränkt „gezählt“ werden kann. Wir werden in diesem Kapitel mit dem Kellerautomaten ein Berechnungsmodell vorstellen, in welchem wir den beschriebenen Algorithmus ausführen können. Unser Ziel ist es zudem, ein Modell zu finden, das möglichst nahe am endlichen Automaten bleibt. Die Sprachen, die ein Kellerautomat erkennt, nennen wir kontextfrei. Diese Sprachklasse ist eine sehr wichtige Sprachklasse mit vielen Anwendungen in der Informatik (zum Beispiel beim Entwurf von Programmiersprachen). Das Modell des Kellerautomaten ist ein nichtdeterministisches Modell. Daraus lässt sich aber auch eine deterministische Version ableiten. Wie wir sehen werden, sind diese Modell (anders als bei den endlichen Automaten) nicht gleich mächtig.
André Schulz
4. Entscheidbare und erkennbare Sprachen
Zusammenfassung
In diesem Kapitel lernen wir die entscheidbaren Sprachen kennen und stellen mit der Turingmaschine das dazugehörige Rechenmodell vor. Die Turingmaschine ist das Modell, welches einen idealisierten Rechner nachbildet. Turingmaschinenprogramme (also konkrete Realisierungen von Turingmaschinen) sind genauso mächtig wie Programme in typischen Programmiersprachen wie zum Beispiel C, Java oder Python. Demnach handelt es sich bei den Sprachen, die durch die Turingmaschinen erkannt werden können, um die Sprachen, für die wir einen Algorithmus (nach unserem intuitiven Verständnis des Begriffes Algorithmus) für das Wortproblem dieser Sprachen angeben können. In der Tat werden wir das Modell der Turingmaschine benutzen, um zu definieren, was wir unter einem Algorithmus oder „das, was wir berechnen können“ verstehen.
André Schulz
5. Unentscheidbare Sprachen
Zusammenfassung
Bislang haben wir uns mit verschiedenen Berechnungsmodellen beschäftigt. Dies waren unter anderem der endliche Automat, der Kellerautomat und die Turingmaschine. Jedem dieser Modelle haben wir eine (oder auch mehrere) Sprachklassen zugeordnet: dem endlichen Automaten die regulären Sprachen, dem Kellerautomaten die kontextfreien Sprachen und der Turingmaschine die entscheidbaren und erkennbaren/aufzählbaren Sprachen. Bei der Untersuchung dieser Sprachklassen haben wir festgestellt, dass die regulären Sprachen eine echte Teilmenge der kontextfreien Sprachen sind und diese wiederum eine echte Teilmenge der entscheidbaren Sprachen. Der Fokus lag bislang darauf, die „Berechenbarkeit“ von Sprachen (beziehungsweise Entscheidungsproblemen) nachzuweisen. Nun werden wir uns im Gegensatz dazu auf den Nachweis der „Nichtberechenbarkeit“ konzentrieren. Wir versuchen zudem, die Grenze zwischen Nichtberechenbaren und Berechenbaren möglichst gut zu bestimmen.
André Schulz
6. Komplexitätstheorie
Zusammenfassung
Bislang haben wir uns mit der Frage beschäftigt, ob ein Problem in einem bestimmten Modell berechenbar ist oder nicht. Dabei wurde ausgeblendet, wie aufwendig eine mögliche Berechnung ist. So kann es natürlich vorkommen, dass es einen Algorithmus für ein Problem gibt, dessen Laufzeit jedoch so hoch ist, dass wir ihn nicht einsetzen können. Schlimmer noch, es könnte sogar sein, dass alle Algorithmen für ein konkretes Problem eine lange Rechenzeit erfordern.
In der Komplexitätstheorie geht es unter anderem darum, Probleme entsprechend ihres Aufwandes zu klassifizieren. Dabei sind in erster Linie zwei Maße von Interesse: Rechenzeit und Speicherbedarf. In diesem Kapitel werden wir uns damit beschäftigen, wie man Probleme sinnvoll in Klassen entsprechend ihrer Komplexität zusammenfassen kann. Dabei konzentrieren wir uns zunächst auf die Zeitkomplexität, das heißt den Aufwand an Rechenzeit.
André Schulz
Backmatter
Metadaten
Titel
Grundlagen der Theoretischen Informatik
verfasst von
André Schulz
Copyright-Jahr
2022
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-65142-1
Print ISBN
978-3-662-65141-4
DOI
https://doi.org/10.1007/978-3-662-65142-1