/ itsummaries

[GER] Komplexitätstheorie

Die Turingmaschine

Eigenschaften

Ein theoretisches Rechnermodell mit ...

  • Einem unendlichen langen Speicheirband
  • Einem Bandalphabet
  • Einem Leerzeichen
  • Einem Lese-/Schreibkopf
  • Einem Zustandsraum

Das Programm

  • Ein Anfangszustand
  • Ein Stoppzustand
  • Eine Eingabe auf dem Speicherband
  • Eine Zustandsübergangsfunktion

Zu Beginn des Programms steht der Lese-/Schreibkopf auf dem ersten Zeichen der Eingabe. Danach wird die Zustandsübergabefunktion so lange aufgerufen, bis der Endzustand erreicht wird.

Die Registermaschine

Ein theoretisches Rechnermodell mit ...

  • Eine bestimmte Anzahl an Registern, welche natürliche Zahlen speichern kann
  • Drei Operationen, welche auf dem Register ausgeführt werden können
    • Inkrementierung eines Registers
    • Dekrementierung falls das Register noch nicht 0 erhält
    • Test ob ein Register eine 0 enthält
  • Ein Programm ist eine Aneinanderreihung von Operationen und Registern.
  • Die Registermaschine ist sehr ähnlich zu einem modernen Computer.
    Register- und Turingmaschinen sind äquivalente Modelle, da sie sich gegenseitig in polynomieller Laufzeit simulieren können.

Komplexitätsklassen

P: Alle Probleme, die in polynomieller Laufzeit zu berechnen sind : $O(n^c)$

EXP: Alle Probleme, die in exponentieller Laufzeit zu berechnen sind : $O(2^{n^{c}})$

R: Alle Probleme, die in endlicher Laufzeit zu berechnen sind: "rekursive" Probleme = berechenbare Probleme

$P \subset EXP \subset R$

Beispiele

  1. Sortieralgorithmen sind in P
  2. Schach ist in EXP, aber nicht in P (Spielbaum ca. $10^{123}$ Knoten$)
  3. Halteproblem, es gibt keinen Algorithmus, welcher entscheidet, ob ein beliebiger anderer Algorithmus terminiert

Durchführbarkeit

Selbst wenn ein Problem berechenbar ist, bedeutet das nicht, dass es "praktisch" berechenbar ist.
Viele Probleme benötigen für die Lösung zu viel Zeit oder Speicherplatz.
Beispiel: Das Problem des Handlungsreisenden ist für realistische Problemgrößen nicht "durchführbar".

Entscheidungsprobleme

Ein Entscheidungsproblem ist eine Frage, zu der eine "Ja" und eine "Nein" Antwort bestehen.
Das Ergebnis hält von den Parametern des Funktionsaufrufes ab. Parameter sind als Binärstring bzw. natürliche Zahlen darstellbar.
Beispiel: Teilt ein X ein Y ohne Rest.

Nicht-deterministische Turingmaschine

Eine nicht-deterministische Turingmaschine kann beim Lösen eines Problemes "raten" und rät immer die korrekte alternative.

NP - Komplexitätsklasse: Die Komplexitätsklasse, welche Probleme enthälte, die von einer nicht-deterministischen Turingmaschine in polynomieller Zeit gelöst werden können.

Beispiel: Baumsuche - Existiert ein Blatt mit Wert X

$P \subset NP \subset EXP \subset R$

NP-schwer: kann auch in $EXP$ oder $R$ liegen

NP-vollständig: liegt selbst auch in $NP$

Beispiel: Problem des Handlungsreisenden, Rucksack-Problem, Graph-Coloring ...

Reduktion

Führt ein ungelöstes Problem $A$ auf ein anderes Problem $B$ zurück
Beispiel: Quadrieren von Zahlen auf Multiplikation zurück führen

Randomisierte Algorithmen

Es gibt Algorithmen, deren Ablauf in bestimmtem Maße zufällig gestreuert wird.
In den meisten Fällen ist die Struktur eines randomisierten Algorithmus bedeutend einfacher, als die Struktur eines "schlaueren" deterministischen Algorithmus.

Spezielle Optimierungsprobleme sind teilweise derart rechenintensiv, dass ein Ergebnis für realistische Szenarien mit deterministischen Algorithmen nicht in annehmbarer Zeit zu berechnen ist.

Monte-Carlo-Algorithmus

Ein Mote-Carlo-Algorithmus ist ein randomisierter Algorithmus, welcher mit einer beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern darf.

  • Durch Wiederholung des Algorithmus mit neuer Zufallsbits kann die Fehlerwahrscheinlichkeit beliebig gesenkt werden
  • Es gibt Monte-Carlo-Algorithmen für Suchprobleme und Entscheidungsprobleme
  • Komplexitätsklassen bei Entscheidungsproblemen
  • BPP (bounded error probabilistic polynomial time): Das korrekte Ergebnis wird mit mindestens Wahrscheinlichkeit $p$ ausgegeben.
  • RP (randomized polynomial time): JA wird mit $p$ ausgegeben, NEIN mit P = 1

Beispiele:

  1. Miller-Rabin-Primzahltest: Zusammengesetzte Zahlen immer mit 100%, Primzahlen mit 75%

  2. Probablistische Bestimmung von $\pi$

  3. Monte-Carlo-Tree-Search: Ein Suchverfahren aus der künstlichen Intelligenz

Las-Vegas-Algorithmus

Ein randomisierter Algorithmus, welcher nie ein falsches Ergebnis liefern darf.

  • Die Rechenzeit kann sehr groß werden
  • Es gibt Varianten in denen der Algorithmus aufgeben darf

Beispiel: Random Quicksort: Das Pivotelement wird zufällig gewählt

Heuristik

Funktionsweise zu Monte-Carlo ist ähnlich, allerdings wird der Zufall durch "Faustregeln" bzw. "intelligentes Raten" beeinflusst.

Beispiel: Spiele-KI: Gegner schadet sich sehr unwahrscheinlich mit Zug selbst