Pseudocode und formale Sprachen

Einordnung des Artikels

• Einführung in die Informatik
  • Einführung in die Programmierung
    • Pseudocode und formale Sprachen

Umgangssprachliche Formulierung

Die Algorithmierung beginnt meist damit, dass man die Methode der schrittweisen Verfeinerung auf das zu lösende Problem anwendet und dabei die Einzelschritte noch in Umgangssprache formuliert.

Beispiel:

Von allen Personen in einem Raum sollen die Personalien aufgenommen werden. Die Vorgehensweise soll als Algorithmus niedergelegt werden.

Man zerlegt das Problem zuerst in zwei Teilprobleme:

1. Wie geht man vor, um die Personalien einer Person aufzunehmen?

2. Wie geht man vor, um alle Personen im Raum abzuarbeiten?

Die Lösungen der Teilprobleme sind noch nicht offensichtlich, also werden sie weiter zerlegt:

1. Personalien einer Person:

1. Liste vorbereiten mit den geforderten Einträgen wie

    A) Name

    B) Vorname

    C) Straße 
	
	usw....

2. Person befragen und die Liste ausfüllen.

2. Vorgehensweise, um alle Personen abzuarbeiten:

1. Man fragt, ob noch jemand im Raum ist, von dem man die Personalien noch nicht aufgenommen hat.  
    Falls sich niemand meldet: 
        Ende.  
    Andernfalls werden die folgenden Schritte abgearbeitet.

2. Auswählen einer Person (zum Beispiel diejenige, die möglichst nahe ist).

3. Aufnehmen der Personalien dieser Person (wie oben beschrieben).

4. Man beginnt wieder am Anfang.

Der Vorteil der umgangssprachlichen Beschreibung liegt auf der Hand:

Man kann sehr schnell für sich entscheiden, ob man das Problem verstanden hat und ob in jedem Teilschritt klar ist, was dabei zu tun ist.

Gibt man diese umgangssprachliche Beschreibung aber einem Programmierer weiter, wird er sicher einige Rückfragen haben. Insbesondere — da das Problem in einen Algorithmus übersetzt werden soll — ist an der Formulierung in Umgangssprache nicht klar, welche Strukturelemente eines Algorithmus für welchen Lösungsschritt eingesetzt werden. Um diese Information bereitzustellen, verwendet man den Pseudocode.

Pseudocode

Bei der Verwendung von Pseudocode wird die umgangssprachliche Formulierung eines Algorithmus überarbeitet und es werden an den Stellen, an denen Strukturelemente eines Algorithmus vorkommen, Textbausteine eingesetzt, die eindeutig das betreffende Strukturelement kennzeichnen.

Die wichtigsten Strukturelemente, die zu kennzeichnen sind, sind Unterprogramm, Alternative und Schleifen. An dem einfachen Beispiel von oben, in dem alle drei Strukturelemente vorkommen, soll dies demonstriert werden.

Beispiel:

In einem Raum befinden sich N Personen, von denen die Personalien aufgenommen werden müssen.

Unterprogramm

Die Befehle, die abgearbeitet werden müssen, um von einer Person die Personalien aufzunehmen, werden im Unterprogramm

PersonalienAufnehmen

zusammengefasst. Die CamelCase-Schreibweise wird in fast allen Programmiersprachen als Namenskonvention (für Unterprogramme, Funktionen oder Variablen) verwendet; hier soll sie andeuten, dass es ein Unterprogramm ist.

Die Befehle, die zusammen das Unterprogramm PersonalienAufnehmen ergeben, würden etwa lauten:

Eingabe: Vorname
Eingabe: Name
Eingabe: Straße
Eingabe: Hausnummer
Eingabe: PLZ
Eingabe: Ort

In der Notation eines Flussdiagramms (= PAP = Programmablaufplan) sieht ein Unterprogramm aus wie in der folgenden Abbildung dargestellt.

Abbildung 1: Unterprogramm-Aufruf im Flussdiagramm.

Alternative

Für die Alternative verwendet man folgende Textbausteine, um sie im Pseudocode darzustellen:

Falls (Bedingung)
    dann (Anweisung)
    sonst (Anweisung)

Im Beispiel oben (Personalien aufnehmen) könnte folgender Befehl vorkommen:

Falls (N = 0)
    dann ENDE
    sonst PersonalienAufnehmen

