Kapitel 9 - Komplexität Flashcards
(18 cards)
Teilbereiche der Theoretischen Informatik
- Formale Sprachen: struktureller Aufbau von Programmiersprachen -> Spezifikation von Programmiersprachen und Compilern, Sprachübersetzungen durch Maschinen
- Automatentheorie: mathematische Modelle des Computers -> Entwurf von Schaltkreisen
- Berechenbarkeitstheorie: vorhersagen können, für welche Probleme es überhaupt Algorithmen gibt
- Komplexitätstheorie: vorhersagen, mit welchem Aufwand (Laufzeit oder Speicherplatzbedarf) ein Problem lösbar ist
Endlicher Automat
= Programm = Programmzeile mit…
- möglichen Einfaben
- Anweisungen zur Verarbeitung des Eingabewortes
Endliche Maschine
- Anwendung
- Grundlage für Werkzeuge und Spezifikation, automatische Generierung und zum Testen von Schaltwerken
- Endliche Maschine = endlicher Automat + Ausgabe
- Endliche Maschine kann durch einen endlichen Automaten simuliert werden
- Endlicher Automat akzeptiert Sprachen, endliche Maschine transformiert Eingabewörter in Ausgabewörter
Modellierung
- Endliche Automaten und Maschinen modellieren sequenzielle Zustandsübergänge
- Modellierung durch (UML) Zustandsdiagramm
- Modellierung paralleler Zustandsübergänge
- Zellulare Automaten: synchrone parallele Zustandsübergänge
- Petri-Netze: asynchrone
Deterministischer endlicher Automat
- Für jeden Zustand + Eingabesymbol / Übergang gibt es höchstens einen möglichen Endzustand
- In einem vollständigen Automaten gibt es genau einen möglichen Endzustand
Turing-Maschine
- Maschine / Automat = mathematisches Modell eines Computers
- Turing-Maschine: ursprünglich als Modell des menschlichen Rechners
- Turing-Modell zerlegt Berechnungen in kleinste Operationen
- Unendliches, in gleichgroße Zellen unterteiltes Band, auf dem sich ein Schreib-/Lesekopf rechts und links zu den Zellen bewegt
- Endlich viele Zeichen, einschließlich Leerzeichen
- Operationen: Lesen, Schreiben, Band verschieben und Merken (Speichern)
Unterschied zu echtem Rechner?
- Turing-Maschine ist für eine bestimmte Aufgabe oder Funktion fest entworfen, kann nicht programmiert werden
Kellerautomat
- Endliche Automaten haben endliches Gedächtnis -> endliche Anzahl von Zuständen -> können schon sehr einfache Sprachen nicht akzeptieren
- Endlicher Automat + Speicher (=Keller) = Kellerautomat
- Keller ist beliebig groß, aber beschränkte Zugriffsmöglichkeiten: LIFO-Prinzip = last in, first out
- Kellerautomat erkennt genau die kontextfreien Sprachen
- Kellerautomat ist per Definition zunächst nichtdeterministisch
- Speicher/Keller: Die Aktionen eines Kellerautomaten hängen nicht nur vom Zustand und eingelesenen Eingabezeichen ab, sondern auch vom Kellerinhalt
Berechenbarkeit und Entscheidbarkeit
Aufzählbarkeit
Aufzählbare Mengen sind genau die Mengen, deren Elemente durch eine Turing-Maschine aufgezählt werden können
Berechenbarkeit und Entscheidbarkeit
Entscheidbarkeit
- Eine Menge ist entscheidbar, wenn für jedes beliebige Wort entschieden werden kann, ob es Teil der Menge ist oder nicht (“Spracherkennung”)
- Entscheidbare Mengen sind eine Unterklasse der aufzählbaren Mengen
Berechenbarkeit und Entscheidbarkeit
Entscheidbarkeit: Wortproblem
Existiert ein Algorithmus, der zu einer gegebenen Turing-Maschine T und einem gegebenen Wort w € Σ* entscheidet, ob T das Wort akzeptiert -> nein
Berechenbarkeit und Entscheidbarkeit
Wortproblem: Anwendung
- Relevante Frage für den Compilerbau: Compiler muss entscheiden, ob ein Wort zu einer Programmiersprache gehört
- Ist eine Sprachklasse nicht entscheidbar, ist sie als Programmiersprache nicht geeignet
Berechenbarkeit und Entscheidbarkeit
Entscheidbarkeit: Äquivalenzproblem
Es gibt keinen Algorithmus, der für zwei deterministische Turing-Maschinen Ti und Tj entscheidet, ob sie dieselbe Sprache akzeptieren -> Es gibt auch keinen Algorithmus, der prüft, ob zwei Computerprogramme bei gleicher Eingabe dieselbe Ausgabe liefern
Komplexitätstheorie
- Ziel: Aussagen über Aufwand algorithmischer Prozesse auf einer Maschine
- Verwendet formale Maschinenmodelle wie Turing-Maschine
Zeitkomplexität
siehe Zusammenfassung
Bandkomplexität Si(n)
- Die Bandkomplexität Si(n) einer Turing-Maschine Ti bei Ansetzen auf ein beliebiges Wort der Länge n ist die Anzahl der im Laufe der Rechnung belegten Zellen.
- Die Bandkomplexität S(n) eines Problems ist S(n) = mini Si(n)
Kolmogorow-Komplexität
- Die Kolmogorow-Lomplexität ist ein Maß für die Strukturiertheit einer Zeichenkette = die Länge des kürzesten Programms, das die Zeichenkette erzeugt = beste Komprimierung der Zeichenkette, ohne dass Information verloren geht
- Wenn die Kolmogorow-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selbst, dann bezeichnet man die Zeichenkette als unkomprimierbar, zufällig oder auch strukturlos. Je näher die Kolmogorow-Komplexität an der Länge der Zeichenkette liegt, desto “zufälliger” ist die Zeichenkette (und desto mehr Information enthält sie).
Komplexitätsklasse P
Zu jedem Problem der Klasse P existiert eine deterministische Turingmaschine, welche das Problem löst und zu der ein Polynom der Form n^k angegeben werden kann, welches die Zeitkomplexität des Lösens im Verhältnis zur Eingabelänge n nach oben beschränkt. Probleme aus P sind somit deterministisch in Polynomialzeit lösbar.
Komplexitätsklasse NP
- Die Komplexitätsklasse NP ist die Menge aller von nichtdeterministischen Turingmaschinen in Polynomialzeit lösbaren Probleme
- Da sich die Probleme aus P natürlich auch nichtdeterministisch in Polynomialzeit lösen lassen, ist P eine Teilmenge von NP
- P c NP
- Gibt es komplexere Probleme als NP-vollständige Probleme? Ja!
