| Algorithmen | Anwendung und Probleme |
| Ersatz | Alternativen für fehlende Konstanten und Formeln |
| Winkelfunktionen | Spezielle Probleme trigonometrischer Funktionen |
| Links |
Ausgewählte
Links zum Thema 'Algorithmen'
|
| Diese Seite bietet Links zu jenen Algorithmen, die im Web von PS-Trainer demonstriert werden. Diese Sammlung ist subjektiv und erhebt keinerlei Ansprüche. |
Die Verwendung steht frei, insoferne nicht die Rechte anderer dabei verletzt werden,
erfolgt jedoch auf eigenes Risiko. Keine Garantie auf Sicherheit oder korrekte Programmierung ! |
| Algorithmen | Anwendung und Probleme |
| Ersatz | Alternativen für fehlende Konstanten und Formeln |
| Winkelfunktionen | Spezielle Probleme trigonometrischer Funktionen |
| Links |
Ausgewählte
Links zum Thema 'Algorithmen'
|
| Astronomie | Erdbahn, Erdachse, Julianischer Tag, Ortszeit, Sonnenstand, Sternzeit, Zeitgleichung, |
| Datum & Zeit |
Umwandlung interner Formate
(Timestamp,
JD,
MJD,
Y1900,
FMP, ..),
Kalender (Woche), Zeit (Zonenzeit, Mittlere und Wahre Ortszeit, Sternzeit, Zeitgleichung, ..) |
| Informatik |
Bit-Level
(Binärzahlen, Bool-Operatoren, Shift) Ganze Zahlen (Abschneiden, Runden, Modulo), 2er-Komplement (negative Zahlen) Gleitkomma (IEEE-754), Zeichensatz (UTF-8) Reguläre Ausdrücke |
| Kartografie |
Länge & Breite,
UTM,
Berechnungen,
Österr.Karten,
Interaktive Weltkarte
|
| Mathematik | Mittelwerte (Glättung, Ausgleichsgerade) |
| Physik | Farbe (Schwarzkörper→RGB, Wellenlänge→RGB) |
| RegExp | Reguläre Ausdrücke zur professionellen String-Verarbeitung |
| Schrift & Druck | Standard-Papierformate, Schriftgröße (Typografische Einheiten) |
Statistik
|
Zufallszahlen-Erzeugung (Verteilungen, Mischen), Ausgleichsgerade |
Algorithmen |
|
|
Algorithmen sind "Rezepte" der Informatik: Eine Zusammenstellung
von Anweisungen, welche dem jeweiligen Zweck dienen. Einfache Beispiele können mit Kalkulations-Programmen realisiert werden, für die meisten Aufgaben benötigt man jedoch Programmiersprachen. |
Typische Algorithmen enthalten Rechnungen, Verzweigungen und Schleifen. Die angeführten Beispiele sind in unterschiedlichen Programmiersprachen erstellt, je nach dem "historischen" Ursprung. |
|
Im Internet und in Büchern findet man unzählige Algorithmen.
Nur die wenigsten davon sind allerdings praktisch verwendbar:
Bei der Umsetzung in eine Kalkulation oder in eine Programmiersprache,
spätestens bei ausgiebigen Tests versagen die meisten.
Einzig jene Funktionen, die fix im Liefer-Umfang von Software enthalten sind,
sind einigermaßen verlässlich. Nachfolgend eine Liste häufig gefundener Probleme. |
Für die in diesem Web vorgestellten Algorithmen wurde daher besondere Vorsicht
angewendet. Trotzdem kann es passieren, dass noch Fehler enthalten sind.
Hier gilt wie überall in diesem Web:
Die Anwendung aller Beispiele erfolgt auf eigenes Risiko !
|
Häufig aufgefundene Fallstricke:Mathematische (physikalische, technische, ..) Formeln
Nur einfache Formeln lassen sich problemlos in Programme umsetzen. Integrale,
komplexe Zahlen, Vektoren, .. erfordern spezielle Maßnahmen. Ein eigener
Zweig (Numerische Mathematik) der Wissenschaft beschäftigt sich u.a. damit,
symbolische Formeln mit realen Daten zu berechnen. Suchen sie nach numerischen
Lösungen, Reihen-Entwicklungen, Polynomen, ..Werte-Bereich
Viele Funktionen haben einen eingeschränkten Werte-Bereich, d.h. man darf
sie nur mit bestimmten Argumenten verwenden. Wenn solche Funktionen in Algorithmen
verwendet werden, dann ist der gesamte Algo anfällig für Fehler -
Meist wird darauf nicht hingewiesen, nur in sehr seltenen Fällen werden
diese Tatsachen korrekt berücksichtigt.+ Bedingte Verzweigung: Ein guter Algo muss alle Sonderfälle erkennen, abfangen und getrennt behandeln. + Fehler: Manchmal ist es notwendig, einen Fehler mitzuteilen. Die meisten Algorithmen kümmern sich leider nicht darum und überlassen es z.B. dem Betriebssystem, mit einer Division durch 0 zurechtzukommen.Prüfen sie bei fremden und eigenen Algorithmen, ob Fehler auftreten können, und was dann passiert. Kulturelle Arroganz und Ignoranz
+ Geografie: Viele Algorithmen sind nur für die
Nordhalbkugel der Erde ausgelegt, manche nur für westliche Länge von
Greenwich. Suchen sie solche Algorithmen zum Vergleich auch in australischen
oder neuseeländischen Webs.Zusätzlich gelten die 'trigonometrischen Warnungen': Vorsicht, wenn einzelne oder mehrere Argumente (Parameter) den Null-Meridian oder den Äquator überschreiten ! + USA Die USA verwenden auf vielen Gebieten andere als die international üblichen Normen. Selbst von den USA anerkannte Standards werden oft ignoriert. Nur wenige Firmen und BürgerInnen haben Kenntnisse von anderen Kulturen, und neigen in jedem Fall zur ungewarnten (!) Verwendung abweichender US-Einheiten und Regeln. Ein spezielles Problem ist der Software-Marktführer: In dessen Software werden Standards häufig ignoriert und torpediert. Sogar offensichtliche Fehler werden manchmal nicht ausgebessert, sondern zu einer Art von aufgezwungenem Standard deklariert. |
Trigonometrische Funktionen:
Wenn solche Funktionen vorkommen, ist besondere Vorsicht geboten:+ Einheiten: Für Menschen meist Grad, für Funktionen immer (!) das Bogenmaß (rad). Selten werden Neugrad (gon) verwendet. + Richtungs-Angaben sind nicht einheitlich: Winkel werden (nur) in der Mathematik von der x-Achse entgegen dem Uhrzeiger angegeben. In allen praktischen Anwendungen (Astronomie, Kartografie, ..) werden Winkel von Nord (y-Achse) in Richtung des Uhrzeigers angegeben. In der Informatik wird die y-Achse oft umgedreht: Für Monitore und Grafik liegt der Ursprung in der linken oberen Ecke, y-Werte nehmen nach unten (!) zu. + Fehler: Einige Funktionen ergeben bei bestimmten Winkeln Fehler. Die Winkel 0°, 90°, 180°, 270° und 360° müssen oft abgefangen und getrennt behandelt werden. + Periode: In der Geometrie ist der Anstieg einer Geraden von 45° oder 225° äquivalent. Für praktische Anwendungen (z.B. Orientierung) besteht jedoch ein erheblicher Unterschied zwischen NO und SW, den man im Algorithmus abfangen und berücksichtigen muss. + 3D: Bei 3dimensionalen Systemen sind übliche Formeln aus Büchern und Internet nur selten brauchbar. Die meisten dieser Algorithmen haben einen eingeschränkten Anwendungs-Bereich. Beim Überschreiten der Grenzen (xy-Ebene, yz-Ebene, Äquator-Ebene, ..) ergeben sich oft Fehler, im schlimmsten Fall unbemerkt falsche Werte. Dagegen hilft nur ausführliche Recherche, klug angelegte Tests, in manchen Fällen Drehung oder Spiegelung eines Systems, bis es wieder in den zulässigen Bereich fällt. Implementierung von Funktionen:
Leider sind nicht alle in der Informatik verwendeten Funktionen wirklich normiert.
Manchmal verhalten sich gleichnamige oder ähnliche Funktionen in verschiedenen
Programmier-Sprachen teilweise unterschiedlich. Durch ungeprüfte Übernahme
von Algorithmen in eine andere Umgebung entstehen Fehler, die sich oft über
viele offenbar voneinander abgeschriebene Webseiten erstrecken.Deshalb werden u.a. die Beispiele dieses Webs nach Möglichkeit mit Zahlen-Beispielen demonstriert. Die Zahlen lassen sich leicht mit eigenen Programmen vergleichen. |
Ersatz für Konstanten und Formeln |
|
|
Die nachfolgende Sammlung entstand in leidvoller Erfahrung, auf der Suche nach
Funktionen, die von einer Software oder Programmiersprache
nicht unterstützt werden. Für die Angaben gibt es keine Garantie: Die Anwendung erfolgt auf eigenes Risiko. |
Im einfachsten Fall ist eine Funktion vorhanden, allerdings unter einem ungewöhnlichen Namen. Suchen sie daher nach alternativen englischen/deutschen Funktionsnamen und phantasievollen Abkürzungen. |
|
Konstanten
Kreiszahl
(Archimedes-Zahl, Ludolph-Zahl) pi = π
pi = 4 * arctan(1) = 3.141592653589793238462643383... |
Euler-Zahl
e
e = exp(1) = 2.7182818284590452353602875... |
|
Logarithmus und Exponential
Dekadischer Logarithmus (Basis 10) oder einer beliebigen Basis
log10(x) = ln(x) / ln(10)
logn(x) = ln(x) / ln(n) Trigonometrische Funktionen
Ein eigenes Kapitel ↓
demonstriert die zahlreichen Stricke und Fallen bei der praktischen Anwendung der
Winkelfunktionen.
|
Spezielle Ganzzahlen-Funktionen wie z.B. zum Abschneiden oder Isolieren von Nachkomma-Stellen, zum Runden oder die Modulo-Funktion verhalten sich leider in verschiedenen Programmier-Sprachen durchaus unterschiedlich. Diese Funktionen werden oft verwendet, ihre Unterschiede sind wenig bekannt. Das führt oft zu hartnäckigen Problemen bei der Übernahme von Algorithmen in andere Programmiersprachen. Leider enthalten auch viele Algo-Beispiele im Internet solche Fehler - sie wurden offenbar zu wenig getestet. ♦ Details dazu: Spezielle Ganzzahlen-Funktionen. |
Winkelfunktionen |
|
| Trigonometrische (Winkel)-Funktionen führen bei der Programmierung zu einigen praktischen Problemen. Es gibt einige erhebliche Unterschiede zwischen der theoretischen Darstellung im Formel-Verzeichnis und der praktischen Anwendung. |
Typische Problem-Felder: • Unterschiedliche Einheiten, Mischung, Verwechslung • Unterschiedliche Periode, mehrdeutige Ergebnisse • Fehlende Funktionen und ungewohnte Funktions-Namen |
|
Einheiten:
Leider wird das verwendete Maß nicht immer angegeben. Wenn eine Formel
oder ein Algorithmus nicht wie erwartet funktioniert, dann versucht man zuerst
ein anderes Maß• In der Geometrie (Formel-Sammlungen) wird meist das Grad-Maß 0..grad..360 verwendet. • In der Informatik (in allen Kalkulations-Programmen, Programmiersprachen, etc.) wird fast ausschließlich das Bogenmaß 0..rad..2pi verwendet.
rad(x) = grad(x) / 180 * pi
Bessere Taschenrechner erlauben die Umschaltung zwischen Grad- und Bogenmaß.grad(x) = rad(x) / pi * 180 • Durch die französische Revolution wurden viele heute verwendete Einheiten eingeführt. Neugrad 0..gon..400 haben sich ausnahmsweise nicht durchgesetzt, werden aber vereinzelt im französischen Sprachraum angewendet. |
• In der Astronomie werden einige spezielle Winkel (z.B. Rektaszension, Stundenwinkel) im Stundenmaß 0..ra..24 angegeben.
ra(x) = grad(x) / 15
Dieses Maß wird teilweise auch in der militärischen Orientierung
('Richtung 10 Uhr') eingesetzt.grad(x) = ra(x) * 15 • Die Himmelsrichtung ist sehr Praxis-freundlich: N NNO NO ONO O OSO SO SSO S SSW SW WSW W WNW NW NNW N
Diese Angabe ist in vielen Fällen besser verständlich als ein numerischer
Richtungs-Winkel, wird jedoch in der Informatik bei der Ausgabe von Daten sehr
vernachlässigt.
|
|
Null-Winkel
Ein Winkel ist ein relatives Maß (z.B. zwischen 2 Geraden).Leider wird oft nur 1 Bezugs-Element angegeben: In diesen Fällen ist der Winkel realtiv zu einem Null-Winkel gemeint. Der Null-Winkel unterscheidet sich je nach Wissenschaft und Arbeits-Gebiet ! Er wird leider fast nie angegeben und im schlimmsten Fall darüber hinaus sogar gewechselt. Zähl-Richtung
Jeder Winkel lässt sich entweder in Richtung des Uhrzeigers oder
entgegengesetzt angeben.Bildverarbeitung
Eine häufige Fehlerquelle ist die Tatsache, dass die Y-Achse in der
Bildverarbeitung vom Ursprung (linke obere Ecka) nach unten
wächst und nicht nach oben wie bei fast allen anderen Anwendungen (und Formeln).
|
Innerhalb einer Wissenschaft oder eines Arbeits-Gebiets gelten meist (aber nicht immer) einheitliche Regeln. Diese werden leider als selbstverständlich vorausgesetzt und daher fast nie angegeben.
Bei der Anwendung von Formeln oder Algorithmen ergeben sich jedoch je nach den
angenommenen Regeln erhebliche Unterschiede - Die Formeln müssen je nach
Anwendung adaptiert werden !
● In der Geometrie (und in den meisten Formel-Sammlungen) ist der Winkel 0° meist nach rechts orientiert und wächst entgegen der Richtung des Uhrzeigers. ● In allen praktischen Anwendungen (Orientierung, Kartografie, Astronomie, ...) ist der Winkel 0° nach Nord orientiert und wächst in Richtung des Uhrzeigers. |
|
Periode
●
Beim Durchlaufen eines vollen Kreises nimmt der Betrag (Wert) eines Winkels
(z.B. in Grad) kontinuiertlich zu und ist immer eindeutig.● Die Werte der Winkelfunktionen sind für einen Kreis-Umlauf nicht eindeutig: sin,cos ergeben je 2mal die gleichen Werte, tan,ctg je 4mal. Das wirkt sich bei der Umkehrung der Winkelfunktionen unangenehm aus: Funktionen wie arcsin, arccos, arctan, arcctg ergeben rechnerisch nur 1 Ergebnis, praktisch jedoch 2 bzw. 4 Ergebnisse. Das wirkt sich in der Geometrie nicht aus, wenn man die Lage von Geraden oder Ebenen beschreibt, da man sie als unendlich ausgedehnt annimmt. ● In allen praktischen Anwendungen besteht jedoch ein erheblicher Unterschied, z.B. zwischen den Richtungen Nord und Süd. Man muss daher entweder 2 (4) Ergebnisse berücksichtigen oder mit Hilfe zusätzlicher Angaben (Quadrant) eines der Ergebnisse auswählen. Das findet man in keiner Formel-Sammlung ... |
Negative Winkel
Der Betrag eines Winkels ist nicht auf den Bereich 0..360° beschränkt,
sondern kann auch negativ oder >360° werden.In der Praxis werden negative Werte ziemlich oft verwendet. Die Geografische Länge wird z.B. entweder 0..lon..360° oder -180°..lon..+180° angegeben, die Breite immer -90°..lat..+90° Diese Tatsache muss insbesondere bei Eingabe und Ausgabe (User Interface) berücksichtigt werden: Bei der ← Umkehrung der Winkelfunktionen ergibt das z.B. für arcsin,arccos entweder 3 mögliche Ergebnisse, oder 2 Ergebnisse, von denen eines einen Winkel <0° angibt. In Algorithmen ist es meistens sinnvoll, Winkel auf den Bereich 0..2pi umzurechnen, wenn sie als Zwischen-Ergebnisse auftreten. Dazu verwendet man am besten speziell angepasste Modulo-Funktionen. In einigen Fällen ist das jedoch unzulässig: Es ist nicht äquivalent, ein Lenkrad um 350° (nach rechts) oder um -10° (nach links) zu drehen ! |
|
Sonderfälle
Viele Winkelfunktionen ergeben für spezielle Argumente Fehler-Werte.
Gute Algorithmen dürfen keine Fehler ergeben: Man muss die Sonderfälle
daher kennen, abfangen und gesondert behandeln.
|
Dafür lassen sich keine verbindlichen Regeln angeben, da die Reaktion eines Programms je nach Anwendung unterschiedlich ausfallen muss. ♣ Tipp: Testen sie (auch in Zwischen-Ergebnissen) immer die verdächtigen Winkel 0°, 90°, 180°, 270°, 360° |
|
Fehlende Funktionen
In der Informatik gibt es kaum Umgebungen, in denen alle trigonometrischen
Funktionen angeboten werden.Viele davon können durch immer verfügbaren Funktionen ersetzt werden (einige unverbindliche Beispiele) Verwendete Funktions-Namen: In den gezeigten Beispielen steht x^2 für x*x = x2
atn = arctan
sgn = Vorzeichen-Funktion (-1,0,+1) sqr = sqrt = wurzel tg = tan |
Standard-Funktionen
tan(x) = sin(x) / cos(x)
ctg(x) = 1 / tan(x) = cos(x) / sin(x) Umkehrung der Standard-Funktionen
arccos(x) = arctan(-x / sqr(-x * x + 1)) + 2 * arctan(1)
arctan - wird oft auch mit atn
bezeichnet !
arcctg(x) = arctan(x) + 2 * arctan(1) arcsin(x) = arctan(x / sqr(-x * x + 1)) |
|
Hyperbolische Funktionen
sinh(x) = 1/2 * (exp(x) - exp(-x))
sinh(x) = sqr(cosh(x)^2 + 1) cosh(x) = 1/2 * (exp(x) + exp(-x)) cosh(x) = sqr(sinh(x)^2 + 1) tanh(x) = sinh(x) / cosh(x) tanh(x) = (exp(x) - exp(-x)) / (exp(x) + exp(-x)) arcsinh(x) = ln(x + sqr(x^2 + 1)) arcsinh(x) = arctanh(x / sqr(x^2+1)) arccosh(x) = ln(x + sqr(x^2 - 1)) arccosh(x) = arctanh(sqr(x^2-1) / x) arctanh(x) = 1/2 * ln((1+x) / (1-x)) für -1..x..+1 arcctgh(x) = 1/2 * ln((x+1) / (x-1)) |
Secans und Cosecans
sec(x) = 1 / cos(x)
cosec(x) = 1 / sin(x) arcsec(x) = arctan(x / sqr(x*x-1)) + sgn(|x|-1) * (2*arctan(1)) arccosec(x) = arctan(x / sqr(x*x-1)) + (sgn(x)-1) * (2*arctan(1)) sech(x) = 2 / (exp(x) + exp(-x)) cosech(x) = 2 / (exp(x) - exp(-x)) arcsech(x) = ln((sqr(-x^2 + 1) + 1) / x) arccosech(x) = ln((sgn(x) * sqr(x^2 + 1) + 1) / x) |
|
Beispiel
Die Funktion modrad (eine angepasste Variante der
Modulo-Funktion) rechnet jeden
Winkel wb (im Bogenmaß) in den
Bereich 0..2pi um.Damit kann z.B. man negative Winkel eliminieren, wenn das zulässig ist. |
Function modrad(wb As Double) As Double
Dim k As Double
k = 8 * Atn(1)
End Function
modrad = wb - Int(wb / k) * k |
|
Beispiel
Diese Funktion gibt die Himmelsrichtung für einen Winkel in
Grad 0..wg..360 zurück. Die Funktion liefert die
meist verwendeten 8 Richtungen und lässt sich leicht für 4 oder 16
Richtungen adaptieren, ebenso natürlich für Winkel im Bogenmaß.Der zulässige Werte-Bereich des Winkels muss unbedingt eingehalten (oder vorher sichergestellt) werden. |
Function hiri_grad(wg As Double) As String
Dim i As Integer Dim hr As Variant
hr = Array("N", "NO", "O", "SO", "S", "SW", "W", "NW", "N")
End Function
i = CInt(Round(wg / 45, 0)) hiri_grad = CStr(hr(i)) |
|
Beispiel:
Programmierung der fehlenden Funktionen arcsin,arccos
in VBA (ohne Gewähr).• Pi (π) wird hier als globale Variable eingesetzt und nur einmal (bei der ersten Verwendung) berechnet. Alternative: Verwendung als Konstante. • Funktions-Namen werden so gewählt, dass keine Kollision mit den 'echten' Namen auftreten kann. |
• Optional kann ein Quadrant 1..q..4 angegeben werden. In diesem Fall wird aus den beiden Ergebnissen das gewünschte ausgewählt. • Sonderfälle (hier für die Argumente x=-1, x=+1) werden abgefangen und getrennt berechnet. Damit werden keine Fehler-Werte ausgegeben. |
|
Dim pi As Double
Function myarccos(x As Double, Optional q As Integer = 0) As Double Dim wb As Double
If pi <= 0 Then pi = 4 * Atn(1)
Select Case x Case Is = 1: wb = 0 Case Is = -1: wb = pi Case Else wb = Atn(-x / Sqr(-x * x + 1)) + pi / 2
End SelectIf (q = 3 Or q = 4) Then wb = 2 * pi - wb myarccos = wb End Function |
Function myarcsin(x As Double, Optional q As Integer = 0) As Double
Dim wb As Double
If pi <= 0 Then pi = 4 * Atn(1)
End Function
Select Case x Case Is = 1: wb = pi / 2 Case Is = -1: wb = -pi / 2 Case Else wb = Atn(x / Sqr(-x * x + 1))
End SelectIf (q = 2 Or q = 3) Then wb = pi - wb
ElseIf q = 4 Then
wb = 2 * pi + wb
End Ifmyarcsin = wb |
|
|
|
Algo-Sammlungen:
Association fpr Computing Machinery (ACM) -
Collected Algorithms (Calgo)Hope College - Collection of Algorithm Animations (CCAA) NetLib / Toms NIST - Dictionary of Algorithms Numerical Recipes - Home, Cornell, TU Harburg, University of NewYork - Stony Brook Algorithm Repository, NetLib / Toms, University of Western Australia CIIPS - Algorithm Animation |
Genetische Algorithmen: Sourceforge - GAUL US-Navy Center for Research and AI - Genetic Algorithms Archive Geometrie & Triangulierung GeomPack - Barry Joe, Univ. Alberta, NewYork Univ, GNU Triangulated Surface Library Daten: 
Wikipedia:
Mathe-Konstanten,
Physik-Konstanten,NIST: Konstanten |