Abbildung 2: Die Alternative im Flussdiagramm: In der Raute steht die Variable, die abgefragt wird (das Fragezeichen deutet die Abfrage an), an den Ausgängen der Raute stehen die möglichen Fälle, hier also die Werte (oder Wertemengen) der abgefragten Variable N. Die Ausgänge führen zu den Anweisungen, die in dem einen oder anderen Fall auszufüren sind. Man beachte, dass bei einer Alternative genau einer der beiden Zweige durchlaufen wird; die Symbolik könnte so missverstanden werden, dass beide Zweige gleichzeitig durchlaufen werden.

Schleife (Iteration)

Arten von Schleifen

Es gibt drei Arten von Schleifen

1. kopfgesteuerte Schleife
2. fußgesteuerte Schleife
3. Schleife mit Zählvariable

Die ersten beiden haben den Vorteil, dass man vor Betreten der Schleife noch nicht wissen muss, wie oft die Schleife durchlaufen wird; dies hat aber umgekehrt den Nachteil, dass man leicht eine Endlos-Schleife bilden kann.

Der Pseudocode würde dann folgendermaßen aussehen:

1. Kopfgesteuerte Schleife

solange (Bedingung)
    wiederhole (Anweisung)

2. Fußgesteuerte Schleife

wiederhole (Anweisung)
    bis (Bedingung)

3. Schleife mit Zählvariable

Für i = 1 bis N Schrittweite 1
    (Anweisung)

Der Unterschied besteht in der Steuerung der Schleife, die in den ersten beiden Fällen durch eine Bedingungsprüfung erfolgt:

1. Kopfgesteuerte Schleife:

Die Bedingung wird vor der ersten Ausführung der Schleife geprüft und dann immer wieder bevor die Schleife betreten wird.

Abbildung 3: Die kopfgesteuerte Schleife zum Aufnehmen der Personalien von N Personen. Ob die Schleife durchlaufen werden muss oder ob sie übersprungen wird, entscheidet sich vor dem Durchlauf der Schleife. Bei jedem Durchlauf verringert sich die Anzahl der Personen, die noch abgearbeitet werden müssen, daher die Anweisung N = N -1.

2. Fußgesteuerte Schleife: Die Bedingung wird nach der ersten Ausführung der Schleife geprüft und dann immer nach der Ausführung der Schleife.

Abbildung 4: Die fußgesteuerte Schleife zum Aufnehmen der Personalien von N Personen. Im Unterschied zur kopfgesteuerten Schleife werden jetzt zuerst die Personalien einer Person aufgenommen und dann erst wird abgefragt, ob die Schleife nochmals durchlaufen werden muss. Wie oben verringert sich bei jedem Durchlauf die Anzahl der Personen, die noch abgearbeitet werden müssen, daher wieder die Anweisung N = N -1.

3. Schleife mit Zählvariable: Die Werte, die die Zählvariable annehmen muss, bestimmen wie oft die Schleife durchlaufen wird.

Im Beispiel werden die Personen durchnumeriert P(1), P(2), ... , P(N) und in der Reihenfolge 1, 2, ..., N abgearbeitet.

Für i = 1 bis N Schrittweite 1
    PersonalienAufnehmen(P(i))

Die Schleife mit Zählvariable besteht aus folgenden Elementen:

1. Eine Zählvariable, die auf einen definierten Startwert gesetzt wird (hier i = 1).
2. Die Zahl die angibt, wie weit die Zählvariable laufen muss (hier N). Dies entpricht der Bedingungsprüfung in den anderen Schleifen, da nach i = N die Schleife verlassen wird.
3. Die Schrittweite, die angibt um wieviel die Zählvariable pro Schleifendurchlauf erhöht wird (hier um 1).
4. Der eigentliche Schleifenkörper, also die Anweisungen, die wiederholt ablaufen (hier das Unterprogramm PersonalienAufnehmen für die i-te Person).

TIPS:

1. Prüfen Sie immer die Initialisierung der Zählvariable: Menschen sind gewohnt von 1 ab zu zählen, Computer zählen immer ausgehend von 0.

2. Besonders einfach ist immer der Grenzfall N = 1 zu überprüfen (eine Schleife soll genau einmal durchlaufen werden); Fehler in der Formulierung der Abbruchbedingung oder mit der Zählvariable lassen sich dabei leicht aufspüren.

Bemerkung zu den Flussdiagrammen:

Die Flussdiagramme wurden hier nur zur Veranschaulichung eingesetzt. Wie erwähnt, sollen sie für ernsthafte Arbeiten nicht mehr eingesetzt werden, da sie dazu verleiten, schlechte Programme zu schreiben. Sie haben ihre Berechtigung lediglich zur Kommunikation (meist mit Nicht-Programmierern), wenn Teile des Ablaufs in einem Programm diskutiert werden sollen. Sie werden merken, dass ein Algorithmus, den man verstanden hat und den man in Pseudocode schreiben kann, direkt in den Quelltext übersetzt werden kann — der Umweg über Diagramme ist nicht nötig.

