12.5. "Berühmte" Klassische lösbare sowie auch heute nicht lösbare Probleme der Informatik history menue Letztmalig dran rumgefummelt: 20.06.18 16:12:19

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:
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 history menue scroll up

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

   


2. Lösbarkeit von Problemen - Entscheidbarkeitskriterien history menue scroll up

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 history menue scroll up

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 history menue scroll up

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

das PASCAL'sche Dreieck

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

 
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

 


5. Definitiv nicht lösbare Probleme history menue scroll up

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 history menue scroll up

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

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)