Unlösbare mathematische Probleme -> theo. Informatik

fizzle · 13. Mai 2010

Hallo,

bezüglich meiner Abipräsentation suche ich noch mathematische Problemstellungen, die nicht mit Algorithmen oder Funktionen zu lösen sind.

Wollte mich auf 2 Probleme fixieren: 1. Primzahlen 2. Halteproblem

zu 1. => Stimmt es das es bis jetzt keinen Algorithmus gibt, der bestimmen kann ob die Zahl X eine Primzahl ist ?

zu 2. => Was hat es mit dem Halteproblem auf sich ? Kann das mir jemand villt näher Erläutern ? Ich weiß nur das es kein Programm gibt, das andere Programme auf Endlosschleifen überprüfen kann

GrandTheft · 13. Mai 2010

Also für 1 gibts Algorithmen - man braucht ja z.B. nur die Zahl X durch alle Zahlen kleiner X zu teilen und jedesmal überprüfen, ob das Ergebnis eine Ganzzahl ist.
Dauert aber geht.

Gruß
GT

Vektor · 13. Mai 2010

fizzle schrieb:
die nicht mit Algorithmen oder Funktionen zu lösen sind.

Das ist schwierig bis unmöglich. Konkretisiere zu: für die es bis heute keine Lösung gibt. Oder für welche die Lösung nicht existiert.
Z.B. es gibt keine allgemeinen Lösungsformeln zur Nullstellenbestimmung von Polynomen mit Grad >= 5. Oder der große Satz von Fermat wären wohl sehr berühmte Beispiele.

fizzle · 13. Mai 2010

Naja es gibt ja Probleme die theoretisch zwar lösbar sind, die jedoch wegen dem Zeitaufwand bzw. an der fehlenden Rechenleistung scheitern.

Ich meinte aber eher Probleme die von Anfang an von der Lösung ausgeschlossen sind, siehe Halteproblem.

Vektor · 13. Mai 2010

Also wie gesagt. zu deinem 1. gibt es natürlich Algorithmen die bestimmen können ob eine Zahl Primzahl ist. GrandTheft hat dir den einfachste genannt. Jedoch gibt es z.B. keinen Algorithmus der Primzahlen generieren kann. Evtl. meinst du das ja.
2 Beispiele für nicht lösbare Probleme habe ich dir genannt.
Probleme die offensichtlich keine Lösung besitzen sind dagegen leicht zu Konstruieren. Entweder man schränkt bei Funktionen ihren Wertebereich ein oder führt "Absurde" Bedingungen ein

Weitere Beispiele sind Differentialgleichungen, welche im Allgemeinen keine Lösung zu brauchen haben.
z.b. ist f(x) = a, mit f(0)=1 und f(1) = 2 für kein a aus den reellen oder komplexen Zahlen lösbar. Jedoch sehr wohl wenn a ein Polynom in x sein darf. also f(x) = a(x), dann wäre a(x) = x+1 eine Lösung.
Vielleicht kannst du ja noch etwas präziser sein, was für Probleme du meinst.

fizzle · 14. Mai 2010

Also gibt es keinen Algorithmus, der beliebige Primzahlen erstellen kann richtig ?

Kannste den Satz von Fermat kurz in eigenen Worten erläutern ?

Vektor · 14. Mai 2010

Also zunächst gibt es keinen Algorithmus der zuverlässig Primzahlen erstellen kann, das ist richtig!
Und weiter:
Wichtig ist, ich meine den Großen Satz von Fermat (nicht den kleinen

) und der besagt ganz "einfach" das es für c^n = a^n + b^n wobei n>2 ist, keine Lösung gibt. Also kann man die n-te Potenz einer Zahl c nicht in 2 Zahlen a und b der selben Potenz zerlegen.
Das das ganze für n=1 und n=2 funktioniert, findet man einfach durch ausprobieren raus.
Der ganze Satz konnte erst 1995 bewiesen werden.

GrandTheft · 14. Mai 2010

Sind zwar keine unlösbaren Algos drauf, aber ne extrem heftige website

http://www-i1.informatik.rwth-aachen.de/~algorithmus/liste.php

Viel Spaß!
GT

asdfman · 14. Mai 2010

Also zunächst gibt es keinen Algorithmus der zuverlässig Primzahlen erstellen kann, das ist richtig!

