Programmieren mit Harald R. Haberstroh

π kann mit Hilfe der folgenden Formel von Strömer (1986) berechnet werden:

^π / ₄ = 44 · arctan ¹/₅₇ + 7 · arctan ¹/₂₃₉ - 12 · arctan ¹/₆₈₂ + 24 · arctan ¹/₁₂₉₄₃

Der Arcustangens wird mit der folgenden Reihenentwicklung

arctan(x) = x - ^x3/₃ + ^x5/₅ - ^x7/₇ + ...

berechnet.

Folgendes Java-Programm verwendet die Klasse BigDecimal zur Berechnung von π. Es soll mittels Threads parallelisiert werden.

import java.math.*;
/**
 * @author Hans Joachim Pflug, RZ, RWTH Aachen
 *
 * Berechnet PI auf eine beliebige Anzahl von Stellen genau
 */
public class Pi {
    private int dec;                  //Anzahl der Dezimalstellen
    private BigDecimal pi = new BigDecimal(0);  //Ergebnis  
    private MathContext m;            //Zur Bestimmung der Laenge der Brueche
    private static final BigDecimal one = new BigDecimal(1);
    private static final BigDecimal four = new BigDecimal(4);
    private BigDecimal r57;           // 1/57
    private BigDecimal r239;          // 1/239
    private BigDecimal r682;          // 1/682
    private BigDecimal r12943;        // 1/12943

    /**
     * Erzeugt ein Objekt mit PI auf die angegebene Stellenzahl genau
     * @param dec Die Stellenzahl, auf die PI berechnet werden soll.
     */
    public Pi(int dec) {
        this.dec = dec;
        m = new MathContext(dec + 5);  //5 als Reserve

        r57 = one.divide(new BigDecimal(57), m);
        r239 = one.divide(new BigDecimal(239), m);
        r682 = one.divide(new BigDecimal(682), m);
        r12943 = one.divide(new BigDecimal(12943), m);

        calculate();
    }

    /**
     * Berechnet den Wert von PI nach der Formel von Stoermer (1896):
     * pi/4 = 44 * arctan(1/57) + 7 * arctan(1/239) - 12 * arctan(1/682) 
     *      + 24 * arctan(1/12943)
     */
    private void calculate() {
        BigDecimal sum1 = arctan(r57).multiply(new BigDecimal(44), m);
        BigDecimal sum2 = arctan(r239).multiply(new BigDecimal(7), m);
        sum1 = sum1.add(sum2, m);
        sum2 = arctan(r682).multiply(new BigDecimal(12), m);
        sum1 = sum1.subtract(sum2, m);
        sum2 = arctan(r12943).multiply(new BigDecimal(24), m);
        sum1 = sum1.add(sum2, m);
        pi = sum1.multiply(four, m);
    }

    /**
     * Berechnet den Arcustangens einer BigDecimal-Zahl.
     * Benutzt die Reihe:
     * arctan(x) = x - x^3/3 + x^5/5 - x^7/7 + ...
     * @param arg Eingabewert
     * @return arctan(arg)
     */
    private BigDecimal arctan(BigDecimal arg) {
        BigDecimal result = new BigDecimal(0);
        BigDecimal z;
        //Abschätzung der Anzahl der Iterationen
        //Nach der Formel  n = - d / log10(x)
        // n: Anzahl der Iterationen
        // d: Anzahl der Stellen fuer Genauigkeit
        // x: Argument des Arcustangens
        //Zwei Stellen Genauigkeit zur Sicherheit
        int iter = (int) -((dec + 2)/ Math.log10(arg.doubleValue()));  

        //Reihenentwicklung
        for (int i = 0; i < iter; i++) {
            int pow = 2 * i + 1;
            z = arg.pow(pow, m).divide(new BigDecimal(pow), m);

            if (i % 2 == 1) {
                z = z.negate();
            }
            result = result.add(z, m);    
        } 
        return result;
    }

    /**
     * Gibt PI formatiert in 100er Bloecken zurueck
     */
    public String toString() {
        String piS = pi.toString();
        StringBuffer b = new StringBuffer();
        b.append("3.1");
        for (int i = 1; i < dec; i++) {
            if (i % 100 == 0) {
                b.append("\n  ");
            } else if (i % 10 == 0) {
                b.append(" ");
            }
            b.append(piS.charAt(i + 2));
        }
        return b.toString();
    }

