Dynamische Programmierung

Irgendwann im Leben, sei es im Studium oder in der aktuellen Lektüre, trifft man auf das Konzept der dynamischen Programmierung. Wikipedia und andere Quellen erklären dieses Konzept mit nicht trivialen Sätzen und bringen die Geschichte dahinter noch mit ein. Da ist dann etwas von Physik(ern) und einer Bellman-Optimierung zu lesen. Das kann alles sehr verwirrend sein. Dabei kann dieses Prinzip der dynamischen Programmierung auch in 10 Minuten verständlich erklärt werden:

Die “dynamische Programmierung” ist ein Konzept, welches auf  Probleme angewendet wird, die sich in kleine Teilprobleme aufspalten lassen. Das bedeutet die Lösung des großen Problems setzt sich aus den kleinen Lösungen unserer Teilprobleme zusammen:

Ein großes und komplexes Problem in kleine Teile auf zu spalten hat den Vorteil, dass diese kleinen Teile leichter zu lösen sind. Durch die vielen Teil-Lösungen kommen wir einfacher zur gesamten Lösung und somit zum Ziel. Wir sparen also beim Computer Rechenzeit. Die CPU wird entlastet. Im Gegenzug müssen wir diese Teil-Lösungen aber auch speichern um diese dann später zusammenfügen zu können. Der RAM (Arbeitspeicher) wird also belastet.

Dynamische Programmierung entlastet die CPU und belastet den RAM.

Hier ein Beispiel dieses Prinzips aus dem Alltag (es hat in diesem Fall nichts mit der Programmierung an sich zu tun):

Wir wollen unseren Kühlschrank wieder mit Nahrungsmitteln auffüllen. Würden wir nicht das Prinzip der “dynamischen Programmierung” kennen, so müssten wir jedes Nahrungsmittel (Milch, Brot, usw.) selbst herstellen. Also die Kuh melken, das Weizen ernten und weiterverarbeiten, usw. Das Kostet Zeit. Bei einem Computer wäre dies die Rechenzeit (betrifft die CPU). Wenn wir alles gemolken und geerntet haben, haben wir nach gefühlten zwei Monaten unseren Kühlschrank wieder gefüllt.

Aber das geht doch sicherlich schneller?! Ja, wir kennen das: Der Supermarkt. Dieser Markt ist ein Ort, wo wir alle unsere Nahrungsmittel finden. Dort kaufen wir sie alle ein (führen sie zusammen) und stellen sie in unseren Kühlschrank. Voilà, unsere Teil-Lösungen haben unser Problem (leerer Kühlschrank) leicht gelöst. Der zeitliche Aufwand dürfte bei höchstens zwei Stunden liegen. Aber es wurde mehr Platz verbraucht. Denn die Nahrungsmittel wurden im Supermarkt “zwischengelagert”.

Dies war ein sehr abstraktes Beispiel. Das Standard-Beispiel in der Programmierung ist die Fibonacci-Folge. Im weiteren Verlauf dieses Artikels wird angenommen, dass dem Leser die Fibonacci-Folge bekannt ist.

In Java kann die Fibonacci-Folge so implementiert werden:

7
8
9
10
11
12
13
14
15
16
17
18

public int fibonacci(int var){
 
    if(var <= 0){
        return 0;
    }
 
    if(var == 1){
        return 1;
    }
 
    return fibonacci(var-1) + fibonacci(var-2);
}

Dies ist eine einfache Umsetzung der Definition für diese Folge. Es gibt noch keine dynamische Programmierung. Wir haben hier die mächtige und zumeist teure Rekursion. Ihr könnt versuchen zu zählen wie oft die CPU eine Addition für fibonacci(100) durchführen muss. Oder lasst euren Rechner fibonacci(1000000) ausrechnen. Erwartet aber bitte kein Ergebnis in diesem Jahr oder Jahrhundert… (kein Scherz!)

Viele werden jetzt (da ja dynamische Programmierung bekannt ist) ein “A-Ha”-Erlebnis haben. Richtig. fibonacci(5) ist doch fibonacci(4) plus fibonacci(3). Das bedeutet, wenn ich ein mal fibonacci(4) und die davor ausgerechnet habe, dann muss ich mir diese Ergebnisse ja nur merken und dann brauch ich keine Rekursion und die Teil-Ergebnisse (Teil-Lösungen) kann ich ganz einfach zusammenführen.

Genau. Wir merken uns einfach die vorherigen Ergebnisse. “Merken” bedeutet, wir speichern diese im Arbeitsspeicher (RAM) ab. Unsere CPU muss nicht mehr so viel Rechnen und wir bekommen ganz schnell ein End-Ergebnis.