Klar gibts einen. Das Sieb des Erasthosthenes.

fizzle · 14. Mai 2010

Ihr widerspricht euch

GrandTheft · 14. Mai 2010

Auch das Sieb GENERIERT keine Primzahlen. Es testet lediglich etwas geschickter als der einfachste Ansatz.

asdfman · 14. Mai 2010

Nun, vielleicht verstehe ich dich falsch. Aber wenn ich bis zu einer bestimmten Zahl gesiebt habe, sind alle
Zahlen, zwischen der gewählten Zahl und der ersten Zahl, die gesiebt wird, garantiert Primzahlen.
Habe ich beispielsweise bereits nach 2 und 3 gesiebt und fange dann mit 5 an, ist die erste Zahl, die entfernt
wird die 25. Alle Zahlen, die zwischen 5 und 25 noch übrig geblieben sind (7, 11, 13, 17, 19, 23), sind also
ab diesem Moment als Primzahlen erkannt worden, und man könnte sagen, das Sieb hätte diese Zahlen im
3. Schritt (2, 3, 5) generiert.

€: Auch, sobald man 2 bis N gesiebt hat, kennt man alle Primzahlen bis N^2. Man könnte also eine Funktion
basteln, die wenn sie N übergeben bekommt, fleißig siebt und dann alle Primzahlen zwischen 1 und N^2
ausgibt, also wenn man so will "generiert". Oder halt von (N-1)^2 bis (N^2).

F(2) gäbe dann 3
F(3) gäbe 5 und 7
F(5) 11, 13, 17, 19, 23
undsoweiter

Oder wie meinst du das?

Vektor · 14. Mai 2010

Eben nicht! Das ist wiederrum nur ein Algorithmus um auf Primzahlen zu prüfen!
Wir suchen aber einen Algorithmus der solche generiert!
Z.B. kann dir das Sieb sagen ob 16 eine Primzahl ist oder nicht! Das kann man aber auch in dem man stupide durch alle Zahlen <16 teilt und schaut ob das Ergebnis ganzzahlig ist. Das Sieb nutzt nur die schon gewonnenen Erkenntnisse um auf dem Weg bereits weitere weitere Zahlen als Primzahlen zu bestimmen.
Wir suchen aber eine Algorithmus mit einer Funktion von IN -> IP wobei IP die Menge aller Primzahlen darstellt.
Also einen Algorithmus der eine Primzahl liefert für jedwede Eingabe.

z.B. nenn ich mal die Funktion prim: IN->IP
dann will ich mit prim(2576) die 2576. Primzahl haben. Solch einen Algorithmus gibt es noch nicht. Natürlich kann man erst alle möglichem Primzahlen ermitteln und dann abzählen. Aber darum geht es nicht.

fizzle · 14. Mai 2010

Wir suchen aber eine Algorithmus mit einer Funktion von IN -> IP wobei IP die Menge aller Primzahlen darstellt.
Also einen Algorithmus der eine Primzahl liefert für jedwede Eingabe.

Genau eine solche Funktion bzw einen Algorithmus gibt es nicht, richtig ?

Vektor · 14. Mai 2010

Richtig ^^
Deswegen beschäftigen sich auch noch ganze Distributed Computing Projekte mit diesen Primzahlen. Da halt für jede immer erst geprüft werden muss ob sie prim ist.

kuddlmuddl · 14. Mai 2010

Ihr müsst unterscheiden:
"Theoretisch möglich" und "praktisch einsetzbar".

asdfman hat vollkommen recht. Es gibt primzahlgenerierende Algorithmen und sein genanntes Sieb des Eratosthenes ist sogar ein sehr effizienter bis zu einer gewissen Größenordnung.

Selbst der Vorschlag von GrandTheft indem einfach "alle kleineren Zahlen als Teiler überprüfen" genügt um die von GrayFoxHard geforderte 2576'te Primzahl zu finden.

Solche Ansätze terminieren "garantiert in endlicher Zeit" (!) für jede natürliche Zahl als Eingabe aufgrund des Satzes von Euklid, der garantiert, dass es unendlich viele Primzahlen gibt. Das ist es worauf es in der theoretischen Informatik ankommt. Garantierte Terminierung in endlicher Zeit.

