Algorithmen und Datenstrukturen 2

Ü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 $

 Name                                   Last modified      Size  Description
 Parent Directory                                            -   
 README.html                            2023-10-11 10:00  957   
 Loesung81.java                         2023-10-11 10:00  1.2K  
 Loesung82.java                         2023-10-11 10:00  1.3K  
 Loesung83.java                         2023-10-11 10:00  1.8K  
 HEADER.html                            2023-10-11 10:00  2.4K