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

# Eingestellt von Harald R. Haberstroh @ 11:54 0 Kommentare

Das ist die erste Zeile und
das ist die zweite Zeile und
hier folgt die dritte Zeile.
Satzzeichen gelten als Trenner.
Folgendes ist kein W0rt und das
4uch nicht.

als 1
Das 3
die 3
dritte 1
erste 1
Folgendes 1
folgt 1
gelten 1
hier 1
ist 3
kein 1
nicht 1
Satzzeichen 1
Trenner 1
und 3
Zeile 3
zweite 1

Labels: algorithmen, Aufgabe, Java, POS1-2

# Eingestellt von Harald R. Haberstroh @ 09:56 0 Kommentare

KLASSE und GESCHL

java Grw [-h | -o ausgabedat] [-d] eingabedatei

------------------------------------------------------------------
STATISTIK zum Schuelerrennen der HTL am SKIKURS 2006 in OBERTAUERN
------------------------------------------------------------------

AMINGER                   Georg                            0.02
ELIAS                     Thomas                           0.97
GALAVICS                  Marcus                           0.15
GALLAUNER                 Alexander                        0.26
HECHER                    Markus                           0.58
HERMANN                   Gregor                           0.65
KAMPER                    Raphael                          0.55
KRIVOKUCA                 Milan                            7.73
MOSER                     Christoph                        2.34
NEPOLA                    René                             0.14
PRIELER                   Stefan                           0.63
RECHBERGER                Christian                        3.11
RIEGLER                   Mario                            0.87
SCHNEEBERGER              Joerg                            1.22
SENN                      Bernhard                         0.65
WIESSNER                  Maximilian                       1.61
ZENZ                      Markus                           2.04

die durchschnittliche Zeitdifferenz bei den MAENNERN betraegt:  1.38

die KLASSE 2AHDV   erreichte eine Durchschnittsdifferenz von  1.38 Sekunden


CMUND                     Katharina                        2.81
HARATHER                  Alice                            1.87
KONLECHNER                Viktoria                         0.39
RIEGER                    Jennifer                         0.63
RINNHOFER                 Elisabeth                        1.65
...........................................................

...........................................................
REICHHART                 Thomas                           0.30
RIEDER                    Dominik                          1.07
SCHERMANN                 Georg                            0.85
STANGL                    Stefan                           1.48
STAUFER                   Andreas                          0.47

die durchschnittliche Zeitdifferenz bei den MAENNERN betraegt:  2.38

die KLASSE 3CHDV   erreichte eine Durchschnittsdifferenz von  2.36 Sekunden
************************************************GESAMT-Differenz :  1.93

Binäres Dateiformat für Eingabe

typedef struct umsatz {
    char artikel[25];
    char verkaeufer[25];
    int  vkpreis;
    int  monat; 
} umsatz_t;

