Algorithmus

Ein Algorithmus (auch genannt Lösungsverfahren) ist eine Handlungsvorschrift zur Lösung eines Problems in endlich vielen Schritten. Diese Verarbeitunsgsvorschrift besteht aus einer endlichen Folge von eindeutig ausführbaren Anweisungen, welche bei gleichen Voraussetzungen immer gleiche Ergebnise liefert. Der Algorithmus wird durch einen aus elementaren Anweisungen bestehenden Text beschrieben.

Definition und Eigenschaften eines Algorithmus

Mit Hilfe des Begriffs der Turing-Maschine kann folgende formale Definition des Begriffs formuliert werden:

Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.

Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar:

1. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
2. Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein (Ausführbarkeit).
3. Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, Platzkomplexität).
4. Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung).

Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt:

1. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
2. Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

gekürzt aus: Algorithmus

Eigenschaften von Algorithmen

Allgemeingültigkeit

Der Algorithmus löst eine Menge gleicher Probleme, einer ganzen Problemklasse.

Wiederholbarkeit

Bei gleicher Voraussetzung liefert ein Algorithmus immer ein gleiches Ergebnis.

Eindeutigkeit

An jeder Stelle ist der nachfolgende Schritt eindeutig definiert.

Endlichkeit/Terminiertheit

Der Algorithmus besteht aus einer endlichen Anzahl von Schritten und kommt immer zu einem Ende. Auch die Anweisungsfolge muss in einem endlichen Text beschrieben werden.

Ausführbarkeit

Die Anweisungen müssen ebenfalls verständlich formuliert und ausführbar sein.

Begriffsherkunft

Der Begriff Algorithmus stammt im Wesentlichen von Abu Abdallah Muhammad ibn Musa al-Khwarizmi, der im Jahr 825 das Buch „Al-kitab al-muchtasar fi hisab al-dschabr wa-l-muqabala“ veröffentlichte. Dieses Buch handelt von Regeln zur Wiederherstellung und Reduktion. Das Buch hatte großen Einfluss auf die arabische und europäische Mathematik. Es wurde auch ins lateinische übersetzt, dabei entwickelte sich aus dem Titel al-dschabr das Wort Algebra. Dieses Buch beginnt auch mit den Worten ”Dixit Algorithmi ...“, was so viel bedeutet wie ”Also sprach Algorithmi“. Dies ist eine Wortschöpfung, die vom Namen seines Geburtsortes al-Khwarizmi abgeleitet wurde.

Grundstrukturen

Algorithmen werden in Struktogrammen dargestellt.

1. Sequenz:

= Eine Folge von Anweisungen

2. Wiederholungen

2.1 Wiederholung

= Solange eine Bedingung erfüllt wird, wird die Aktion wiederholt.

2.2 Kopfgesteuerte Schleife

= Solange eine Bedingung erfüllt wird, wird eine Aktion ausgeführt.

2.3 Fußgesteuerte Schleife

= Eine Aktion wird solange ausgeführt, bis eine Bedingung erfüllt wird.

3. Verzweigung

= Wird eine Bedingung erfüllt (Ja), wird Aktion 1 ausgeführt. Wird die Bedingung nicht erfüllt (Nein), wird Aktion 2 ausgeführt

Beispiele für Algorithmen

Mathematik

• Divisionsalgorithmus
• Euklidischer Algorithmus
• Sieb des Eratosthenes zur Bestimmung von Primzahlen

Informatik

• Sortierverfahren

Alltagsalgorithmen

In unserem Alltag gibt es oft Situationen, bei denen wir Algorithmen benutzen. Wie zum Beispiel beim Kaffeekochen oder beim Computer-Hochfahren. Das Kaffeekochen und das Computer-Hochfahren sind Algorithmen, da man diese Vorgänge immer gleich ausübt.

Weitere Beispiele sind:

• Kochrezepte
• Spielen einer Melodie
• Reparatur- und Bedienungsanleitungen
• Hilfen zum Ausfüllen von Formularen

Algorithmus zum Kaffeekochen

• Fülle Wasser in Kanne füllen
• Kanne in Kaffeeautomaten setzen
• Filter in Kaffeeautomaten legen
• Kaffeepulver in Filter füllen
• Kaffeemaschine anschalten
• Tasse aus Schrank holen
• Wenn Kaffee durchgelaufen ist, in Tasse gießen

Algorithmus zum Computer-Hochfahren

• Startknopf des Computers drücken
• Bildschirm einschalten
• Computer hochfahren lassen
• Ein Konto aussuchen
• Passwort eingeben (sich anmelden)