Praxis-Tips zum Umgang mit Schleifen

1. Überschreiben von Variablen:

Bei der Arbeitsweise des Prozessors wurden immer wieder Register eingesetzt, die als Zwischenspeicher dienen. Meist waren ihre Inhalte gerade für die Abarbeitung eines Maschinensprache-Befehls relevant; die Inhalte wurden also nicht permanent gespeichert, sondern im nächsten Maschinensprache-Zyklus überschrieben.

Diesen Mechanismus kann man auch beim Programmieren nutzen — man muss sich aber immer zuvor klar machen: Müssen die Werte abgespeichert werden oder dürfen sie nach ihrer Verarbeitung gelöscht werden. Das folgende Beispiel soll dies demonstrieren:

Beispiel:

Zehn Zahlen x(1), x(2),..., x(10) sollen addiert werden und ihre Summe ausgegeben werden.

Da hier die Anzahl der Schleifendurchläufe bekannt ist, wählt man die Schleife mit Zählvariable. Für die Summe der Zahlen wird eine weitere Variable namens Summe eingeführt, die bei jedem Durchlauf der Schleife überschrieben wird:

Summe = 0

Für i = 1 bis 10 Schrittweite 1
    Summe = Summe + x(i)

Ausgabe: Summe

(Die Leerzeilen sind ohne Bedeutung, sie sollen nur die Anweisungen besser strukturieren.)

Die Variable Summe muss vor Betreten der Schleife auf null gesetzt werden; in ihr sind dann die Zwischensummen der Zahlen x(1), x(2),..., x(10) abgespeichert:

Nach dem 1. Durchlauf: Summe = x(1)

Nach dem 2. Durchlauf: Summe = x(1) + x(2)

Nach dem 3. Durchlauf: Summe = x(1) + x(2) + x(3)

usw.

Diese Zwischensummen sind offensichtlich irrelevant und müssen nicht permanent abgespeichert werden. Dagegen liegt das Endergebnis nach dem Verlassen der Schleife in der Variable Summe und kann weiterverarbeitet werden.

2. Welche Schleife soll man wählen?

Am klarsten strukturiert ist die Schleife mit Zählvariable. Wer zum Beispiel mit dem Summenzeichen der Mathematik vertraut ist, kann sich sehr leicht vorstellen, wie diese Schleife abgearbeitet wird.

Die Schleife mit Zählvariable setzt aber voraus, dass bekannt ist, wie oft die Schleife durchlaufen werden muss. Ist dies der Fall, sollte man sie auch einsetzen. Andernfalls muss man mit der kopf- oder fußgesteuerten Schleife arbeiten. Dies ist etwa dann der Fall, wenn der Nutzer beliebig viele Eingaben machen kann und erst bei der Eingabe eines vereinbarten Abbruchssignals die Verarbeitung der Daten beginnt.

Beispiele:

1. Der Nutzer soll 10 Zahlen eingeben, deren Summe anschließend ausgegeben wird.

Mögliche Lösung:

Summe = 0

Für i = 1 bis 10 Schrittweite 1
    Eingabe: x
    Summe = Summe + x

Ausgabe: Summe

2. Der Nutzer soll solange Zahlen eingeben bis er anstelle einer Zahl ESC eingibt. Die Summe der Zahlen soll anschließend ausgegeben werden.

Mögliche Lösung:

Summe = 0

wiederhole
    Eingabe: x
    Summe = Summe + x
bis (x = ESC)   

Ausgabe: Summe

3. Kopf- oder fußgesteuerte Schleife?

Diese Frage ist zum Teil sehr schwer zu beantworten, in einfachen Fällen sind beide gleichwertig — es ist dann nur eine Geschmacksfrage.

Bei genauer Betrachtung der beiden Schleifen erkennt man aber den Unterschied — und dessen Nicht-Beachtung kann zu unerwünschten Effekten führen.

Worin liegt der Unterschied?

• Die kopfgesteuerte Schleife wird eventuell überhaupt nicht durchlaufen, da man sofort aus ihr herausspringen kann.
• Die fußgesteuerte wird mindestens einmal durchlaufen.

Um das Beispiel PersonalienAufnehmen wieder aufzugreifen: Was passiert, wenn man aufgefordert wird, die Personalien aller Personen in einem Raum aufzunehmen, man wird aber in einen leeren Raum geschickt? Wie die fußgesteuerte Schleife hier arbeitet, ist nicht klar — schlimmstenfalls kann es zu einem Programm-Absturz kommen.

