12.4. Aufgaben, Probleme, Lösbarkeit und Problemlösungsstrategien

Letztmalig dran rumgefummelt: 22.06.12 06:41:57

	Probleme im Bereich der Informatik tangieren recht schnell die Begriffe Lösbarkeit, Algorithmus, Effizienz, Aufwand sowie Aufwandsklassen „Es gibt nur einfache Lösungen. Einziges Problem: Man muss sie finden.“ Robert M. Pirsig (* 1928), amerik. Schriftsteller ("Zen und die Kunst ein Motorrad zu warten. Ein Versuch über Werte.") Umgangssprachlich gehen wir mit dem Begriff Problem (wie übrigens mit so vielen Begriffen) recht lax um. Erst wenn's genau hinterfragt wird, merken wir, dass es Defizite gibt. Talente finden Lösungen, Genies entdecken Probleme. Wenn ich sie dann gefunden habe, sollen sie nachfolgend auch einer Lösung zugeführt werden - und hier nun wird's noch enger mit der verfügbaren Luft. Denn: Wie löst man eigentlich Probleme?
	1. Wir haben Probleme! 2. Problemlösen mit System 3. Problemlösungsverfahren 4. Problemklassen 5. Praktisch nicht lösbare Probleme 6. Verwandte Themen
	die Informatikseiten Lösbarkeit und Problemlösungsstrategien inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	Kennzeichnungspflicht für hintergündigen Humor seit dem 5.12.07 Die berühmten letzten Worte des Informatikers: "... ich bleib' hier sitzen, bis das Problem gelöst ist!" in der Informatik gilt der Problemerhaltungssatz! die Summe aller Probleme ist konstant der Problemerhaltungssatz eben ;-) ... bringen Sie Lösungen, oder sind Sie das Problem? Das Problem sitzt immer vor dem Computer - kein geliebter, aber ein wahrer Satz! Da war'n sie wieder, meine drei Probleme: kein Geld, keine Arbeit, keine Ahnung, wie es weiter gehen soll Otto Waalkes in dem Film "Otto" „Talente finden Lösungen, Genies entdecken Probleme.“ Krailsheimer ein zweifellos besonderes Problem für die gesamte Kommunikationswelt ist der DAU - und der kostet eigentlich richtig Geld - die Privatwirtschaft schottet sich eben auch vor solchen Mitarbeitern ab - Schulen nehmen sie :-( der DAU "Lehrer sind das größte Problem bei der Einführung von Computern in der Schule." Niklaus Wirth § 1 Informatiklehrer haben immer recht! § 2 Sollten Informatiklehrer ausnahmsweise einmal  nicht recht haben, so tritt automatisch § 1 in Kraft!

1. Wir haben Probleme!

	Wie sagt unser Kollege Pfeifer immer so treffend: "... bringen Sie Lösungen, oder sind Sie das Problem?"
	Als Problem bezeichnet man im Rahmen einer geplanten Aufgabenerfüllung (Planung) eine ungeklärte Situation, die noch nicht erkennen lässt, wie die Aufgabe im einzelnen erfüllt werden kann. Ein Problem kann auch darin liegen, dass die Aufgabenstellung als solche noch unklar und unscharf ist, so dass diese zunächst analysiert und durchleuchtet werden muss, ehe man das Problem der Aufgabenerfüllung angeht. Die wichtigsten Stationen bei der Lösung von Problemen sind die Problemanalyse und die dabei genutzten Problemlösungsverfahren. Als Problemanalyse bezeichnet man die im Rahmen der Planung auftretende Notwendigkeit, unklare Situationen durch systematisches Durchdenken zu strukturieren, so dass die Einzelheiten, in denen noch Unklarheit herrscht, deutlich werden. Die Problemanalyse, durch die noch nicht das Problem selbst gelöst wird, ist die Voraussetzung für die Problemlösung (Problemlösungsverfahren), da durch sie veranschaulicht und bewusst wird, welche Fragen einer Klärung zuzuführen sind. Im Bereich der Einführung eines Datenverarbeitungssystems liegen die Probleme im allgemeinen in der Frage, welche Ziele mit dem Rechnereinsatz verfolgt werden sollen, welche Aufgaben überhaupt durch den Rechner gelöst werden können, welche Aufgaben und Ziele miteinander verträglich oder unverträglich sind und, das ist der umfassendste Problemkreis, welche Verfahren sinnvoller Weise entwickelt und eingesetzt werden können, die gesetzten Ziele und Aufgaben zu realisieren. Die Durchführung einer Problemanalyse setzt bei den betreffenden Personen intime Kenntnis der Gesamtsituation voraus, in der Zielsetzungen und Aufgabenstellungen auftreten, sowie ausreichende Erfahrung mit den formalen Problemlösungsverfahren und den Verfahren und Methoden, die in dem betreffenden Bereich verwendet werden. Im Rahmen der Systementwicklung stellt die Problemlösung den ersten Schritt dar, der vor allem auf die Klärung der Ziele und Aufgaben gerichtet ist.
	einige Probleme haben als alleiniges Ziel, die Extrema aufzuzeigen, welche in der Praxis im Worst-Case vorkommen könnten