Hier mal die Fibonacci-Folge mit dem Prinzip der dynamischen Programmierung:

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public int fibonacci(int var){
 
    //Hier werden alle Teil-Ergebnisse gespeichert (Belastung des RAMs)
    int array[] = new int[var];
 
    for(int i=0;i<var;i++){
        if(i==0){
            array[i] = 0;
        }else if(i==1){
            array[i] = 1;
        }else{
            //Hier führen wir zwei Teil-Ergebnisse zu einem neuen Ergebnis zusammen!
            array[i] = array[i-1] + array[i-2];
        }
    }
 
    //Das End-Ergebnis
    return array(var-1) + array(var-2);
}

Der Code hat sich jetzt leicht verändert. Wir haben keine Rekursion mehr, dafür aber ein Array, welches alle Teil-Ergebnisse enthält. Wir speichern zwar mehr Daten im RAM, dafür ist unsere Berechnung aber um einiges schneller. Wenn wir jetzt fibonacci(1000000) ausrechnen wollen ist der Rechner so schnell fertig… Wir könnten nicht mal bis 3 zählen. (Vorausgesetzt wir haben genügend RAM ) Glückwunsch. Das Prinzip der dynamischen Programmierung wurde erfolgreich umgesetzt.

Wie Viele bemerkt haben ist dieses Konzept sehr effizient. Die Fibonacci-Folge ist nur ein kleines Beispiel. Bei anderen Problemen kann sich diese Art von Programmierung deutlich positiver auswirken. Bei mobilen Geräten (Smartphone etc.) bedeutet eine Belastung der CPU auch eine Belastung des Akkus. Und das möchte niemand!

Damit wäre die “dynamische Programmierung” erklärt. Ich hoffe dieser Artikel konnte dem Ein oder Anderen helfen. Für Alle, die noch Zeit haben: Im folgenden Abschnitt erkläre ich, wie die Verwendung des RAMs verbessert werden kann. Für das Verständnis der dynamischen Programmierung ist dieser Abschnitt nicht relevant.

Optimierung: Verwendung des RAMs

Die CPU konnte jetzt erfolgreich entlastet werden. Aber manchmal haben wir nur einen begrenzten Arbeitsspeicher zur Verfügung. Um so wenig wie möglich und nur so viel wie nötig Speicher zu belegen ist es wichtig zu wissen, welche Teil-Ergebnisse wir uns eigentlich merken müssen. Bei der Fibonacci-Folge, zum Beispiel, genügen eigentlich zwei Ergebnisse: fibonacci(var-1) und fibonacci(var-2).

Ich sage euch nicht warum, ich zeige euch aber dazu den Quellcode (Java). Diesen Schritt sollte jeder selbst erarbeitet haben um das Prinzip der Optimierung zu verstehen.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public int fibonacci(int var){
 
    int varEven = 0;
    int varOdd = 1;
 
    //Abbruchbedingungen
    if(var <= 0){
        return 0;
    }
 
    if(var == 1){
        return 1;
    }
 
    //Schleife, welche die beiden Variablen aktualisiert
    for(int i=2;i<var;i++){
        if(i%2==0){
            varEven = varEven + varOdd;
        }
 
        if(i%2==1){
            varOdd = varEven + varOdd;
        }
    }
 
    //Das End-Ergebnis
    return varEven + varOdd;
}

Diese Optimierung ist nicht ganz trivial, aber immer noch relativ einfach. Das liegt aber hauptsächlich am Fibonacci-Beispiel. In viel komplexeren Problemen kann eine Optimierung der Verwendung des RAMs viel Zeit und Gehirnschmalz verbrauchen.

Als zeitlichen Vergleich könnt ihr die Fibonacci-Folge nehmen. Wie lange habt/hättet ihr gebraucht um diese zu Programmieren (mit Rekursion) ? Zwei Minuten? Und mit dynamischer Programmierung? 4 Minuten? Und jetzt werdet euch klar, wie lange ihr für die Optimierung der RAM-Verwendung gebraucht habt (Und sie zu verstehen). Übertragt mal diese Zeiten auf große Projekte (Probleme). Es ist jetzt zwar nur eine kleine Spinnerei aber ihr dürft ruhig Annehmen, dass diese Optimierung geistig sehr Aufwändig ist.

Wir sind nun am wirklichen Ende dieses Artikels. Anmerkungen und Kommentare sind gern gesehen.

Informatik: Was ist das?

“Du bist doch Informatiker. Dann kannst du mir doch meinen PC einrichten und Microsoft Office installieren.” - Ja natürlich! Aber das kann jedes 14 jährige, technikbegeisterte Kind auch!

