Kapitel 9 - Komplexität

Question 1

Teilbereiche der Theoretischen Informatik

Answer 1

• 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

Question 2

Endlicher Automat

Answer 2

= Programm = Programmzeile mit…

• möglichen Einfaben
• Anweisungen zur Verarbeitung des Eingabewortes

Question 3

Endliche Maschine

Answer 3

• 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

Question 4

Modellierung

Answer 4

• 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

Question 5

Deterministischer endlicher Automat

Answer 5

• 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

Question 6

Turing-Maschine

Answer 6

• 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

Question 7

Kellerautomat

Answer 7

• 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

Question 8

Berechenbarkeit und Entscheidbarkeit

Aufzählbarkeit

Answer 8

Aufzählbare Mengen sind genau die Mengen, deren Elemente durch eine Turing-Maschine aufgezählt werden können

Question 9

Berechenbarkeit und Entscheidbarkeit

Entscheidbarkeit

Answer 9

• 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

Question 10

Berechenbarkeit und Entscheidbarkeit

Entscheidbarkeit: Wortproblem

Answer 10

Existiert ein Algorithmus, der zu einer gegebenen Turing-Maschine T und einem gegebenen Wort w € Σ* entscheidet, ob T das Wort akzeptiert -> nein

Question 11

Berechenbarkeit und Entscheidbarkeit

Wortproblem: Anwendung

Answer 11

• 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

Question 12

Berechenbarkeit und Entscheidbarkeit

Entscheidbarkeit: Äquivalenzproblem

Answer 12

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

Question 13

Komplexitätstheorie

Answer 13

• Ziel: Aussagen über Aufwand algorithmischer Prozesse auf einer Maschine
• Verwendet formale Maschinenmodelle wie Turing-Maschine

Question 14

Zeitkomplexität

Answer 14

siehe Zusammenfassung

Question 15

Bandkomplexität S_i(n)

Answer 15

• Die Bandkomplexität S_i(n) einer Turing-Maschine T_i 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 S_i(n)

Question 16

Kolmogorow-Komplexität

Answer 16

• 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).

Question 17

Komplexitätsklasse P

Answer 17

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.

Question 18

Komplexitätsklasse NP

Answer 18

• 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!