Bitte nutzt die Fragen und Antworten für eure Fragen.

Diese Seite kann ohne Wiki-Account bearbeitet werden. Teilt eure Lösungen untereinander und korrigiert Fehler, wenn ihr sie findet.

1. Berechne die Tiefe eines Baums B, der in Kind-Geschwister-Darstellung gegeben ist.

Die Tiefe eines Baumes B (und nicht die Tiefe eines Knotens) meint die maximale Tiefe des Baumes B und die ist gleich der Höhe des Baumes. Das ist irritierend, aber man muß sich klarmachen, daß sich nur die Richtung des Weges untescheidet: Der längste Weg von der Wurzel zu einem Blatt bestimmt die Höhe eines Baumes, der umgekehrte Weg die Tiefe.

Ein rekursiver Algorithmus zur Ermittlung der Tiefe:

global im Baum: maximum = 0

int getTiefe(p)
	if (p == NULL)
		return 0
	if (p→LKind == NULL) 	// p ist Blatt 
		return 0
	else
	   return 1 + max( getTiefe(p->LKind), getTiefe(p->RG1), ... getTiefe(p->RGn))

Die letzte Anweisung läßt sich noch genauer notieren:

        max = 0
	for (q=p→LKind; q != null; q=q→RGeschwister)
		if (q->tiefe > max)
			max = q->tiefe
		return 1 + max 

Alternativ kann man den Algorithmus aus der Vorlesung (Folie 27 von 103 im 2. Foliensatz) voraussetzen und alle Knoten mit ihrer Tiefe markieren:

tiefe(wurzel,-1);
void tiefe (Knoten *p, int t)
    { Knoten *q; t = t+1;
    if (p != null)
         { p→tiefe = t;
         for (q=p→LKind; q != null; q=q→RGeschwister)
             tiefe(q,t); }}

Die Tiefe wird in einem Attribut des Knotens (hier Zugriff über p→ tiefe) gespeichert. Der Baum habe ein globales Attribut maximum, das mit 0 initialiert ist und die maximale Tiefe speichern soll. Nun genügt eine Traversierung durch den Baum, um das Maximum der Tiefe zu ermitteln.

void getTiefe (Knoten* p)
{
   Knoten p = Kopf;     // Wurzel
   if (p == NULL)
	   return 0;
   for (q=p→LKind; q != null; q=q→RGeschwister)
   {
	getTiefe(q)
	if (q→tiefe > maximum)
		maximum = q→tiefe
   }}

Was spricht für den einen, was für den anderen Weg?

1. Gib eine rekursive Implementierung von lookup in einem Heap H an. Tipp: lookup(wo, x), wobei wo die Position im Heap-Array ist.

lookupRek(int priority, int wo)
{
	if(wo <= n)
	{
			if (H[wo] == priority )
				print priority
			else if (H[wo] >  priority )
				lookupRek( priority, 2*wo);
			if (H[wo+1] == priority )
				print priority
			else if (H[wo+1] > priority )
				lookupRek( priority, 2*wo+1);
	}
}

1. Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): Statt einem Feld Gewinner g speichert ein Knoten nun eine Zahl int gewinn. Es gilt: gewinn > 0, wenn Alice gewinnt und gewinn < 0, wenn Bob gewinnt. Anfänglich sind nur die Blätter mit den gewinn-Werten markiert. Für alle inneren Knoten ist gewinn = 0. Wer gewinnt das Spiel und wie hoch ist der Gewinn, wenn jeder Spieler nach einem betragsmäßig großen Gewinn strebt?

Der MinMax-Algorithmus bleibt erhalten. Nur Details der Implementierung (Datentyp für gewinn) ändern sich. Was ist daran interessant? Antwort: Der Name “MinMax-Algorithmus” stammt eigentlich aus diesem Modell. Die Frage, ob eine Gewinnstrategie existiert, ist nur ein Spezialfall. Interessant ist, dass man über die Gewinnfunktion für jeden Spieler den lokal optimalen Zug bestimmen kann und letztlich für denjenigen mit der Gewinnstrategie auch exakt angeben kann, welchen Zug er spielen soll, um möglichst hoch zu gewinnen.

1. Erweitere die lookup(x)-Funktion eines binären Suchbaums, sodass sie den Pfad von der Wurzel zum Schlüssel zurück gibt, sofern er existiert.

1. Eine Schwarz-Weiß-Pixelgrafik mit Länge n und Breite n soll abgespeichert werden. Jedes einzelne Pixel soll in konstanter Laufzeit O(1) auf schwarz bzw. weiß gesetzt werden. Wie viel Speicherplatz benötigen wir in Abhängigkeit von n? Du kannst davon ausgehen, dass die Datenstruktur bereits initialisiert vorliegt.
2. Wir überlegen uns eine einfache Komprimierungsmöglichkeit: Wenn viele nebeneinander liegende Pixel die gleiche Farbe haben, dann genügt es, wenn nur einmal die Farbe und die Anzahl der betroffenen Pixel abgespeichert wird. So können wir Speicherplatz sparen. Der Zugriff auf ein Pixel p darf nun länger dauern, nämlich O(k), wobei k die Anzahl der Pixel links von p ist. Im besten Fall kann die Laufzeit auch geringer sein. Tipp: Was haben diese Aufgabe und ihr Vorgänger mit den Graph-Datenstrukturen aus der Vorlesung gemeinsam?

