Demoseite

2. Informatik-Algorithmen

In der Informatik gibt es ebenfalls Handlungsanweisungen, die allerdings werden als Programme vom Computer zum Lösen von Problemen ausführt.

Beispiel eines Algorithmus zum Lösen von Gleichungen

Der persische Gelehrte Al-Chwarizmi – der in der Zeit von 780 bis 850 n. Chr. lebte – entwickelte Handlungsvorschriften zum Lösen von Gleichungen (Algebra). Vermutlich wurde der Gelehrte aus diesem Grund Namensgeber für den Begriff Algorithmus.

Algorithmus »Gleichungen«

In der Abbildung 1 ist der im Struktogramm^[1] dargestellte Algorithmus »Gleichungen« zum Lösen linearer Gleichungen ax+b=0 gegeben

Bild 01 — Abbildung 1: Algorithmus »Gleichungen«

Die Variablen »a« und »b« sind vom Datentyp Gleitkommazahl (float/double).^[2]
Wie in der Abbildung 1 zu erkennen ist, gibt es im Algorithmus beim Lösen der Gleichungen drei Fälle:
1. Jede Zahl ist Lösung.
2. Keine Lösung.
3. x=-b/a

In der Abbildung 2 ist im Algorithmus der Datenfluss beim Lösen der linearen Gleichungen durch die roten Pfeillinien gekennzeichnet.

Bild 02 — Abbildung 2: Datenfluss beim Lösen der Gleichungen

Aufgabe A6

Beantworte die Frage:

Welche Pfeillinie (links, mitte, rechts) führt zur Lösung welcher linearen Gleichung?

a): -7.0x+0=0
b): 0x+3.4=0
c): 0x-0=0
d): 4.5x+9.0=0

Intuitiver Algorithmus

Wird in der Fachliteratur nachgeschlagen oder im Internet gesucht, dann finden sich verschiedenste Definitionen des Begriffs »Algorithmus«. An dieser Stelle bietet sich die folgende Begriffsdefinition an.

Begriff »Algorithmus«

»Ein Algorithmus ist ein schrittweises, präzises Verfahren zur Lösung eines Problems.«

»Schrittweise bedeutet, dass ein Algorithmus aus einzelnen Schritten besteht, die in genau festgelegter Reihenfolge ausgeführt werden müssen.«

In der Informatik müssen Algorithmen »präzise und eindeutig sein.«

»In der Informatik muss jeder Schritt eines Algorithmus so klar beschrieben sein, dass ein Rechner ihn in eindeutiger Weise ausführen kann.«

[Ein Algorithmus] »hat einen Namen […], über den man sich auf ihn beziehen kann.«

Mössenböck, Hanspeter (2001): Sprechen Sie Java? Eine Einführung in das systematische Programmieren, Heidelberg: dpunkt-Verlag, S. 4 f.

Der Begriff »Algorithmus« lässt sich anhand des in der Abbildung 1 gegebenen Algorithmus zum Lösen linearer Gleichungen erläutern.

Der Algorithmus hat den Namen »Gleichungen«.
Beim zu lösenden Problem handelt es sich um das Lösen linearer Gleichungen ax+b=0. Das heißt, der Algorithmus löst jede dieser linearen Gleichungen und ist nicht nur auf eine einzelne Gleichung (beispielsweise 4.5x+9.0=0) eingeschränkt.
Der Algorithmus besteht insgesamt aus sieben Anweisungen, wovon zwei zusammengesetze Anweisungen sind.
In einzelnen Schritten werden die Gleitkommazahlen eingegeben und die Lösung der Gleichung berechnet und ausgegeben.
Danach endet in jedem Fall der Algorithmus, was beispielsweise anhand des Java-Programms »gleichungen.java« oder Python-Programms »gleichungen.py« überprüft werden kann.
Im Struktogramm sind die Lösungsschritte und ihre Aufeinanderfolge exakt und eindeutig – das heißt präzise – beschrieben.
Das Lösen jeder linearen Gleichung kann beliebig oft wiederholt werden, wobei dabei die Lösung dieselbe bleibt.
Der Algorithmus ist sowohl im Java-Programm »gleichungen.java« als auch im Python-Programm »gleichungen.py« implementiert. Beide Programme sind am Computer ausführbar.

