3. Probleme die Allgemein nur mit Computern gelöst werden könnnen

Probleme die Allgemein nur mit Computern gelöst werden könnnen

  • ?

    Moin,
    ich suche ("Mathematische") Probleme die allgemein nur mit Hilfe von Algorithmen gelöst werden können.
    Ich mein nicht irgenwelche numerischen sachen ala Dreikörper problem.

    Meist waren das glaub relativ simple aufgaben, von denen man erstmal gar nicht erwartet hätte das man sie nicht durch eine Formeln im allgemeinen lösen kann.

    Ich kanne mal welche aber sie wollen mir bei besten willen nicht mehr einfallen.

    Eine genauere Beschreibung kann ich leider nicht liefern. Ich hoffe ihr könnt mir weiter helfen.

    MFG Sta Li F

    0
  • V

    du meinst vermutlich http://de.wikipedia.org/wiki/Computerbeweis

    0
  • ?

    Moin,
    danke, aber passt noch nicht wirklich, wenn ich bei Google nach Computer beweisen such.
    Ich schau mal evtl. fällt mir noch ein beispiel ein, werd es dann nochmal posten.

    MFG

    0

  • Meinst du Dinge die nicht formal bewiesen werden können, aber von denen die meisten Mathematiker annehmen dass sie stimmen? Und die man dann halt mit dem Computer für Millionen von Fällen testen kann, und wenn man nach X Millionen Läufen noch nix gefunden hat wo es nicht passen würde, einfach sagt "wird schon passen"?
    Das wäre dann kein "Beweis" mittels Computer, sondern bloss ein Test, der "noch nicht fehlgeschlagen" ist. Da gibt's soweit ich mich erinnere in der Cryptographie ein paar Sachen, und in der Numerik (Primzahlen und so).

    Oder meinst du Sachen für die es nur numerische Lösungen gibt, also diverse Integrale die man nur numerisch lösen kann? Da gibt's tonnenweise davon. Hier rein fällt z.B. auch das von dir genannte Dreikörperproblem.

    Oder meinst du Dinge wie dass man die N. Zahl aus einer Folge nicht direkt ausrechnen kann, sondern alle N-1 Zahlen davor ausrechnen muss? Was es dann für grosse N nahezu unmöglich macht es ohne Computer zu machen. Hier wären sämtliche Fraktale zu nennen. Diese haben oft auch ganz einfache Formeln, wie z.B. x(n) = x(n-1)^2 + c für das Mandelbrot-Fraktal (x und c sind komplexe Zahlen). Oder natürlich auch alle "deterministischen Zufallszahlen-Generatoren" (einfachstes Beispiel: Lineare Kongruenzgeneratoren aka LCG).

    0
  • ?

    Sta Li F schrieb:

    Moin,
    ich suche ("Mathematische") Probleme die allgemein nur mit Hilfe von Algorithmen gelöst werden können.
    Ich mein nicht irgenwelche numerischen sachen ala Dreikörper problem.

    Meist waren das glaub relativ simple aufgaben, von denen man erstmal gar nicht erwartet hätte das man sie nicht durch eine Formeln im allgemeinen lösen kann.

    Ich kanne mal welche aber sie wollen mir bei besten willen nicht mehr einfallen.

    Eine genauere Beschreibung kann ich leider nicht liefern. Ich hoffe ihr könnt mir weiter helfen.

    MFG Sta Li F

    Mit Computern kann man ganz gut das Unendliche darstellen. Endlosschleifen ftw.

    0
  • ?

    Moin,

    ein Beispiel, zwar ein bisl makaber aber was solls:

    Eine reihe von personen stehen im Kreis. Dann wird jede n-te person zb. jede 3 Umgebracht. Und man soll herrausfinden welche person überlebt.
    Ich meine diese Aufgabe kann man nur in Spezialfällen mit einer Formeln lösen.

    MFG

    0
  • V

    Sta Li F schrieb:

    Eine reihe von personen stehen im Kreis. Dann wird jede n-te person zb. jede 3 Umgebracht. Und man soll herrausfinden welche person überlebt.
    Ich meine diese Aufgabe kann man nur in Spezialfällen mit einer Formeln lösen.

    nebenbei: das ding heißt unter anderem Josephus-Problem
    http://de.wikipedia.org/wiki/Josephus-Problem

    0
  • V

    also suchst du probleme, die ohne fließkommazahlen auskommen und keine sehr schnell berechenbare lösungsformel haben.
    vielleicht haste am komplexitätenzoo spaß: http://qwiki.stanford.edu/wiki/Complexity_Zoo:N#npc
    und zum reinkommen das bekannte problem des handlungsreisenden. http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

    0

  • Fibonacci Zahlen sind doch auch sowas, oder täusche ich mich da jetzt?
    Also Fib(N) ausrechnen.
    Oder die N. Primzahl ausrechnen.
    Oder ...

    Im Prinzip alles, was ein "Summe über" Zeichen in der (einfachsten) Formel hat, und ohne Unendlichkeiten auskommt.

    Mit Unendlichkeiten ("Summe über i von 0 bis unendlich") gibt's natürlich auch Haufenweise davon, z.B. die ganzen Winkelfunktionen, Wurzeln die kein Ganzzahliges Ergebnis haben, Logarithmen etc.

    0
  • V

    hustbaer schrieb:

    Fibonacci Zahlen sind doch auch sowas, oder täusche ich mich da jetzt?
    Also Fib(N) ausrechnen.

    nee. gibt ne schnelle formel.

    Oder die N. Primzahl ausrechnen.