    public static void main(String args[]) {  
        Pi p = new Pi(1000);
        System.out.println(p);
    }
}

Wieviele Threads sind hier sinnvoll?

Vergleich zwischen serieller und paralleler Berechnung:

Zeitmessungen unter Linux auf einem Intel(R) Core(TM) i3-2100 CPU @ 3.10GHz (Quadcore) (Intel(R) Core(TM) i3 CPU 560 @ 3.33GHz) mit 8GB RAM. Daneben wurden eclipse und chrome verwendet.

Stellen	sequentiell	4 Threads
1000	4,395s	2,530s
2000	35,814s	19,260s
3000	126,145s	65,693s
4000	321,916s	163,393s
5000	626,394s	323,876s
6000	1132,480s	568,905s
7000	1800,781s	912,360s
8000	2753,654s	1462,561s
9000	3941,230s	2134,741s
10000	5527,330s	2878,974s

Bei der JVM kann man nicht bestimmen, ob und wie die Threads auf die CPUs (Kerne) aufgeteilt werden sollen. Die JVM und das Betriebssystem bestimmen, wie die Threads auf CPU-Kerne abgebildet werden. Das ist natürlich auch von der allgemeinen Systemlast abhängig.

Die Messungen zeigen, dass sich die Rechenzeit bei 4 Threads halbiert. Die CPU trägt zwar im Namen "Quadcore", tatsächlich ist es aber nur ein Dualcore mit vier Threads (siehe Link oben). Das bedeutet bei dieser Anwendung, dass nur zwei Threads echt parallel laufen können (weiter geteilt mit den anderen Prozessen, die auf dem System laufen).

Labels: algorithmen, Aufgabe, Java, POS1-3

Dies ist eine Mini-Einführung in die O-Notation. Wer es genau wissen will, soll gleich unten bei der Literaturliste bzw. den Links weitermachen.

Die O-Notation (engl. Big O Notation) wird in der Informatik zu Beschreibung der Komplexität (und damit der Laufzeit) eines Algorithmus. Die O-Notation beschreibt den schlechtesten Fall (worst-case scenario). Sie beschreibt die Ausführungszeit oder den Speicheraufwand, den ein Algorithmus benötigt.

Alle, die Programming Pearls (Programming Pearls (ACM Press)) oder irgend ein anderes Informatik Buch lesen und kein fundiertes mathematisches Wissen haben, werden sich den Kopf stoßen, sobald sie Kapitel erreichen, in denen so komische Dinge wie O(N log N) vorkommen. Ich hoffe, dieser Beitrag wird zu einem besseren Verständnis der Grundlagen zur O-Notation verhelfen.

Für Programmierer sind wahrscheinlich kurze Code-Beispiele am Besten geeignet die O-Notation zu verstehen. Die Beispiele zeigen die übliche Reihenfolge der Komplexität, von einfachen bis zu aufwendigen Beispielen.

O(1)

O(1) beschreibt einen Algorithmus, der immer die selbe Zeit (oder den selben Speicher) benötigt, unabhängig von der Größe der Eingabedaten.

boolean isFirstElementNull(String[] strings) {
    if (strings[0] == null) {
        return true;
    }
    return false;
}

Es ist (hoffentlich) offensichtlich, dass diese Funktion immer gleich lange braucht, egal wie groß das String-Array ist (Außer natürlich, wenn strings == null oder strings.length == 0 ist, denn da kommt es zu einer Exception! Diese Sonderfälle lassen wir weg.).

O(N)

O(N) beschreibt Algorithmen, deren Laufzeit linear in direkter Proportionalität zur Größe des Eingabedatensatzes wachsen (z.B. dreimal so große Eingabe bewirkt eine dreimal so lange Laufzeit). Das folgende Beispiel zeigt auch, dass die O-Notation den schlechtesten (worst-case) Fall beschreibt. Die gesuchte Zahl kann natürlich in jedem Schleifendurchlauf gefunden werden und die Funktion frühzeitig beenden, aber die O-Notation beschreibt die obere Grenze, bei der die maximale Anzahl Schleifendurchläufe benötigt wird.

boolean containsValue(int[] values, int value) {
    for (int i = 0; i < values.length; i++) {
        if (value == values[i]) { // always the same time!
            return true;
        }
    }
    return false;
}

