1.2 Algorithmen

Vorgehen vom Problem zur AUsführung

Im Diagramm links wird das typische Vorgehensmodell gezeigt welches von einer Problemstellung zur einer ausführbaren Anwendung führt.

  1. Lösungsidee: Der erste Schritt zur Lösung der in der Vorlesung vorgestellten Probleme basiert auf einer Idee zur Lösung des Problems
  2. Algorithmus: Im nächsten Schritt wird die Lösungsidee zu einem Algorithmus verfeinert und ausgearbeitet
  3. Programm: Ein wesentlicher Teil der Vorlesung wird aus der Umsetzung eines Algorithmus in ein ausführbares Java-Programm bestehen

Üblicherweise treten in jeder Phase Fehler auf, die ein Zurückgehen und Verbessern der Ergebnisse einer früheren Phase erfordern.

Algorithmus

  • Vorgehensbeschreibung, Handlungsanweisung
  • Alltagsbeispiele:
Kochrezept, Bastelanleitung, Partitur
  • Mathematische Beispiele:
    • 
Euklids ggT-Bestimmung, geometrische Konstruktionen
  • Name abgeleitet von Muhammed al-Chwarizmis Buch „Über das Rechnen mit indischen Ziffern“ (um 825)
  • Erster Computeralgorithmus:
1843 von Ada Lovelace für Charles Babbages Analytical Engine (Maschine wurde nicht vollendet)

Anforderungen an einen gültigen Algorithmus

  • Er verlangt gültige Eingaben und liefert definierte Ausgaben, durch die seine Korrektheit überprüft werden kann
  • Er umfasst endlich viele Einzelschritte und besteht aus hinreichend elementaren Anweisungen
  • Er ist in realistischer Zeit ausführbar
  • Er terminiert garantiert: d.h. ist nach endlich vielen Schritten fertig abgearbeitet, liefert ein Ergebnis und „hält an“
Definition
Algorithmus
  • Ein Algorithmus ist ein generelles, schrittweises, präzises, allgemeingültiges, endliches Lösungsverfahren für eine bestimmte Aufgabenart.
  • Er beruht auf elementaren Verarbeitungsschritten.
  • Alle Aufgaben einer bestimmten Art sind prinzipiell lösbar.