Oder ...

    ja.

    Im Prinzip alles, was ein "Summe über" Zeichen in der (einfachsten) Formel hat, und ohne Unendlichkeiten auskommt.

    nee. arithmetische und geometriesche reihen haben schnelle formeln.

    0

  • Im Prinzip alles, was ein "Summe über" Zeichen in der (einfachsten) Formel hat, und ohne Unendlichkeiten auskommt.

    nee. arithmetische und geometriesche reihen haben schnelle formeln.

    Grmpf. 🙂
    OK. Aber ich hoffe du weisst was ich meinte.

    Wenn die schnellste (nicht einfachste, das war natürlich Unsinn) Formel ein "Summe über i=0 bis n" drin hat, dann kann man es für grosse n nur sinnvoll mit Computern lösen. Wenn man natürlich nur z.B. log(n) Elemente durchklappern muss, kann man es für relativ grosse n natürlich auch noch mit Hand rechnen. Wenn man unbedingt will 😉

    0
  • V

    hustbaer schrieb:

    Wenn die schnellste (nicht einfachste, das war natürlich Unsinn) Formel ein "Summe über i=0 bis n" drin hat, dann kann man es für grosse n nur sinnvoll mit Computern lösen.

    sagen wir mal, wir haben nen wissenschaflichen taschenrechner, der sauviele stellen hat. dann meine ich mit schnell wenn ich als mensch mit taschenrechner das locker ausrechnen kann.
    zum beispiel für
    summe für i=1 bis 154785 von i^2
    dann tippe ich
    154785*(154785-1)(2154785+1)/6

    nur so meinte ich das. hier war n=154785
    daß man für große n am ende doch nen computer braucht, weil millionenstellige multiplikationen dem menschen weh tun, hab ich ignoriert im sinne des fragestellers.

    mathematisch gesehen haste natürlich recht. sorry.

    ansonsten ist die aussage "schnellste formel hat summenzeichen bis n" nur "schnellster algo braucht O(n)".

    0
  • ?

    hustbaer schrieb:

    Fibonacci Zahlen sind doch auch sowas, oder täusche ich mich da jetzt?
    Also Fib(N) ausrechnen.
    Oder die N. Primzahl ausrechnen.

    für Fib(N) gibt es seit (spätestens) 1730 die berühmte Formel von Moivre-Binet:

    (a^n-b^n)/(a-b), wobei a = .5(1+sqrt(5)) und b = .5(1-sqrt(5))

    Um die N-te Primzahl auszurechnen, muß man dagegen schon etwas früher aufstehen 😃

    0
Anmelden zum Antworten