O(N²)

O(N²) repräsentiert Algorithmen, deren Laufzeit direkt proportional zum Quadrat der Größe des Eingabedatensatzes sind. Das ist üblicherweise bei verschachtelten Schleifen der Fall. Tiefer verschachtelte Schleifen resultieren demnach in O(N³), O(N⁴) etc.

boolean containsDuplicates(int[] values) {
    for (int i = 0; i < values.length; i++) {
        for (int j = 0; j < values.length; j++) {
            if (i == j) { // don't compare self
                continue;
            }
            if (values[i] == values[j]) {
                return true;
            }
        }
    }
    return false;
}

O(2^N)

O(2^N) beschreibt Algorithmen, deren Laufzeit sich für jedes weitere Element der Eingabedaten verdoppelt. Die Ausführungszeit einer O(2^N) Funktion wird sehr schnell sehr groß. Das folgende Beispiel zeigt einen Algorithmus, der alle möglichen Zeichenfolgen eines Strings liefert (permutiert). Permutationen sind üblicherweise exponentiell (allgemein O(k^N) für ein bestimmtes k).

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutation(prefix + str.charAt(i), 
                str.substring(0, i) + str.substring(i+1, n));
        }
    }
}

Primzahlenbestimmung hat auch exponentiellen Aufwand (O(k^N)).

Logarithmus O(log N)

Ich werde logarithmisches Verhalten an einem üblichen Beispiel erklären:

Denken Sie an ein Telefonbuch, welches Einträge sortiert nach Name, Vorname und Adresse (in dieser Reihenfolge) enthält. Wie würde man die Suche nach der Telefonnummer eines bestimmten Teilnehmers mit gegebenem Namen programmieren? Nehmen wir an, das Telefonbuch hätte 1.000.000 Einträge.

Wenn man linear sucht, dann ist der Aufwand O(N), also maximal 1.000.000 Schleifendurchläufe (im Durchschnitt 500.000). Geschickter ist jedoch die Binäre Suche, bei der man zunächst den 500.000 Eintrag nimmt und prüft. Ist das der gesuchte Name, dann ist man fertig. Ist der gesuchte Name größer (also alphabetisch weiter hinten), dann teilt man die obere Hälfte wieder in zwei Teile und vergleicht mit dem mittleren Eintrag (750.000). Ist der Eintrag nun größer als der gesuchte, dann teilt man die untere Hälfte und nimmt die Mitte ((750.000 - 500.000) / 2 + 500.000 = 625.000) usw. Nach spätestens 20 Teilungen hat man den Namen gefunden (oder er ist nicht im Telefonbuch).

Bei 3 Einträgen benötigt man höchstens 2 Schritte, bei 7 höchstens 3, bei 15 höchstens 4, bei 1000 höchstens 10 und bei 1.000.000 höchstens 20 Schritte.

Der Aufwand ist also O(log N), wobei es egal ist, welche Basis man für den Logarithmus nimmt, weil sich die Logarithmen nur durch Konstante unterscheiden, welche man bei der O-Notation weglassen kann. Die O-Notation gilt nämlich nur für große Werte von N, so dass sich Konstante praktisch nicht mehr auswirken. Die binäre Suche hat eigentlich den Aufwand von log₂ N, welcher sich nur durch den konstanten Wert log 2 (Logarithmus von 2) unterscheidet.

// nums ... sorted array
public static int binarySearch(int[] nums, int check) {
    int hi = nums.length - 1;
    int lo = 0;
    while (hi >= lo) {
        guess = lo + ((hi - lo) / 2);
        if (nums[guess] > check) {
            hi = guess - 1;
        } else if (nums[guess] < check) {
            lo = guess + 1;
        } else {
            return guess;
        }
    }
    return -1;
}

Obiges Beispiel zeigt die binäre Suche mit einem sortierten int-Arrays nums und der zu suchenden Zahl check. Zurückgeliefert wird der Index oder -1, wenn die Zahl nicht in dem Array vorkommt.

Der log N ist die Umkehrung von 10^N und log₂ N die Umkehrung von 2^N.

Es gilt:

O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(N³) < O(k^N)

Quellen

Jon Bentley: Programming Pearls
Binäre Suche (Wikipedia)
Donald E. Knuth: The Art of Computer Programming
BIG-O Notation
Plain English explanation of Big O
Big O, how do you calculate/approximate it?
A Beginner’s Guide to Big O Notation

