Robustheit

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Robustheit (v.lat.: robustus; aus robur Hart- Eichenholz) ist die Fähigkeit eines Systems, seltenere Vorkommnisse der Umwelt, die in ihren Eigenschaften stark abweichend sind, geschehen lassen zu können, ohne dass der Fortgang des Systems hiervon wesentlich betroffen ist.

In der Informatik wird der Begriff Robustheit auch verwendet, um die Eigenschaft eines Verfahrens zu beschreiben, auch unter ungünstigen Bedingungen noch zuverlässig zu funktionieren. Oft ist damit gemeint, dass ein Algorithmus auch dann noch zügig und korrekt ein Ergebnis liefert, wenn der Schlimmste Fall (Worst-Case) eintritt. Damit kann gemeint sein, dass ein Verfahren Fehlersituation erkennt und umgeht. Es gibt aber auch Algorithmen, die nur unter bestimmten Bedingungen effizient arbeiten, aber ineffektiv sind, wenn diese Bedingungen nicht gegeben sind.

[Bearbeiten] Beispiel

Ein Beispiel für ein nicht robustes Verfahren ist die Lineare Suche. Angenommen, man sucht in einem Telefonbuch mit 1 Millionen Namen eine bestimmte Telefonnummer. Wie bei der Linearen Suche wird die Liste der Namen von oben nach unten durchgesehen, bis der gesuchte Name gefunden wurde. Im Mittel muss man also 500.000 Namen durchsuchen, um das Ergebnis zu erhalten. Wenn der gesuchte Name aber der letzte in der Liste ist, muss man sogar alle Worte durchsuchen. Das Verfahren ist nicht robust, da es keine Maßnahmen gegen diesen Schlimmsten Fall (Worst-Case) trifft.

Unterteilt man hingegen die Liste anhand der Anfangsbuchstaben solange in Teillisten, bis jede Teilliste nicht länger als 100 Namen ist, dann kann man die Suche auf eine kleine Teilliste beschränken. Sie kann also im Worst-Case nur noch die Zeit kosten, 100 Namen zu durchsuchen. Das Verfahren ist also robust gegen das Problem, dass ein Suchbegriff der Letzte in einer Liste ist.

Obwohl das zweite Verfahren wesentlich robuster ist als das ursprüngliche, ist es nicht robust gegen den Umstand, dass der Suchname der letzte in der Liste ist und alle Namen bis auf den Suchnamen gleich sind. Nun wäre eine Unterteilung in Teillisten zu 100 Namen nicht mehr möglich. Dieser Fall ist zwar theoretischer Natur, dennoch ist die Praxis oft nicht vorhersehbar. Ein robuster Algorithmus muss auch mit unwahrscheinlichen Situationen umgehen können.