Algorithmusbegriff

Bereits aus den Klassenstufen 7 un 8 kennst du den Algorithmusbegriff. In Klasse 10 wollen wir nun den Begriff präzisieren.

Definition und Eigenschaften

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. Ein Algorithmus gibt an, wie Eingabegrößen schrittweise in Ausgabegrößen umgewandelt werden.

Endlichkeit: Ein Algorithmus besteht aus endlich vielen Anweisungen (Verarbeitungsbefehlen bzw. Regeln) endlicher Länge.

Eindeutigkeit: Mit jeder Anwendung ist auch die nächstfolgende festgelegt, d. h., die Reihenfolge der Abarbeitung der Anweisungen unterliegt nicht der Willkür des Ausführenden. (Man sagt auch: Algorithmen sind deterministisch). Das heißt, dass bei gleichen Bedingungen gleiche Eingabegrößen bei wiederholter Abarbeitung eines Algorithmus auf dieselben Ausgabegrößen abgebildet werden. (Man sagt auch: Algorithmen sind determiniert).

Ausführbarkeit: Jede einzelne Anweisung muss für den Ausführenden des Algorithmus verständlich und ausführbar sein. Ein Algorithmus ist also immer nur ein Algorithmus bezüglich des Ausführenden.

Allgemeingültigkeit: Ein Algorithmus muss auf alle Aufgaben gleichen Typs (Aufgabenklasse) anwendbar sein und (bei richtiger Anwendung) stets zum gesuchten Resultat (zur Lösung bzw. zur Einsicht, dass die Aufgabe nicht lösbar ist) führen.

1) Engelmann, Lutz (Hrsg.): Duden Informatik Lehrbuch S II, DUDEN PAETEC GmbH, Berlin 2006, S. 30-31

Algorithmische Grundstrukturen und Darstellungsformen

Bereits in Klasse 8 hast du verschiedene Darstellungsformen und algorithmische Grundstrukturen kennengelernt:

darstellungsformen.pdf

In der Klasse 10 wollen wir die algorithmischen Grundstrukturen mit Struktogrammen und in einer textorientierten Programmiersprache (Python) umsetzen.

darstellungsformen.pdf

Programme und Programmiersprachen

Ein Programm ist ein Algorithmus, der in einer für einen Computer verständlichen Sprache, einer Programmiersprache, verfasst ist.

Für Programmiersprachen gibt es verschiedene Möglichkeiten der Einteilung. Eine erste ist die Einteilung in

Maschinensprache: Sprache die nur aus Nullen und Einsen besteht und die Direkt von einem Bestimmten Prozessor ausgeführt werden kann.

Assemblersprache: Die Sprache benutzt symbolische Namen für Operanten und Operationen und ist damit leichter lesbar als reiner Maschinencode.

Höhere Programmiersprachen: Die Sprachen sind der natürlichen Sprache (meist Englisch) nachempfunden und weitestgehend vom Prozessor unabhängig.

Ein Prozessor kann nur Maschinencode ausführen. Damit ein Prozessor ein Assemblerprogramm ausführen kann muss es assembliert werden, damit er ein Programm in einer höheren Programmiersprache ausführen kann, benötigt man einen Compiler oder einen Interpreter (Siehe unten!).

Höhere Programmiersprachen kann man z.B. nach der Art des zugrunde liegenden Algorithmusbegriffs einteilen:

Je nach Art der Übersetzung in Maschinencode kann man höhere Programmiersprachen auch einteilen in

Compilersprachen: Der Quelltext des Programms wird durch den Compiler vollständig in Maschinencode übersetzt. Das entstandene Maschinenprogramm kann dann direkt ausgeführt werden. (z.B. C, C++, Rust)

Interpretersprachen: Der Interpreter übersetzt einen Befehl in Maschinencode und führt ihn aus, bevor er den nächsten Befehl übersetzt. (z.B. Python. PHP, Perl)

Mischtypen: In Compiler übersetzt das Programm in Bytecode, dieser wird dann von einem Interpreter ausgeführt.

Grundsätzliches Vorgehen beim Programmieren mit textorientierten Sprachen

Der Quelltext wird in einem Texteditor erstellt.

Bei Assemblerprogrammen wird das Programm vom Assembler übersetzt, gelinkt und kann dann ausgeführt werden.

Bei Compilersprachen wird das Programm zunächst vom Compiler übersetzt und kann dann direkt ausgeführt werden.

Bei Interpretersprachen wird das Programm direkt mit dem Interpreter aufgerufen und dadurch ausgeführt.

Beispiel: "Hallo Welt!"-Programm in Assembler

section .text global _start ;must be declared for using gcc _start: ;tell linker entry point mov edx, len ;message length mov ecx, msg ;message to write mov ebx, 1 ;file descriptor (stdout) mov eax, 4 ;system call number (sys_write) int 0x80 ;call kernel mov eax, 1 ;system call number (sys_exit) int 0x80 ;call kernel section .data msg db 'Hello, world!',0xa ;our dear string len equ $ - msg ;length of our dear string

Aufruf des Assemblers in der Kommandozeile:

nasm -f elf64 hallo.asm

Programm linken:

ld hallo.o -o hallo

Programm ausführen:

./hallo

Ausgabe:

Hello, world!

Beispiel: "Hallo Welt!"-Programm in C

#include <stdio.h> int main() { printf("Hello, World!\n"); return 0; }

Programm compilieren:

gcc hallo.c -o hallo

Programm ausführen:

./hallo

Ausgabe:

Hello, world!

Beispiel: "Hallo Welt!"-Programm in Python

print ("Hello, world!\n")

Programm ausführen:

python hallo.py

Ausgabe:

Hello, world!