Labels: algorithmen, Informatik, POS1-2, POS1-3

Zum Testen der Sortierfunktionen aus dem Beispiel IntList benötigt man Testdaten in Form von Listen ganzer Zahlen und zwar aufsteigend sortiert und absteigend sortiert für die Grenzfälle sowie Listen von zufälligen ganzen Zahlen. Weiters ist es sinnvoll, eine Methode zum Feststellen ob ein Array auf- bzw. absteigend sortiert oder gar nicht sortiert ist. Schreiben Sie dazu eine Klasse GenIntArray, die folgende Methoden zur Verfügung stellt:

• GenIntArray() Default-Konstruktor für Arraylänge 10.
• GenIntArray(int size) Konstruktor für Arraylänge size.
• GenIntArray(int size, long seed) Konstruktor für Arraylänge size sowie einem Anfangswert für den Zufallsgenerator (java.util.Random).
• int[] getSortedArray(boolean up) liefert ein sortiertes Array von zufälligen int-Werten. Ist up true, so sollen die Zahle aufsteigend sortiert sein, ansonsten absteigend.
• int[] getArray() liefert ein (unsortiertes) Array von zufälligen int-Werten.
• String sorted(int[] array) prüft, ob das Array sortiert ist und liefert die Strings "up", wenn das Array aufsteigend sortiert ist, "down", wenn das Array absteigend sortiert ist und "unsorted", wenn das Array nicht sortiert ist.

Verwenden Sie diese Klasse um die Sortiermethoden von IntList zu testen.

Labels: algorithmen, Aufgabe, Java, POS1-2

Erstellen Sie ein Java-Programm, welches einfache CSV-Dateien erzeugen, darstellen und ändern kann. Verwenden Sie zur Darstellung der CSV-Datei eine JTable. Beim Neuanlegen wird die Anzahl der Spalten festgelegt. Beim Laden einer CSV-Datei wird die Anzahl der Zeilen/Spalten durch die Datei gegeben. Das Programm soll es ermöglichen, jede Zelle (definiert durch Zeile und Spalte) zu ändern. Sehen Sie eine Möglichkeit zum Einfügen neuer Zeilen vor. Eine markierte Zeile soll gelöscht werden können.

Labels: Aufgabe, GUI, Java, POS1-3, User Interface

Erweitern Sie die Klasse IntList aus dem letzten Beispiel (Liste von ganzen Zahlen (POS1: 2BHIF)) um Sortiermethoden:

1. void sel_sort() ... Sortieren mit Selection Sort.
2. void bubble_sort() ... Sortieren mit Bubble Sort.
3. void ins_sort() ... Sortieren mit Insertion Sort.
4. void sort() ... Sortieren mit der Methode java.util.Arrays.sort() von Java.

Im folgenden finden Sie die Algorithmen in Python formuliert.

Selection Sort

Suche das minimale Element und tausche es mit dem ersten Element. Setze den Algorithmus mit dem Rest der Liste fort (d.h. suche beginnend mit dem 2. Element das Minimum und tausche es mit dem 2. Element), bis das letzte Element erreicht wurde.

def sel_sort(seq):
    """sort the mutable sequence (list) in place with selection sort.
       seq MUST BE A MUTABLE SEQUENCE.
 
       As with list.sort() and random.shuffle this does NOT return 
    """
    for i in range(0, len(seq)-1):
        mn = min(range(i, len(seq)), key=seq.__getitem__) # find minimal item
        seq[i], seq[mn] = seq[mn], seq[i]

Bubble Sort

Gehe alle Elemente der Liste durch und vertausche jeweils zwei benachbarte Elemente, falls das erste der beiden größer als das zweite ist. Setze das ganze fort, bis nicht mehr vertauscht wurde.

def bubble_sort(seq):
    """Inefficiently sort the mutable sequence (list) in place.
       seq MUST BE A MUTABLE SEQUENCE.
 
       As with list.sort() and random.shuffle this does NOT return 
    """
    changed = True
    while changed:
        changed = False
        for i in range(len(seq) - 1):
            if seq[i] > seq[i+1]:
                seq[i], seq[i+1] = seq[i+1], seq[i]
                changed = True

Insertion Sort

