Algorithmus
Definition
«Ein Algorithmus beschreibt die Methode, mit der eine Aufgabe gelöst wird. Ein Algorithmus besteht aus einer Folge von Schritten, deren korrekte Abarbeitung die gestellte Aufgabe löst. Die Abarbeitung oder den Vorgang selbst bezeichnet man als Prozeß.»
Les Goldschlager/Andrew Lister: Informatik, 1984
Damit wir von einem Algorithmus sprechen, müssen also zwei Bedingungen erfüllt sein:
- Es muss eine Schritt-für-Schritt-Anleitung vorliegen.
- Diese Schritt-für-Schritt-Anleitung muss eine Aufgabe oder ein Problem lösen.
Die folgende Tabelle zeigt ein paar Beispiele von Prozessen mit zugehörigem Algorithmus:
| Prozess | Algorithmus | Typischer Schritt |
|---|---|---|
| Kranich falten | 👉 Faltanleitung | Papier entlang einer Linie falten |
| Möbel zusammenbauen | 👉 Bauanleitung | Schraube anziehen |
| Musikstück spielen | 👉 Notenblatt | Ein c' spielen |
EVA
Algorithmen folgen dem Grundprinzip der Informatik: EVA (Eingabe, Verarbeitung, Ausgabe). Dabei wird eine Eingabe verarbeitet und es entsteht eine Ausgabe. Die Verarbeitung erfolgt in mehreren Schritten, die nacheinander abgearbeitet werden.
EVA
Anforderungen
Wir können Algorithmen auf verschiedenen Anforderungen hin prüfen:
Anforderungen an Algorithmen
| Anforderung | Beschreibung | Erklärung / Beispiel |
|---|---|---|
| Allgemeinheit | Es soll nicht nur ein einzelnes Problem gelöst werden. | Ein Addier-Algorithmus nicht nur 7 + 4 addieren können, sondern zwei beliebige natürliche Zahlen. |
| Eindeutigkeit | Die Abfolge der einzelnen Schritte soll genau festgelegt sein. Es soll zu jedem Zeitpunkt klar sein, welcher Schritt als nächstes ausgeführt werden muss. | Ein Algorithmus sollte keine Angaben machen wie «jetzt könnte man beispielsweise…» |
| Ausführbarkeit | Man (respektive, ein Prozessor) muss jeden Einzelschritt des Algorithmus auch wirklich ausführen können. | Ein Algorithmus sollte keine Schritte enthalten, die nicht ausführbar sind, wie z.B. «den Himmel berühren». |
| Endlichkeit | Ein Algorithmus soll immer nach einer endlichen Anzahl Schritte zu einer Lösung kommen und auch nur endlich viel Platz auf dem Computer beanspruchen. | Benötigt er unendlich lange, erhält man nie ein Ergebnis. Benötigt er unendlich viel Platz, kann ihn kein Computer der Welt speichern und ausführen. |
| Korrektheit | Ein Algorithmus soll für alle möglichen (erlaubten) Eingaben zu einer korrekten Lösung kommen. | Ein Sortier-Algorithmus sollte immer die Elemente in der richtigen Reihenfolge sortieren. |
| Determiniertheit | Ein Algorithmus soll mit den gleichen Eingabewerten immer zur gleichen Ausgabe kommen. Es sollte keinen Zufallsfaktor geben. | Die Quadratwurzel aus 49 muss immer 7 geben. |
Diese Anforderungen entscheiden nicht, ob es sich um einen Algorithmus handelt oder nicht. Wir nutzen sie, um Algorithmen zu beschreiben.
In der Praxis erfüllen Algorithmen nicht zwingend alle Anforderungen:
- Eindeutigkeit, Ausführbarkeit, Endlichkeit und Korrektheit sollten immer erfüllt sein, damit wir einen brauchbaren Algorithmus haben.
- Determiniertheit ist generell wünschenswert, allerdings nicht immer zwingend notwendig, und manchmal sogar unerwünscht.
- Allgemeinheit ist eine wünschenswerte Eigenschaft, aber grundsätzlich nicht zwingend notwendig.
Übungen
Gehen Sie bei jeder der folgenden Aufgaben wie folgt for:
- Überlegen Sie sich, ob es sich hier um einen Algorithmus handelt, oder nicht. Notieren und begründen Sie Ihre Antwort in ersten der beiden Textfelder.
- Basierend auf Ihrer Entscheidung…
- Wenn es sich um einen Algorithmus handelt, analysieren Sie nun, welche der sechs Kriterien hier erfüllt sind und welche nicht. Begründen Sie jeweils kurz. Halten Sie Ihre Antwort im zweiten Textfeld fest.
- Wenn es kein Algorithmus ist, dann können Sie den zweiten Teil der Aufgabe überspringen. Die sechs Kriterien lassen sich nur auf Algorithmen anwenden.
Manchmal müssen Sie gewisse Annahmen treffen, um eine Antwort geben zu können. Halten Sie diese Annahmen jeweils in Ihrer Antwort fest!
Aufgabe 1
Eine Lego-AnleitungHandelt es sich hier um einen Algorithmus? Wieso (nicht)?
Sofern es sich um einen Algorithmus handelt: Welche der sechs Anforderungen sind erfüllt? Begründen Sie.
Aufgabe 2
Ein ZeitungsartikelHandelt es sich hier um einen Algorithmus? Wieso (nicht)?
Sofern es sich um einen Algorithmus handelt: Welche der sechs Anforderungen sind erfüllt? Begründen Sie.
Aufgabe 3
Ein StundenplanHandelt es sich hier um einen Algorithmus? Wieso (nicht)?
Sofern es sich um einen Algorithmus handelt: Welche der sechs Anforderungen sind erfüllt? Begründen Sie.
Aufgabe 4
Ein OrganigrammHandelt es sich hier um einen Algorithmus? Wieso (nicht)?
Sofern es sich um einen Algorithmus handelt: Welche der sechs Anforderungen sind erfüllt? Begründen Sie.
Aufgabe 5
Eine Knotensammlung (z.B. als Poster)Handelt es sich hier um einen Algorithmus? Wieso (nicht)?
Sofern es sich um einen Algorithmus handelt: Welche der sechs Anforderungen sind erfüllt? Begründen Sie.
Aufgabe 6
Info-Plakat: Hände richtig waschenHandelt es sich hier um einen Algorithmus? Wieso (nicht)?
Sofern es sich um einen Algorithmus handelt: Welche der sechs Anforderungen sind erfüllt? Begründen Sie.
Aufgabe 7
Eine Wegbeschreibung:
Start: Ländtestrasse 12, Biel, Gebäude D, Ausgang Strasse
schräg rechts zur Ampel
Zebrastreifen überqueren, dem Weg für 130m folgen
Rechts abbiegen auf Dammweg / Aarbergstrasse
Dem Weg bis zum Parkplatz folgen
Treppe heruntergehen
Zebrastreifen überqueren
Parkplatz überqueren
Ziel: Bahnhof Biel \
Handelt es sich hier um einen Algorithmus? Wieso (nicht)?
Sofern es sich um einen Algorithmus handelt: Welche der sechs Anforderungen sind erfüllt? Begründen Sie.
Aufgabe 8
Deutsches Braille-AlphabetHandelt es sich hier um einen Algorithmus? Wieso (nicht)?
Sofern es sich um einen Algorithmus handelt: Welche der sechs Anforderungen sind erfüllt? Begründen Sie.
Abschlussquiz
quiz) ist eine Anmeldung erforderlich.⭐️ Al-Chwarizmi
Abu Dschaʿfar Muhammad ibn Musa al-Chwārizmī war ein Mathematiker und Universalgelehrter. Er stammte zwar aus dem iranischen Choresmien, verbrachte jedoch den größten Teil seines Lebens in Bagdad und war dort im «Haus der Weisheit», einer Art Akademie, tätig.
Al-Chwarizmi gilt als einer der bedeutendsten Mathematiker, da er sich mit Algebra als elementarer Untersuchungsform beschäftigte.1
In der lateinischen Übersetzung eines Werkes von Al-Chwarizmi wurde sein Name als «algorismus» geschrieben. Davon leitet sich der heutige Begriff «Algorithmus» ab.2
Abbildung von Al-Chwarizmi auf einer sowjetischen Briefmarke