Zum Menü springen.

Übungsblatt 8: Maximum–Sub-Array–Problem, lineare Algorithmen

Abgabe bis Montag, 22. Juni, 15:50 Uhr.

Aufgabe 8-1 *

Durch invariante Festlegung einer der beiden Sub-Array–Grenzen auf einen bestimmten Index lässt sich das derart eingeschränkte Maximum–Sub-Array–Problem leicht mit einer linearen Zeitkomplexität von O(n) lösen. Formulieren Sie einen Algorithmus, der das sog. linke Randmaximum ermittelt, dessen linke Grenze auf den Index 0 festgelegt ist.

Schreiben Sie wahlweise präzise „natürliche Sprache“ nach Dr. Bürg oder eine Java-Klassenmethode! In Java wird lediglich der Gesamt-Array als Parameter übergeben; es genügt die Rückgabe der Sub-Array–Summe als Ergebnis.

Aufgabe 8-2

Formulieren Sie analog zu Aufgabe 8-1 einen Algorithmus, der das rechte Randmaximum ermittelt.

Aufgabe 8-3

Der auf dem sog. Scanline-Prinzip arbeitende Algorithmus von Kadane bestimmt den Maximum–Sub-Array frei, indem an jeder Position des Arrays dasjenige Maximum–Sub-Array ermittelt wird, das an dieser Position seinen rechten Rand hat. Weil dieses Sub-Array immer entweder leer ist oder gerade um das eine Element an dieser Position länger ist als das an der vorhergehenden Position endende Maximum–Sub-Array, lässt sich mit diesem Algorithmus das Maximum–Sub-Array auch ohne eine invariante Grenze in linearer Zeitkomplexität lösen.

Implementieren Sie diesen Scanline-Algorithmus in Java in einer Klassenmethode! Es genügt die Rückgabe der Sub-Array–Summe als Ergebnis.

Zusatzaufgabe 8-4

Überlegen Sie, welche Angaben ein in Aufgabe 8-1 ermitteltes Randmaximum eindeutig identifizieren würden.

  1. Schreiben Sie eine Java-Klasse, deren Instanzen alle benötigten Daten bzw. Referenzen darauf enthalten können.
  2. Passen Sie Ihren Algorithmus aus Aufgabe 8-1 derart an, dass Ihre Klasse aus Teilaufgabe (a) für das Ergebnis verwendet wird.
  3. Welche Auswirkungen auf die Effizienz hat die Änderung aus Teilaufgabe (b)?
$Id: HEADER.html 2009-06-14 $
Icon  Name                                   Last modified      Size  Description
[DIR] Parent Directory - [HTM] HEADER.html 2023-10-11 10:00 2.4K [TXT] Loesung83.java 2023-10-11 10:00 1.8K [TXT] Loesung82.java 2023-10-11 10:00 1.3K [TXT] Loesung81.java 2023-10-11 10:00 1.2K [HTM] README.html 2023-10-11 10:00 957