Jedes Element wird in den bereits sortierten Bereich an der richtigen Stelle eingefügt. Der verbleibende Rest des sortierten Bereichs wird nach hinten geschoben. Die Stelle, an die ein Element eingefügt werden muss, wird von hinten aus gesucht, damit das Nach-hinten-schieben in der selben Schleife erfolgen kann (sonst hätte man immer zwei Schleifen, eine zum Suchen und eine zweite zum Verschieben).

def ins_sort(seq):
    """Sort the mutable sequence (list) in place with insertion sort.
       seq MUST BE A MUTABLE SEQUENCE.
 
       As with list.sort() and random.shuffle this does NOT return 
    """
    for i in range(1, len(seq)):
        j = i-1 
        key = seq[i]
        while (seq[j] > key) and (j >= 0):
            seq[j+1] = seq[j]
            j -= 1
        seq[j+1] = key

Labels: algorithmen, Aufgabe, Java, POS1-2, Python

Erstellen Sie eine Klasse IntList, welche beliebige viele ganze Zahlen aufnehmen kann.
IntList soll die Zahlen in einem Array der Länge capacity (default: 8) speichern.Sollte beim Aufnehmen einer neuen Zahl (mit add()) die Länge des Arrays überschritten werden, so ist ein neues Array mit der doppelten Größe anzulegen und die Werte des alten Arrays zu übernehmen und dann die neue Zahl aufzunehmen.
IntLIst soll das Interface Comparable implementieren:

public class IntList implements Comparable {
}

Dieses Interface verlangt eine Methode compareTo().

Funktionsweise der Methoden:

Konstruktor IntList(int capacity) legt ein Array der Größe capacity
Konstruktor IntList() legt ein Array der Größe 8
void add(int value) hängt den Wert an. Ist die Kapazität erschöpft, so ist die Größe des internen Arrays zu verdoppeln.
int compareTo(Object other) vergleicht das Objekt mit einem anderen Objekt vom Typ IntList. Dabei liefert die Methode 0, wenn alle Elemente gleich sind, einen Wert kleiner 0, wenn das Objekt vor dem anderen zu "sortieren" ist, also wenn irgend eine Zahl kleiner ist als die entsprechende des anderen Objekts oder wenn das Objekt weniger Zahlen enthält (die aber gleich sind). compareTo() liefert einen Wert größer 0, falls das Objekt nach dem anderen Objekt zu "sortieren" ist.
boolean equals(Object other) liefert true, wenn die Anzahl der Zahlen und die Zahlen selbst identisch sind (oder wenn es sich tatsächlich um das selbe Objekt handelt).
int get(int index) liefert die Zahl an der Stelle index. Es soll IndexOutOfBoundsException geworden werden, falls es sich um einen ungültigen Index handelt (Arraygrenze genügt nicht, die tatsächliche Anzahl der Elemente zählt).
int hashCode() soll einen "eindeutigen" Wert, der vom Inhalt bestimmt wird, zurückliefern.
void set(int index, int value) soll value an der Stelle index setzen. Es soll IndexOutOfBoundsException geworden werden, falls es sich um einen ungültigen Index handelt (Arraygrenze genügt nicht, die tatsächliche Anzahl der Elemente zählt).
int size() liefert die Anzahl der tatsächlich gespeicherten Zahlen.
int[] toArray() liefert ein int-Array mit den gespeicherten Werten. Das Array muss genau so lang sein, als es Zahlen in dem Objekt gibt (vgl. size()).
String toString() liefert alle Zahlen in einem String, der so aussieht: "[1, 23, 99, 0, 12]" oder "[]", falls das Objekt keine Zahl enthält.
void clear() setzt IntList wieder in den Anfangszustand zurück (mindestens die Anzahl der Elemente auf 0 setzen).

Labels: Aufgabe, Java, POS1-2

Erstellen Sie eine Klasse Averager, welche den Durchschnitt beliebig vieler Zahlen berechnen kann:
add() soll eine Zahl aufnehmen
getAverage() liefert den Mittelwert
getSum() liefert die Summe der Zahlen
getNum() liefert die Anzahl der Zahlen
reset() setzt alles zurück, d.h. ab reset() kann ein neuer Mittelwert einer Folge von Zahlen bestimmt werden.

Schreiben Sie eine passende Testklasse.

Labels: Aufgabe, Java, POS1-2