Algorithmus

Vorlage:Babel-3 Unter einem Algorithmus versteht man eine genau definierte Handlungsvorschrift zur Lösung eines Problems.

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, 21.05.06

Beispiele für Algorithmen

Mathematik

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

Alltag

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

Informatik

• Sortierverfahren

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. 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: {{{2}}}

Weblinks

• Liste von Algorithmen