2. Problemlösen mit System

	Lösbar ist eine Aufgabe nur, wenn es ein irgendwie sinnvolles Antwortzeitverhalten auf eine sinnvolle Datenmenge mit eindeutigen (als zum Beispiel schon mal nicht gerundeten) Zwischenergebnissen gibt, deren Aufwand sich im Sinne der Problemstellung.
	In unserem Zusammenhang gehört dazu die Frage nach der Korrektheit eines Programms (d. h. danach, ob es auch tatsächlich das leistet, was es leisten soll) sowie die nach der Effizienz (d. h. danach, wie viel Zeit und Speicherplatz es benötigt). Im Fall der Korrektheit kann man sich im Unterricht zuweilen mit einer die Programmentwicklung begleitenden Argumentation begnügen, welche die Korrektheit des Programms einsichtig macht. Im Fall der Effizienz helfen oft empirische Zeitmessungen und Plausibilitätsbetrachtungen weiter. Die künstlerische Seite des Problemlösens wird mit Begriffen wie Phantasie, Kreativität, Intuition umschrieben, und es scheint, als ob sich dazu nicht viel Allgemeines sagen ließe. Diese Annahme wäre jedoch falsch, denn auch auf besagtem Gebiet gibt es bewährte Regeln; mit ihnen befasst sich die sogenannte Heuristik, die Lehre vom Entdecken und Erfinden. Im Folgenden wollen wir uns durch Ausdeutung der Ratschläge eines großen Denkers - des Philosophen René Descartes - und eines bedeutenden Wissenschaftlers - des Mathematikers George Pölya - klarmachen, wie man an ein informatisches Problem herangeht und wie man damit zurechtkommt, auch wenn es zunächst als sehr schwierig erscheint.
	René Descartes Der Entwurf eines Informatiksystems ist ein schöpferischer Vorgang. In seinen Regeln zur Leitung des Geistes stellt der französische Philosoph Rene Descartes folgende Maximen auf: Übereilung und Vorurteil sind sorgfältig zu meiden. Jede der zu untersuchenden Schwierigkeiten ist in so viele Teile zu zerlegen, wie möglich und zur besseren Lösbarkeit nötig ist. Mit den einfachsten und fasslichsten Objekten ist zu beginnen und von da aus schrittweise zur Erkenntnis der kompliziertesten fortzuschreiten. Hinreichend vollständige Aufzählungen und allgemeine Übersichten sind anzufertigen, um sicherzugehen, dass nichts vergessen wurde. Dies sind allgemeine Regeln, die jedem Informatiker frommen. Wir erkennen in ihnen zwei Prinzipien, nämlich erstens das Dekomponieren, d. h. Zerlegen eines Ganzen in Teile, und zweitens das Abstrahieren, d.h. das Absehen von Details zugunsten des Allgemeinen. Die konsequente Anwendung dieser Prinzipien führt zur Methode der schrittweisen Verfeinerung bzw. der strukturierten Programmierung. George Pölya In seinem Buch „Schule des Denkens" unterscheidet George Pölya (1887-1985) vier Phasen beim Lösen eines Problems einer Aufgabe. Er sagt: Erstens müssen wir die Aufgabe verstehen, d. h. wir müssen klar erkennen, was verlangt wird. Zweitens müssen wir feststellen, wie die verschiedenen Einzelheiten untereinander zusammenhängen, wie die Unbekannte und die Daten miteinander verbunden sind, um auf eine Lösungsidee zu kommen und um einen Plan zu machen. Drittens müssen wir den Plan durchführen. Viertens halten wir Rückschau, d. h. wir überprüfen die fertige Lösung, diskutieren und dokumentieren sie. Pölyas Überlegungen beziehen sich hauptsächlich auf mathematische Probleme; dort ist mit „Lösung" in der Regel eine Zahl, eine Funktion oder eine geometrische Figur gemeint. In der Informatik dagegen ist stets ein allgemeines Verfahren, also ein Algorithmus oder ein Programm gesucht. Trotz dieses Unterschieds sind die Ratschläge und Regeln aus der Schule des Denkens für uns von Wert; sie werden daher im Folgenden durch Beispiele illustriert.
	Wir haben einen Plan, wenn wir - wenigstens in Umrissen - wissen, welche Aktionen zur Lösung der Aufgabe führen werden. Der Weg vom Verstehen der Aufgabe bis zum Aufstellen eines Plans kann lang und gewunden sein. Die eigentliche Leistung beim Lösen besteht darin, die Idee des Plans zu finden. Diese Idee mag langsam auftauchen; sie kann uns aber auch nach anscheinend erfolglosen Versuchen und einer Periode des Zögerns ganz plötzlich in einer Art Erleuchtung als ein „Geistesblitz" einfallen. Natürlich ist es schwer, auf eine gute Idee zu kommen, wenn wir nur geringe Kenntnisse über den Gegenstand besitzen; es ist ganz und gar unmöglich, wenn wir überhaupt nichts über ihn wissen. Das heißt: Gute Ideen beruhen auf Erfahrung und früher erworbenen Kenntnissen. Die Erinnerung allein reicht jedoch für eine gute Idee nicht aus - aber wir können nur dann zu einer guten Idee gelangen, wenn wir uns einiger dazu gehöriger Tatsachen erinnern. Sehr oft ist es angebracht, die Arbeit mit der Frage: „Kenne ich eine verwandte Aufgabe?" zu beginnen. In der objektorientierten Programmierung spricht man in diesem Zusammenhang von Entwurfsmustern. Im Fall von Beispiel 1 (Erbteilung) fallen uns vielleicht eine ähnliche Aufgabe (möglicherweise zum sogenannten Rucksackproblem) sowie die Stichwörter Backtracking und Rekursion ein. Ausführen des Plans Einen Lösungsplan auszudenken, auf die Lösungsidee zu kommen, ist nicht leicht. Zum Gelingen ist vieles erforderlich: früher erworbene Kenntnisse, geistige Disziplin, Konzentration auf das Ziel - und schließlich: Glück. Die Ausführung des Plans ist viel leichter; was wir dazu brauchen, ist hauptsächlich Geduld und etwas „handwerkliches" Können, z. B. die Beherrschung einer Programmiersprache, insbesondere Erfahrung in der Wahl einer geeigneten Datenstruktur und bei der Anwendung von Suchstrategien (siehe unten). Der Plan gibt uns einen allgemeinen Umriss; wir haben uns nun davon zu überzeugen, dass die Einzelheiten in diesen Umriss passen, und so müssen wir die Details geduldig nacheinander ausarbeiten, bis alles vollkommen klar ist und keine dunkle Stelle übrig bleibt. In der Informatik besteht der „allgemeine Umriss" in der Grobfassung unseres Programms, die wir Schritt für Schritt immer weiter verfeinern, d. h. ausgestalten (Methode der schrittweisen Verfeinerung). Gehen wir nach objektorientierter Methodik vor, müssen wir zunächst die wichtigsten Objekte bzw. Klassen und ihre Beziehungen zueinander festlegen.
	Der Fluch des Pharao (8. BWI,1989) Im Königsdreieck, das sich zwischen drei Pyramiden erstreckt, befindet sich irgendwo unter dem Staub der Jahrtausende der Eingang zur Grabkammer des Pharao Tutramses. Schon viele Schatzsucher haben sich aufgemacht, das Grab zu finden und nach den kostbaren Grabbeigaben zu schürfen. Vergeblich! Der Fluch des Pharao bewirkt, dass sich der Schatzsucher, sobald er sich im Königsdreieck befindet, immer nur gradlinig auf eine der Pyramidenspitzen zu bewegen kann. Dabei schafft er jeweils genau die Hälfte der Strecke bis - zur nächsten Pyramide und muss eine Weile rasten, um dann von Neuem irgendeine der drei Pyramiden anzusteuern. Gibt es Stellen im Königsdreieck, die ein Schatzsucher niemals erreichen kann, so dass der Eingang zur Grabkammer verborgen bleibt und der Pharao seine ewige Ruhe behalten wird? Aufgabe: Schreibe ein Simulationsprogramm für die Schatzsuche, das nur die Rastpunkte auf dem Bildschirm anzeigt. Gib dazu die Koordinaten für die drei Eckpunkte des Königsdreiecks sowie für den Startpunkt des Schatzsuchers vor. Schicke als Lösung mindestens fünf Grafiken ein. Bei einer davon sollen der Startpunkt und die drei Eckpunkte genau in den vier Ecken des Bildschirms liegen und 5000 Tterationen durchgeführt werden. Rückschau Selbst gute Schüler geben sich schnell zufrieden, wenn ihr Programm bei einigen wenigen Beispielen „läuft". Damit lassen sie jedoch eine entscheidende Arbeitsphase aus. Durch Rückschau müssen wir uns nämlich dessen versichern, dass die (vermeintliche) Lösung auch richtig ist, wir diskutieren und dokumentieren sie. Im Bundeswettbewerb Informatik, aber erst recht in der Berufspraxis ist die Dokumentation eine wichtige Arbeitsphase, da wir ja ein Programm i. d. R. nicht für uns selbst geschrieben haben, sondern andere vom Wert unserer Lösung überzeugen und sie eventuell in die Lage versetzen müssen, an unserem Werk weiterzuarbeiten. Durch Rückschau auf die fertige Lösung (das Programm), durch nochmaliges Erwägen und Überprüfen des Resultats und des Weges, der dazu führte, können wir unser Wissen festigen und die Fähigkeit zum Problemlösen entwickeln. Im Grunde ist eine Aufgabe niemals vollständig und endgültig gelöst. Es bleibt immer noch etwas zu tun, jede Lösung lässt sich verbessern, und auf jeden Fall können wir unsere Lösung besser verstehen.
	der Fluch des Pharao-Algorithmus
	Acht Schritte - obige Regeln lassen sich in die folgenden acht Schritte umsetzen: Versichere Dich, dass Du das Problem vollkommen verstanden hast. Versuche eventuell, es geeignet umzuformulieren. Entwickle ein allgemeines Verfahren (einen Algorithmus) zur Lösung des Problems. Gelingt dies nicht auf Anhieb, fahre mit Schritt 2 fort. Untersuche zuerst einen einfachen Spezialfall, und zwar in allen Einzelheiten. Benutze dabei noch keinen Computer. Bearbeite (mit Bleistift und Papier) zuerst den leichtesten Fall. Erstelle ein Programm für weitere Spezialfälle. Modifiziere dein Programm so, dass es noch mehr einfache Fälle erfasst. Verallgemeinere nun das Programm dergestalt, dass es alle bisherigen Lösungen (und eventuell noch weitere) liefert. Teste das Programm, um sicherzugehen, dass es korrekt arbeitet. Analysiere die Ergebnisse daraufhin, ob sie mathematische Zusammenhänge erkennen lassen, die sich zur Verbesserung des Algorithmus eignen. Prüfe: ist das ursprünglich gegebene Problem zur Zufriedenheit gelöst? Wenn nicht, fahre mit Schritt 5 fort Dokumentiere die Lösung
	extrem komplexe Rechenprobleme