1) Bedarf an Speicherplatz: $O(n^2)$

2) Lauflängencodierung: Alle Zeilen werden separat codiert. Die Zeilen werden in einem Array verwaltet. Das Array enthält einen Zeiger auf einen Knoten mit dem Beginn der Zeile. Die Anzahl gleichfarbeiger Zellen wird in einem Knoten gespeichert. Weiße und schwarze Zellen wechseln einander ab. Die erste Codierung entspricht der Adjazenzmatix, die zweite der Adjazenzliste.

1. Welche Rechenregeln für Logarithmen gibt es?
2. Vereinfache die folgenden Terme:
   • $\log_2(8) = \log_2(2^3) = 3 \cdot \log(2) = 3 \cdot 1 = 3 \rightarrow \Theta(3) = \Theta(1)$
   • $\log_3(1) = 0$, da $x^0$ mit $x \in \mathbb{N}$ immer 1 ist $\rightarrow \Theta(1)$
   • $\log_2(n^4) = 4 \cdot log_2(n) \rightarrow \Theta(log \ n)$
   • $\log_{10}\left(\frac{1}{n^2}\right) = log_{10}(1) - log_{10}(n^2) = 0 - 2 \cdot log_{10}(n)$, Anmerkung: $\Theta$-Schreibweise entfernt; O-Notation haben wir nur für Funktionen $f:\mathbb{N} \to \mathbb{R}_{\geq 0}$ definiert.
   • $2^{\log_4(n)} = 2^{(log_4 2) \cdot (log_2 n)} = 2^{(log_2 n) \cdot (log_4 2)} = n^{log_4 2} = n^{1/2} = \sqrt n \rightarrow \Theta(\sqrt n)$
   • $\log_n(n) = 1 \rightarrow \Theta(1)$, da $\forall x \in \mathbb{N}: x^1=x$
   • $\log_a(b) \cdot \log_b(n)$ ist der Basiswechsel (siehe Formel) rückwärts, s.d.: $\log_a(b) \cdot \log_b(n) = log_a n \rightarrow \Theta(log \ n)$
   • $\log_2(4n^3)=log_2(4)+log_2(n^3)=2+3\cdot log_2(n) \rightarrow \Theta (log \ n)$
   • $\log_2(\sqrt{n})=1/2 \cdot log(n^{1/2}) = 1/2 \cdot log_2(n) \rightarrow \Theta(log \ n)$
   • $\log_2\left( \sum_{i=0}^n i \right) =\log_2\left( \frac{n\cdot(n+1)}{2} \right) = \log_2(n) + \log_2(n+1) - \log_2(2) = \Theta(\log(n)) $
   • $\log_3\left(\prod_{i=1}^n 3^i \right) = \sum_{i=1}^n \log_3\left(3^i \right) = \sum_{i=1}^n i \log_3(3) = \sum_{i=1}^n i = \frac{n\cdot(n+1)}{2}$
   • $\sum_{i=1}^n n \cdot i = n \cdot \sum_{i=1}^n i = n \cdot \frac{n \cdot(n+1)}{2} \rightarrow \Theta(n^3)$
   • $\sum_{k=0}^n 2^{-k} = 2- \frac{1}{2^n} \leq 2 = \Theta(1)$
   • $\sum_{k=1}^{\frac{n}{2}} 4^{-k} = (\sum_{k=0}^{\frac{n}{2}} 4^{-k}) - 1 = (\frac{1-(\frac{1}{4})^{(1+n/2)}} {1-\frac{1}{4}})-1 < \frac{1}{\frac{3}{4}}-1 = \frac{1}{3} = \Theta(1)$
   • $\sum_{i=1}^n \frac{2}{i} = O(log(n))$, da $\int \frac{1}{x} dx = \ln(x) + C$
3. Wahr oder falsch? Begründe deine Antwort.
   • $1 = \Theta(3)$, wahr
   • $2 = \Omega(1)$, wahr
   • $3 = \omega(2)$, falsch
   • $n = \omega(1)$, wahr, denn $\lim_{n\to \infty} \frac{n}{1} = \infty$.
   • $f = \mathcal{O}(g)$ und $g = \mathcal{O}(f) \iff f = \Theta(g)$, wahr, siehe Definition
   • $\sum_{k=0}^n 2^{-k} = \mathcal{O}(1)$, wahr, geometrische Summe
   • $\log_2(n) = \Theta(\log_8(n))$, wahr, denn $\log_2(n) = \log_2(8) \cdot \log_8(n)$.
   • $2^{\log_2(2n)} = \mathcal{O}(n^2)$, wahr, denn $2^{\log_2(2n)} = 2^{1 + \log_2(n)} = 2 \cdot 2^{\log_2(n)} = 2n$
   • $f_1 = \Omega(g_1)$ und $f_2 = \Omega(g_2) \implies f_1 + f_2 = \Omega(g_1 + g_2)$, wahr, einfach in die Definition der Omega-Notation einsetzen.
   • $f = o(g) \iff f = \mathcal{O}(g)$, “$\implies$” ist wahr, “$\impliedby$” ist falsch.
   • $f(n) = g(\frac{n}{2}) \implies f = \Omega(g)$, falsch, Gegenbeispiel: $g(n) = 2^n$.

Welchen Wert hat k in Abhängigkeit von n nach der Ausführung des Programms?

