Praktische Informatik 1

2.3 Darstellung von Algorithmen

Ein Algorithmus ist ein präzises, schrittweises und endliches Verfahren zur Lösung eines Problems oder einer Aufgabenstellung (insbesondere zur Verarbeitung von Informationen, vgl. Kap. 0). Das bedeutet, an einen Algorithmus sind folgende Anforderungen zu stellen:

• 
  Präzise Beschreibung (relativ zu den Kommunikationspartnern) der zu bearbeitenden Informationen und ihrer Repräsentation
  
• 
  Explizite, eindeutige und detaillierte Beschreibung der einzelnen Schritte (relativ zu der Person oder Maschine, die den Algorithmus ausführen soll)
  
• 
  Endliche Aufschreibung des Algorithmus, jeder Einzelschritt ist in endlicher Zeit effektiv ausführbar, und jedes Ergebnis wird nach endlich vielen Schritten erzielt.
  

Um Algorithmen von einem Computer ausführen zu lassen, müssen sie (genau wie andere Informationen) in einer für die jeweilige Maschine verständlichen Form repräsentiert werden. Eine solche Repräsentation nennt man Programm. Zum Beispiel kann das eine Folge von Maschinenbefehlen sein, die ein bestimmter Rechner ausführen kann. Die tatsächliche Ausführung eines Algorithmus bzw. Programms nennt man einen Prozess. Sie findet auf einem (menschlichen oder maschinellen) Prozessor statt. Ein Algorithmus bzw. Programm terminiert, wenn seine Ausführung nach einer endlichen Zahl von Schritten (Befehlen) abbricht. Ein Algorithmus (bzw. ein Programm) heißt deterministisch, wenn für jeden Schritt der nächste auszuführende Schritt eindeutig definiert ist. Er bzw. es heißt determiniert, wenn die Berechnung nur ein mögliches Ergebnis hat.
Beispiel: Wechselgeldbestimmung (nach Kröger / Hölzl / Hacklinger)

Aufgabe: Bestimmung des Wechselgeldes w eines Fahrscheinautomaten auf 5 Euro bei einem Preis von p Euro (zur Vereinfachung fordern wir, p sei ganzzahliges Vielfaches von 10 Cent; es werden nur 10-, 20- und 50-Cent Münzen zurückgegeben).

Der Algorithmus ist nicht determiniert! Damit das Ergebnis eindeutig bestimmt ist, legen wir zusätzlich fest: „es sollen möglichst wenige Münzen zurückgegeben werden“.

Als erstes muss die Repräsentation der Schnittstellen festgelegt werden: p könnte zum Beispiel als natürliche Zahl in Cent, als rationale Zahl oder als Tupel (Euro, Cent) repräsentiert werden, und w als Multimenge oder Folge von Münzen. Dann erfolgt die Aufschreibung des Algorithmus.
1. Darstellung in natürlicher Sprache: „Die Rückgabe enthält maximal eine 10-Cent-Münze, zwei 20-Cent-Münzen, und den Rest in 50-Cent-Münzen. 10-Cent werden zurückgegeben, falls dies nötig ist, um im Nachkommabereich auf 0, 30, 50, oder 80 Cent zu kommen. Eine oder zwei 20-Cent-Münzen werden zurückgegeben, um auf 0, 40, 50 oder 90 Cent zu kommen. Wenn der Nachkommaanteil 0 oder 50 ist, werden nur 50-Cent-Münzen zurückgegeben.“
Ein Vorteil der natürlichen Sprache ist, dass sie sehr flexibel ist und man damit (fast) alle möglichen Ideen aufschreiben kann. Nachteile bei der Darstellung von Algorithmen in natürlicher Sprache sind, dass keine vollständige formale Syntax bekannt ist, d.h. es ist nicht immer leicht festzustellen, ob eine Beschreibung syntaktisch korrekt ist oder nicht, und dass die Semantik weitgehend der Intuition überlassen bleibt. Dadurch bleibt immer eine gewisse Interpretationsfreiheit, verschiedene Prozessoren können zu verschiedenen Ergebnissen gelangen.
2. Darstellung als nichtdeterministischer Pseudo-Code:

Sei w={} Multimenge;

Solange p<5 tue

1. 
   erste Nachkommastelle von p {2,4,7,9}:
   p = p + 0.10, w = w  {10c}
   
2. 
   erste Nachkommastelle von p {1,2,3,6,7,8}:
   p = p + 0.20, w = w  {20c}
   
3. 
   erste Nachkommastelle von p {0,1,2,3,4,5}:
   p = p + 0.50, w = w  {50c}
   

Ergebnis w
Auch Pseudo-Code verwendet keine feste Syntax, es dürfen jedoch nur solche Sprachelemente verwendet werden, deren Bedeutung (Semantik) klar definiert ist. Damit ist die Menge der möglichen Ergebnisse zu einer Eingabe eindeutig bestimmt.
Berechnungsbeispiel:

