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:
- Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
- Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein (Ausführbarkeit).
- Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, Platzkomplexität).
- 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:
- Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
- 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.
Struktogramm
Algorithmen werden in Struktogrammen dargestellt.
Grundstrukturen
Anweisungsblock (Sequenz)
= Eine Folge von Anweisungen
Schleifen (Wiederholungen)
= Solange eine Bedingung erfüllt wird, wird die Aktion wiederholt.
Kopfgesteuerte Schleife
= Solange eine Bedingung erfüllt wird, wird eine Aktion ausgeführt.
Fußgesteuerte Schleife
= Eine Aktion wird solange ausgeführt, bis eine Bedingung erfüllt wird.
bedingte Anweisung (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
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
- 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
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 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.
|
- Beispiele in Java mit Links und Literaturhinweisen
- Einführung für den Unterricht mit Beipielen in Java.
Algorithmus der Woche beim Informatikjahr
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
- 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