1. k = 1
   for i=1,2,...,n
       k = k + 1

   $k = \Theta(n)$

2. k = 1
   for i=1,2,...,n
       k = k + 1
   for j=1,2,...,100
       k = k + 2

   $k = \Theta(n)$

3. k = 1
   for i=1,2,...,n*n
       k = k + 2

   $k = \Theta(n^2)$

4. k = 1
   for i=n,n/2,n/4...,1
       k = k + 1

   $k = \log_2(n)$

5. k = 1
   for i=1,2,...,n
       k = k + i

   $k = 1 + \sum_{i=1}^n i = \Theta(n^2)$

6. k = 1
   while i < n
       i = i + i
       k = k + 1

   Tipp: i verdoppelt sich in jedem Schritt. Wie oft kann es sich verdoppeln bis $i \geq n$ gilt?

7. i = 0
   k = 0
   while i < n
       i = i + k
       k = k + 1

8. k = 1
   for i=sqrt(n), 2sqrt(n),...,n
      k = k + 1

   $k = \Theta(\sqrt{n})$, denn $i$ erhöht sich mit Schrittweite $\sqrt{n}$. Nach $\sqrt{n}$ Schritten erreichen wir die obere Schranke $n$ und brechen die for-Schleife ab.

Umgekehrt: Schreibe Pseudocode mit den folgenden Laufzeiten:

1. $\Theta(1)$
2. $\Theta(n)$
3. $\Theta(n^3)$
4. $\Theta(2^n)$, erzeuge einen vollständigen Binärbaum der Tiefe n-1, denn dieser Baum hat $\Theta(2^n)$ Knoten. Tipp: Schreibe ein rekursives Programm, dass als Parameter die Tiefe des Baumes erhält.
5. $\Theta(\sqrt{n})$

    i = 1
    k = 1
    while i <= n
        i = i + k
        k = k + 1
    

$i = \Theta(k^2)$ (Gauß-Summe), d.h. die Zählvariable i wächst mit quadratischer Geschwindigkeit und erreicht nach $\Theta(\sqrt(n))$ Schritten die Schranke n.

1. $\Theta(\log{n})$
2. $\Theta(\log{n^3})$
3. $\Theta(n!)$, gib alle möglichen Permutationen der Zahlen 1,2,…,n aus.

Billiglösung, die immer funktioniert: Pseudocode mit der Laufzeit $\Theta(f(n))$:

for i = 1, 2, ..., f(n)
    print "hallo"

Was tut der folgende Pseudocode? Angenommen $n = 2^k$ für ein beliebiges $k \in \mathbb{N}$.

function raetsel(Array A[0,..,n-1], int l, int r)
{
    if l == r 
    {
        return A[l]
    }
    else
    {
        grenze = floor( (l+r)/2 )        // untere Gaußklammer
        m_l = raetsel(A, l, grenze)
        m_r = raetsel(A, grenze + 1, r)
        if m_l > m_r
        {
            return m_l
        }
        else
        {
            return m_r
        }
    }
}

Welche Ausgabe liefert raetsel(A, 0, 7) für A = [1,5,3,10,2,11,9,4]?

Lösung: raetsel(A, l, r) geht so ähnlich vor wie die binäre Suche, aber die Funktion liefert den größten Wert aus den Zahlen A[l], A[l+1], …, A[r]. Das kann man sich folgendermaßen verdeutlichen: Im Basisfall enthält das zu prüfende Intervall nur eine einzige Zahl, die wir zurückgeben. Klar: Das muss das Maximum sein. Im Rekursionsfall teilen wir das Intervall in zwei Hälften und erhalten aus der linken Hälfte (laut Induktionsannahme) das “linke” Maximum m_l und aus der rechten Hälfte das “rechte” Maximum m_r. Die darauf folgende if-Abfrage bewirkt, dass das Maximum des gesamten Intervalls max{m_l, m_r} zurückgegeben wird.

Aufstellen:

1. def f(n):
       if n == 1
           return 1
       else
           return n + f(n-1)

2. def g(n):
       if n > 1:
           return g(n/2)
       else
           return 0

Lösen:

1. $T(1) = 0$ und $T(n) = 2 T(\frac{n}{2}) + \frac{n}{2}$ für $n > 1$
2. $T(2) = 1$ und $T(n) = T(\frac{n}{2}) + n - 1$ für $n > 2$

• Was ist ein Array?
• Wie sieht ein Array im Arbeitsspeicher aus?
• Wie lang dauert ein Zugriff (lesen oder schreiben) auf das n. Element A[n]? Wieso?
• Schreibe ein Programm in Pseudocode, das ein gegebenes Array A[1,…,n] mit den Werten 2, 4,…, 2n befüllt.

for i = 1, 2, ..., n
    A[i] = 2*i

• Schreibe ein Programm in Pseudocode, das die Summe der Einträge dieses Arrays ausgibt.

sum = 0
for(i = 1; i <= n; i++)
    sum = sum + A[i]
return sum

• Entwerfe eine Datenstruktur, die Zahlen aus dem Intervall {0,1,…,n-1} speichert und die Operationen lookup(x), insert(x) und remove(x) in der Laufzeit O(1) unterstützt.

Idee: Das Intervall ist schon gegeben, d.h. es müssen keine “unerwarteten” Zahlen in der Datenstruktur verwaltet werden. Wir wählen ein Array A[0,…,n-1], da Lese- und Schreibzugriffe in konstanter Zeit O(1) möglich sind. A ist ein Bitvektor, also A[x] = 1, wenn x in unserer Datenstruktur vorhanden ist und A[x] = 0, sonst.

