Algorithmen und ihre Grundstrukturen

Häufig begegnen uns Beschreibungen von Verfahren und Vorgängen:

ein Kochrezept

eine Bedienungsanleitung

ein mathematisches Verfahren

Der arabische Mathematiker Abu Ja’far Mohammed ibn Musa al-Khowarizmi hat solche, speziell mathematische Verfahren in der ersten Hälfte des 9. Jahrhunderts beschrieben. Deshalb nennt man solche Beschreibungen von Vorgängen auch Algorithmus.

Definition:

„Ein Algorithmus ist eine Verarbeitungsvorschrift, die aus einer endlichen Folge von eindeutig ausführbaren Anweisungen besteht, mit der man eine Vielzahl gleichartiger Aufgaben lösen kann.“ 1) Engelmann, Lutz (Hrsg.): Duden Informatik Lehrbuch S II, DUDEN PAETEC GmbH, Berlin 2006, S.30

Eigenschaften eines Algorithmus

Endlichkeit: Ein Algorithmus besteht aus endlich vielen Anweisungen.

Eindeutigkeit: Mit einer Anweisung ist auch die nächste Anweisung festgelegt. Gleiche Eingabedaten müssen zu gleichen Ausgabedaten führen.

Ausführbarkeit: Alle Anweisungen eines Algorithmus müssen für den Ausführenden verständlich und damit ausführbar sein.

Allgemeingültigkeit: Ein Algorithmus muss alle Probleme einer bestimmten Problemklasse lösen.

Terminiertheit: Ein Algorithmus muss nach endlich vielen Schritten eine Lösung gefunden haben. (In der theoretischen Informatik verzichtet man häufig auf diese Eigenschaft und betrachtet auch Algorithmen, die nicht terminieren.)

Darstellungsformen von Algorithmen

Einen Algorithmus kann man auf verschiedene Weisen darstellen:

Beschreibung mit Hilfe der Umgangssprache

verbale formalisierte Beschreibung

Struktogramm

Programmablaufplan (Flussdiagramm)

Computerprogramm

Ein Beispiel

Ein berühmter Algorithmus ist der Euklidische Algorithmus, mit dem man den größten gemeinsamen Teiler zweier natürlicher Zahlen a und b ermitteln kann. Dieser Algorithmus wird hier (in der Differenzvariante) in den verschiedenen Darstellungsformen präsentiert:

Beschreibung mit Hilfe der Umgangssprache:

Wenn a gleich b ist, dann ist a der gesuchte größte gemeinsame Teiler und der Algorithmus bricht ab; sonst:

Wenn a kleiner als b ist, werden die Werte von a und b vertauscht.

Wenn a größer als b ist, bildet man die Differenz c von a und b. a ergibt sich aus dem Wert von b, b ergibt sich aus dem Wert von c.

Weiter bei 1!

verbale formalisierte Beschreibung:

Solange a ungleich b ist wiederhole:

Wenn a < b, dann vertausche die Werte von a und b.

Berrechne c = a - b.

Gebe a den Wert von b und b den Wert von c.

Gebe ggT = a aus.

Struktogramm:
Auf die einzelnen Struktogrammelemente wird bei den algorithmischen Kontrollstrukturen noch genauer eingegangen.

Programmablaufplan (Flussdiagramm):
Diese Darstellungsform soll nur der Vollständigkeit halber erwähnt werden. Es wird nicht genauer darauf eingegangen.

Computerprogramm:
Hier ist der Algorithmus in der Programmiersprache Python dargestellt. Die einzelnen Elemente des Programms werden noch behandelt.

a = int(input("a = ")) b = int(input("b = ")) while a != b: if a < b: c = a a = b b = c c = a - b a = b b = c print("ggT:",a)

Algorithmischen Grundstrukturen

Es gibt bestimmte Grundstrukturen, aus denen sich alle Algorithmen aufbauen lassen. Diese werden in den folgenden Abschnitten behandelt.

Lineare Programme - Aus- und Eingabe

Einfache und zweifache Verzweigung

Mehrfachverzweigung

Schleifen mit Abbruchbedingung

Zählschleifen

Zusammenfassung algorithmische Kontrollstrukturen

Computerprogramme und Programmiersprachen

„Ein Programm ist ein vom Computer umsetzbarer Algorithmus, der in einer für den Computer verständlichen Sprache (einer Programmiersprache) verfasst ist.“2) eben da, S. 38

Einteilung von Programmiersprachen

Einteilung nach historischer Entwicklung

Bei Machinensprachen (Programmiersprachen der 1. Generation) wird das Computerprogramm direkt in einer für den Prozessor des Computers ausführbaren Form (als duale oder hexadezimale Zahlen) eingegeben. Das Programm ist dann direkt ausführbar.

