Algebraische Entscheidungsbäume

Algebraische Entscheidungsbäume

Vortrag zum Seminar über Algorithmen

20.04.23 1Behsaad Ramez

•Behsaad Ramez•6.Sem. Informatik(Diplom)

20.04.23 Behsaad Ramez 2

Übersicht

•Vergleichsbäume•Algebraische Berechnungsbäume•Lineare Entscheidungsbäume•Algebraische Entscheidungsbäume•Beispiele


Vergleichsbäume

•Allgemeine Sortieralgorithmen•Darstellung durch Vergleichsbaum


Untere Schranke

• n! Blatter => Höhe

•Beispiel Tennisturnier


Algebraischer Berechnungsbaum

•Algorithmus:


Beispiel


Definitionen

•Problem P ist im Berechnungsbaummodell lösbar, wenn

•Zeitkomplexität von ist die Höhe von T

•Zeitkomplexität von P ist die minimale Höhe von allen Bäumen die P lösen.


Algebraische Entscheidungsbäume

• ist Entscheidungsproblem, wenn S={YES,NO}

Ein algebraischer Berechnungsbaum , der ein Entscheidungsproblem löst , wird algebraischer Entscheidungsbaum genannt.

•Beispiel element uniqueness:


• sei ein Entscheidungsproblem

• Ein Punkt wird YES-Instanz genannt , falls

• sei die Menge aller YES-Instanzen.

•Beispiel element uniqueness:


Untere Schranke

•Untere Schranke kann über Topologie von gefunden werden

• ist die Anzahl der Zusammenhangskomponenten von

•Untere Schranke im linearen Entscheidungsbaummodell:

•Untere Schranke im algebraischen Entscheidungsbaummodell:


Lineare Entscheidungsbäume

•Jeder Berechnungsknoten u ist mit beschriftet:

•Z(u) ist lineare Funktion auf den Eingabevariablen

•R(w) ist dann die Menge aller Punkte für die gilt:


R(w)

•R(w) sei die Menge aller Eingaben ,für die im Blatt w terminiert

• seien die Knoten ,auf dem Weg zu w ,die zwei Kinder haben.

1. falls man bei nach links geht2. falls man bei nach rechts geht

Ist lineare Funktion auf der Eingabe


Konvexität von R(w)

•R(w) ist konvex


Untere Schranke für Höhe h

•A,B seien zwei verschiedene Zusammenhangskomponenten eines Problems P

• ,Blätter in denen terminiert sind verschieden

Anzahl Blätter von T


Element Uniqueness

• seien verschiedene Permutationen von 1..n

•Punkte sind in verschiedenen Zusammenhangskomponenten von


Allgemeine Untere Schranke

Im algebraischen Entscheidungsbaummodell ist R(w) nicht immer konvex


Satz

• Seien , Polynome auf n Variablen

•Der Grad von sei kleiner oder gleich g

Die Menge W hat höchstens Zusammenhangskomponenten


Umformung von Ungleichungen

• sind Polynome, Grad 2

•W ist die Menge der Punkte für die gilt:

• ist dann:



• sei ein beliebiger Punkt aus der j-ten Zusammenhangskomponente von W.



• mit b+c neuen Variablen formen wir E,N,P in polynomielle Gleichungen um.•W‘ sei die Menge aller Punkte :

Die Projektion von W‘ auf die ersten n Koordinaten ergibt

•Man kann R(w) mit k+s polynomiellen Ungleichungen auf n+k Variablen darstellen

• seien die Eingabewerte , repräsentieren


Entscheidungsbäume reduzieren

• sei ein Pfad p in T von der Wurzel zum Blatt .

• s sei die Anzahl der Anweisungen auf p.


Ersetzungsregeln

Gehe auf p entlang und füge für Gleichungen und Ungleichungen hinzu

Wird zu


•Sei r die Anzahl der Berechnungsknoten ,s die Anzahl der Funktionen und t die Anzahl der Entscheidungen für den linken Weg

•Es gibt s+t polynomielle Ungleichungen

•Es gibt k-r-t polynomielle > Ungleichungen

•Da wir n+k Variablen haben folgt aus



Beispiele

•Element Uniqueness:

•Sorting•Closest Pair•Diskriminante

•Set Disjointness

•Resultante


Danke

Danke!

Documents

Algebraische Entscheidungsbäume