def lookup(x):
    return A[x]
    
def insert(x):
    A[x] = 1
    
def remove(x):
    A[x] = 0

• Was ist eine Liste?
• Wie sieht eine Liste im Arbeitsspeicher aus?
• Wie unterscheiden sich Arrays und Listen?
• Welche Zeiger und Funktionen hat die Listen-Implementierung aus der Vorlesung zur Verfügung?
• Wie lange dauert es, das größte Element einer aufsteigend (absteigend) sortierten Liste zu finden?

aufsteigend: O(n), wobei n die Länge der Liste ist, da wir uns vom head-Element bis zum letzten Element durchhangeln müssen. absteigend: O(1) mit folgendem Code:

L.movetofront()    // current-Zeiger auf das head-Element zurücksetzen
return L.read()

• Wie lange dauert das Einfügen der Zahl 7 in eine (un)sortierte Liste?

unsortiert: O(1), mit L.insert(7) wird die 7 nach dem current-Element eingefügt.

• Wieso ist binäre Suche auf Listen keine gute Idee?

Wir können dort nicht “navigieren”, da wir keine Indizes haben. Es ist “schwierig”, die Mitte zwischen zwei Elementen zu finden bzw. noch nicht einmal ohne Weiteres möglich, zu entscheiden, welches der beiden Elemente links bzw. rechts liegt.

• Schreibe ein Programm in Pseudocode, das beide Aufgaben (sortiert und unsortiert) erledigt.

unsortiert:

def insert_unsortiert(x):
    L.insert(x)

sortiert (aufsteigend):

def insert_sortiert(x):
    L.movetofront()         // verschiebe den current-Zeiger auf das head-Element
    while not L.end():      // alternativ: for(Element curr = L.head; curr = curr.next; curr != null) {...}
        nachfolge_wert = L.read()
        if nachfolge_wert >= x:
            L.insert(x)     // füge x nach dem current-Element ein
            return;         // Ende der Funktion
        else
            L.next()        // verschiebe den current-Zeiger auf das nächste Element
    L.insert(x)             // Füge x als letztes Element ein (hinten anhängen)

• Die Datenstruktur Liste aus der Vorlesung ist eine einfach verkettete Liste, d.h. jedes Element hat nur einen Zeiger next auf seinen Nachfolger in der Liste. Erweitere die Datenstruktur, sodass auch jeder Vorgänger über einen Zeiger erreicht werden kann. Welche Veränderungen ergeben sich für die Funktionen insert und remove?

• Was ist ein Stack?
• Wie lange dauert ein Zugriff auf das oberste/unterste Element?
• Beschreibe, wie mit einer Liste ein Stack implementiert werden kann.

def push(x):
    L.movetofront()    // nicht unbedingt nötig (current-Zeiger auf das Head-Element verschieben)
    L.insert(x)        // x ist nun das erste (= oberste) Element
    
def pop():
    L.movetofront()    // nicht unbedingt nötig
    L.remove()         // entferne das oberste Element

• Schreibe ein Programm, das einen Stack A als Eingabe erhält und den Stack B ausgibt, wobei B die Elemente aus A in umgekehrter Reihenfolge enthält.
• Erweitere die Datenstruktur Stack um die Funktion bottom(), die das unterste Element des Stacks in Laufzeit O(1) ausgibt.

Benutze eine private Hilfsvariable bot und ergänze die Funktion push(x) folgendermaßen:

def push(x):
    if S.empty():
        bot = x
        push_alt(x)    // benutze nun die konventionelle push-Funktion
        
def bottom():
    if not S.empty():
        return bot
    else
        "FEHLER"

• Bonusfrage: Wie werden Stacks in Programmiersprachen beim Aufruf von Funktionen verwendet? Smashing The Stack For Fun And Profit

• Was ist eine Queue?
• Befolgen Queues das Prinzip LIFO oder FIFO?

FIFO (First in, first out).

• Beschreibe die Situation im Supermarkt an der Kasse mithilfe einer Queue.
• Wie würde sich das Einkaufen verändern, wenn Supermarkt-Kassen wie Stacks funktionieren würden?

Wenn eine neue Kasse geöffnet wird, dann sollte man sich möglichst ans Ende der Warteschlange anstellen, damit man als erste Person abkassiert wird.

• Welche Algorithmen aus der Vorlesung verwenden Queues? Wieso?
• Schreibe ein Programm in Pseudocode, das eine Liste L erhält und den Wert jedes Listenelements in eine Queue einfügt.

def list_to_queue(Liste L):
    Q = new Queue()
    L.movetofront()
    while not L.empty():
        data = L.read()
        Q.enqueue(data)
        L.remove()

• Lösche das jüngste Element aus einer Queue Q, ähnlich wie pop() bei Stacks.

H = new Queue()  // Hilfsqueue erzeugen
while not Q.empty():
    data = Q.dequeue()
    if not Q.empty():     // data ist nicht das jüngste Element
        H.enqueue(data)
Q = H                     // statt alles wieder nach Q zu schaufeln, können wir auch einfach Q durch H ersetzen

• Was ist ein Baum?

ein zusammenhängender Graph ohne einfache Kreise

