Programmieren mit Harald R. Haberstroh

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

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

1. Untersuchen Sie die Syntax einer Gleitkomma-Konstanten in Java.
2. Konstruieren Sie dazu einen endlichen Automaten, der diese Konstanten akzeptiert.
3. Entwicklen Sie daraus den Minimalautomaten.
4. Ausgehend von diesem Minimalautomaten schreiben Sie ein Programm (Automat mit switch und tabellengesteuerter Automat), das eine Zeichenkette akzeptiert, falls diese eine ganzzahlige Konstante der untersuchten Programmiersprache ist.
5. Testen Sie die Funktionsweise des Automaten (beider Implementierungen) mit Unit-Tests.

double r = 1.e3;
double s = 1.;
double u = 1e3;
double v = +.2;
double w = -.2e-2;
double x = .1;
double y = -.2;
double z = -123.123e-2;

Labels: Aufgabe, Informatik, Java, POS1-3

# Eingestellt von Harald R. Haberstroh @ 17:28 0 Kommentare

ClassFinder

package classfinder;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.LinkedList;

public interface ClassFinder {
 /**
  * finds Classes using the Pattern.
  * 
  * The pattern could be a simple String, i.e. "MyList" which matches all
  * classnames (java-filenames) containing "MyList" (i.e. "ThatMyList",
  * "Mylist", "MylistMaker",...) ignoring case, or it is a pattern like "SCM"
  * (all capital letters) which means names like "SimulateComputerModel",
  * "SCM", "StrCatMaker" and so on.
  * 
  * @param pattern
  * @return List of filenames
  * @throws FileNotFoundException
  * @throws IOException
  */
 public LinkedList<String> findClassFiles(String pattern)
   throws FileNotFoundException, IOException;

 /**
  * finds files containing methods using the Pattern.
  * 
  * The pattern could be a simple String, i.e. "doThis" which matches all
  * classnames (filenames) containing method declarations "doThis" ignoring
  * case, or it is a pattern like "scm" (ignore case) which means methods
  * like "searchClassMembers", "scM", "strCatMerger" and so on. So pattern
  * should be interpreted in both ways.
  * 
  * @param pattern
  * @return List of filenames
  * @throws FileNotFoundException
  * @throws IOException
  */
 public LinkedList<String> findMethodFiles(String pattern)
   throws FileNotFoundException, IOException;
}

MyList

liefert folgende Dateien:

MyList.java
myList.java
ThatMyList.java
MylistMaker.java
    

CF

liefert folgende Dateien:

CF.java
ClassFinder.java
CharacterFixer.java
CharFinderFactory.java
    

doThis

passt zu folgenden Methodennamen:

doThis
dothis
tryToDoThis
doTaskHelpings
    

ScM

passt zu folgenden Methodennamen:

scm
doScm
searchClassMembers
setCornerMarker
    

Testen

Main

hh@knuth:~$ java Finder -c MyList
MyList.java
myList.java
ThatMyList.java
maker/MylistMaker.java
hh@knuth:~$ java Finder -m ScM
MyClass
helpers.Helper
gui.Main
gui.Frame
hh@knuth:~$ java Finder -h
Finder, a java-tool for finding classes and methods.
(c) 2012, Harald R. Haberstroh
hh@knuth:~$

Hinweise

• Verwenden Sie reguläre Ausdrücke zum Suchen (Java ist eine Insel: Reguläre Ausdrücke).
• Testen Sie mit geeigneten Unit-Tests (JUnit 4 Tutorial).

Labels: Aufgabe, Informatik, Java, POS1-3

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

import ctypes # see help(ctypes)

def inc(var):
    """increment var by one"""
    return type(var)(var.value + 1)

def dec(var):
    """decrement var by one"""
    return type(var)(var.value - 1)

if __name__ == '__main__':
    var = ctypes.c_byte(126) # var = 126 - one byte
    var = inc(var)           # var = 127
    print(var.value)
    var = inc(var)           # var = -128 (10000000 binary)
    print(var.value)
    
    var = ctypes.c_byte(-1)  # var = -1 - one byte (11111111 binary)
    var = inc(var)           # var = 0
    print(var.value)

Labels: allgemeines, Informatik, POS1-2, Python

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