Problem

alltagssprachlich: eine schwierige Aufgabe oder Belastung, die einer Lösung oder Beseitigung bedarf.

Ein Problem im Sinne der Informatik besteht, wenn von einem gegebenen Ausgangszustand aus ein gewünschter Zielzustand nicht ohne weiteres erreicht werden kann.

Die zwischen Ist- und Soll-Zustand liegende Barriere muss durch Einsatz von Hilfsmitteln (sog. Operatoren) beseitigt werden.

Siehe auch:

Problemlösungsprozess - Lösung - problematisch - Intelligenz - Denken und Problemlösen - Schwierigkeit - Rätsel - Hindernis

Problemstrukturen

Wohldefiniertes vs. Nicht-Wohldefiniertes Problem

Bei einem Wohldefinierten Problem stehen die Merkmale der Lösung von vornherein fest. Beispiel: xxx oder ooo in einer Reihe beim xox-Spiel.

Dagegen ist bei einem Nicht-Wohldefinierten Problem keine Zielvorgabe definiert. Es ist Teil der Problemlösung, die Kriterien, welchen die Lösung des Problems gerecht werden soll, festzulegen. Beispiele: Entscheidung für einen Beruf, Wahl eines Urlaubsortes, behelfsmäßige Reparatur eines Defektes.

Entscheidungsprobleme vs. Optimierungsprobleme

Will man für bestimmte Aufgaben nur wissen, ob eine Lösung existiert, ist jedoch nicht an deren weiterer Struktur interessiert, so spricht man von Entscheidungsproblemen. Will man jedoch wissen, wie genau eine Lösung des Problems aussieht, so spricht von Optimierungsproblemen.

Ein Beispiel hierfür:

Entscheidungsvariante

Lässt sich eine Zahl x in ihre Primfaktoren zerlegen? Dies gilt für alle Zahlen

Optimierungsvariante

Wie sieht die Primfaktorenzerlegung von x aus? Welche Primfaktoren hat x? Dies ist bei großen Zahlen nicht mehr so einfach zu bestimmen, es gibt verschieden Verfahren zur Faktorisierung.

Viele Optimierungsprobleme sind nicht wesentlich schwieriger als ihre Entscheidungsvarianten, obwohl dies auf den ersten Blick durchaus zu sein scheint. Wie Probleme bezüglich ihrer Schwierigkeit eingeteilt werden können und wie sich diese Einteilungen zueinander verhalten, damit beschäftigt sich die Komplexitätstheorie der Informatik.

Problemeigenschaften

• Regularität
• • Konsistenz
  • Vorhersagbarkeit
  • Kontinuität
  • Zerlegbarkeit
  • Lösungsdichte
  • Merkmalsnamen
• Komplexität
• • Grenzenlosigkeit
  • Verschiedenheit
  • Seltenheit von Lösungen
  • Unvorhersagbarkeit

Berühmte Probleme

• Drei-Türen-Problem
• Hamiltonkreis-Problem
• Königsberger Brückenproblem
• Quadratur des Kreises
• Traveling-Salesman-Problem
• Vier-Farben-Problem
• Turm von Hanoi

Zitat

Auch Probleme möchten gerne am Leben bleiben. - Werner Winkler (Probleme schnell und einfach lösen, ISBN_3636070010, S. 13)

Probleme sind Probleme, weil sie aufrecht erhalten werden. - Steve de Shazer, zit. ebd. S. 24)

Siehe auch

• Gödelscher Unvollständigkeitssatz
• Entscheidbarkeit

Literatur

Funke, J. (2003). Problemlösendes Denken. Stuttgart: Kohlhammer.