• Was ist ein (vollständig) binärer, ternärer, k-ärer Baum?

Ein vollständiger binärer Baum der Tiefe t ist ein binärer Baum, in dem alle Blätter die Tiefe t besitzen und alle inneren Knoten wie auch die Wurzel den Aus-Grad genau 2 besitzen.

• Kann die Datenstruktur Liste auch als Baum aufgefasst werden? Ist ein Baum nur eine verzweigte Liste?

ja und ja, man kann beides so auffassen (je nach Implementierung)

• Welche Datenstrukturen für allgemeine Bäume kennen wir?

Eltern-Array, Binärbaum (bzw. k-är)-Baum mit Zeigern auf das linke und rechte bzw. auf Kind_1, Kind_2,…, Kind_k, Kind-Geschwister-Darstellung

• Entwerfe eine Datenstruktur für einen ternären Baum. Wieso sind Eltern-Arrays nicht geeignet?

struct Knoten
{    schluesseltyp	schluessel;	
     infotyp 		info;		//	Nutzdaten
     Knoten 		*links, *mitte, *rechts;
...  };

Eltern-Arrays: Es kommt auf die geforderten Operationen an. Was spricht dagegen, ein Verzeichnisbaum (directory) als Eltern-Array zu speichern? Die Laufzeit der meisten Operationen (z.B. dir) ist O(n), die Ermitllung des kompletten Pfades von der Wurzel aus O(1).

• Gib eine rekursive Definition für Bäume an: Wie sieht ein Baum im Basisfall (Rekursionsanfang) aus? Wie sieht der Rekursionsfall (Rekursionsschritt) aus?

Basisfall: Der Baum ist ein Blatt Rekursionsfall: Der Baum ist ein Knoten mit Kindern, die wiederum Bäume sind.

• Welche Datenstrukturen kennen wir für Graphen?

Adjazenzmatrix, Adjazenzliste (und noch die speziellen Datenstrukturen für Bäume)

• Nenne Vor- und Nachteile dieser Datenstrukturen.

Tipp: Überlegt euch, wie lange es jeweils dauert, verschiedene Aufgaben zu lösen wie etwa “alle Nachbarn eines Knotens ausgeben”, “neue Kante einfügen”, “neuen Knoten einfügen”, “Zugriff auf die Wurzel”, “Zugriff auf den Elternknoten” usw.

• Führe Tiefen- und Breitensuche an einem selbst gewählten Beispiel aus. Dabei soll jeder Knoten seine Nachbarn in aufsteigender Reihenfolge speichern.
• Wieso müssen wir uns bei der Tiefen- und Breitensuche in allgemeinen Graphen merken, welche Knoten wir schon besucht haben?
• Führe Prä-/In-/Postorder auf einem selbst gewählten Baum aus.

Wikipedia (en.) - Tree Traversal, Achtung: Bei Inorder auf Bäumen mit mehr als zwei Kindern

• Finde einen Baum, bei dem alle drei Traversierungen das gleiche Ergebnis liefern.

Der Baum ist ein Blatt.

• Gib eine rekursive Implementierung der Postorder-Traversierung an. Orientiere dich an Algorithmus 4.1 (S. 96 im Skript).
• Was hat die Tiefensuche auf Bäumen mit Prä-/In-/Postorder zu tun?
• Welche Laufzeit hätten die Tiefen- und die Breitensuche, wenn der Graph als Adjazenzmatrix statt als Adjazenzliste vorliegen würde?

Beim Besuch jedes Knotens müssen wir all seine Nachbarn überprüfen (wurden sie schon besucht?). Die Frage ist daher: Wie lange dauert es pro Knoten, all seine Nachbarn zu finden in der Adjazenzmatrix und in der Adjazenzliste? Adjazenzmatrix: $O(|V|)$, Adjazenzliste: $O(\deg(v))$. Wie lange dauert es dann insgesamt für alle Knoten? Tipp: Mit dem Handshake-Lemma (doppeltes Abzählen) folgt dann, dass die Summe aller Knotengrade das doppelte der Kantenzahl ist: $\sum_{v \in V} \deg(v) = 2 \cdot |E|$

• Benutzt die (nicht rekursive) Tiefensuche einen Stack oder eine Queue? Wie sieht es mit der Breitensuche aus?

Tiefensuche: Stack Breitensuche: Queue

• Unter welchen Voraussetzungen kann ein Graph topologisch sortiert werden?

Wenn er keine Kreise hat.

• Ist diese Sortierung immer eindeutig?

nein.

• Gib eine topologische Sortierung an einem selbst gewählten Beispiel an.

• Was ist ein Heap?
• Was ist der Unterschied zwischen Min- und Max-Heaps?

die Heap-Ordnung: Wurzel ist das kleinste bzw. größte Element.

• In welcher Laufzeit kann bei einem Min-Heap (Max-Heap) auf das kleinste Element zugriffen werden?

O(1) durch return H[1]

• Was ist die Heap-Ordnung?
• Richtig oder falsch: Ein Heap ist ein binärer Suchbaum?

Im Allgemeinen nein.

• Gib ein Beispiel für einen Heap an, der ein binärer Suchbaum ist.

Jeder Heap, der nur einen Knoten enthält ist ein binärer Suchbaum. Es gibt allerdings auch Min- und Max-Heaps mit zwei Knoten, die die Suchbaum-Eigenschaft erfüllen.

