Lösungsvorschläge

zu den Aufgaben im Kapitel 2

Aufgabe 2.6: Berechnen Sie von folgenden Folgen jeweils die maximale Teilsumme sowie das rechte und das linke Randmaximum:

folge1 = (-3, +5, -20, +4, +8, -4, -9, -2, +3, +2)
folge2 = (+3, -2, +5, -20, +3, +3)
folge3 = (-20, +5, +3)
folge4 = (+1, +1, +1)
folge5 = (-1, -1, -1)
folge6 = (+27)
folge7 = (-27)
folge8 = ()

Lösung:

Aufgabe 2.7: Wie oft kann man eine Folge der Länge 2, der Länge 4, der Länge 8, ... der Länge 1024 in zwei gleiche Hälften teilen?

Lösung: 1, 2, 3, ... 10 mal

Aufgabe 2.8: Wie oft kann man eine Folge der Länge 37, der Länge 578 oder der Länge 1234 in zwei ungefähr gleich große Hälften teilen?

Lösung: 5, 9, 10 mal

Aufgabe 2.9: Wenn man die Funktion maxTeilsummeRekursiv mit einer Folge der Länge n als Parameter aufruft, wie oft ruft sie sich dann rekursiv auf?

Lösung: ⌊log₂ n⌋ mal, wobei mit ⌊und ⌋die nach unten gerundete ganze Zahl (floor) gemeint ist.

Aufgabe 2.10: „Wie viele Befehle“ werden bei jedem Aufruf von maxTeilsummeRekursiv ausgeführt, wenn man die rekursiven Aufrufe von maxTeilsummeRekursiv nicht mitzählt?

Lösung: 5: if, mitte errechnen, rechtesRandMax, linkesRandMax, Math.max

Aufgabe 2.11: Begründen Sie, dass der Zeitbedarf der Funktion maxTeilsummeRekursiv proportional zu n log n wächst.

Lösung: rechtesRandMax und linkesRandMax hat eine Schleife, deren Ausführungszeit proportional zu n wächst; die Anzahl ihrer Aufrufe wächst proportional zu log₂ n.

Aufgabe 2.12: Diskutieren Sie die „Geschwindigkeiten“ der Funktionen maxTeilsumme3, maxTeilsumme2 und maxTeilsummeRekursiv relativ zueinander. Ist maxTeilsummeRekursiv immer schneller als maxTeilsumme3? Welche Rolle spielen die Umgebungen (Compiler, Hardware usw.,) in denen die Funktionen ablaufen?

Lösung: maxTeilsummeRekursiv ist nur bei großen n’s ist schneller als die anderen; bei kleinen n’s können maxTeilsumme3 oder maxTeilsumme2 schneller sein. Die Umgebung spielt im Vergleich der Geschwindigkeiten bei großen n’s keine Rolle. Selbst wenn eine spezielle Hardware verwendet wird, die besonders auf eine der Techniken (z.B. Rekursion oder Zählschleife) ausgerichtet ist und sie besonders schnell ausführt, wird nur die Grenze für n’s verschoben, bei der maxTeilsummeRekursiv schneller wird.

Aufgabe 2.13: Wie verändert sich der Zeitbedarf der Funktion maxTeilsumme1 wenn wir die Länge von folge verdoppeln? Welche Zeitkomplexität hat die Funktion maxTeilsumme1 also?

Lösung: Der Zeitbedarf verdoppelt sich. maxTeilsumme1 hat eine lineare Zeitkomplexität (proportional zu n).

Aufgabe 2.14: Halten Sie es für möglich, dass man in Zukunft einen Algorithmus maxTeilsumme0 findet, der dasselbe Problem löst wie maxTeilsumme1, aber eine noch bessere Zeitkomplexität besitzt? Wenn ja: Wie könnte maxTeilsumme0 funktionieren? Wenn nein: warum nicht?

Lösung: Mit unserer jetzigen Rechnern heißt die Antwort „Nein“: Jede Zahl der Reihung muss gelesen und addiert werden. An einem hypothetischen Parallelrechner (mit einer unbegrenzten Anzahl von Prozessoren) jedoch, wo diese Operationen gleichzeitig ausgeführt werden können, ist eine Komplexität von log n möglich.

Aufgabe 2.15: Wie passen diese Messergebnisse zu den theoretischen Zeitkomplexitäten?