p=3.20, w={}  p=3.70, w={50c}  p=3.80, w={50c, 10c}  p=4.00, w={50c, 10c, 20c}  p=4.50, w={50c, 10c, 20c, 50c}  p=5.00, w={50c, 10c, 20c, 50c, 50c}
3. Darstellung mathematisch-rekursiv:
 {}, falls p=5



 0,50+Wechselgeld (p+0.50), falls p5 und 5-p  0.50

Wechselgeld (p) = 

 0,20+Wechselgeld (p+0.20), falls p5, 5-p < 0.50 und 5-p  0.20



 0,10+Wechselgeld (p+0.10), sonst

Beispiel zum Berechnungsablauf:

Wechselgeld(3.20) =0.50+Wechselgeld(3.70) =0.50+0.50+Wechselgeld(4.20) =0.50+0.50+0.50+Wechselgeld(4.70) =0.50+0.50+0.50+0.20+Wechselgeld(4.90) =0.50+0.50+0.50+0.20+0.10+Wechselgeld(5.00) =0.50+0.50+0.50+0.20+0.10

Die Syntax und Semantik in dieser Aufschreibung folgt den üblichen Regeln der Mathematik bzw. Logik, ist fest definiert, aber jederzeit erweiterbar. In der Schreibweise der Informatik könnte man dasselbe etwa wie folgt aufschreiben:
Wechselgeld (p) =

Falls 5-p=0 dann Rückgabe({}) sonst

falls 5-p  0.50 dann Rückgabe(0.50+Wechselgeld(p+0.50)) sonst

falls 5-p  0.20 dann Rückgabe(0.20+Wechselgeld(p+0.20)) sonst

Rückgabe(0.10+Wechselgeld(p+0.10))

Diese Notation lässt sich unmittelbar in funktionale Programmiersprachen übertragen. Als Groovy--Programm aufgeschrieben sieht das etwa so aus:
int wg(p){

if (5-p==0) return(0) else

if (5-p>=0.50) return(100+wg(p+0.50)) else

if (5-p>=0.20) return(10+wg(p+0.20)) else

return(1+wg(p+0.10))}
Hier wählen wir zur Darstellung des Ergebnisses eine dreistellige natürliche Zahl, deren erste Stelle die Anzahl der 50-Cent-Münzen, die zweite die Anzahl der 20-Cent-Münzen und die letzte die Anzahl der 10-Cent-Münzen angibt.
wg(2.70)

411

wg(3.10)

320
Eine andere Form der Ergebnisdarstellung (Multimenge!) wäre etwa als Liste:

def wg(p){

if (5-p==0) return([]) else

if (5-p>=0.50) return([50] + wg(p+0.50)) else

if (5-p>=0.20) return([20] + wg(p+0.20)) else

return([10] + wg(p+0.10))}

assert wg(2.70) == [50, 50, 50, 50, 20, 10]

4. Darstellung als Ablaufdiagramm oder Flussdiagramm.

Ein Ablaufdiagramm ist prinzipiell ein endlicher Automat! Zusätzlich dürfen jedoch Variablen, Bedingungen, Zuweisungen, Unterprogramme und andere Erweiterungen verwendet werden.
Ausführungsbeispiel:

p=3.20, w={}  p=3.30, w={10c}  p=3.50, w={10c, 20c}  p=4.00, w={10c, 20c, 50c}  p=4.50, w={10c, 20c, 50c, 50c}  p=5.00, w={10c, 20c, 50c, 50c, 50c}
5. Darstellung als Groovy- oder Java-Programm (mit heftigem Gebrauch von Mathematik)

Groovy:

int fuenfzigCentStuecke(float p) {

((5 - p) * 10 / 5)}

int zehnCentStuecke(float p) {

int cent = (p-(int)(p)) * 100

cent in [20, 40, 70, 90] ? 1 : 0}

int zwanzigCentStuecke(float p) {

int tencent = ((p-(int)(p)) * 10)

coins = [0,2,1,1,0,0,2,1,1,0]

coins[tencent]}
Java:

static int fünfzigCentStücke(double p) {

return (int)((5 - p) * 10 / 5) ;}

static int zehnCentStücke(double p) {

int cent = (int)((p-(int)(p)) * 100);

return((cent==20 || cent==40 || cent==70 || cent==90) ? 1 : 0) ;}