• Füge eine selbst gewählte Folge von acht Zahlen in einen Min-Heap ein.
• Entferne alle Zahlen mit delete_min() und gib die Reihenfolge an. Was fällt dir auf?

Heap-Animation

• Benutze diese Beobachtung für folgendes: Schreibe ein Programm in Pseudocode, das ein Array A[1,…,n] als Eingabe erhält und dessen Elemente in aufsteigender Reihenfolge ausgibt.

// Das ist Heap-Sort

H = new MinHeap()
for i=1,2,...,n
    H.insert(A[i])    // füge alle Elemente des Arrays in den Heap ein
for i=1,2,...,n
    min = H.delete_min()
    print min

Laufzeit-Analyse: Der Heap wächst mit jeder insert-Operation um ein Element. Die Laufzeiten steigen somit im schlimmsten Fall: $O(\log(1)), O(\log(2)),..., O(\log(n))$. Umgekehrt verhält es sich mit jedem delete_min. Wie muss ein solches Array aussehen, damit bei jedem insert ein repair_up bis zur Wurzel hinauf ausgeführt werden muss? Konstruiere ein solches Worst-Case-Beispiel. Heapsort hat also eine Laufzeit von $O(\sum_{i=1}^n \log(1))$. Eine “ungenauere” obere Abschätzung für die Laufzeit ist $\sum_{i}^n \log(n) = O(n\log(n))$. Ist das im Worst-Case zu ungenau? Nein, denn allein für jeden Wert A[n/2], A[n/2+1],…, A[n] benötigt insert die Laufzeit $\sum_{i=n/2}^n \log(n/2) = \Omega(n \log(n))$, (Achtung: Die Omega-Abschätzung gilt nur, wenn A eine Worst-Case-Eingabe ist. Im besten Fall kann es weniger sein, z.B. für die Eingabe 1,1,1,1,1,…).

• Wahr oder falsch: Wenn wir die Folge der einzufügenden Zahlen schon vorher kennen, kann das Einfügen aller Zahlen in den Heap in linearer Laufzeit realisiert werden.

wahr, mit der buildheap-Funktion

• Entwerfe einen Heap, der als ternärer Baum aufgefasst werden kann.

Speichere die Kinder von H[i] an den Positionen H[3i], H[3i+1], H[3i+2].

• Was ist ein binärer Suchbaum?
• Können auch Buchstaben in einem binären Suchbaum verwaltet werden?
• Welche Tiefe hat ein binärer Suchbaum mit n Schlüsseln im besten und im schlechtesten Fall?
• Was passiert bei remove(5), wenn der Baum den Schlüssel 5 gar nicht enthält?

Nichts oder Fehlermeldung

• Was passiert bei insert(5), wenn der Baum den Schlüssel 5 bereits enthält?

Nichts oder Fehlermeldung (Achtung: andere Implementierungen, z.B. die aus der Datenstrukturen-Visualisierungswebsite fügen auch doppelte Schlüssel ein).

• Gib einen binären Suchbaum mit zehn Knoten an.
• Entferne die Wurzel.
• Entferne einen weiteren inneren Knoten
  • mit einem Kind.
  • mit zwei Kindern.
• Entferne ein Blatt.
• In welcher Laufzeit kann die Folge 1,2,…,n/2 in einen binären Suchbaum eingefügt werden?

Bei dieser Folge landet insert(i) in Tiefe $\Theta(i)$. Damit ergibt sich die Laufzeit $\sum_{i=1}^{n/2} i = \frac{n/2 \cdot (n/2 + 1)}{2} = \Theta(n^2)$

• Gib eine Folge an, die in möglichst geringer Laufzeit eingefügt werden kann. Tipp: Breitensuche auf Bäumen.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …, 1: Jedes insert(1) geht in Laufzeit O(1). Der Baum besteht immer nur aus einem einzigen Knoten.

• Was ist ein AVL-Baum?
• Wahr oder falsch: Jeder AVL-Baum ist ein binärer Suchbaum.
• Wahr oder falsch: Jeder binäre Suchbaum ist ein AVL-Baum.
• Wozu dienen die Rotationen?
• Was ist die Tiefe eines AVL-Baums mit n Knoten im besten und im schlechtesten Fall?
• Welche Nachteile hat die Verwendung von AVL-Bäumen gegenüber üblichen binären Suchbäumen?
• Füge die Zahlen 1,2,…,15 in einen anfangs leeren AVL-Baum ein. Gib bei Balance-Grad-Verletzungen außerdem an, ob es sich um einen ZickZick, ZickZack, ZackZick oder ZackZack-Fall handelt.

• Was ist ein (a,b)-Baum?
• Was bedeutet das a?
• Was bedeutet das b?
• Wie viele Kinder hat ein innerer Knoten, der 3 Schlüssel speichert?
• Füge die folgenden Zahlen in einen anfangs leeren (2,3)-Baum ein: 1, 4, 6, 9, 5, 11, 2, 3, 12, 10, 7, 8. Lösche anschließend wieder alle Schlüssel in der gleichen Reihenfolge.

• Was ist Hashing?
• Was ist eine Kollision?
• Welche Laufzeit haben insert(x), remove(x) und lookup(x) im besten und im schlechtesten Fall?

Insert

Remove

Lookup