4. Sonderfälle zuerst!

Das letzte Beispiel lehrt folgendes:

Es reicht nicht, den Normalfall abzuarbeiten, man muss sich immer auch um die Sonderfälle kümmern.

Mit Normalfall ist hier gemeint, dass man bei der Stellung der Aufgabe eine ganz gewisse Situation vor Augen hat — und die Lösung der Aufgabe beginnt meist damit. Dass es auch Grenzfälle oder Sonderfälle geben kann, die mit der Lösung nicht abgedeckt sind, vergisst man dabei womöglich. Die Regel für den Programmierer lautet daher:

TIP:

Sonderfälle immer zuerst abarbeiten!

Beispiel:

Um wieder das Beispiel PersonalienAufnehmen aufzugreifen: Wie behandelt man den Fall, dass man in einen leeren Raum geschickt wird?

Falls (N = 0)
    dann ENDE
    sonst
        Für i = 1 bis N Schrittweite 1
            PersonalienAufnehmen(P(i))

Aufgabe:

Das Beispiel oben zur Summation der eingegebenen Zahlen (bis ESC eingegeben wird), sollte in der dargestellten Form besser nicht in ein Programm umgesetzt werden.

Wo liegt der Fehler?

Wie lässt sich dieser Fehler durch Verwendung einer kopfgesteuerten Schleife leicht vermeiden?

Formale Sprachen

Pseudocode ist schon eine deutliche Verbesserung gegenüber der umgangssprachlichen Formulierung eines Algorithmus: durch die Verwendung von Textbausteinen sind die Strukturelemente des Algorithmus erkennbar und dadurch sollte es sehr viel leichter fallen, den Quelltext in einer speziellen Programmiersprache zu schreiben.

Aber was macht eigentlich den Unterschied zwischen Pseudocode und Quelltext aus? Bei der Verwendung von Pseudocode besteht immer noch die Gefahr, dass umgangssprachliche Formulierungen einfließen, die eine gewisse Unschärfe besitzen. Dagegen hat eine Programmiersprache eine eindeutige Syntax, also Regeln wie die Sprache eingesetzt und wie die Befehle verknüpft werden müssen.

Um einige dieser Regeln zu nennen:

1. Es gibt Schlüsselwörter, die für eine bestimmte Verwendung reserviert sind (wie etwa if oder else, oder die Bezeichnung der elementaren Datentypen wie int, char, double); diese Schlüsselwörter dürfen dann nicht für andere Zwecke eingesetzt werden, etwa um Variablen zu bezeichnen.

2. Nahezu alle Befehle werden mit einem Strichpunkt abgeschlossen, um das Ende eines Befehls eindeutig zu kennzeichnen (manche Programmiersprachen erlauben auch Zeilenumbrüche oder Einrückungen als Trennungszeichen zwischen Befehlen).

3. Klammern haben stets eine besondere Bedeutung: Wie in der Mathematik werden die Argumente einer Funktion in runde Klammern geschrieben, also f (x, y). Die geschweiften Klammern werden oft verwendet, um Blöcke abzugrenzen, etwa der Block, der Anweisungen einer Funktion zusammenfasst.

4. Operatoren wie +, -, *, /, % haben eine eindeutige Bedeutung, die aber davon abhängt, von welchem Datentyp die verknüpften Operanden sind. So kann ein Divisions-Zeichen entweder für die Division von reellen Zahlen stehen oder für die Division mit Rest bei natürlichen Zahlen — eine häufige Fehlerquelle!

5. Das Gleichheitszeichen = steht meist für den Zuweisungsoperator; damit ist gemeint, dass etwa in

n = n + 1

zunächst die rechte Seite ausgewertet wird und dann das Ergebnis der Variable auf der linken Seite zugewiesen wird. So hat die Anweisung — die in der Mathematik zum Widerspruch 0 = 1 führen würde — plötzlich eine Bedeutung (n ist hier wohl eine Zählvariable, die um 1 erhöht wird).

In Programmiersprachen wird daher streng zwischen linker und rechter Seite einer Gleichung unterschieden:

• rechts steht immer ein Term, der ausgewertet werden kann
• links steht eine Variable, der der soeben berechnete Wert zugewiesen wird.

Beispiele:

n = 1000    // der Variable n wird der Wert 1000 zugewiesen
m = 2*n     // die rechte Seite wird ausgewertet, ergibt 2000, und dieser Wert wird der Variable m zugewiesen
m = m + 1   // jetzt ist m = 2001
2001 = m    // Fehler: die rechte Seite kann zwar ausgewertet werden, aber links steht keine Variable
m + 1 = m   // Fehler: links steht wieder keine Variable