Bei Assemblersprachen (Programmiersprachen der 2. Generation) wird das Programm in einem sogenannten mnemonischen Code mit einem Texteditor erstellt. Die verwendeten Befehle entsprechen dem Befehlsvorrat einer bestimmten Prozessorarchitektur. Sie werden dann mit einem Programm, dem Assembler, in Maschinencode übersetzt.

Bei höheren Programmiersprachen (Programmiersprachen der 2. Generation) wird der Programmquelltext in einer für Menschen gut lesbaren Form in eine Textdatei geschrieben. Diese Datei kann dann auf verschiedene Arten (Siehe unten!) in eine für den Prozessor (Maschinencode) Form übersetzt.

Einteilung höherer Programmiersprachen nach der Art der Übersetzung

Compilersprachen: Hier übersetzt der Compiler zunächst das Programm in Maschinencode. Danach kann die Maschinencodedatei vom Computer ausgeführt werden. (z.B. C, C, Delphi) * **Interpretersprachen:** Die Quelltextdatei wird zusammen dem Interpreter aufgerufen. Der Interpreter übersetzt jetzt den ersten Befehl in Maschinencode und führt ihn aus. Danach wird der nächste Befehl übersetzt und ausgeführt, usw., bis die gesamte Datei abgearbeitet ist. (z.B. Perl, Python, JavaScript) * **Mischtypen** Bei einigen Programmiersprachen (z.B. Java, C#) wird der Quelltext zunächst von einem Compiler in einen Zwischencode (Bytecode) übersetzt. Dieser Bytecode wird dann von einem Interpreter im jeweiligen Betriebssystem ausgeführt. \\ Bei einigen Interpretersprachen (z.B. Python) werden Bibliotheken von einem Precompiler zunächst in einen Zwischencode übersetzt, bevor die eigentliche Programmdatei vom Interpreter ausgeführt wird. ===Einteilung höherer Programmiersprachen nach dem Programmierparadigma=== Die folgende Übersicht zeigt eine mögliche Einteilung von Programmiersprachen nach ihrem Programmierparadigma. ((eben da)) {{ :python:einthoeprogr.png?600}} * Imperative Sprachen bestehen aus einer Folge Befehlen die vom Computer nacheinander ausgeführt werden. man kann sie einteilen in:

* //**Prozedurale Sprachen:**// Das Programm besteht aus Anweisungen und algorithmischen Grundstrukturen. Das Gesamtproblem kann durch Prozeduren in kleinere Teilprobleme zerlegt werden. (Typische Vertreter: C, Turbo Pascal)
* //**Objektorientierte Sprachen:**// Das Programm besteht aus Objekten mit Attributen und Methoden. Für diese Objekte werden Klassen als Vorlagen definiert. (Typische Vertreter: Java C#)
* Bei deklarativen Sprachen wird ein Problem und die Beziehungen zwischen den Teilproblemen beschrieben. In dieser Beschreibung steckt das Wissen zur Lösung des Problems. Man kann diese Sprachen einteilen in:
* //**Funktionale Sprachen:**// Das Programm besteht aus aufeinander bezogenen Funktionsdefinitionen. Es wird gestartet durch Funktionsaufrufe mit bestimmten Eingabedaten. Diese Eingabedaten werden durch Funktionsaufrufe in Ausgabedaten umgewandelt. (Typischer Vertrter: Haskell)
* //**Logische Sprachen:**// Das Programm besteht aus einer Niederschrift von Fakten und Regeln, wie aus den Fakten neue Fakten gewonnen werden können. Bei der Programmausführung werden Anfragen an das Programm gestellt die bestimmte Probleme, z.B. einen Beweis, lösen können. (z.B. Prolog)

Durch viele Programmiersprachen können mehrere Paradigmen umgesetzt werden. Eine kleine Übersicht gibt die nachfolgende Tabelle: ^ Sprache ^ prozedural ^ objektorientiert ^ funktional ^ logisch ^ ^ C | X | | | | ^ C++ | X | X | | |

^ Java | | X | | |

Perl	X	X
Python	X	X	X
Haskell	X
Prolog	X

>> Workshop: Erstellen von Programmen in verschiedenen Programmiersprachen

Erklärvideo

Im folgenden Video werden die Inhalte dieser Seite nochmal erklärt.

Aufgaben

Aufgabe 1

Beantworte die folgenden Fragen zum Inhalt der Seite und überprüfe deine Lösungen!

Aufgabe 2

Informiere dich im entsprechenden Wikipediaartikel über Programmiersprachen.

Aufgabe 3

Informiere dich über die Sprache Scratch. Erstelle online einen kleinen Algorithmus und lade dir die Datei herunter.

>> Lösung zur Aufgabe 1

>> Lineare Programme - Aus- und Eingabe