Quelltext des Java-Programms »gleichungen.java«

import java.util.Scanner;

public class Gleichungen {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        
        System.out.print("a: ");
        double a=input.nextDouble();
        System.out.print("b: ");
        double b=input.nextDouble();
        
        if (a==0) {
            if (b==0) {
                System.out.println("Jede Zahl ist Lösung.");
            }
            else {
                System.out.println("Keine Lösung.");
            }
        }
        else {
            System.out.println(
                String.format("x=%f", -b/a));
        }
        
        input.close();
    }
}

Quelltext des Python-Programms »gleichungen.py«

a=float(input("a: "))
b=float(input("b: "))

if a==0:
    if b==0:
        print("Jede Zahl ist Lösung.")
    else:
        print("Keine Lösung.")
else:
    print(f"x={-b/a}.")

Obwohl beiden Programmen derselbe Algorithmus »Gleichungen« zugrunde liegt, sind in den Quelltexten die verschiedenen programmiertechnischen Besonderheiten der jeweiligen Programmiersprache – die nur mittelbar etwas mit dem Algorithmus zu tun haben – zu erkennen.
Aus diesem Grund sollten Algorithmen zuallererst unabhängig von den Implementiierungen in den jeweiligen Programmen entwickelt werden.

Bleibt noch zu verstehen, dass es sich beim gegebenen Begriff »Algorithmus« um einen intuitiven Algorithmusbegriff handelt.

Das Wort »intuitiv« bedeutet, dass es sich um einen auf Erfahrungen basierenden Begriff handelt und nicht um einen wissenschaftlichen Begriff.
Das heißt, der Begriff basiert – beginnend in den 1940er Jahren – auf den langjährigen Erfahrungen des Programmierens von Problemen am Computer.
Erst im Zusammenhang mit der Frage nach der Berechenbarkeit in der Theoretischen Informatik wird ‐ u. a. durch die Turingmaschine – der Algorithmusbegriff wissenschaftlich definiert.

Aufgabe A7

Erstelle einen Algorithmus zum Lösen linearer Gleichungen ax+b=c. Die Variablen a, b, c sind vom Datentyp Gleitkommazahl (float/double).

Stelle den Algorithmus in einem Struktogramm mit dem Structorizer dar.

Teste, ob die folgenden linearen Gleichungen mithilfe des Algorithmus gelöst werden können:

6.5x−5.5=7.5
−34.6x+2.9=2.9
0x−0=0
0x+4.1=−1.0
5.1x+0=0

Darstellungsformen von Algorithmen

Es gibt verschiedene Möglichkeiten, einen Algorithmus darzustellen:

verbal beschrieben in der Umgangssprache

Abbildung 3: Algorithmus verbal beschrieben
grafisch dargestellt in einem Programmablaufplan (PAP)

Abbildung 4: Algorithmus im Programmablaufplan
grafisch dargestellt in einem Struktogramm (Abbildung 1)
beschrieben in Pseudocode (angelehnt an eine Programmiersprache)

Abbildung 5: Algorithmus in Pseudocode

Im weiteren Verlauf des Themengebiets Algorithmen erfolgt die Darstellung der Algorithmen ausschließlich in Struktogrammen.

Entwickeln von Algorithmen

Algorithmen:

werden entwickelt, um Probleme zu lösen
bekommen identifizierende Namen
werden auf eine bestimmten Art dargestellt (beispielsweise verbal, Pseudocode, in PAPs oder Struktogrammen)
enthalten Variablen, deren Datentypen (int, float/double, str, bool, …) angegeben werden müssen
sind zu testen, ob sie die gestellten Probleme lösen, das heißt effektiv sind
werden letztendlich in Programmiersprachen beschrieben, sodass sie als Programme am Computer ausgeführt werden können

[1] Es gibt auch andere Darstellungsformen eines Algorithmus.
[2] In den Programmiersprachen wird bei den Zahlen zwischen Ganzzahlen und Gleitkommazahl unterschieden.

Lehrer-Login