Nicht implementierbare Algorithmen

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
Nicht implementierbare Algorithmen
Servus,

nachdem ich endlich gefallen an Sätzen wie "es gibt eine Lösung und sie ist sogar eindeutig" gefunden hatte, holt mich die Numerik mit der Frage nach dem konkreten Aussehen der selbigen wieder aus meiner schönen Welt heraus.

Es "quält" mich nun die Frage, ob jedes Problem dessen Lösung existiert (vielleicht sogar eindeutig) und man einen theoretischen Algorithmus zur Bestimmung dieser Lösung angeben kann auch implementierbar ist?

Vielleicht sollte ich noch sagen, dass ich damit auch meine, dass es keine theor.äquivalente Umformung des Algorithmus zur Implementierung gibt (klassisches Beispiel - Pi und die eingeschriebenen n-Ecke)

Wenn ja - Wie lautet der zugehörige Satz?

Wenn nein, was wären Gründe für das Scheitern? Beispiel?

Danke,
tigerbine Wink
papahuhn Auf diesen Beitrag antworten »
RE: Nicht implementierbare Algorithmen
Was ist für dich ein theoretischer Algorithmus? Vielleicht hilft dir das weiter: http://de.wikipedia.org/wiki/Church-Turing-These
sqrt(2) Auf diesen Beitrag antworten »

Ich frage mich, was du unter einem "theoretischen Algorithmus" und "implementieren" verstehst. Wenn ich meine Begriffe zugrunde lege, dann kann man einen Algorithmus natürlich implementieren (die Definition besagt ja, dass ein Algorithmus endlich und jeder Schritt ausführbar sein muss). Ob der Algorithmus dann in deiner Lebenszeit terminiert oder in Realität genug Speicher da ist, ist eine andere Frage, aber da ein Algorithmus per Definition nach endlicher Zeit terminiert und eine Turingmaschine ein unendlich langes Band hat, sind das weniger mathematische Fragen...
tigerbine Auf diesen Beitrag antworten »
RE: Nicht implementierbare Algorithmen
Ein theoretischer Algorithmus ist für mich eine Anweisung was ich zu tun habe, um zur Lösung zu kommen. Diese wird im analytischen Fall dann auch durch den Algorithmus erreicht.

Beispiel siehe Ergänzung oben
sqrt(2) Auf diesen Beitrag antworten »

Also die Annhäherung von durch Einbeschreiben von n-Ecken in einen Kreis ist kein Algorithmus, da er entweder nicht terminiert oder nicht jeder Schritt ausführbar ist...
tigerbine Auf diesen Beitrag antworten »
RE: Nicht implementierbare Algorithmen
@ sqrt(2)

Vielleicht muss ich dann doch weiter ausholen, um mein "Problem" zu erklären. Ich gehe gerade meine Numerik Unterlagen durch, und da wird ja am Anfang immer mit MAschinenzahlen, Rundungen, Problemen wie overflow, Auslöschung begonnen.

Wenn man dann zu den zu lösenden mathematischen Problemen kommt, wird immer erstmal theoretisch gezeigt, dass und unter welchen umständen eine Lösung existiert und auf welche Weise man sie theoretisch Berechen kann. Diese "Weise" wird dann in einem Algorithmus in einer Pseudo-Programmiersprache zusammengefasst. Dann kommt noch eine (I) Laufzeitanalyse und ggf. (II) Hinweise auf geschicktere Implementierung.

Nur sind (I), (II) meist eher kurz abgehandelt, wohin man sich mit der "Theoretischen" Lösung lange beschäftigt.

Nun stellte sich mir die Frage, warum diese "Aufwandsbetreibung" gerechtfertigt ist.

D.h. am Beispiel pi: Wenn ich eine theoretische Vorschrift zur Berechnung habe (theoretischer Algorithmus) die zum Erfolg führt, so gibt es Äquivalenzumformungen, so dass der Algorithmus implementiert auch gegen pi läuft.

