Problem

Einführung

Allgemein spricht man in der Informatik von einem Problem, wenn ein Ist-Zustand nicht mit einem gewünschten Soll-Zustand übereinstimmt und mit Hilfe eines Algorithmus zu lösen ist. Dies schließt nicht aus, dass Probleme auch außerhalb der Informatik existieren und Algorithmen auch dort Probleme lösen.

So ist das Verteilen von Briefen auf Zustellbezirke und Haushalte ein Problem, welches schon vor der Informatik gelöst wurde. So lassen sich Lösungswege für ein Problem zu erst in der realen Welt analysieren und planen, dann in einem Algorithmus beschreiben und schließlich in ein Computer-Programm übertragen.

Merkmale

Für Probleme lassen sich Merkmale definieren, nach denen sich Probleme charakterisieren lassen:

Lösbarkeit

Nicht alle Probleme sind lösbar. Bei vielen Problemen geht die scheinbare Unlösbarkeit auf mangelhafte Beschreibung des Problems zurück. Ist-Zustand , Soll-Zustand oder Hindernis wurden nicht klar formuliert, um eine Lösung zu ermöglichen. Doch auch für sauber formulierte Probleme in Umfeldern mit klar vorgegebenen Regeln kann unter Umständen gezeigt werden, dass eine Aufgabe unlösbar ist, wie z. B. die Quadratur des Kreises, die für unlösbare Probleme sprichwörtlich geworden ist. Arbeitsaufwand in die Lösung erwiesenermaßen unlösbarer Probleme zu stecken ist nicht sinnvoll.

Zerlegbarkeit

Lässt sich ein Problem in mehrere Unterprobleme zerteilen, so nennt man es zerlegbar. Unterprobleme lassen sich leichter lösen. Zudem ist die Lösung mit weniger Aufwand verbunden. Das Zerlegen von Komplexen Problemen ist schon häufig selbst Teil der Lösung und wird in diesem Zusammenhang "divide and conquer" (dt. "teile und herrsche") genannt.

Stellt die Zerlegung selbst ein schwieriges Problem dar, lässt sich ein Problem überhaupt nicht unterteilen oder sind die entstehenden Unterprobleme bei jeder möglichen Zerlegung ebenso komplex wie das Ausgangsproblem, so nennt man das Problem nicht zerlegbar oder elementar.

Verwandtheit

Manche Probleme sind eng verwandt, so dass mit einem Problem gleichzeitig ein anderes Problem gelöst wird. In diesem Fall sind Ist- und Soll-Situation bei beiden Problemen gleich, wenn auch anders formuliert. Eines der Probleme lässt sich jedoch in das jeweils andere Problem überführen. In diesem Zusammenhang spricht man auch von Problemklassen. Wird ein Problem dieser Klasse gelöst, gilt dieser Lösungsansatz für alle Ausprägungen (Instanzen) dieser Problemklasse. Auf diese Weise können ganze Problemklassen ausfindig gemacht werden, deren Probleme ungelöst sind. Kann ein Problem nicht auf andere Probleme zurückgeführt werden, so bildet es eine Problemklasse für sich.

Lösungsaufwand

Man kann Probleme nach dem Lösungsaufwand beurteilen: Der Lösungsweg eines Problems kann kurz und knapp sein, aber auch so aufwändig, dass das erreichbare Ziel die Mühe nicht lohnt. Extrem aufwändige Probleme können sogar unbegrenzt lange Lösungswege erfordern. So kann ein Problem zwar theoretisch lösbar sein, in der Praxis aber weiterhin als „unlösbar“ gelten.

Der benötigte Aufwand zur Lösung eines Problems hängt von seiner Komplexität und der Arbeitsleistung des ausführenden Systems.

Spezifikation

Um Probleme durch Algorithmen lösen zu können, sind sie genau zu beschreiben. Die Beschreibung eines Problems findet im Softwareentwicklungsprozess im Rahmen der Anforderungsanalyse statt. Folgende Aspekte sollten bei der Beschreibung berücksichtigt werden:

Ist-Zustant

Beschreibung eines gültigen Ist-Zustandes auf den das Problem anzuwenden ist.

Soll-Zustand

Beschreibung eines gültigen Soll-Zustand der zu erreichen ist.

Vollständigkeit

Beschreibung aller geltenden Rahmenbedingungen und einzuhaltenden Regeln.

Detailliertheit

Beschreibung der erlaubten Funktionen und Hilfsmittel.

Eindeutigkeit

Die Beschreibung ist insgesamt eindeutig. Der Erfolg kann anhand klarer Kriterien überprüft werden.