Lehrbuch Grundlegende Algorithmen: Supplement

Vorbemerkungen

Wir stellen hier Lösungshinweise zu ausgesuchten Übungsaufgaben des Buches zusammen. Dabei werden keine vollständigen Lösungen angegeben, sondern lediglich Hinweise zur Lösung oder explizite Lösungen zum Vergleich (je nachdem, was für die einzelne Aufgabe sinnvoller ist).

Im Folgenden bedeutet ---, dass (noch) kein Lösungshinweis zur Verfügung steht.

Lösungshinweise:

Kapitel 1

1.1

Beweis durch vollständige Induktion.

1.2

a) Wähle Algorithmus A.
b) Wähle Algorithmus B.

1.3

Beispiele:
Eingabegröße für T₁ bei 1M: etwa 5,184,000
Eingabegröße für T₂ bei 1d: etwa 103,708
Eingabegröße für T₃ bei 1h: etwa 1,897
Eingabegröße für T₄ bei 1m: etwa 271
Eingabegröße für T₅ bei 1s: etwa 15

1.4

Zu berechnen ist T_i(10n)/T_i(n)
Damit gilt für T₁: Faktor 10
Damit gilt für T₂: Faktor fast 10
Damit gilt für T₃: Faktor etwa 3.3 (Wurzel 10)
Damit gilt für T₄: Faktor etwa 2.15 (dritte Wurzel aus 10)
Damit gilt für T₅: wird um etwa 2.1 additiv gröser

1.5-1.9

Die RAM-Programme sind im Prinzip leicht, aber technisch aufwendig. Für 1.7 geben wir exemplarisch ein RAM-Programm an (es gibt auch andere).
Wir lösen die Endrekursion des iterierten Quadrierens auf. Da wir in der RAM die Bits nur in der Reihenfolge vom niederwertigsten (LSB) zum höchstwertigsten (MSB) erhalten, für das iterierte Quadrieren die Reihenfolgen aber vom MSB zum LSB benötigen, werden die Bits in den Registern 4 bis m zwischengespeichert und im Register 4 wird im Wesentlichen die Nummer des höchsten verwendeten Registers gespeichert.

      01: LOAD  #4
      02: STORE 3
      03: ODD   1        // momentanes LSB ermitteln
      04: STORE @3       // und ablegen
      05: LOAD  3        // c(3) erhöhen
      06: ADD   1
      07: STORE 3
      08: SHIFT 1        // x halbieren
      09: STORE 1
      10: IF =0 GOTO 12  // Ist c(1)==0, dann haben wir alle Bits (x==c(1))
      11: GOTO  3
      12: LOAD  3
      13: SUB   #4
      14: IF =0 GOTO 26  // Ist c(3)=4, dann ist der Bitstring abgearbeitet
      15: ADD   #3
      16: STORE 3        // letzendlich c(3) dekrementiert
      17: LOAD  1        // Eine Bitstelle, also Ergebnis verdoppeln
      18: ADD   1        // (beim ersten Durchlauf geschieht hier nichts
      19  STORE 1        //  0+0=0)
      20: ODD   @3       // War das Bit gleich 1
      21: IF =0 GOTO 14  // Wenn nein, dann nächstes Bit
      22: LOAD  1        // Wenn ja, dann noch c(2)==y drauf addieren
      23: ADD   2
      24: STORE 1
      25: GOTO 12
      26: END

1.10

a) n Stellen.
b) Es werden ganau dann die i-letzten Stellen inspiziert, wenn die Binärzahl mit einer 1 gefolgt von i-1 Nullen endet. Damit ist die Wahrscheinlichtkeit, dass genau i Stellen inspiziert werden gerade 2^-i. Summation von i=1 bis i=n über i*2^-i liefert 2-1/2ⁿ.

1.11

Betrachte (a*2^2k+1+c)*(b*2^2k+1+d). Die ersten 2k Bits liefern a*b, die letzten 2k bits c*d.

1.12

f₈=o(f₃),
f₃=o(f₄),
f₄=o(f₁),
f₁=o(f₉),
f₉=o(f₁₀),
f₁₀=o(f₂),
f₂=o(f₆) und
f₆=o(f₅).

Weiter ist f₇=o(f₆).
f₇ ist mit den anderen Funktionen (außer f₅ undf₆) unvergleichbar.

1.13

Beweis mit vollständiger Induktion.
Alternativ betrachte man die mit (x-1) multiplizierte Gleichung.

1.14

Ja, es gilt.

1.15

Die Implikation von links nach rechts gilt, die umgekehrte Implikation nicht.

1.16

Gilt nicht.

1.17

Nachrechnen und mehrfache Anwendung von l'Hospital.