Lösung: Die Laufzeiten von maxTeilsumme3 (mit Zeitkomplexität von n³) wachsen mit n sehr schnell: Eine Verdoppelung von 200 auf 400 bewirkt einen etwa 8-fachen Zeitbedarf. Die Laufzeiten von maxTeilsumme2 wachsen langsamer: Hier bewirkt die Verdoppelung von 300 auf 600 bewirkt einen etwa 4-fachen Zeitbedarf. Die Laufzeiten von maxTeilsummeRekursiv wachsen noch langsamer, und von maxTeilsumme1 ganz langsam: Die Zeiten bei kleinen n’s sind nicht messbar, die Verdoppelung von 4000 auf 8000 bewirkt eine ungefähre Verdoppelung des Zeitbedarfs

Aufgabe 2.16: Nehmen wir an, dass die Prozedur blubs einen konstanten Zeitbedarf hat (d.h. jeder Aufruf von blubs benötigt für seine Ausführung gleich viel Zeit, z.B. 37 Millisekunden). Geben Sie für jede der folgenden Prozeduren proz1, proz2, ... proz9 an:

1. wie sich ihr Zeitbedarf verändert, wenn man den Parameter n verdoppelt und

2. welche Zeitkomplexität die Prozedur hat, z.B. O(n) oder O(n²) oder O(n³) oder O(n log n) usw.

void proz1(int n) { // requires n > 0
  for (int i = 1; i <= n; i++)
   blubs();
}

void proz2(int n) { // requires n > 0
  for (int i = 1; i <= n; i++)
   for (int j = 1; j <= n; j++)
     blubs();
}

void proz3(int n) { // requires n > 0
  for (int i = 1; i <= n; i++)
   blubs();
  for (int i = 1; i <= n; i++)
   blubs();
}

void proz4(int n) { // requires n > 0
  for (int i = 1; i <= 100; i++)
   for (int j = 1; j <= n; j++)
     for (int k = 1; k <= 100; k++)
      blubs();
}

void proz5(int n) { // requires n > 0
  for (int i = 1; i <= n; i++)
   for (int j = 1; j <= i; j++)
     blubs();
}

void proz6(int n) { // requires n > 0
  for (int i = 1; i <= n/2; i++)
   for (int j = 1; j <= n/4; j++)
     for (int k = 1; k <= n/8; k++)
      blubs();
}

void proz7(int n) { // requires n > 0
  for (int i = 1; i <= n * n; i++)
   for (int j = 1; j <= n * n * n; j++)
     blubs();
}

void proz8(int n) { // requires n > 0
  blubs();
  if (n > 1)
   proz8(n-1);
}

void proz9(int n) { // requires n > 0
  blubs();
  if (n > 1) {
   proz9(n-1);
   proz9(n-1);
  }
}

Lösung: proz1 ist linear (der Zeitbedarf wächst mit dem Parameter n) - die Zeitkomplexität ist O(n).
proz2 ist quadratisch (der Zeitbedarf wächst mit n*n) - die Zeitkomplexität ist O(n²).
proz3 ist linear (der Zeitbedarf wächst mit 2*n) - die Zeitkomplexität ist O(n).
proz4 ist linear (der Zeitbedarf wächst mit 100*100*n) - die Zeitkomplexität ist O(n).
proz5 ist quadratisch (der Zeitbedarf wächst mit n*n/2) - die Zeitkomplexität ist O(n²).
proz6 ist kubisch (der Zeitbedarf wächst mit n*n*n) - die Zeitkomplexität ist O(n³).
proz7 hat die Komplexität von n⁵ (wächst mit n*n*n*n*n) - die Zeitkomplexität ist O(n⁵).
proz8 ist linear (der Zeitbedarf wächst mit dem Parameter n) - die Zeitkomplexität ist O(n).
proz9 ist exponentiell (der Zeitbedarf wächst mit dem Parameter 2**n-1) - die Zeitkomplexität ist O(2ⁿ).

Aufgabe 2.17: Programmieren Sie das Eintragen in eine vorwärts verkettete Liste auf eine bestimmte (durch eine Knotenreferenz angegebene) Stelle. Überlegen Sie sich, welcher Knoten angegeben werden muss.

Lösung: Es muss der Knoten vor der Einfügestelle angegeben werden.

public void eintragen(final Object element, Knoten vorgaenger) {
  vorgaenger.verbindung = new Knoten(element, vorgaenger.verbindung);
}