hp@L211 $ hexdump -C daten.dat 
00000000  50 72 6f 64 30 31 00 01  4c 00 ba 01 e5 e2 e6 b7  |Prod01..L.......|
00000010  00 00 00 00 e4 98 04 08  28 4d 61 69 65 72 00 08  |........(Maier..|
00000020  a0 fc f5 b7 dc e9 b9 bf  48 e9 b9 bf f1 86 04 08  |........H.......|
00000030  90 8b f8 b7 dc 00 00 00  01 00 00 00 50 72 6f 64  |............Prod|
00000040  30 32 00 01 4c 00 ba 01  e5 e2 e6 b7 00 00 00 00  |02..L...........|
00000050  e4 98 04 08 28 4d 61 69  65 72 00 08 a0 fc f5 b7  |....(Maier......|
00000060  dc e9 b9 bf 48 e9 b9 bf  f1 86 04 08 90 8b f8 b7  |....H...........|
00000070  90 01 00 00 02 00 00 00  50 72 6f 64 30 33 00 01  |........Prod03..|
00000080  4c 00 ba 01 e5 e2 e6 b7  00 00 00 00 e4 98 04 08  |L...............|
00000090  28 48 75 62 65 72 00 08  a0 fc f5 b7 dc e9 b9 bf  |(Huber..........|

Labels: algorithmen, Aufgabe, Java, POS1-2

# Eingestellt von Harald R. Haberstroh @ 09:48 0 Kommentare

KLASSE und GESCHL

java Grw [-h | -o ausgabedat] [-d] eingabedatei

------------------------------------------------------------------
STATISTIK zum Schuelerrennen der HTL am SKIKURS 2006 in OBERTAUERN
------------------------------------------------------------------

AMINGER                   Georg                            0.02
ELIAS                     Thomas                           0.97
GALAVICS                  Marcus                           0.15
GALLAUNER                 Alexander                        0.26
HECHER                    Markus                           0.58
HERMANN                   Gregor                           0.65
KAMPER                    Raphael                          0.55
KRIVOKUCA                 Milan                            7.73
MOSER                     Christoph                        2.34
NEPOLA                    René                             0.14
PRIELER                   Stefan                           0.63
RECHBERGER                Christian                        3.11
RIEGLER                   Mario                            0.87
SCHNEEBERGER              Joerg                            1.22
SENN                      Bernhard                         0.65
WIESSNER                  Maximilian                       1.61
ZENZ                      Markus                           2.04

die durchschnittliche Zeitdifferenz bei den MAENNERN betraegt:  1.38

die KLASSE 2AHDV   erreichte eine Durchschnittsdifferenz von  1.38 Sekunden


CMUND                     Katharina                        2.81
HARATHER                  Alice                            1.87
KONLECHNER                Viktoria                         0.39
RIEGER                    Jennifer                         0.63
RINNHOFER                 Elisabeth                        1.65
...........................................................

...........................................................
REICHHART                 Thomas                           0.30
RIEDER                    Dominik                          1.07
SCHERMANN                 Georg                            0.85
STANGL                    Stefan                           1.48
STAUFER                   Andreas                          0.47

die durchschnittliche Zeitdifferenz bei den MAENNERN betraegt:  2.38

die KLASSE 3CHDV   erreichte eine Durchschnittsdifferenz von  2.36 Sekunden
************************************************GESAMT-Differenz :  1.93

Binäres Dateiformat für Eingabe

typedef struct umsatz {
    char artikel[25];
    char verkaeufer[25];
    int  vkpreis;
    int  monat; 
} umsatz_t;

hp@L211 $ hexdump -C daten.dat 
00000000  50 72 6f 64 30 31 00 01  4c 00 ba 01 e5 e2 e6 b7  |Prod01..L.......|
00000010  00 00 00 00 e4 98 04 08  28 4d 61 69 65 72 00 08  |........(Maier..|
00000020  a0 fc f5 b7 dc e9 b9 bf  48 e9 b9 bf f1 86 04 08  |........H.......|
00000030  90 8b f8 b7 dc 00 00 00  01 00 00 00 50 72 6f 64  |............Prod|
00000040  30 32 00 01 4c 00 ba 01  e5 e2 e6 b7 00 00 00 00  |02..L...........|
00000050  e4 98 04 08 28 4d 61 69  65 72 00 08 a0 fc f5 b7  |....(Maier......|
00000060  dc e9 b9 bf 48 e9 b9 bf  f1 86 04 08 90 8b f8 b7  |....H...........|
00000070  90 01 00 00 02 00 00 00  50 72 6f 64 30 33 00 01  |........Prod03..|
00000080  4c 00 ba 01 e5 e2 e6 b7  00 00 00 00 e4 98 04 08  |L...............|
00000090  28 48 75 62 65 72 00 08  a0 fc f5 b7 dc e9 b9 bf  |(Huber..........|

Labels: algorithmen, Aufgabe, Java, POS1-2

# Eingestellt von Harald R. Haberstroh @ 11:43 0 Kommentare

Implementieren Sie in einem Paket recursion Klassen mit Testmethoden für folgende Aufgabenstellungen:

1. Fakultät: 0! = 1, 1! = 1, n! = n * (n -1)
2. Fibonaccizahlen: fib(0) = 0, fib(1) = 1, fib(n) = fib(n - 1) + fib(n - 2)
3. McCarthys 91: f(n) = n-10, wenn n > 100 bzw. f(f(n+11)) für allen anderen n.
4. Bestimmen Sie ob eine Zahl gerade oder ungerade ist, in dem Sie zwei indierekt rekursive Funkionen boolean istUngerade(int n) und boolean istGerade(int n) verwenden.
5. Implementieren Sie den Euklidischen Algorithmus zum Finden des größten gemeinsamen Teilers zweier Zahlen.

Floodfill

Aus Wikipedia: Floodfill bzw. Flutfüllung ist ein Begriff aus der Computergrafik. Es ist ein einfacher Algorithmus, um Flächen zusammenhängender Pixel einer Farbe in einem digitalen Bild zu erfassen und mit einer neuen Farbe zu füllen.

Ausgehend von einem Pixel innerhalb der Fläche werden jeweils dessen Nachbarpixel darauf getestet, ob diese Nachbarpixel auch die alte Farbe enthalten. Jedes gefundene Pixel mit der alten Farbe wird dabei sofort durch die neue Farbe ersetzt.
Zwei Varianten des Algorithmus sind gängig:

1. Es werden jeweils die vier benachbarten Pixel oben, unten, links und rechts vom Ausgangspunkt untersucht.
   
2. Es werden jeweils die acht benachbarten Pixel oben, unten, links, rechts, oben-links, oben-rechts, unten-links und unten-rechts vom Ausgangspunkt untersucht.
   

Legen Sie ein neues Package floodfill an und Erstellen Sie die beiden Klassen Grafik und Logik mit dem unten angegebenen Source-Code (Dank an W. Schermann).

• floodfill.Grafik.java (enthält die Grafik-Funktionen und main())
• floodfill.Logik.java (enthält die Logik, sie müssen die Methode run() erweitern)

Speichern Sie die folgenden beiden Bilder in einem Ordner images im Ordner des Projektes.

Implementieren Sie in der Logik eine rekursive Funktion zum Füllen eines Bildabschnittes (In 4 Richtungen und alternativ in 8 Richtungen). Rufen Sie die rekursive Funktion aus der Funktion run aus auf. Sie können folgende Funktionen der Grafik-Klasse verwenden.

public Color getColor(int x, int y) //Bildfarbe abfragen
public void setColor(int x, int y, Color c) //Bildfarbe ändern

Der Algorithmus ist hoch-rekursiv. Daher besteht ein hohes Risiko, dass der Algorithmus zu einem Stack-Überlauf führt. (Z.B. beim Hintergrund)

Um die Übung ohne trotzdem komplett testen zu können kann die Stack-Größe in Java verändert werden. In Eclipse kann dies bei den Argumenten der Virtual-Machine in den Run-Konfigurationen eingestellt werden. Mit -Xss5M wird der Stack-Speicher auf 5 Megabyte gesetzt.

Beachten Sie die eventuellen "Fehler" beim Füllen mit dem Algorithmus für 8 benachbarte Pixel.

Labels: algorithmen, Aufgabe, Java, POS1-2

# Eingestellt von Harald R. Haberstroh @ 11:42 0 Kommentare

Installieren Sie OpenCV für C# nach der Anleitung in dem Tutorial OpenCV tutorial 5: Emgu CV with C#.

Tatsächlich wird in diesem Tutorial Emgu CV installiert, ein .Net-Wrapper für diese Bibliothek.

Im Tutorial wird gezeigt, wie Visual Studio für die Verwendung von OpenCV eingerichtet werden muss. Als Beispielanwendung wird eine "Ball-Erkennung" programmiert.

Probleme gibt es eventuell mit der Kamera bzw. eigentlich mit dem Treiber der Kamera. Im Installationsverzeichnis von Emgu CV gibt es aber weitere Beispiele, bei denen die Kamera auch funktioniert.

Aufgabe:

1. Bringen Sie eine Gesichtserkennung mit OpenCV unter C# zum Laufen.
2. Finden Sie heraus, wie so eine Gesichtserkennung funktioniert.

Labels: algorithmen, C#, POS1-4

# Eingestellt von Harald R. Haberstroh @ 10:16 0 Kommentare

Anforderungen

1. Anlegen von Knoten - Knoten sollen durch einfachen Klick auf die leere Zeichenfläche angelegt werden. Die Beschriftung soll automatisch erfolgen (A, B, C, ...). Die Knoten dürfen sich nicht überlappen.
2. Anlegen von gerichteten Kanten - durch Ziehen mit der rechten Maustaste soll eine Kante von einem Knoten zu einem anderen Knoten gezeichnet werden können (gerade Linie mit Pfeilspitze). Alternativ kann die linke Maustaste mit gedrückter Strg-Taste verwendet werden.
3. Die Gewichtung einer Kante soll eingegeben werden können.
4. Die Gewichtung einer Kante soll geändert werden können.
5. Knoten sollen durch ziehen verschoben werden können (linke Maustaste), die Kanten von/zu diesem Knoten müssen entsprechend neu gezeichnet werden können. Die Knoten dürfen sich nicht überlappen!
6. Knoten sollen (de-)selektiert/markiert werden können (Mausklick). Markierung/Selektion soll umgeschaltet werden (toggle).
7. Kanten sollen (de-)selektiert/markiert werden können (Mausklick). Markierung/Selektion soll umgeschaltet werden (toggle).
8. Markierte Elemente sollen gelöscht werden können (Menüpunkt, Shortcut Entf).
9. Ein Graph soll in einer Datei gespeichert werden können.
10. Ein Graph soll aus einer Datei geladen werden können.
11. Die Zeichenfläche soll gelöscht werden können.
12. Im Hilfemenü soll eine Infobox mit Ihrem Namen, der Klasse und dem Erstellungsjahr aufgerufen werden können.
13. Optional: Eine Hilfe zur Bedienung (Dialogfenster mit HTML-Text).
14. Optional: Die Sprache soll geändert werden können (Englisch, Deutsch, weitere mit Sprachdateien). Standard ist die Systemeinstellung.
15. Scrollbars sollen eingeblendet werden, wenn das Fenster kleiner als die benötigte Zeichenfläche ist.
16. Ein Graph soll gedruckt werden können. Gegebenenfalls auf eine Seite skalieren.
17. Simulation der Tiefensuche - Ist ein Knoten markiert, so soll die Tiefensuche beginnend nur mit diesem Knoten durchgeführt werden und die einzelnen Schritte dargestellt werden (weiß/grau/schwarz). Ist kein Knoten markiert, so soll der Algorithmus auf alle Knoten angewendet werden.
    Verwenden Sie dazu einen Thread.
18. Simulation der Breitensuche - Ist ein Knoten markiert, so soll die Breitensuche beginnend nur mit diesem Knoten durchgeführt werden und die einzelnen Schritte dargestellt werden (weiß/grau/schwarz). Ist kein Knoten markiert, so soll der Algorithmus auf alle Knoten angewendet werden.
    Verwenden Sie dazu einen Thread.
19. Optional: Die Simulation(en) sollen abgebrochen werden können.
20. Optional: Es soll eine undo/redo-Funktionalität implementiert werden (Command Pattern).
21. Das Programm soll als "ausführbare" Jar-Datei geliefert werden, d.h. alle nötigen Klassen, Bibliotheken, Grafiken und Konfigurationsdateien (Sprachdateien) sollen sich in dem Jar-Archiv befinden. Aufruf soll nur über java -jar graph.jar möglich sein (meist kann man die graphische Oberfläche so einstellen, dass ein Klick auf die Datei genügt).

Links

• Graphen und Graphenalgorithmen
• Graphentheorie (Wikipedia)
• Tiefensuche (Wikipedia)
• Breitensuche (Wikipedia)
• Command Pattern (Wikipedia)

Literatur

• Robert Sedgewick; Kevin Wayne: Algorithms, Fourth Edition (Addison-Wesley Professional)
  
  
• Gunter Saake; Kai-Uwe Sattler: Algorithmen und Datenstrukturen, 4th Edition (dpunkt)
  
  
• Eric Freeman; Elisaebth Freeman; Kathy Sierra; Bert Bates: Entwurfsmuster von Kopf bis Fuß (O'Reilly Verlag)
  
  

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

# Eingestellt von Harald R. Haberstroh @ 10:45 0 Kommentare

KLASSE und GESCHL

java Grw [-h | -o ausgabedat] [-d] eingabedatei

------------------------------------------------------------------
STATISTIK zum Schuelerrennen der HTL am SKIKURS 2006 in OBERTAUERN
------------------------------------------------------------------

AMINGER                   Georg                            0.02
ELIAS                     Thomas                           0.97
GALAVICS                  Marcus                           0.15
GALLAUNER                 Alexander                        0.26
HECHER                    Markus                           0.58
HERMANN                   Gregor                           0.65
KAMPER                    Raphael                          0.55
KRIVOKUCA                 Milan                            7.73
MOSER                     Christoph                        2.34
NEPOLA                    René                             0.14
PRIELER                   Stefan                           0.63
RECHBERGER                Christian                        3.11
RIEGLER                   Mario                            0.87
SCHNEEBERGER              Joerg                            1.22
SENN                      Bernhard                         0.65
WIESSNER                  Maximilian                       1.61
ZENZ                      Markus                           2.04

die durchschnittliche Zeitdifferenz bei den MAENNERN betraegt:  1.38

die KLASSE 2AHDV   erreichte eine Durchschnittsdifferenz von  1.38 Sekunden


CMUND                     Katharina                        2.81
HARATHER                  Alice                            1.87
KONLECHNER                Viktoria                         0.39
RIEGER                    Jennifer                         0.63
RINNHOFER                 Elisabeth                        1.65
...........................................................

...........................................................
REICHHART                 Thomas                           0.30
RIEDER                    Dominik                          1.07
SCHERMANN                 Georg                            0.85
STANGL                    Stefan                           1.48
STAUFER                   Andreas                          0.47

die durchschnittliche Zeitdifferenz bei den MAENNERN betraegt:  2.38

die KLASSE 3CHDV   erreichte eine Durchschnittsdifferenz von  2.36 Sekunden
************************************************GESAMT-Differenz :  1.93

Binäres Dateiformat für Eingabe

typedef struct umsatz {
    char artikel[25];
    char verkaeufer[25];
    int  vkpreis;
    int  monat; 
} umsatz_t;

hp@L211 $ hexdump -C daten.dat 
00000000  50 72 6f 64 30 31 00 01  4c 00 ba 01 e5 e2 e6 b7  |Prod01..L.......|
00000010  00 00 00 00 e4 98 04 08  28 4d 61 69 65 72 00 08  |........(Maier..|
00000020  a0 fc f5 b7 dc e9 b9 bf  48 e9 b9 bf f1 86 04 08  |........H.......|
00000030  90 8b f8 b7 dc 00 00 00  01 00 00 00 50 72 6f 64  |............Prod|
00000040  30 32 00 01 4c 00 ba 01  e5 e2 e6 b7 00 00 00 00  |02..L...........|
00000050  e4 98 04 08 28 4d 61 69  65 72 00 08 a0 fc f5 b7  |....(Maier......|
00000060  dc e9 b9 bf 48 e9 b9 bf  f1 86 04 08 90 8b f8 b7  |....H...........|
00000070  90 01 00 00 02 00 00 00  50 72 6f 64 30 33 00 01  |........Prod03..|
00000080  4c 00 ba 01 e5 e2 e6 b7  00 00 00 00 e4 98 04 08  |L...............|
00000090  28 48 75 62 65 72 00 08  a0 fc f5 b7 dc e9 b9 bf  |(Huber..........|

Labels: algorithmen, Aufgabe, Java, POS1-2

# Eingestellt von Harald R. Haberstroh @ 09:38 0 Kommentare

Implementieren Sie in Java eine Simulation des Philosophenproblems (Aufgabenstellung über den Link).

Zeigen Sie das Auftreten eines Deadlocks.

Entwickeln Sie eine Lösung ohne Deadlock.

Labels: algorithmen, Aufgabe, Informatik, Java, POS1-3

# Eingestellt von Harald R. Haberstroh @ 09:01 0 Kommentare

π 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

# Eingestellt von Harald R. Haberstroh @ 22:45 0 Kommentare

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

# Eingestellt von Harald R. Haberstroh @ 19:44 0 Kommentare

• 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.

Labels: algorithmen, Aufgabe, Java, POS1-2

# Eingestellt von Harald R. Haberstroh @ 13:45 0 Kommentare

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.

Selection Sort

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

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

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

# Eingestellt von Harald R. Haberstroh @ 14:16 0 Kommentare