1.18

f₁=Θ(log(n))
f₂=Θ(1)
f₃=Θ(nlog(n))
f₄=Θ(n)
f₅=Θ(log³(n))

1.19

f(n)=1+(-1)ⁿ und g(n)=1-(-1)ⁿ.

1.20

Das c verändert sich in jedem Induktiosschritt und ist somit nicht konstant.

Kapitel 2

2.1: Nach jedem Vergleich wissen wir von der größeren Zahl, dass sie nicht das Minimum sein kann. Werden weniger als n-1 Vergleiche ausgeführt, so gibt es mindestens zwei Zahlen, die noch für das Minimum in Frage kommen. Wir können beide Werte im Nachinein geeignet erniedrigen, ohne dass die vorherigen Vergleiche dadurch falsch werden. Je nachdem, wie wir das tun, ist entweder die eine oder die andere das Minimum. Ein beliebiger Algorithmus mit maximal n-2 Vergleichen kann also nicht feststellen, welche der beiden nun wirklich das Minimum ist.
2.2: Erweitere den Schlüssel k des i-ten Datensatzes zu (k,i) und verwende eine lexikographische Ordnung, die auf der ersten Komponente die ursprüngliche Ordnung verwendet.
2.3: Die obere Schranke ist klar, da es maximal n(n+1)/2 Verschiebungen geben kann.
Bei n Elementen ist die Wahrscheinlichkeit, dass das letzte Element Rang k hat gerade 1/n. Somit ist die erwartete Anzahl an Verschiebungen gerade die Summe von i=0 bis i=n über i/n, was (n+1)/2 ergibt.
Per Induktion lässt sich zeigen, dass dann die erwartete Anzahl von Verschiebungen durch 1/4(n-1)² nach unten beschränkt ist.
2.4: Es gilt.
2.5: Man kann zeigen: In der i-ten Phase wird das i-te größte Element an die richtige Position gebracht.
2.6: Man mische jeweils zwei der k Folgen zu einer neuen Folge zusammen. Man erhält dann k/2 Folgen der Länge 2n/k. Dies führt man fort, bis nur noch eine Folge übrig ist. In der i-ten Phase werden also je zwei Folgen der Länge 2^i-1n/k zu einer Folge der Länge 2ⁱn/k zusammengemischt. Dabei gibt es je Phase k/2ⁱ Mischvorgänge. Insgesamt benötigt jede Phase maximal n Vergleiche und da es maximal log(k) Phasen gibt, maximal nlog(k) Vergleiche:
T(n) < k*T(n/k)+nlog(k).
Per Induktion kann man zeigen, dass T(n)=O(nlog(n)) gilt.
2.7: Mit vollständiger Induktion und Fallunterscheidung, ob n gerade oder ungerade ist. Für den Fall n ungerade ist der Beweis technisch etwas aufwendiger.
2.8: T(n)=n-1.
2.9: Man muss nur zeigen, dass innerhalb eines Levels die Knoten aufsteigend nummeriert werden und dass der linkeste Knoten eines Levels eine um eins größere Nummer als der rechteste Knoten des vorherigen Levels erhält. Dies lässt sich mit Abzählen leicht nachweisen.
2.10: Laufzeit Θ(nlog(n)).
2.11: Für k=2 ist der beschriebene Algorithmus vom Prinzip her derselbe wie Heapsort. Die Details der Implementierung weichen jedoch etwas voneinander ab.
Zu Beginn werden in den Gruppen die Minima bestimmt. Dies benötigt O(n) Vergleiche. Anschließend werden in m Gruppen von jeweils maximal k Elementen die Maxima bestimmt. Da dies etwa n Mal wiederholt wird, ergibt sich eine Laufzeit von O(nmk)=O(knlog_k(n)).
Dies geht etwas effizienter für große k, wenn man nicht nur in jeder Gruppe das Minimum bestimmt, sondern die Elemente als sortiertes Feld verwaltet. Wenn man die Gruppen als Baum interpretiert, hat der Baum insgesamt O(n/k) Knoten (d.h. Gruppen). Das Sortieren aller Gruppen benötigt daher insgesamt O(n/k*klog(k)) =O(nlog(k)). Das Einfügen eines neuen Elements mittels binärer Suche in eine Gruppe kann in Zeit O(log(k)) geschehen. Somit benötigt die zweite Phase maximal Zeit O(nmlog(k)) =O(nlog_k(n)log(k)) =O(nlog(n)).
2.12: Ersetze in den beiden do-while-Schleifen (array[i] < array[pivot]) bzw. (array[j] > array[pivot]) durch (array[i] ≤ array[pivot]) bzw. (array[j] ≥ array[pivot]).
2.13: Betrachte H_n als Ober- bzw. Untersumme des Integrals über dx/x mit geeigneten Grenzen.
2.14: Man rechnet nach, dass die Höhe des entstehenden Rekursionsbaumes durch log(n)/log(1/(1-ε))=O(log(n) beschränkt ist (wobei ε konstant ist). Auf jedem Level benötigen alle Partitionierungen der einzelnen Teilintervalle (die ja eine Partition von [1:n] sein müssen) maximal Zeit O(n). Somit ist der Zeitbedarf insgesamt O(nlog(n)).
2.15: Quicksort: (3,3,1,1,2); wobei das letzte Element als Pivot gewählt wird.
Heapsort: (1,2,2,2); Beachte, dass das Feld bereits die Heap-Bedingung erfüllt.
2.16: Zeige mittels vollständiger Induktion, dass V_wc(n)≥1/2(n-1)n. Dabei zeigst sich, wie die worst-case Eingabe aussieht.
2.17: Nachrechnen.
2.18: Verfahre analog zu Mergesort und teile die Folge in eine linke und rechte Folge. Bestimme rekursiv die optimalen Teilsequenzen. Die optimale Teilsequenz ergibt sich aus den beiden optimalen Lösungen der Rekursion sowie einer optimalen Folge die über den Schnittpunkt hinweggeht. Letztere kann in linearer Zeit gefunden werden.
2.19: Fleißaufgabe; Mittels lineare Suche siehe extra Skizze.
2.20: Fleißaufgabe
2.21: Verwende einen Entscheidungsbaum: Da es (n+m)!/(n!m!) verschiedene Lösungen gibt, ist eine untere Schranke log((n+m)!/(n!m!))

Kapitel 3

3.1

Beweis durch Induktion. Dabei darf man die n-1 Vergleiche für das Partitionieren nicht vergessen (man könnte das Partitionieren bei der Medianbestimmung miterledigen, dies wurde hier aber nicht vorausgesetzt!) und den Term O(n) mit 0 ansetzen.

3.2

Es sind sogar nur 6 Vergleiche ausreihend und notwendig.

Bild zunächst zwei Paare von Elementen und vergleiche diese (1. und 2. Vergeich).
Vergleiche die beiden gröseren miteinander (3. Vergleich). Das Maximimun muss nun Rang 1 oder zwei besitzen und kommt als Median nicht in Frage.
Nun haben wir ein Paar von Elementen, die bereits miteinander verglichen wurden und zwei Elemente, die jeweils nicht mit den restlichen dre Elementen verglichen wurden. Vergleiche die beiden einzelen Elemente (4. Vergleich), so dass wir wieder zwei Paare von Elementen eralten, die miteinander verglichen wurden.
Vergleiche nun wieder die beiden Maxima der Paare (5. Vergleich). Dieses muss nun den Rang 1 oder zwei besitzten, d.h. wir kennen jetzt die beiden größten Elemente.
Im letzten und 6. Vergleich vergleichen wir jetzt unter den drei verbliebenen Elementen, die beiden Elemente, die noch keinen Vergleich gegen diese Elemente verloren haben. Das größere davon besitzt den Rang 3 und ist der gesuchte Median.

Die allgemeine untere Schranke aus diesem Kapitel liefert die hier gesuchte untere Schranke.

3.3

Nachrechnen.

3.4

Für k=3 zeigt sich, dass die lineare Laufzeit nicht zu halten ist.
Für ungerade k>5 ist die Analyse nicht einfach, da es aufwendig ist, die minimale Anzahl von Vergleichen zur Medianbestummung zu ermitteln. Eine ausführliche Analyse (aufwendig!) zeigt, dass die Werte zuerst absteigen und dann wieder zunehmen, wobei dies nur für sehr große n gilt.

3.5

Man vergleiche die Mediane der beiden Listen. Wenn beide gleich sind, hat man den Median der Gesamtmenge gefunden. Andernfalls kann man (m+n)/2 Elemente als Kandidaten für den Median der Gesamtmenge ausschließen und man wendet das Verfahren rekursiv auf die verbleibenden Liste der Länge m/2 bzw. n/2 an.

3.6

Bestimme zuerst mit Hilfe eines fast vollständigen binären Baumes das Maximum (n-1 Vergleiche). Bestimme dann das Maximum aller Verlierer gegen das eigentliche Maximum (log(n)-1 Vergleiche).
---

3.7

Wir diskutieren nur den Fall, dass n gerade ist. Führe zuerst n/2 Vergleiche von disjunkten Paaren aus (n/2 Vergleiche). Die jeweils größeren bzw. kleineren Elemente sammle in der Menge G bzw. L. Bestimme in G das Maximum und in L das Minimum (2(n/2-1)=n-2 Vergleiche).

Wir diskutieren nur den Fall, dass n gerade ist. Wir führen folgende Bezichnungen für Elemente ein

o bedeutet, das Element war noch an keinem Vergleich beteiligt;
+ bedeutet, das Element hat alle bisherigen Vergleiche gewonnen;
- bedeutet, das Element hat alle bisherigen Vergleiche verloren;
* bedeutet, das Element hat bereits Vergleiche sowohl gewonnen als auch verloren.

Elemente * brauchen wir nicht mehr zu berücksichtigen, sie können weder das Maximum noch das Minimum sein. Demnach machen nur noch folgende Vergleiche einen Sinn (beachte die Symmetrie):

o/o geht über in +/-;
o/+ geht schlimmstenfalls in -/+ über;
o/- geht schlimmstenfalls in +/- über;
+/+ geht in +/* über;
+/- geht schlimmstenfalls in +/- über (Vergleich somit sinnlos!);
-/- geht in -/* über;

Somit ist der Vergleich o/o der fruchtbarste, er liefert zwei Einschränkungen. Alle anderen (außer +/-) liefern im schlimmsten Fall nur eine weitere Einschränkung. Man überlegt sich leicht, dass mindestens 2n-2 Einschränkungen benötigt werden, bevor ein beliebiger Algorithmus sowohl das Maximum als auch das Minimum verkünden kann.
Somit kann ein cleverer Algorithmus mit n/2 Vergleichen vom Typ o/o insgesamt maximal n Einschränkungen holen; dann gibt es nur noch Elemente vom Typ + oder -. Die benötigen restlichen n-2 Einschränkungen müssen dann mit n-2 Vergleichen vom Typ +/+ bzw. -/- gemacht werden. Daher sind mindestens 3n/2-2 Vergleich nötig.

3.8

Konstruiere nebenher einen Graphen, der für jedes Ergebnis x<y die Kante (x,y) aufnimmt. Zum Schluss entferne alles ausgehenden Kanten des Medians m (d.h. (m,*)). Man kann zeigen, dass die Zusammenhangskomponente mit m genau die k Elemente umfasst, die größer gleich m sind.

3.9

Bestimme den Median der Menge und partitioniere die Menge in zwei Mengen, eine mit Elementen kleiner gleich und eine mit Elementen größer als der Median. Suche rekursiv in der richtigen Menge weiter.

Kapitel 4

4.1: Nein, da nicht surkektiv.
4.2: Es muss ggT(l,n)=1 gelten, da sonst die verallgemeinerte Hashfunktion nicht surjektiv ist.
Primäre und sekundäre Häufung bleiben bestehen.
4.3: ---
4.4: Ja, durch sukzessives Einfügen in den Suchbaum und anschließendes Traversieren des Baumes in Preorder.
Zeitbedarf O(nlog(n)).
4.5: Durch Induktion und Ausnutzen der Rekursion |T(h)|≥1+|T(h-1)|+|T(h-2)|.
4.6: Minimale Anzahl für gerades h: 2^(h/2+2)-3.
Minimale Anzahl für ungerades h: 3*2^((h+1)/2)-3.
Maximale Anzahl: 2^(h+1)-1.
4.7: ---
4.8: Für einen Hinweis das Kapitel nochmal lesen.
4.9: Einsetzen und Nachrechnen.
4.10: Maximale Anzahl: (b^h+1-1)/(b-1).
Minimale Anzahl: 1+(a^h-1)/(a-1) (Die Wurzel darf ein Kind haben!).
4.11: ---
4.12: Fleißaufgabe.

Kapitel 5

5.1

Starte an einem beliebigen Knoten und laufe entgegen der Kantenrichtung (dies ist nach Voraussetzung eindeutig). Entweder trifft man auf einen Knoten mit Eingangsgrad 0 oder man findet einen Zyklus (da der Graph endlich ist).

5.2

=>: Angenommen, |E|≠|V|-1. Betrachte unter allen solchen Graphen einen mit kleinster Knotenanzahl. Dann enthält G keinen Knoten mit Grad 1, denn dass Entfernen des Knotens samt seiner inzidenten Kante würde zu einem kleineren Graphen mit denselben Eigenschaften führen.
Ist |E|<|V|-1, dann kann G nicht zusammenhängend sein. Sei also |E|≥|V|. Nach Annahme hat jeder Knoten mindestens Grad 2. Starte an einem beliebigen Knoten und durchlaufen den Graphen. Sobald man einen Knoten zum zweiten Mal besucht, hat man einen Kreis gefunden (dies muss geschehen, da der Graph endlich ist und jeder Knoten mindestens Grad 2 hat). Dies ist ein Widerspruch zur Azyklität von G.

<=: Angenommen G sei zyklisch. Wähle unter allen solchen Graphen einen mit minimaler Knotenanzahl. Dann enthält G keinen Knoten mit Grad 1, denn dass Entfernen des Knotens samt seiner inzidenten Kante würde zu einem kleineren Graphen mit denselben Eigenschaften führen. Da die Summe der Knotengrade gleich der doppelten Kantenanzahl ist und jeder Knoten Grad mindestens 2 hat, gilt |E|≥|V|>|V|-1, was ein Widerspruch zur Voraussetzung ist.

5.3

Induktion über die Anzahl der Blätter.

5.4

Unterteile die Matrix in Blöcke der Größe k*k mit k=√log(n) Es gibt nur 2^k*k=O(n) verschiedene k*k-Matrizen mit Einträgen aus {0,1}. Diese können vorab in Platz O(nlog(n)) gespeichert werden. Jeder echte Block der Adjazenzmatrix wird dann durch einen Verweis auf diese vorberechneten Blöcke repräsentiert und benötigt daher Platz n/k*n/k=O(n²/log(n))

5.5

Es müssen nur die im Text genannten Charakterisierungen der entsprachenden kanten berücksichtigt werden.

5.6

Eine Vorwärtskante würde man in einem ungerichteten Graphen zuerst andersherum als Rückwärtskante identifizieren.
Eine Querkante würde man in eineme ungerichteten Graphen zuerst andersherum als Baumkante indentifizieren.

5.7

In gerichteten Graphen entstehen Baumkanten, Querkanten und Rückwärtskanten.
Bei ungerichteten Graphen entstehen Baumkanten und Querkanten.

5.8

=>: In einen Eulerkreis wird jeder Knoten genau so oft verlassen, wie er besucht wurde. Somit muss der Knotengrad gerade sein.

<=: Starte an einem beliebigen Knoten v und durchlaufe den Graphen, solange es geht. Man kann zeigen, dass man wieder an v endet, da man jeden Knoten den man besucht wieder verlassen kann (da der Knotengrad gerade ist) außer bei v. Hat man einen Eulerkreis konstruiert, so ist man fertig. Sonst gibt es noch unbesuchte Kanten. Entferne den bisher gefundenen Kreis. Im neuen Graph hat jeder Knoten weiterhin geraden Grad. Starte an einem beliebigen Knoten und finden einen neuen Kreis. Zum Schluss muss aus der Menge der gefundenen Kreise ein neuer, einziger Kreis konstruiert werden (dies ist möglich, da G nach Voraussetzung zusammenhängend ist).

5.9

Die Wurzel des Baumes ist der erste Knoten in der Preorder. Wir finden jetzt die Teillisten für die Teilbäume, die an den Kindern der Wurzel gewurzelt sind. Der zweite Knoten der Preorder-Liste ist die Wurzel des ersten Teilbaumes. In der Postorder-Liste gehören alle Knoten vor diesem Knoten zum ersten Teilbaum. Der auf diese Menge von Knoten in der Preorder-Liste folgende Knoten ist die Wurzel des zweiten Teilbaumes usw. Die Teilbäume selbst werden dann aus den Bruchstücken der Preorder- und Postorder-Liste rekursiv konstruiert.

5.10

Verwende eine rekursive Tiefensuche; Sobald eine Rückkante gefunden wird, ist der Graph kein DAG.
Die topologische Sortierung erhält man, indem man einen globalen Zähler mit n=|V| initilisiert und nach dem Abschluss der rekursiven Tiefensuche an einem Knoten dort den Wert n vergibt und anschließend n um 1 dekrementiert.

5.11

Traversiere den Graphen und füge für jede Kante (u,v) die Kante (v,u) hinzu.

5.12

Sei T(i,j,k) die Anzahl Operationen, die benötigt werden, um D^k_i,j zu berechnen. Dabei sei T(i,j,0)=1. Dann gilt T(i,j,k)=3^k (Beweis mittel Induktion). Also ist die Gesamtlaufzeit Θ(n²3ⁿ).

5.13

G=({a,b,c}, {(a,b,2), (a,c,3), (c,b,-2)})

5.14

Sobald ein Wert D^k_i,i negativ wird, gibt es einen Kreis negativer Länge.

5.15

Beweis mit Induktion.

5.16

Wir nehmen hier schlingenfreie Graphen an, d.h. E(i,i)=0. Es gilt E^-=E-sgn*(E^*), wobei sgn* alle positiven Elemente auf 1 setzt und die Elemente der Hauptdiagonale auf 0 setzt.

5.17

Analog wie bei normalen Heaps.

5.18

Schlüssel und Name eines Elementes werden im Folgenden als identisch betrachtet:

insert(0); insert(n); insert(n-1); delete_min();
insert(0); insert (n+1); insert(n-2); delete_min();
decrease_key(n+1,0); insert(n+1); insert (n-3); delete_min();
...
decrease_key(n+1,0); insert(n+1); insert (n-i); delete_min();
...
decrease_key(n+1,0); insert(n+1); insert (1); delete_min();
decrease_key(n+1,0); delete_min();

Zum Schluss hatt man einen Baum der aus einer linearen liste mit n Elementen besteht, wobei 4n-2 Operationen benötigt werden.

5.19

delete(k)={decrease_key(k,min-1); delete_min();}

5.20

Betrachte einen minimalen Spannbaum T. Enthält T die Kante e nicht, so ist nichts zu zeigen. Sei also e eine Kante von T, die die beiden Teilbäume T₁ und T₂ verbindet. Verfolge nun den Pfad, der durch den restlichen Kreis induziert wird, beginnend vom Endkonten von e, der in T₁ liegt. Dieser Pfad enthält eine Kante e', die von T₁ zu T₃ geht. Da e' ebenfalls eine Kante des Kreises mit maximaler Kante e ist, ist das Gewicht von e' höchstens so groß wie von e und somit ist T₁ und T₃ verbunden mit e' ebenfalls ein minimaler Spannbaum.

5.21

In den U.S.A. ist er optimal, in Utopia nicht (betrachte den Wechel von beispielsweise 30 Einheiten). Wie wäre es bei den Nennwerten {1,5,25,100}?

5.22

Angenommen, ein minimaler Spannbaum enthält e. Nach dem Entfernen von e aus dem Spannbaum bleiben zwei Bäume übrig. Beim Durchlaufen der restlichen Kanten des gegebenen Kreises trifft man auf mindestens eine Kante e', die zwischen den beiden Bäumen verläuft. Nach Voraussetzung muss das Gewicht von e; gleich dem von e sein.

5.23

Ein Binomial-Baum k-ter Ordnung ist rekursiv wie folgt definiert. Ein Binomial-Baum 0-ter Ordnung besteht aus nur einem Knoten. Ein Binomial-Baum k-ter Ordnung entsteht aus zwei Binomial-Bäumen (k-1)-ter Ordnung, indem man die Wurzel des einem Baumes zum Kind des anderen Baumes macht.
Ein Binomial-Baum k-ter Ordnung besitzt offenichtlich 2^k Knoten und hat eine Tiefe von k. Man kann weiter zeigen, dass man sich einen Binomial-Baum k-ter Ordnung auch als eine Wurzel vorstellen kann, an dem für jedes i∈[0:k-1] ein Binomial-Baum i-ter Ordung als Kind angehängt wird.
Sei k:=log(n/2). Man erzeugt zunächst mit Union-Operationen einen Binomial-Baum k-ter Ordnung (mit n/2 Knoten). Hängt man dieses Biniomial-Baum (mittels einer Union-Operation) an einen anderen Knoten als Kind an und führt ein Find (mit Pfadkompression) auf das tiefste Blatt in diesem Baum durch, so kann man zeigen, dass im Wesentlichen wieder ein Binomial-Baum gleicher Ordnung entsteht (an deren Wurzel nur ein weiterer Knoten hängt). Diese Find-Operation verursacht Kosten in Höhe von Ω(log(n)). Da nun noch n/2-1 Knoten übrig sind, kann man dies noch &Omega(n/2) mal wiederholen und erhält einen Gesamtaufwand von Ω(nlog(n)).

Kapitel 6

6.1: Initialisiere eine neue Variable found=0; ersetze return i; durch found++; break; und ersetze return -1; durch return found;
6.2: border[]=(0,0,1,0,1,0,1,2,3,4)
6.3: S[]=(12,12,12,12,12,12,12,7,12,12,3,1)
6.4: Der Einfachheit halber nehmen wir an, dass n gerade und m ungerade ist: Wähle t=(ab)^n/2; s=a(ab)^m/2;
6.5: Der Suffix-Trie besitzt Θ(n²) Knoten.
6.6: Fleißaufgabe.
6.7: Konstruiere den Suffix-Baum für die konkatenierte Zeichenreihe und entferne Teilbäume die Dollarzeichen enthalten. Alternativ konstruiere einen Suffix-Baum für t₁. Konstruiere dann den Suffix-Baum für t_i innerhalb des bereits konstruierten Suffix-Baumes.
6.8: Komnstruiere einen verallgemeinerten Suffix-Tree T für x,y∈&Sigma^*. Markiere die Blätter mit x oder y, je nach dem, ob der zugehörige Suffix aus x oder y stammt. Der tiefste Knoten (gemäß der String-Tiefe) in T, der in seinem Teilbaum sowohl ein mit x als auch mit y markiertes Blatt besitzt, korrespondiert zum längsten gemeinsamen Teilwort.
6.9: Suche nach v in ww.
6.10: Suche nach dem zweiten Vorkommen von v in vv.
6.11: ---
6.12: ---

Kapitel 7

7.1: Seien e und e' zwei neutrale Elemente, dann gilt: e=ee'=e'.

Sei a ein Gruppenelement und b sowie c zwei Inverse zu a, d.h.: ab=e sowie ac=e (wobei e das eindeutige neutrale Element ist).
Wir zeigen zunächst, dass ba=e ist (das Monoid ist nicht notwendig abelsch!). Sei dazu d das Inverse zu ba, d.h. bad=e.
Dann gilt: ba=bae=ba(bad)=b(ab)ad =bead=bad=e.
Betrachte jetzt: b=be=b(ac)=(ba)c=ec=c.
7.2: Beweis durch Induktion.
7.3: Schreibe die Elemente als Potenzen des erzeugenden Elementes und verwende die vorhergehende Aufgabe.
7.4: ⇒: Wenn (M',*) eine Untergruppe ist, dann ist M' nach Definition auch abgeschlossen.
⇐: Sei a∈M' und sei M={b₁,...,b_k}. Betrachte a*b₁,...,a*b_k. Da dies auch Elemente von M sind und M eine Gruppe ist, müssen alle Elemente paarweise verschieden sein. Es gibt also ein j&isin[1:k] mit a*b_j=a, d.h. b_j=1 und somit eine neutrales Element in M'. Weiterhin muss es ein i&isin[1:k] mit a*b_i=b_j=1. Also existiert zu a auch ein Inverses in M'. Da a ein beliebiges Element aus M' war, muss es zu jedem Element aus M' ein Inverses geben.
7.5: Sei z das Inverse zu 0*a. Betrachte: 0=0*a+z =(0+0)*a+z =(0*a+0*a)+z =0*a+(0*a+z) =0*a+0 =0*a
7.6: Die Halbringeigenschaften nachrechnen.
7.7: Sei a≠0 und b≠0, dann existieren die Inversen ac=1 und bd=1. Dann folgt aus ab=0, dass abdc=0dc. Mit Aufgabe 7.5 folgt dann: 1=0.
7.8: ---
7.9: {e} und G.
7.10: ---
7.11: Verwende den Satz aus Aufgabe 7.4.
7.12: ⇒: Wenn p∈P, dann ist Z^*p=Z_p\{0} und &phi(p)=p-1. Somit folgt die Behauptung aus einem Satz von Euler.
⇐: Sei d ein Teiler von p, d.h da=p. Nach der rechten Seite gilt d^p-1=1mod p, d.h. d^p-1-1=qp für ein q&isinN. Somit gilt unter Berücksichtigung von p≥2: d(d^p-2-qa)=1. Diese Gleichung über N kann dann und nur dann gelten, wenn d=1.
Aus der Kontraposition der Richtung von links nach rechts kann so erst einmal kein sinnvoller randomisierter Primzahltest abgeleitet werden, da Z_n\{0} im Allgemeinen keine multiplikative Gruppe ist und über die Anzahl der Zeugen nichts ausgesagt werden kann.
7.13: Beweis durch Induktion.
7.14: ---
7.15: Fleißaufgabe.
Die Rekursionsgleichung lautet: B(n)=Sum(i=1..n-1) B(i)*B(n-i).
Das Ergebnis lautet: 1/(n)*C(2n-2,n-1), wobei C(.,.) der Binomialkoeffizient ist.

Alternativmöglichkeit: Stelle eine bijektive Beziehung zwischen geordneten erweiterten binären Bäumen und Klammerausdrücken her.
7.16: Es gilt offensichtlich: A(n,m) =1+A(n-1,m)+A(n-1,m-1) sowie A(n,n)=A(n,0)=0. Wir setzen B(n,m):=1+A(n,m). Dann gilt B(n,m) =B(n-1,m)+B(n-1,m-1) sowie B(n,n)=B(n,0)=1. Also ist B(n,m) gleich m aus n. Damit kennen wir auch A.
7.17: ---

Kapitel 8

8.1: ⇒: Definiere ψ(x):=min{n&isinN|φ(n)=x}. Zeige jetzt noch, dass ψ injektiv ist, wenn φ surjektiv ist.
⇐: Definiere &phi(n):=&psi^-1(n), wenn &psi^-1(n) existiert und &phi(n):=m für ein festes m&isinM sonst. Zeige jetzt noch, dass φ surjektiv ist, wenn ψ injektiv ist.
8.2: Wir geben den Beweis für das zweielementiges Alphabet Σ={0,1}. Erweiterungen auf andere Alphabete sind nahe liegend. Sei w∈Σ^*. Interpretiere 1w als Binärzahl x und setze &psi(w):=x. Nach Aufgabe 8.1 muss nur noch gezeigt werden, dass ψ injektiv ist.
8.3: Die Brüche in Q lassen sich auch als Paare in N² interpretieren (dabei gibt es mehrere Darstellungen von q aus Q in N², was aber hier nicht von Belang ist.)
Nimm an, das R abzählbar sei und leite einen Widerspruch her.
8.4: a) Man nehme an, es gibt ein k&isinN. Man kann dann leicht zeigen, dass dann weder ψ(2k)∈&phi(k) noch ψ(2k)∉&phi(k) gelten kann.
b) Das kann durchaus sein, dann muss k auf jeden Fall ungerade sein.
8.5: Man rechnet leicht nach, dass für &phi(n,m)=x gilt: n+m=⌈1/2+(2x+1/4)^1/2⌉ Der Rest ist dann nur Rechnerei.
8.6: Die erste ist keine, die zweite schon (welche!).
8.7: Analog wie bei universellen Registermaschinen.
8.8: Nein. Beispielsweise Reduktion auf das Halteproblem.
8.9: Zum Beispiel durch Erstellen der entsprechenden Wertetabellen.
8.10: Wir nutzen aus, dass x⇒y äquivalent zu (¬x)&ory ist. Damit lassen sich alle Klauseln aus zwei Literalen als Implikationen über zwei Literalen schreiben. Diese Implikationen übersetzen wir wie folgt in einen Graphen. Alle Literale sind Knoten. Eine gerichtete Kante von x nach y existiert genau dann, wenn x⇒y als Klausel vorkommt.
Wir bestimmen dann alle starken Zusammenhangskomponeten, wobei die Literale in einer solchen starken Zusammenhangskomponente denselben logischen Wert besitzen müssen. Wir konstruieren dann den so genannten reduzierten Graphen, wobei alle Knoten einer starken Zusammenhangskomponete zu einem Superknoten zusammengefasst werden. Eine Kanten von einem Superknoten W zu einem anderen Superknoten W' existiert genau dann, wenn es w∈W und w'∈W' gibt, so dass (w,w')∈E eine Kante im ursprünglichen Graphen war. Der reduzierte Graph muss dann ein DAG sein.
Wir müssem jetzt nur noch den Superknoten logische Werte so zuordnen, dass 1⇒0 nicht vorkommt. Wenn das möglich ist, ist die Formel erfüllbar, sonst nicht.
8.11: siehe Garey/Johnson.
8.12: P ist nicht in NPO enthalten, da weder I in P ist noch μ in polynomieller Zeit berechenbar ist.
8.13: Offensichtlich lässt sich eine potenzielle Lösung leicht in polynomieller Zeit auf ihre Zulässigkeit hin prüfen. Auch die Optimierungsfunktion μ ist in polynomieller Zeit berechenbar.
8.14: Einfach nachrechnen.
8.15: Es wird iterativ eine Partition X und Y aufgebaut. Wir betrachten eine Knoten v. Gehen von v mehr Knoten nach X als nach Y, so platzieren wir v in die Menge Y und sonst in X.
Da für jeden Knoten im Auswahlschritt mindestens die Hälfte der Kanten zwischen X und Y verläuft, ist die Approximationsrate mindestens 2.
8.16: Konstruiere einen minimalen Spannbaum T für G. Erzeuge eine Euler-Tour für T und überspringe doppelt besuchte Knoten. Dies liefert die konstruierte TSP-Tour.
Für die Approximationsgüte überlge man sich, dass das Gewicht von T höchstens so groß ist, wie die Kosten einer optimalen TSP-Tour. Die Kosten der Euler Tour sind doppelt so groß wie die des optimalen Spannbaumnes, da jede Kante genau zweimal abgelaufen wird. Also sind die Kosten der Euler-Tour maximal doppelt so hoch wie die einer optimalen TSP-Tour. Beim Überspringen von Knoten hilft die metrische Dreiecksungleichung, dass die Kosten nicht größer werden.

Suche

Links und Funktionen

Sprachauswahl

Benutzermenü

Navigationspfad

Hauptnavigation

Inhalt

Lehrbuch Grundlegende Algorithmen: Supplement

Vorbemerkungen

Lösungshinweise:

Servicebereich

Fußzeile