Solche Algorithmen sind nicht unbedingt praktisch einsetzbar, aber sie sind trotzdem Entscheidbar.
(Hier steht z.B. auch über Primahlen:
"Alle endlichen Mengen, die Menge aller geraden Zahlen und die Menge aller Primzahlen sind entscheidbar. Zu jeder entscheidbaren Menge ist auch sein Komplement entscheidbar. Zu zwei entscheidbaren Mengen sind deren Schnittmenge und deren Vereinigungsmenge entscheidbar.")

In den Wiki-Artikeln sind andere Beispiele für unentscheidbare Probleme verlinkt. Das Halteproblem ist irgendwie der "Klassiker" an den Unis.

Wenn du in deinem Vortrag neben "Entscheidbarkeit" noch einen sinnvollen Begriff erklären/vorstellen willst dann wäre das Berechenbarkeit

Kleinstädtler · 14. Mai 2010

Mir würd noch das Problem des Handlungsreisenden einfallen. Das ist zwar lösbar, aber nach einer ziemlich kleinen Anzahl von Zielpunkten mit heutigen Rechnern nicht praktikabel zu lösen. (also wohl eher praktische Informatik)

Zu 1, das wurde ja bereits gesagt, gibt es das Sieb des Eratosthenes (oder so ähnlich

), ist ziemlich simpel.

kuddlmuddl · 14. Mai 2010

Beim Problem des Handlungsreisenden, wie auch dem bekannten Rucksackproblem geht es um die Komplexität der Lösungsalgorithmen. Es gibt für beide entscheidbare/berechenbare!

Das geht in Richtung P-NP-Problem.
Dh die Frage, ob es einen Algorithmus gibt, dessen Speicherplatz und Rechenzeit durch ein Polynom beschränkt werden kann.
Beim Handlungsreisenden geht es mittels dynamischer Programmierung.

Das hat eigtl mit seinem Thema nicht viel zu tun, da es immer berechenbare Lösungsalgorithmen gibt. Die haben dann zwar evtl exponentielle Laufzeit - was ja aber nicht verboten ist bei der Frage nach entscheidbarkeit

fizzle · 14. Mai 2010

Ja genau die Problemstellung mit der exponnentiellen Laufzeit handle ich schon ab.

Ich glaub das Halteprobleme wäre ganz interessant um es kurz zu Erläutern. Ich weiß, dass es bis jetzt kein Programm gibt das andere Programme auf Endlosschleifen hin untersuchen kann.

Kann mir jemand in "einfachen" Worten erklären wieso ?

kuddlmuddl · 14. Mai 2010

Na weil man nie vorher weiß, ob sie tatsächlich "endlos" (=nie haltend) ist, oder evtl nur noch nicht lange/weit/tief genug gesucht wurde.
Wenn du dir vorstellst eine Funktion ruft sich selbst oder Unterfunktionen auf - und das immer wieder und wieder kann man nicht immer im voraus sicher sein, obs jemals endet.

Btw: Travelling Salesman Problem und NP-Complete

Um nochmal das von Wikipedia zu erklären:

In der praktischen Informatik lautet die Frage: Kann man ein Programm entwickeln, das als Eingabe den Quelltext eines zweiten Programms sowie dessen Eingabewerte erhält, welches entscheiden kann, ob das zweite Programm terminiert, d. h. nicht endlos weiterläuft?

Alan Turing bewies 1936, dass es keine Turingmaschine gibt, die das Halteproblem für alle Eingaben löst.

Man kann das auch so formulieren, dass es immer möglich ist ein Programm zu schreiben und dieses mit Daten zu füttern, wo dann nicht im voraus durch ein anderes Programm entschieden werden kann, ob es jemals anhält.

An dieser Stelle sollte man evtl. noch darauf hinweisen, dass Programmiersprachen Touring-mächtig sind. http://de.wikipedia.org/wiki/Turing-Vollst%C3%A4ndigkeit. Dh. wenns keine Touring-Maschine kann, kanns auch kein Programm - egal in welcher Sprache es geschrieben wird.

Unlösbare mathematische Probleme -> theo. Informatik

Captain

Lt. Commander

Lt. Commander

Captain

Lt. Commander

Captain

Lt. Commander

Lt. Commander

Commander

Captain

Lt. Commander

Commander

Lt. Commander

Captain

Lt. Commander

Commander

Ensign

Commander

Captain

Commander

Ähnliche Themen