Bücher online kostenlos Kostenlos Online Lesen
Algorithmen

Algorithmen

Titel: Algorithmen Kostenlos Bücher Online Lesen
Autoren: Veikko Krypczyk
Vom Netzwerk:
sind vor der Weiterverarbeitung von Rechenergebnissen mögliche Fehler im Vorfeld zu kalkulieren. Im Beispiel wäre es angezeigt, die Prüfung nicht gegen den exakten Wert (hier Null) durchzuführen, sondern eine bestimmte Toleranzgrenze (Fehlerschranke) zuzulassen. Da sowohl positive als auch negative Abweichungen vom exakten Wert möglich sind, ist der Betragswert von Interesse (Listing 1, unterer Teil). Studieren Sie bei Bedarf die Fachliteratur, z. B. [3]. Unterschieden werden folgende Fehlerarten:
Eingabefehler: Diese entstehen z. B. wegen fehlerhafter Messung oder Rundung der Werte. Die Fehler werden im Algorithmus verarbeitet und können sich dadurch noch verstärken. Das Ergebnis der Berechnungen ist bezüglich der Genauigkeit auf die Qualität der Eingabedaten beschränkt. Das bedeutet, dass ein noch so genaues Rechenverfahren bestehende Mängel in den Eingabedaten nicht heilen kann.
Verfahrensfehler: Da gegebenenfalls für das eigentliche Problem kein geeignetes Lösungsverfahren zur Verfügung steht, kommt oftmals ein Näherungsverfahren zur Anwendung. Dieses Näherungsverfahren löst nicht mehr das eigentliche Problem, sondern ein so genanntes Ersatzproblem. Selbstverständlich soll die Lösung des Ersatzproblems der Lösung des Ursprungproblems möglichst nahe kommen. Die Differenz zwischen tatsächlicher Lösung des Ursprungsproblems (meist unbekannt) und der Lösung des Ersatzproblems wird als Verfahrensfehler bezeichnet. Die Größe dieses Fehlers muss abgeschätzt werden. Eine weitere Voraussetzung ist, dass das Ersatzproblem leichter zu lösen ist als das Ursprungsproblem.
Fortpflanzungsfehler: Fehler die sich in den Ausgabedaten niederschlagen, aber durch die Eingabedaten verursacht werden, heißen Fortpflanzungsfehler. Nicht zwangsläufig muss sich der Eingabefehler bei der laufenden Verarbeitung vergrößern. Dann spricht man von einem gut konditionierten Problem. Anderenfalls ist es auch möglich, dass es zu einer Vergrößerung des Fehlers kommt. Diese Möglichkeit ist bei der Bewertung des Ergebnisses zu beachten.
Rechenfehler: Rechenfehler ergeben sich durch die Ausführung der eigentlichen Rechenoperationen, beispielsweise durch die Verwendung von Dezimalbrüchen statt exakter Werte. Insbesondere das Potenzieren oder die Berechnung von Wurzeln und Logarithmen führt schnell zu Abweichungen, da die Algorithmen in den Klassenbibliotheken ihrerseits wieder auf Näherungsverfahren zurückgreifen.

1.2Methodisches Vorgehen bei der Entwicklung von Algorithmen
    Das Vorgehen bei der Entwicklung eines formalen – oft mathematisch orientierten – Algorithmus lässt sich verallgemeinern. Folgende Schritte ( Abb. 1 ) sind dabei zu durchlaufen:
Spezifizierung der Problemstellung: Die Problemstellung ist fachlich aufzuarbeiten. Dabei ist unter anderem die Frage zu beantworten, ob es sich um ein exakt lösbares Problem handelt oder ob ein Näherungsverfahren zum Einsatz kommen soll.
Ausarbeitung eines maschinenausführbaren Algorithmus: Es ist ein Algorithmus zu finden/zu entwickeln, der durch den Rechner ausgeführt werden kann. Im Gegensatz zum Menschen können (heute) Computerprogramme nur streng algorithmisch vorgehen. Ein intuitives Gestalten des Lösungswegs ist somit nicht möglich. Im Ergebnis dieses Vorgehens sollte ein spezifischer Algorithmus vorliegen. Dieser kann durch ein Sequenzdiagramm ergänzt werden. Bevor die Implementierung in der Zielsprache erfolgt, kann die formale Niederschrift in der so genannten Pseudocode -Notation (Kasten „Pseudocode“) erfolgen.
Beachtung des Laufzeit- und Fehlerverhaltens: Hinsichtlich möglicher Fehler gelten die dargestellten Aussagen. Das Laufzeitverhalten wurde noch nicht angesprochen. Es ist jedoch unbedingt zu beachten. Insbesondere iterative (schrittweise verbessernde) Verfahren können sehr schnell einen hohen Bedarf an Rechenzeit verursachen. Ein Ansatzpunkt ist beispielsweise das Auslagern des Rechenalgorithmus in einen eigenen Thread der Anwendung. Dieses Vorgehen kann bei heutigen Mehrkernprozessoren erhebliche Vorteile bieten. Es handelt sich dabei um einen Kompromiss zwischen (verfügbarer) Rechenzeit und Ergebnisgenauigkeit.
Implementierung des Algorithmus in der jeweiligen Programmiersprache.
Test des implementierten Algorithmus: Zum einen ist auf logische Konsistenz zu überprüfen (Werden alle Verzweigungen des Codes erreicht?), zum anderen sollte eine Überprüfung mit Testdaten stattfinden. Referenzergebnisse können beispielsweise

Weitere Kostenlose Bücher