• Berechne $3x \mod 5$ für alle $x \in \{0, 1, 4, 5, 10, 12\}$.
• Fülle eine Wertetabelle für $f(x) := 3x \mod 11$
• Füge die Schlüssel 9, 20, 31, 42, 53 in eine Hash-Tabelle ein und gib jeweils die Reihenfolge der getesteten Zellen an:
  • Hashing mit Verkettung
  • Hashing mit linearem Austesten
  • doppeltes Hashing mit $h(x) := f(x) + i\cdot g(x) \mod 11$, wobei $g(x) := 5 - (x \mod 5)$.
  • Was ist der Auslastungfaktor $\lambda$ bei den beiden letzten Verfahren? Hängt er davon ob, ob linear ausgetestet oder doppelt gehasht wurde?

Löse die folgenden Aufgabenstellungen mit rekursiven Programmen. Was ist jeweils der Basisfall und was ist der Rekursionsfall?

1. Maximum einer Liste finden
   • Eingabe: Liste L
   • Ausgabe: Wert eines größten Listenelements

   • // Variante 1: 
     // Basisfall: Liste besteht nur aus einem einzigen Element
     // Rekursionsfall: Liste besteht aus einem Element, das auf eine weiter Liste zeigt
     
     def max1(Element e):
         if(e.next == NULL)       // Basisfall
             return e.wert
         else                     // Rekursion
             max_restliste = max1(e.next)
             if (e.wert > max_restliste)
                 return e.wert
             else
                 return max_restliste
     ------------------------------------------------
                 
     // Variante 2: 
     // Basisfall: leere Liste
     // Rekursionsfall: Liste besteht aus einem Element, das auf eine weiter Liste zeigt
     
     def max2(Element e):
         if(e == NULL)          // Basisfall
             return -∞ 
         else                   // Rekursion
             max_restliste = max1(e.next)
             if (e.wert > max_restliste)
                 return e.wert
             else
                 return max_restliste

2. Blätter eines Binärbaums zählen
   • Eingabe: Zeiger root auf den Wurzelknoten eines Binärbaums
   • Ausgabe: eine natürliche Zahl k > 0, wenn der Binärbaum k Blätter hat

   • def count(Knoten v):
         if (v == NULL)
             return 0
         else 
             if (v.links == NULL und v.rechts == NULL)    
                 // Basisfall: v ist ein Blatt
                 return 1               
             else        
                 // Rekursionsfall: v mindestens einen Binärbaum als Kind
                 return count(v.links) + count(v.rechts)              

3. größte vollständige Teilbäume finden
   • Eingabe: Zeiger root auf den Wurzelknoten eines Binärbaums
   • Ausgabe: Zeiger auf einen Knoten, der die Wurzel eines vollständigen Binärbaums mit möglichst vielen Blättern ist

Pseudocode

im Baum:	maximum = 0, maxNode = leer
im Knoten:	zaehler = 0

def maxFullBinTree()		// Rahmenprozedur
	markFullBinTree(Wurzel des Binärbaums)
	return maxnode = Zeiger auf den Knoten des größten vollständigen Teilbaums

def markFullBinTree(Knoten)
	wenn Knoten leer
		return
	wenn Knoten ein Blatt
		zaehler = 1
	wenn Knoten ein Halbblatt (nur ein Kind)
		return
	sonst hat der Knoten zwei Kinder
		markFullBinTree(Knoten.links)
		markFullBinTree(Knoten.rechts)
		wenn beide Teilbäume gleich groß 
			zaehler =  Knoten.links.zaehler + Knoten.rechts.zaehler + 1
		wenn 	zaehler > maximum
			maximum = zaehler
			maxNode = Knoten
return

laufffähiger Code in C++

struct Knoten
{    schluesseltyp	schluessel;
     infotyp 		info;		 //	Nutzdaten
     int    		count;		 //     Knotenzähler, wird mit 0 initialisiert
     Knoten 		*links, *rechts;
...  };

class bsbaum
{
private:
  Knoten* Kopf;			// Wurzel
  Knoten* maxNode;		// Größe des Teilbaums global speichern
  int maximum;			// Zeiger auf diesen  Teilbaums global speichern
...  };


Knoten* bsbaum::maxFullBinTree()   // Rahmenprozedur
{
	Knoten* Zeiger = Kopf;
	markFullBinTree(Zeiger);
	cout << endl << "Anzahl innere Knoten: " << maximum << endl; // zum testen
	return maxNode;
}

void bsbaum::markFullBinTree(Knoten* Zeiger)    // markiert Knoten mit Anzahl der Knoten im vollst. Teilbaum
{						// in Variable count und ermittelt größten Teilbaum
        if (Zeiger == NULL)			// leerer Zeiger
		return;
	else if ((Zeiger->links == NULL) && (Zeiger->rechts == NULL))
	{						// Blatt
		Zeiger->count = 1;			// wird gezählt
		return;
	}
	else if (!((Zeiger->links != NULL) && (Zeiger->rechts != NULL)))
		{					// HalbBlatt
		return;					// kein vollständiger Teilbaum
		}					// nichts zu tun
	else						// innerer Knoten mit 2 Kindern
    	{
		markFullBinTree(Zeiger->links);		// markiere linken Teilbaum
		markFullBinTree(Zeiger->rechts);	// markiere rechten Teilbaum
		int lb = Zeiger->links->count;  	// Knoten im linken, vollständigen TB
		int rb = Zeiger->rechts->count; 	// Knoten im rechten, vollständigen TB
		if  (lb == rb)				// wenn Teilbäume gleich groß
			Zeiger->count = lb + rb + 1;    // zähle ihre Knoten
		if	(Zeiger->count > maximum)	// wenn Teilbaum größer als der bisher ermittelte TB
		{
			maximum = Zeiger->count;	// Größe des Teilbaums global speichern
			maxNode = Zeiger;		// Zeiger auf diesen  Teilbaums global speichern
		}
		return;
	}
}