edit: wird das mit deiner Definiton vom Algorithmus besser, wenn eich an Abbruckkriterium - Genauigkeit hinzufüge?)
 
 
AD Auf diesen Beitrag antworten »

@tigerbine

Da wir hier im Bereich numerische Mathematik sind:

Sobald z.B. Fließkommazahlen ins Spiel kommen, unterscheidet sich eh die "reine" Mathematik und deren Operationen von dem, was im Computer abläuft. Das geht schon bei den elementaren Grundrechenarten + - * / los, man kann also i.a. sowieso keine genauen, sondern nur noch -genaue Resultate erwarten.

Insofern verstehe ich nicht ganz, was du mit deinem Beispiel zu bezweckst. Oder denkst du an CAS - die haben eigentlich kein Problem mit der zugehörigen Grenzwertbildung bei den n-Ecken. Allerdings laufen dort dann andere Algorithmen ab, als die, an die du vielleicht denkst. Augenzwinkern


P.S.: Sorry, hab deinen letzten Beitrag zu spät gesehen.
tigerbine Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
P.S.: Sorry, hab deinen letzten Beitrag zu spät gesehen.


Und wie würde die Anwort dann lauten? unglücklich
AD Auf diesen Beitrag antworten »

Auch nicht viel anders, ich hätte mich nur kürzer gefasst.
sqrt(2) Auf diesen Beitrag antworten »
RE: Nicht implementierbare Algorithmen
Zitat:
Original von tigerbine
Diese "Weise" wird dann in einem Algorithmus in einer Pseudo-Programmiersprache zusammengefasst. Dann kommt noch eine (I) Laufzeitanalyse und ggf. (II) Hinweise auf geschicktere Implementierung.

Nur sind (I), (II) meist eher kurz abgehandelt, wohin man sich mit der "Theoretischen" Lösung lange beschäftigt.

Nun stellte sich mir die Frage, warum diese "Aufwandsbetreibung" gerechtfertigt ist.

Ich muss sagen, dass ich dein Problem immer noch nicht wirklich verstehe. Man hat eben ein Ziel, das man erreichen will, entwickelt einen Algorithmus, der das Problem löst, und beweist dann, dass er dies auch wirklich tut. Natürlich ist das die Hauptsache, denn was nützt mir ein Problem ohne Lösung oder eine Lösung ohne den Nachweis, dass sie wirklich das Problem löst?

Dann kann man natürlich betrachten, wie schnell das Problem gelöst wird, und ob man es auf Grundlage der bisherigen Überlegungen verbessern kann, aber wenn man darauf kommt, dazu braucht man eben überhaupt erst etwas.

Zitat:
Original von tigerbine
edit: wird das mit deiner Definiton vom Algorithmus besser, wenn eich an Abbruckkriterium - Genauigkeit hinzufüge?)

Ja, dann wird ein Algorithmus draus.
tigerbine Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Sobald z.B. Fließkommazahlen ins Spiel kommen, unterscheidet sich eh die "reine" Mathematik und deren Operationen von dem, was im Computer abläuft. Das geht schon bei den elementaren Grundrechenarten + - * / los, man kann also i.a. sowieso keine genauen, sondern nur noch .


Ok, wir erwarten nur Ergbenisse im Rahmen der MAschinengenauigkeit. Gibt es dann immer eine Implementierung die den analytischen Wert in dieser Genauigkeit darstellt?

Oder in einer "brauchbaren" Genauigkeit g >

Dabei hängt "Brauchbarkeit" sicher vom Auge des Betrachtes ab, ja. Nur grob gesagt 85% der Unterlagen beziehen sich auf die analytische Mathematik.

Die Implementierung und Fehlerabschätzung werden eher untergeordnet behandelt. Aber wäre das nicht eigentlich das Hauptthema?
tigerbine Auf diesen Beitrag antworten »