6. In der Mathematik hat das Gleichheitszeichen = eher die logische Bedeutung, die die Gleichheit von linker und rechter Seite zeigen soll; dafür verwenden die meisten Programmiersprachen den Vergleichs-Operator == , wie etwa in

Falls (n == 0)
    dann doSomething();

Hier wird nicht der Variable n der Wert 0 zugewiesen, sondern es wird geprüft, ob n den Wert 0 hat.

Sprachen, die nach solchen eindeutigen Regeln aufgebaut sind, werden als formale Sprachen bezeichnet. Programmiersprachen fallen unter diese Kategorie. Der Name Programmiersprache soll zudem andeuten, dass es zu dieser Sprache einen Compiler gibt, der den Quelltext in Maschinensprache verwandeln kann.

Aufgaben

Schreiben Sie zu folgenden Aufgaben Pseudocode. Geben Sie dazu insbesondere alle nötigen Formeln an. Falls Sie Unterprogramme einsetzen, müssen diese natürlich auch in Einzelschritte aufgelöst werden. Später werden diese Aufgaben in Quelltext übersetzt.

TIP:

Gehen Sie bei der Lösung der Aufgaben folgendermaßen vor:

1. Formulieren Sie die Lösung zuerst im Umgangssprache.

2. Falls Ihnen einige Schritte nicht ganz klar sind, verwenden Sie die Methode der schrittweisen Verfeinerung, bis Ihnen jeder Einzelschritt klar erscheint.

3. Geben Sie alle Formeln an, die zur Lösung der Aufgabe notwendig sind. Schreiben Sie Formeln stets in der Form auf wie oben beschrieben (Zuweisungsoperator).

4. Gehen Sie jetzt zum Pseudocode über (Strukturelemente kennzeichnen).

5. Bei einfachen Aufgaben lassen sich einige dieser Schritte zusammenfassen oder überspingen, bei schwierigen Aufgaben besser nicht.

Aufgaben:

1. Es sollen alle Zahlen zwischen 1 und 10000 ausgegeben werden, die durch 17 teilbar sind.

2. Der Nutzer wird aufgefordert, eine Zahl n zwischen 1 und 100 einzugeben. Ausgegeben werden sollen alle Zahlen zwischen 1 und 10000, die durch n teilbar sind.

3. Der Nutzer wird aufgefordert, eine Zahl n zwischen 1 und 1000 einzugeben. Ausgegeben werden sollen alle Teiler von n.

4. In der Mathematik (Fourier-Analyse) wird folgende Formel hergeleitet:

Abbildung 5: Formel zur Berechnung der Kreiszahl π.

• Geben Sie einen Algorithmus an, der die Summe bis zu einer einzugebenden Zahl N berechnet. Ausgegeben werden soll die Summe und die damit berechnete Näherung der Kreiszahl π.
• Die Summe soll so weit geführt werden, bis der neu hinzukommende Summand kleiner als 10^-10 ist. Bis zu welchem N wird jetzt summiert und wie groß ist die Näherung für π?

5. Die Fläche unterhalb der Normalparabel (für x zwischen 0 und 2) soll durch Riemannsche Summen angenähert werden. Der Nutzer kann vorgeben, in wieviele Intervalle n der Integrationsbereich zerlegt wird.

• Berechnet werden soll die Näherung für den Flächeninhalt
  • einmal mit Riemannscher Untersumme,
  • einmal mit Riemannscher Obersumme.
• Die Ergebnisse sollen mit dem exakten Wert (ausgewertet mit der Stammfunktion) verglichen werden.

6. Ausgabe der Dualzahlen von (0000)₂ bis (1111)₂, wobei jede Zahl vierstellig angegeben werden soll (also eventuell mit führenden Nullen).

7. Ausgabe der Hexadezimalzahlen von (0000)₁₆ bis (FFFF)₁₆, wobei jede Zahl vierstellig angegeben werden soll (also eventuell mit führenden Nullen).

8. Eine Zahl zwischen 0 und 4096 soll in eine Hexadezimalzahl umgerechnet werden.

9. Das SR-Flip-Flop soll simuliert werden:

• mit allen möglichen Eingabewerten für S (Set) und R (Reset) und gespeicherten Werten Q = 0; 1.
• mit einer Überprüfung, ob ein Zustand stabil ist oder nicht (falls er instabil ist, soll der nachfolgende stabile Zustand berechnet werden).
• mit einer Überprüfung, ob das Flip-Flop einen inkonsistenten Zustand annimmt.

Zur Vereinfachung können Sie davon ausgehen, dass S dominant ist.