12.5. "Berühmte" Klassische lösbare sowie auch heute nicht lösbare Probleme der Informatik

Letztmalig dran rumgefummelt: 22.11.24 11:50:21

	Die grundsätzliche Idee von "Otto-Normalverbraucher" lautet: alle Probleme sind irgendwann lösbar, man muss nur über die hinreichenden Kapazitäten verfügen. Mit den folgenden Beispielen vor allem aus dem Bereich der nicht lösbaren Probleme wollen wir darauf aufmerksam machen, dass diese Idee grundsätzlich falsch zumindest für eine ganze Reihe von Aufgabenstellungen auch schon aus der Gegenwart ist „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.")
	1. Lösbare Probleme 2. NP-vollständige Probleme 3. Problemklassen 4. Sammlung schwieriger und kniffliger, jedoch prinzipiell lösbarer Aufgaben 5. ... definitiv nicht lösbare Probleme 6. Verwandte Themen
	die Informatikseiten Logo zur Problemlösung inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Wissen für Fortgeschrittene der Informatik
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	mehreren der hier genannten Probleme sind sechs Eigenschaften gemein: sie sind ganz einfach zu beschreiben - siehe dazu: das Königsberger Brückenproblem sie sind im Lösungsansatz teilweise extrem einfach - siehe dazu: die Türme von Hanoi sie mausern sich schon bei teilweise recht geringer Mächtigkeit zu nicht mehr in Lebzeiten eines Einzelanwenders lösbaren Untersuchungsstrukturen - siehe dazu: das Rundreiseproblem sie besitzen eine enorme Praxisbedeutung - siehe dazu: das Rucksackproblem lassen es zu, durch intelligente Vorbetrachtungen eine ganze Reihe von theoretisch möglichen Fällen durch die Eigenschaft "unmöglich" einfach außen vor zu lassen ;-) die gefundenen Teillösungen besitzen schon ab 10 % der untersuchten Fälle die Eigenschaft, zu 93% an der optimalen Lösung zu sein sie sind also nicht komplex - sie sind aufwändig oder aber: zeitkomplex!
	Komplexität, Mächtigkeit und Aufwand Worst-Case-Denken Algorithmentheorie Lösbarkeit und Problemlösungsstrategien die Komplexität eines Problems & Komplexitätsklassen bei einer ganzen Reihe der nun folgenden Probleme stoßen wir auf die Klasse der NP-vollständige sowie NP-schwere Probleme - unbedingt vorab dazu informieren, was das ist und welche Aufgaben da auf uns zukommen
	eine ganze Reihe von Problemen rutschen von der Klasse der lösbaren schnell in die Klasse der nichtlösbaren, wenn die Mächtigkeit nur geringfügig zunimmt - typisch wäre hier das Rucksack-Problem oder auch Knapsackproblem. Mit zwei Gegenständen eine einfache Lösung - mit 50 schon nicht mehr - das hat dann schon was Komplexität und Aufwand zu tun ;-)
	„Talente finden Lösungen, Genies entdecken Probleme.“ Krailsheimer

1. Lösbare Probleme und Algorithmen

	Wie sagt unser Kollege Pfeifer immer so treffend: "... bringen Sie Lösungen, oder sind Sie das Problem?". Schauen wir mal, welche unscheinbaren Dinge fier die Informatik aufwerfen kann - viel Spaß beim Versuch, Lösungen eigenständig zu finden - ein wenig Literatur sollte dazu aber schon an Bord sein.
	das 8-Damen-Problem das Cliquenproblem das Dominoproblem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem   die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamiltonproblem das K-Farben-Problem das Königsberger Brückenproblem das Philosophenproblem das Post'sche Korrespondenz-Problem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit! das Springerproblem die Türme von Hanoi - mit hoher Anzahl von Scheiben wird das Problem praktisch nicht lösbar - 64 ist bereits enorm hoch das Wortproblem The Busy Beaver-Problem Greedy Algorithm das Knotenüberdeckungsproblem das Teilsummensummenproblem das Maximalflussproblem das Syntheseproblem das Spannbaumproblem der Maze-Running-Algorithmus das Schachspiel geometrischen Probleme Dijkstra-Algorithmus Fermat'sche Problem das Binärbaumproblem der austarierte Baum

2. Lösbarkeit von Problemen - Entscheidbarkeitskriterien

Probleme dieser Klasse scheitern heutzutage an der Mächtigkeit des Problems sowie an der geringen Rechenkapazität und -Geschwindigkeit modernen Computer. Einige von ihnen sind niemals entscheidbar - ihre Zwischenlösungsmenge ist unendlich. Damit bekomme ich niemals die Aussage, ob ich alle Lösungen gefunden habe ist die optimale in der untersuchten Menge enthalten Als extremer Rest aus dieser Menge verbleiben die Probleme, welche noch nicht einmal algorithmierbar sind!

die Ackermann-Funktion die Collatz-Funktion die Hofstädter-Funktion die McCarthy-Funktion das Post'sche Korrespondenz-Problem das Halteproblem

3. Problem- und Komplexitätsklassen

Lassen wir y gleich der Anzahl der zur Lösung des Problems mit dem gefundenen Algorithmus notwendigen Elementaroperationen sein, dann verhält sich die Anzahl n der gegebenen Elemente im günstigsten Falle y = n. Das ist allerdings niemals in der Praxis der Fall - ja es sieht schon gut aus, wenn gilt y = x • n. Nun gilt aber für die weitaus größte Klasse von informatischen Problemen y = x • n² oder gar y = x • n³. Und Extreme verhalten sich wie y = x • 2n, wie y = x • 3n.