@ sqrt

Vielleicht versthe ich die Aufgabe der Numerik auch falsch? Ist es die Aufgabe einen "Weg" zu finden, die Lösung eines Problems theoretisch zu finden?

Und die geschickte Implementierung dieser Vorschrift ist dann ein Fall von "anderen" und wird nur in Ausblicken dargestellt?
AD Auf diesen Beitrag antworten »

Ich wollte mit meinem Einwurf nur andeuten, dass man sich bei Verwendung von Fließkommazahlen einiger zusätzlichen Probleme bewusst sein muss - zusätzlich zu den sowieso üblichen algorithmischen Betrachtungen. Z.B. dass selbst einfache Dinge wie das Assoziativgesetz für die Fließkommaaddition nicht gilt. Ein nettes Beispiel dazu ist eine einfache Partialsummenberechnung der harmonischen Reihe:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
#include <stdlib.h>
#include <stdio.h>

int main (int argc, char *argv[])
{
  int k;
  long n = 10000000;
  volatile float sumforward = 0.0f;
  volatile float sumbackward = 0.0f;
  for (k = 1; k <= n; k++) sumforward += 1.0f/k;
  printf("Sum forward  : %9.6f\n", sumforward);
  for (k = n; k >= 1; k--) sumbackward += 1.0f/k;
  printf("Sum backward : %9.6f\n", sumbackward);
  return 0;
}

Resultat ist
code:
1:
2:
Sum forward  : 15.403683
Sum backward : 16.686031

Tatsächlich gilt, auf 6 Stellen nach dem Komma genau:
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Vielleicht versthe ich die Aufgabe der Numerik auch falsch? Ist es die Aufgabe einen "Weg" zu finden, die Lösung eines Problems theoretisch zu finden?

Ich habe die Motivation der Numerik in der Approximation als das Finden von Algorithmen, die eine solche Näherung liefern, und die Abschätzung des Fehlers kennengelernt. Natürlich soll das Laufzeitverhalten auch akzeptabel sein, wenn man mit den Algorithmen dann etwas anfangen will, aber das geht dann schon wieder mehr in die Richtung der theoretischen Informatik.
tigerbine Auf diesen Beitrag antworten »

Also erstmal Danke smile , aber irgendwie scheine ich nicht in der Lage zu sein, mein Problem zu formulieren. Ich wage noch einen Versuch.

Ein Themenblock ist ja die z.B. die Polynominterpolation. Da kommt man von der Existenz und Eindeutigkeit der Lösung der Lagranschen Interpolationsaufgabe, zu den verschiedenen Darstellungen und deren Berechnungen.

Beispiel: Nevillsche Formel




Bis hierhin hätte ich das alles noch nicht als Numerik gesehen.

Erst die nächste Bemerkung:

... Zur Implementieren verwendet man zweckmäßiger Weise die Darstellung:



...

hätte ich als Numerik angesehen und mir daher auch eine Begündung für diese Darstellung gewünscht.

In meiner vorherigen Begriffwahl ist der erste latex Teil der theor. Algorithmus, der zweite die Implementierung.

Habe ich also die aufgabe der Numerik falsch verstanden? Wer ist dann dafür zuständig "aus der ersten die zweite" Darstellung zu machen?
AD Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
... Zur Implementieren verwendet man zweckmäßiger Weise die Darstellung:


Vielleicht sind es ja doch ähnliche Gründe, auf die ich oben aufmerksam zu machen versuchte: Die Reihenfolge der Operationen ist bei Fließkommaarithmetik von entscheidender Bedeutung - gerade dann, wenn irgendwelche Auslöschungseffekte drohen. Ob das hier nun konkret der Fall ist, vermag ich nicht zu beurteilen, aber möglich ist es schon.
tigerbine Auf diesen Beitrag antworten »

Ok, nur ist es die Aufgabe der Numerik dies zu untersuchen?
sqrt(2) Auf diesen Beitrag antworten »