Der Code berücksichtigt nicht den Fall, daß es mehrere vollständige Teilbäume mit gleicher Knotenzahl geben kann. Hier wäre sinngemäß in der Rahmenprozedur zu ergänzen:

printMaxTree(Knoten)	
	if (Knoten == NULL) return
	if (Knoten->links == NULL ) || (Knoten->rechts == NULL)	return
	else
		if (zaehler = maximum)
			printTree(Knoten)
		else	
			printMaxTree(Knoten)

1. Entwirf eine Wörterbuch-Datenstruktur, die für die gegebene Menge M := {0, 1,…, n-1} folgende Laufzeiten ermöglicht:
   • lookup(x): O(1)
   • insert(x): O(1)
   • remove(x): O(1)
   1. Lösung: Siehe Arrays
2. Ein Projekt besteht aus einer geordneten Aufzählung von beliebig vielen Aufgaben. Jede Aufgabe hat eine Bearbeitungszeit. Die Bearbeitungszeit eines Projekts ist die Summe der Bearbeitungszeiten seiner Aufgaben. Entwirf eine Datenstruktur, die uns bei der Planung der Projekte unterstützt. Es soll jeweils das Projekt mit der geringsten Bearbeitungszeit mit der höchsten Priorität durchgeführt werden. Anschließend ist das Projekt abgeschlossen und muss nicht mehr von der Datenstruktur verwaltet werden. Außerdem sollen neue Projekte eingefügt werden können. Der Einfachheit halber setzen wir voraus, dass die Bearbeitungszeiten der Projekte eindeutig sind und dass zu jedem Projekt p die Bearbeitungszeit in der Variable p.zeit gespeichert werden kann. Zu Beginn ist p.zeit nicht initialisiert. Realisiere die folgenden Laufzeiten:
   • hinzufuegen(p): O(|p| + log(k)), wobei |p| die Anzahl der Aufgaben des Projekts p und k die Anzahl der momentan verwalteten Projekte ist. Die Funktion soll das neue Projekt p in die Datenstruktur einfügen.
   • naechstes(): O(log(k)). Die Funktion soll das Projekt ausgeben, das als nächstes bearbeitet werden soll.

konstante Laufzeit O(1), vorgegebene Menge (feste Größe), Indizes, sortiert, Bitvektor, Array hat eine feste/fixe Größe, Matrix

variable Länge, beliebig lang, sortiert, O(n) Laufzeit, veränderliche/dynamische Länge bzw. Größe, Nachfolger, Vorgänger, (Anwendungsbeispiel: dünnbesetzte Matrizen, Graphen mit wenigen Kanten), Kopf (head), current-Zeiger

push, pop, beides in O(1), LIFO (last in, first out), (Anwendungsbeispiel: Tiefensuche, Parsen von arithmetischen Klammerausdrücken), Stapel, “reverse”, Stacks statt Rekursion

enqueue, dequeue, beides in O(1), FIFO (first in, first out), Warteschlange, (Anwendungsbeispiel: Breitensuche, Level-Order-Traversierung)

Prioritätswarteschlange, (nicht unbedingt eindeutige) Prioritäten (Schlüssel), Min-Heap, Max-Heap, insert in O(log(n)), delete_min/max() in O(log(n)), repair_up/down in O(log(n)), Heap-Ordnung, Heap-Struktur, “(fast) vollständiger” Binärbaum, Implementierung als Array der Länge n, Kinder und Eltern können in O(1) ermittelt werden H[i] → H[2i], H[2i+1], build_heap() in O(n)

Adjazenz, Knoten, Kanten, Kreise, gerichtet, ungerichtet, Nachbarn,

Wörterbuch, eindeutige Schlüssel, linker Teilbaum speichert kleinere Schlüssel, rechter Teilbaum speichert größere Schlüssel, (Anwendungsbeispiel: Inorder-Traversierung liefert aufsteigende Reihenfolge der Schlüssel, ), Spezialfälle: AVL-Bäume, (a,b)-Bäume, Laufzeit im Worst Case O(n) (wegen Tiefe O(n))

Wörterbuch, Spezialfall von binären Suchbäumen mit geringer Tiefe O(log(n)), Balance-Grad, Rotation (links, rechts), Zick, Zack, lazy remove,

Erweiterung von binären Suchbäumen, a ⇐ Anzahl Kinder ⇐ b, Big Data, Externspeicher, mehrere Schlüssel pro Knoten, Schlüsselklau, geringe Tiefe $\Omega(\log_b(n)), O(\log_a(n))$, alle Blätter in der gleichen Tiefe

Wörterbuch, Verkettung, Hash-Funktionen, Auslastungsfaktor $\lambda$, modulo, Teilen/Dividieren mit Rest, lineares Austesten (nacheinander nach einem freien Speicherplatz suchen), Kollision, Speicherplatz schon besetzt, $1/(1-\lambda)$ erwartete Zugriffszeit bei zufälligen Eingaben