die Komplexität eines Problems & Komplexitätsklassen NP-vollständige sowie NP-schwere Probleme

4. Sammlung schwieriger und kniffeliger, jedoch prinzipiell lösbarer Aufgaben

	Die Mehrzahl der nun folgenden Aufgaben vereinigt in sich die gesamte Komplexität der Informatik - heruntergebrochen auf die Begriffe: Unendlichkeit sowie Aufwand, Rekursion und Lösungsstrategien für komplexe Algorithmen. Wir haben hier nun die Informatik insgesamt vor Augen und dürfen alle aufgeworfenen Fragen auch per Software beweisen - das heißt: man kann einen Computer zur Lösung benutzen - muss man aber meist gar nicht - das ist Denksport pur. Übrigens lassen sich einige der Aufgaben gar nicht unbedingt per Software beweisen - zum Beispiel schon der Fluch des Pharao berührt die Unendlichkeit und ermittelt in ihr einen Punkt, welcher somit nie erreicht werden kann - per Programm schon!
	die Primzahlsuche die Primzahl-Faktorierung Miller-Rabin-Test   der Fluch des Pharao-Algorithmus das Teilerproblem Die Sache mit dem Wüstenfit (gefällt mir zu gut) die Chiffrierung ohne Schlüssel SUDOKU Die Magischen Quadrate - hier beschrieben von Stefan Hecker in einer Belegarbeit aus dem Schuljahr 2001/02 das Chinesische Kisten-Problem das Labyrinth das PASCAL'sche Dreieck
	einfache aber rechenintensive Spielereien mit Zahlen all den folgenden Problemstellungen ist gemein, dass sie extrem einfach zu beschreiben sind - einzelne Lösungen oder gar alle bzw. mindestens viele zu finden, ist jedoch u. U. extrem zeitkomplex - auch schnelle Computer können daran sehr lange tüffteln. - wer's nicht glaubt, probiert's aus, aber vorab die Randbedingungen gut durchlesen - teilweise gibt's extrem lange Wartezeiten und die Lösung erscheint evtl. in einer Woche, wenn überhaupt Selbst, wenn wir die mitunter große Laufzeit akzeptieren können, stoßen wir teilweise recht schnell an die Realisierbarkeit durch die verfügbaren Datentypen - eine Million ist hier ein eher kleiner Wert - dies zeigen uns sehr deutlich die Perfect Numbers die Primzahl-Zwillingssuche die Primzahl-Palindrome der Kaprekar Algorithmus die befreundeten Zahlen das 153-Problem - Narziß-Zahlen das Autoquadratzahlenproblem die Schmidtzahlen Pythagoräische Tripel Ulam-Spirale die Polynomzahlen Pascal-Zahlen die Goldbach-Vermutung das Palindrom-Spiegelsummen-Problem die Perfect Numbers die ABC-Vermutung Zahlensystem-Umechner ...als Startbare Datei Software zur Veranschaulichung der Zahlenumrechung

5. Definitiv nicht lösbare Probleme

Hier brauchen wir eine Vorbetrachtung, denn werden die zulässigen Grenzwerte für die folgenden Problemklassen eingegrenzt oder verstehen sich automatisch als klein, dann existieren sehr wohl in absehbarer Zeit Lösungen und diese sind auch noch lustigerweise von jedermann zu ermitteln - dazu braucht es keinerlei besondere Fähigkeiten und/oder Fertigkeiten! Werden jedoch die Eingangsgrößen hinreichend groß, bzw. die Anzahl der zu untersuchenden Fälle wird diese, so ist bereits für uns relativ klein erscheinende Ausgangswerte in absehbarer zeit kein vernünftiges Ergebnis erzielbar - und das gilt nachgewiesener Maßen!!! Nicht so schlimm, könnte man sagen, das sind sicher ganz besondere Spezailfälle, mit denen sich Mathematiker bereits viele Jahre schon herumgeprügelt haben! Dummerweise betrifft das eine ganze Menge uns durchaus - und sogar mitunter täglich auftretenden Aufgabenfelder!!!

... ganz reale Probleme aus unserer täglichen Umwelt, welche die Misere deutlich aufzeigen, wenn n (Anzahl der Eingangsgrößen sowie die Anzahl der umgebenden Bedingungen) hinreichend groß wird!!! das Wörterbuchproblem das Stundenplanproblem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit!

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.
	Problemstellungen aus dem bereich der Informatik Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Zufall und Computer Graphentheorie Petri-Netze Traversierungs-Probleme Baumstrukturen Turingmaschine Rekursion
	Bereich Begriffswelt der Informatik Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching
	Bereich Programmierungstechnik Programme Programmierung Programmiersprachen Software-Engeneering Datentypen - sind ja auch besond're Typen gewesen ;-) Logo der Struktogramme EVA-Prinzip & Objekt-, Attribut-, Operatiosnbeziehung Modultechnik Intel-Interrupt
	Bereich Kryptologie Grundlagen der Kryptologie Allgemeines zur Verschlüsselung Steganografie CÄSAR-Chiffre Vigenère-Chiffre Angriff auf den ENIGMA-Chiffre: Projekt ULTRA- oder Shark

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im August 1995