Algorithmen
-
Algorithmus:
- Beschreibung eines allgemeinen Verfahrens zur
Lösung eines gegebenen Problems mit Hilfe einfacher Schritte
- soll immer in endlich vielen Schritten fertig
sein
- allgemein beschreibbar, unabhängig von einer
Programmiersprache
- meistens für (potentiell unendlich viele)
verschiedene Eingabewerte
- hier nur Algorithmen, die auf Computern
programmiert werden können
-
Beispiel:
- Addition zweier großer Zahlen
-
Beschreibung
- schreibe beide Zahlen stellenrichtig
untereinander
- addiere die Einerstellen
- Ergebnis < 10 →
schreibe das Ergebnis als letzte Stelle der
Summe
- Ergebnis ≥ 10 →
schreibe Einer des Ergebnisses als letzte
Stelle der Summe
markiere 1 als Übertrag in der vorletzten
Stelle
- Gehe analog für die nächsten Stellen vor,
wobei ggf. noch ein Übertrag aufaddiert wird
- Ein Übertrag in der ersten Stelle wird als 1
vor das Ergebnis geschrieben
- Was sind "einfache Schritte"? Hier z.B. Addition
von zwei einstelligen Zahlen
- Zahl der Schritte hängt von der Eingabe
(Stellenanzahl der Summanden) ab
-
Vergleich von Algorithmen:
- häufig verschiedene Algorithmen zur Lösung eines
Problems
- Vergleich der Algorithmen etwa nach Umsetzung in
Programm
- Unterschiede z.B. im Zeitaufwand (Rechendauer),
benötigtem Speicher, Programmieraufwand
-
Einsatz von Algorithmen:
- für viele wichtige Probleme gute (schnelle,
speichereffiziente, ...) Algorithmen vorhanden
- eigenen ad-hoc-Lösungen fast immer überlegen
-
Beispiele:
- schnelle Sortierverfahren wie Quicksort
- Zeichenverfahren auf Bildschirmen
(Pixelgraphik)
- schnelle Fourier-Transformation (FFT)
- häufig basieren bessere Algorithmen auf neuen
mathematischen Einsichten
- Merke: Ein Auto kaufen führt meist schneller zum
Ziel als das Rad neu erfinden