3. Problemlösungsverfahren

	Wenn wir nunmehr in der Lage sind, ein Problem mit all seinen Randbedingungen sowie Worst-Cases hinreichend zu beschreiben, suchen wir nach generellen Lösungsstrategien - und siehe: auch diese gibt es und sie lassen sich sogar auf Mikrorechnern implementieren.
	... hier schauen wir erst nochmals nach, damit wir auch wissen, worum es überhaupt geht die Mutter aller Computer-Algorithmen - die Turingmaschine Algorithmentheorie Probleme & Problemlösungsverfahren ... und hier gibt's dann, wenn alles mal fertig ist, echte Lösungsrezepte - leider mathematisch etwas abstrakt :-( Brute-Force-Angriffe das Backtracking-Verfahren das Branch & Bound-Verfahren
	Heuristische Lösungsmethode die Trial-&-Error-Methode

4. Problemklassen

	Entscheidbar ist ein Problem hinsichtlich seiner Lösung, wenn die Anzahl der Zwischenargumente zwar groß, im Extremfall auch sehr groß - aber endlich ist. Ist dies nicht mehr gegeben, so ist auch das Problem hinsichtlich seiner Lösung und/oder seines Lösungsumfanges nicht mehr entscheidbar
	Praktische Elementaralgorithmen Probleme & Problemlösungsverfahren NP-vollständige und schwierige Probleme was aber bedeutet Aufwand im softwaretechnischen Sinne?
	Graphentheorie in der Anwendung - Laufzeitoptimierung und Zeitkomplexität das ist Komplexität die Zusammenhänge zwischen den Faktoren die Zusammenhänge zwischen den Faktoren NP-vollständige und schwierige Probleme die Komplexität eines Problems & Komplexitätsklassen

5. Praktisch nicht lösbare Probleme

	NP steht für nicht proportional - will sagen, wenn die Menge der Argumente geändert wird, so steigt oder fällt der Aufwand zur Problemlösung im nichtproportionalen Verhältnis. Sie gehören in die Klasse der lösbaren Probleme, um aber alle möglichen Lösungen wirklich zu finden, kann die benötigte Rechenzeit extrem groß werden.
	Entscheidbarkeitsproblem Halteproblem

6. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze Traversierungs-Probleme Baumstrukturen Turingmaschine
	Informationsbegriff Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching
	Funktionen & Prozeduren mit Parameterübergabe Rekursion

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost November 2002