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

20.04.23 Behsaad Ramez 3

Vergleichsbäume

•Allgemeine Sortieralgorithmen•Darstellung durch Vergleichsbaum

20.04.23 Behsaad Ramez 4

Untere Schranke

• n! Blatter => Höhe

•Beispiel Tennisturnier

20.04.23 Behsaad Ramez 5

Algebraischer Berechnungsbaum

•Algorithmus:

20.04.23 Behsaad Ramez 6

Beispiel

20.04.23 Behsaad Ramez 7

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.

20.04.23 Behsaad Ramez 8

Algebraische Entscheidungsbäume

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

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

•Beispiel element uniqueness:

20.04.23 Behsaad Ramez 9

• sei ein Entscheidungsproblem

• Ein Punkt wird YES-Instanz genannt , falls

• sei die Menge aller YES-Instanzen.

•Beispiel element uniqueness:

20.04.23 Behsaad Ramez 10

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:

20.04.23 Behsaad Ramez 11

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:

20.04.23 Behsaad Ramez 12

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

20.04.23 Behsaad Ramez 13

Konvexität von R(w)

•R(w) ist konvex

20.04.23 Behsaad Ramez 14

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

20.04.23 Behsaad Ramez 15

Element Uniqueness

• seien verschiedene Permutationen von 1..n

•Punkte sind in verschiedenen Zusammenhangskomponenten von

20.04.23 Behsaad Ramez 16

Allgemeine Untere Schranke

Im algebraischen Entscheidungsbaummodell ist R(w) nicht immer konvex

20.04.23 Behsaad Ramez 17

Satz

• Seien , Polynome auf n Variablen

•Der Grad von sei kleiner oder gleich g

Die Menge W hat höchstens Zusammenhangskomponenten

20.04.23 Behsaad Ramez 18

Umformung von Ungleichungen

• sind Polynome, Grad 2

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

• ist dann:

20.04.23 Behsaad Ramez 19

Umformung von Ungleichungen

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

20.04.23 Behsaad Ramez 20

Umformung von Ungleichungen

• 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

20.04.23 Behsaad Ramez 21

Entscheidungsbäume reduzieren

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

• s sei die Anzahl der Anweisungen auf p.

20.04.23 Behsaad Ramez 22

Ersetzungsregeln

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

Wird zu

20.04.23 Behsaad Ramez 23

•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

20.04.23 Behsaad Ramez 24

20.04.23 Behsaad Ramez 25

Beispiele

•Element Uniqueness:

•Sorting•Closest Pair•Diskriminante

•Set Disjointness

•Resultante

20.04.23 Behsaad Ramez 26

Danke

Danke!