Algorithmus zum Schreiben und Absenden eines Briefes

Algorithmus zum Schreiben und Absenden eines Briefes

• Text auf Blatt schreiben
• Blatt in Umschlag stecken
• Umschlag zukleben
• Wenn Adresse des Empfängers bekannt, dann schreibe Adresse auf Umschlag, sonst suche Adresse im Adressbuch und schreibe Adresse auf den Umschlag
• Eine Poststation aufsuchen
• Wenn Briefgewicht < 20 Gramm, dann kaufe 55-Cent-Briefmarke, sonst kaufe 90-Cent-Briefmarke
• Briefmarke aufkleben
• Brief absenden

Algorithmus zum Zähneputzen

Algorithmus zum Zähneputzen

Beim Zähneputzen kann das Problem auftreten, dass die Zahnpastatube leer ist und man diese wechseln muss. Bei voller Tube nimmt man sie weiterhin, jedoch beim Leeren der Pasta muss man entweder eine neue aus dem Schrank nehmen oder, falls keine da ist, in den Laden gehen und eine kaufen.

Algorithmus zum Bestimmen von Mineralien

Problemstellung: Man besitzt zwei Mineralien (Smaragd und Rubin), die zu bestimmen sind.

Algorithmus zum Bestimmen von Mineralien

Algorithmus zum Fensteröffnen

Algorithmus zum Fensteröffnen

• wenn man sitzt, dann aufstehen
• zum Fenster gehen
• zum Ankippen den Hebel nach oben drehen
• zum Öffnen den Hebel in die Waagerechte bringen

Auto fahren

Algorithmus zum Motor starten und Losfahren eines Autos mit Automatikgetriebe

• Zündung betätigen
• Licht einschalten
• Handbremse oder Parkbremse lösen
• Gang auf „Drive“ oder „Fahren“ schalten
• Gaspedal betätigen

„Mc Drive“

• An Ausgabeluke heranfahren
• Bestellung abgeben
• Bezahlen
• Bestellung entgegennehmen
• Wegfahren

Spezielle Algorithmen und Algorithmusklassen

Genetische Algorithmen

Die Grundidee genetischer Algorithmen ist, ähnlich der biologischen Evolution, eine Anzahl Lösungskandidaten (Individuen) zufällig zu erzeugen und diejenigen auszuwählen, die einem bestimmten Gütekriterium am besten entsprechen. Deren Eigenschaften (Parameterwerte) werden dann leicht verändert und miteinander kombiniert, um neue Lösungskandidaten (eine neue Generation) zu erzeugen. Algorithmus Genetischer Algorithmus, Wikipedia – Die freie Enzyklopädie, 21.05.06 - Der Text ist unter der Lizenz „Creative Commons Attribution/Share Alike“ verfügbar; zusätzliche Bedingungen können anwendbar sein. Siehe die Nutzungsbedingungen für Einzelheiten. In der Wikipedia ist eine Liste der Autoren verfügbar.

• Beispiele in Java mit Links und Literaturhinweisen
• Einführung für den Unterricht mit Beipielen in Java.

Algorithmus der Woche beim Informatikjahr

• Algorithmus der Woche

    Binäre Suche 
    Sortieren durch Einfügen 
    Schnelle Sortieralgorithmen 
    Zahlen richtig aussprechen 
    Labyrinth und Tiefensuche 
    Roboter im Labyrinth 
    Kürzeste Wege 
    Topologisches Sortieren 
    Eulerkreise 
    Page-Rank-Algorithmus 
    Broadcasting (Gerüchte verbreiten) 
    Paralleles Sortieren 
    Fehlererkennende Codes

Unterrichtsidee

Übung

• Lassen Sie einen Algorithmus entwickeln und durchspielen. Sind die Kriterien für einen Algorithmus erfüllt?
• Lassen Sie einen Algorithmus von einem Schüler für einen anderen Schüler schreiben. Ggf. kann man die Zielbeschreibung zunächst verheimlichen und dann diskutieren, ob der Algorithmus das getan hat, was er sollte.

Der Einstieg in eine Unterrichtseinheit zu Algorithmen kann auch über einen Lehrtext geschehen. Hier ein Beispiel zu einem Lehrtext, der auch Aufgaben zu unterschiedlichen Kompetenzstufen enthält:  Lehrtext zu Algorithmen

Weblinks

• Liste von Algorithmen
• selfhtml: Einführung in die Programmierlogik
• Sieb des Eratosthenes