static int zwanzigCentStücke(double p) {

int tencent = (int)((p-(int)(p)) * 10);

int[] coins = {0,2,1,1,0,0,2,1,1,0};

return coins[tencent] ;}
Syntax und Semantik sind eindeutig definiert, jedes in einer Programmiersprache aufschreibbare Programm ist normalerweise determiniert und deterministisch (Ausnahme: Verwendung paralleler Threads). Wie man in diesem Fall auch leicht sieht, terminiert das Programm auch für jede Eingabe. Eine wichtige Frage ist die nach der Korrektheit, d.h. berechnet das Programm wirklich das in der Aufgabenstellung verlangte?

6. Darstellung als Assemblerprogramm

In der Frühzeit der Informatik wurden Rechenmaschinen programmiert, indem eine Folge von Befehlen angegeben wurde, die direkt von der Maschine ausgeführt werden konnte. Assemblersprachen sind Varianten solcher Maschinensprachen, bei denen die Maschinenbefehle in mnemotechnischer Form niedergeschrieben sind. Häufig verwendete Adressen (Nummern von Speicherzellen) können mit einem Namen versehen werden und dadurch referenziert werden. Viele Assemblersprachen erlauben auch indirekte Adressierung, d.h. der Inhalt einer Speicherzelle kann die Adresse einer anderen Speicherzelle. Die in einer Assemblersprache verfügbaren Befehle hängen stark von der Art der zu programmierenden Maschine ab. Typische Assemblerbefehle sind z.B. mov rx ry (Bedeutung: transportiere / kopiere den Inhalt von rx nach ry) oder jgz rx lbl (Bedeutung: wenn der Inhalt von rx größer als Null ist, gehe zur Sprungmarke lbl)

// Eingabe: Preis in Register p in Cent (wird zerstört)

// Ergebnisse in fc, zc, tc (fünfzigCent, zwanzigCent, tenCent)

mov 0, fc

mov 0, zc

mov 0, tc

loop:

mov p, ac // lade p in den Akkumulator

sub ac, 450 // subtrahiere 450

jgz hugo // jump if greater zero to hugo

add ac, 500 // addiere 500

mov ac, p // speichere Akkumulator nach p

mov fc, ac

add ac, 1

mov ac, fc // fc := fc + 1

goto loop

hugo:

mov p, ac // wie oben

sub ac, 480

jgz erna

add ac, 500

mov ac, p

mov zc, ac

add ac, 1

mov ac, zc

goto hugo

erna:

mov p, ac

sub ac, 490

jgz fertig

mov 1, tc

fertig:

7. Darstellung als Maschinenprogramm

Ein Maschinenprogramm ist eine Folge von Befehlen, die direkt von einer Maschine eines dafür bestimmten Typs ausgeführt werden kann. Jedem Assemblerbefehl entspricht dabei eine bestimmte Anzahl von Bytes im Maschinenprogramm.

Programmiersprachen

Ein Programm ist, wie oben definiert wurde, die Repräsentation eines Algorithmus in einer Programmiersprache. Die Menge der syntaktisch korrekten Programme einer bestimmten Programmiersprache (JAVA, C, Delphi, …) wird im Allgemeinen durch eine kontextfreie Grammatik beschrieben. Maschinen- und Assemblersprachen sind dabei sehr einfache Sprachen (die sogar durch reguläre Grammatiken definiert werden könnten). Das Programmieren in einer Maschinensprache oder Assembler ist außerordentlich mühsam und sehr fehleranfällig. Höhere Programmiersprachen sind nicht an Maschinen orientiert, sondern an den Problemen. Programme, die in einer höheren Programmiersprache geschrieben sind, können nicht unmittelbar auf einem Rechner ausgeführt werden. Sie werden entweder von einem speziellen Programm interpretiert (d.h., direkt ausgeführt) oder von einem Compiler in eine Folge von Maschinenbefehlen übersetzt und erst dann ausgeführt. Bei einigen Prgrammiersprachen (Java, C#, USCD-Pascal) erfolgt die Übersetzung zunächst in die Maschinensprache einer virtuellen Maschine, d.h. einer nicht in Hardware realisierten Maschine, welche daher unabhängig von einer speziellen Hardwaretechnologie ist. Die Ausführung von Maschinenprogrammen der virtuellen auf einer realen Maschine erfolgt von speziellen Interpretern (der natürlich für jede reale Maschine neu entwickelt oder angepasst werden muss). Die Sprachen, die einer maschinellen Behandlung nicht zugänglich sind und von Menschen in Programme überführt werden müssen, nennen wir Spezifikationssprachen.

Seit Beginn der Informatik wurden mehr als 1000 unterschiedliche Programmiersprachen erfunden, von denen die meisten in vielen verschiedenen Varianten und Dialekten existieren. Beispielsweise gibt es von Java inzwischen sieben Hauptvarianten (Versionen), und Groovy kann als eine Erweiterung von Java betrachtet werden. Im vierten Kapitel werden wir Möglichkeiten zur Klassifikation von Programmiersprachen betrachten.