Leider gibt es viele Menschen die immer noch ein falsches Bild vom Beruf “Informatiker” beziehungsweise von der Informatik haben. Dieser Artikel soll einen Überblick über die Tätigkeiten und das Aufgabenfeld eines Informatikers und den Bereich der Informatik schaffen.

Die Informatik:

Grundlegend beschäftigt sich die Informatik mit “Information” und “Automatisierung”. Diese beiden Begriffe stecken im Wort: Informatik. Die automatische Verarbeitung von Information. Korrekt wäre aber eher:

Die automatische Verarbeitung und Interpretation von Daten.

Diese Definition ist grob und deckt somit einen weiten Bereich in unserem Leben oder Alltag ab. Sei es der Fernseher, der ein Signal verarbeitet und als Bild darstellt oder der elektronische Wecker. Auch ein PC gehört natürlich dazu und alles was auf die obige Definition zutrifft.

Der Begriff Informatik ist nun erklärt. Jetzt könnte die Frage aufkommen, welche Menschen diese Geräte entwickeln, bauen oder herstellen und vor allen Dingen: Welche Menschen sorgen dafür, dass diese Geräte auch das machen, was sie machen sollen?

Der Informatiker / Die Informatikerin:

Informatiker sind genau diese Menschen. Sie entwickeln Maschinen und programmieren diese. Sie entwickeln neue Strategien und Wege um Maschinen oder Prozesse effizienter zu machen und sie versuchen Probleme der Informatik zu lösen. Der Informatiker entwickelt also im Grunde Maschinen oder Programme, die den Alltag des Menschen erleichtern. Natürlich nur im Bezug auf die Verarbeitung von Information.

Eine Maschine zu bauen macht aus einem Menschen also noch keinen Informatiker. Die Maschine dann so zu programmieren, dass diese automatisch eine Aufgabe verrichtet, ist der Knackpunkt.

Eine Maschine zu programmieren bedeutet im entfernteren Sinn, dass der Maschine “beigebracht” oder “gesagt” wird, was sie machen soll.

Ein metaphorisches Beispiel:

Wir haben eine Küche mit einem Koch. Der Koch kann mit der Küche und einem Rezept ein Gericht zubereiten. Das klingt ziemlich einfach, denn jeder hat schon ein mal ein Gericht unter Anleitung (Rezept) zubereitet. Aber wer hat das Rezept geschrieben? Und viel wichtiger: Wer hat das Rezept so geschrieben, dass der Koch es versteht und danach kochen kann? In diesem Fall war es wohl ein anderer Koch.

Nehmen wir an die Küche mit Koch wäre eine programmierbare Maschine. Das bedeutet, dass diese Maschine bestimmte Anweisungen (Befehle) versteht. Und das Rezept ist eine Folge von Befehlen. Die Maschine führt jeden Befehl der Reihe nach aus und am Ende ist das Ergebnis ein leckeres fünf Gänge Menü. Das Rezept zu schreiben ist das eigentliche Programmieren.

Wir sagen also dem Koch bzw. der Maschine was sie machen soll und das ist schon alles? Jein. Ein Rezept für einen Koch zu schreiben ist relativ einfach. Der Koch ist ein Mensch. Er ist intelligent. Er erkennt Fehler und korrigiert sie. Eine Maschine ist dumm. Sie führt jeden Befehl korrekt aus. Auch wenn der Befehl ist: “Alufolie in der Mikrowelle zwei Minuten erhitzen”. Dem Koch können wir sagen: “Der Kuchenteig muss eine Stunde bei 200 °C in den Ofen”. Der Maschine müssen wir erst ein mal befehlen, die Ofentür auf zu machen, etc.

Der Bereich Programmierung ist komplex und bedarf eines eigenen Artikels. Hier sollte nur kurz gezeigt werden, was programmieren im eigentlichen Sinn ist.

Für einen Informatiker ist die Programmierung von zentraler Bedeutung. Jeder Informatiker kann programmieren.

Informatiker sind aber auch bemüht bestehende Maschinen und Programme zu verbessern. Sie entwickeln neue Verfahren (Vorgehensweisen) um Probleme zu lösen. Dieser Bereich wird oft auch von Mathematikern übernommen. Informatik hat sehr viel mit Mathematik zu tun. Das geht aber jetzt zu weit in den theoretischen Part der Informatik.

Für Alle die bis hierhin gelesen haben: Vielen Dank! Dieser Artikel soll die zum Teil falsche Auffassung des Informatikers bei einigen Menschen revidieren. Informatiker sind KEINE Nerds, Freaks oder komische Gestalten. Sie sind keine Hacker und sind keine Microsoft Office Experten.