Für meinen Begriff ist auch das Entwickeln der Nevillschen Formel Teil der Numerik.
tigerbine Auf diesen Beitrag antworten »

@ sqrt(2)

"auch" heißt ja, dass sie sich um beides zu kümmern hat. Warum wird dann dem zweiten Teil (Neville hier nur als Beispiel) so wenig Aufmerksamkeit geschenkt (In den Vorlesungen Numerik I+II, um nicht generell die Numerik zu verurteilen)?

Oft bleibt es da bei einer Bemerkung.

Meist lautet ja das erste Kapitel: Zahldarstellung un Rundungsfehler. auf Probleme die damit zusammenhängen hat ja Arthur auch schon hingewiesen.

Dann wendet man sich einem Problem zu und "konstruiert" einen Algorithmus ( entspricht jetzt dem Weg bis zur ersten Neville Formel). Um dort hin zu gelangen, bracuht man aber das Wissen über Maschinenzahlen und die resultierenden Probleme nicht.

Dann folgt entweder in einer Bemerkung oder sehr kurzer Abhandlung eher eine Art Ausblick : "In der Praxis würde man das mit der zweiten Formel implementieren."

Ich hätte nun erwartet, dass diesem Teil mehr Aufmerksamkeit gewidmet wird, quasi - wie implementiere ich die Neville-Formel I und warum mache ich das so.

Ich versuche noch einmal den Bogen zum Anfang des Posts zu spannen. Gibt es Beispiele, dass die "erste" Formel nicht sinnvoll implementierbar ist, d.h. ich finde keine Darstellung 2, so dass sich die Fehler, die generell durch die Verwendung von Maschinenzahlen enstehen, im Rahmen halten.

Wobei ihr mich jetzt wahrscheinlich wieder mit sinnvoll "aufziehen" werdet. Klar, wenn ich mich nur für die erste Vorkommastelle von pi interessiere liefern beide Formeln tolle Ergebnisse.

Ok, aber irgendwelche "Zielsetzung" muss es doch geben, sonst hätte ich mir die zweite Formel doch auch sparen können. Wieder die Frage:

Welche sind dies?
Wer formuliert sie?
Wer löst sie?



Vielleicht ist aber auch alles anders und die Vorlesung Numerik I, II sollte mir nur den Weg zur Lösung 1 zeigen und mich auf die Probleme, die entstehen können, wenn ich diese, z.b. mit matlab umsetzten will , aufmerksam machen.
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Vielleicht ist aber auch alles anders und die Vorlesung Numerik I, II sollte mir nur den Weg zur Lösung 1 zeigen und mich auf die Probleme, die entstehen können, wenn ich diese, z.b. mit matlab umsetzten will , aufmerksam machen.

Genauso würde ich das sehen.
tigerbine Auf diesen Beitrag antworten »

Ok, dann wird der Hauptteil einer Numerik Prüfung darin bestehen - Fragen zum Thema: "Wie sind zu zur Formel I gekommen? " zu stellen und nicht "wie würden sie diese unter folgenden ... Zielsetzungen implementieren?"
mathemaduenn Auf diesen Beitrag antworten »
Formel
Hallo Tigerbine,
Bei deiner Formel wäre es schonmal ein Ansatz die nötigen Operationen durchzuzählen. Was sonst noch für die 2. Formel spricht sehe ich gerade nicht.

viele Grüße
mathemaduenn
tigerbine Auf diesen Beitrag antworten »
RE: Formel
Also ich sag mal Danke an alle die sich an einer Antwort versucht haben. Durch googlen habe ich auch ein Skript gefunden, was die Vorlesung mehr unter dem Aspekt der Implementierung sieht.

Auf jedem Fall sind mir durch den Thread noch ein paar Ideen zur Nachbereitung der Vorlesung gekommen.

Danke,
tigerbine Wink
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »