Algorithmen und mathematische Grundlagen



  • Welche Algorithmen die in der Informatik Anwendung finden basieren auf welchen mathematischen Grundlagen? (Grundrechenarten können vernachlässigt werden)

    Bubblesort: Aussagenlogik
    ...



  • binäre Suche <=> Intervallschachtelung



  • Huffman-Codierung <=> Informationstheorie (ok, irgendwie ja alle Kompression)
    Bezier-Kurven <=> Bernstein-Polynome



  • aufzählung schrieb:

    Welche Algorithmen die in der Informatik Anwendung finden basieren auf welchen mathematischen Grundlagen? (Grundrechenarten können vernachlässigt werden)

    Bubblesort: Aussagenlogik
    ...

    Was hat den Bubblesort mit Aussagenlogik zu tun?



  • aus Wiki: "Algorithmen sind eines der zentralen Themen der Informatik und Mathematik."
    und nochmal aus Wiki "Historisch hat sich die Informatik als Wissenschaft aus der Mathematik entwickelt"

    Nenne mal nen Algorithmus, der keine Mathematik enthält...
    Ansonsten gibts da ja noch "Algorithm = logic + control". Von daher kannste mit Sicherheit einen Algorithmus nennen und sagen "DAS ist Aussagenlogik".



  • Foobie schrieb:

    aus Wiki: "Algorithmen sind eines der zentralen Themen der Informatik und Mathematik."

    Ich denke nicht, dass Algorithmen ein zentrales Thema der Mathematik sind. Klar, in der Mathematik fällt schon mal ein Algorithmus ab, aber das ist ja nicht das Ziel dieser Wissenschaft.

    Foobie schrieb:

    und nochmal aus Wiki "Historisch hat sich die Informatik als Wissenschaft aus der Mathematik entwickelt"

    In dem Zusammenhang ist wohl der Teil "als Wissenschaft" ganz besonders wichtig. Informatik ist aber mehr als nur die Wissenschaft. Es gibt sehr viele (nicht wissenschaftliche) Teilbereiche der Informatik, die andere Ursprünge haben.



  • Gregor schrieb:

    Foobie schrieb:

    aus Wiki: "Algorithmen sind eines der zentralen Themen der Informatik und Mathematik."

    Ich denke nicht, dass Algorithmen ein zentrales Thema der Mathematik sind.

    natürlich geht es auch darum. Am Anfang des Studiums fängt man meisten damit an, dass man einfache Beweise durch Induktion macht, um den Prinzip der Induktion zu verstehen, das im Prinzip das Erlenen und Anwenden eines Beweisalgorithmus. Und sonst, Beweise laufen immer nach einem bestimmten Schema, den man erst kennen (oder selber herausfinden [was sehr schwer sein kann]) muss.

    Es gibt Bereiche, wo man Algorithmen ausführlich behandelt, mir fallen zum Beispiel Numerik, Logik, Modelltheorie, Zahlentheorie ein.

    Gregor schrieb:

    aber das ist ja nicht das Ziel dieser Wissenschaft.

    und was ist denn "das Ziel" der Wissenschaft?



  • supertux schrieb:

    natürlich geht es auch darum. Am Anfang des Studiums fängt man meisten damit an, dass man einfache Beweise durch Induktion macht, um den Prinzip der Induktion zu verstehen, das im Prinzip das Erlenen und Anwenden eines Beweisalgorithmus. Und sonst, Beweise laufen immer nach einem bestimmten Schema, den man erst kennen (oder selber herausfinden [was sehr schwer sein kann]) muss.

    Wenn Beweisen so einfach algorithmisch durchführbar wäre, hätte man Mathematiker schon längst durch Maschinen ersetzt. 🙂

    supertux schrieb:

    Es gibt Bereiche, wo man Algorithmen ausführlich behandelt, mir fallen zum Beispiel Numerik, Logik, Modelltheorie, Zahlentheorie ein.

    Numerik, mag sein.

    Aber Logik und Modelltheorie, definitiv nein. Das allermeiste in Logik und Modelltheorie handelt von unendlich großen, sehr oft sogar unberechenbaren Strukturen.
    Es gibt zwar Teilgebiete der Logik, die sich mit endlichen Strukturen befassen und an Algorithmen interessiert sind, die sind aber IMHO nicht repräsentativ für das, was Mathematiker unter "Logik" bzw. "Modelltheorie" verstehen.

    In Zahlentheorie sieht es ähnlich aus, würde ich sagen: Die wirklich großen Aussagen in Zahlentheorie sind keine Algorithmen, sondern reine (Nicht-)Existenz-Aussagen wie der große Satz von Fermat:
    Für alle natürlichen Zahlen n > 2 hat die Gleichung x^n + y^n = z^n keine nichttrivale, ganzzahlige Lösung.

    In Zahlentheorie gibt es aber das Teilgebiet "Computational number theory". Das befasst sich gezielt mit Algorithmen. Aber auch hier wieder: IMHO würden die meisten Zahlentheoriker sich nicht der "computational number theory" zuordnen.



  • Christoph schrieb:

    supertux schrieb:

    natürlich geht es auch darum. Am Anfang des Studiums fängt man meisten damit an, dass man einfache Beweise durch Induktion macht, um den Prinzip der Induktion zu verstehen, das im Prinzip das Erlenen und Anwenden eines Beweisalgorithmus. Und sonst, Beweise laufen immer nach einem bestimmten Schema, den man erst kennen (oder selber herausfinden [was sehr schwer sein kann]) muss.

    Wenn Beweisen so einfach algorithmisch durchführbar wäre, hätte man Mathematiker schon längst durch Maschinen ersetzt. 🙂

    Dazu ein Nachtrag: Wenn man die Church-Turing-These annimmt, dann ist alles, was Menschen prinzipiell erforschen können, durch Computer machbar. Argumentiert man weiter in diese Richtung, kann man jede Diskussion erschlagen, denn auch Physiker, Biologen etc. arbeiten dann nur nach Algorithmen, die sie im Studium lernen, also ist im Prinzip jede Wissenschaft auf Algorithmen aus. Das ist keine besonders hilfreiche Sichtweise, finde ich.



  • Christoph schrieb:

    Wenn man die Church-Turing-These annimmt, dann ist alles, was Menschen prinzipiell erforschen können, durch Computer machbar.

    Vorrausgesetzt, wir sind Computer?

    Die These bezieht sich doch auf allgemeinen Berechnungsverfahren. Allerdings ist "erforschen" ja ein bisschen mehr als sture Berechnungen durchzuführen; also z.B. das Lösen einer nicht berechenbaren Aufgabe. Und das können wir Menschen doch erstaunlich gut.

    Ansonsten sind doch solche Existenzsätze doch besonders wichtig. Ich arbeite gerade an einem Algorithmus, den ich verbessern möchte. Der ursprüngliche Algorithmus ist zwar an kleinen Stellen abgeändert, aber ich beweise hier prinzipiell die Existenz oder die Nichtexistenz von bestimmten Objekten.

    Mathematiker verfolgen ja auch konstruktive Ziele. Ist ja nicht so, als stellen die den ganzen Tag nur nutzlose Sätze auf, die keiner haben will. Auch sie wollen Probleme lösen. Dann kann man das als Formel hinschreiben oder auch als Algorithmus.



  • tphilipp schrieb:

    Christoph schrieb:

    Wenn man die Church-Turing-These annimmt, dann ist alles, was Menschen prinzipiell erforschen können, durch Computer machbar.

    Vorrausgesetzt, wir sind Computer?

    Die These bezieht sich doch auf allgemeinen Berechnungsverfahren. Allerdings ist "erforschen" ja ein bisschen mehr als sture Berechnungen durchzuführen; also z.B. das Lösen einer nicht berechenbaren Aufgabe. Und das können wir Menschen doch erstaunlich gut.

    Leider nein. Wenn Menschen nicht berechenbare Probleme lösen könnten, wäre das ein ganz erstaunliches Resultat.

    Du meinst vermutlich, dass Menschen für bestimmte Computerprogramme sagen können "das Programm terminiert" oder "das Programm terminiert nicht", obwohl das Halteproblem nicht berechenbar ist. Für bestimmte Programme kann ein Computer das aber auch problemlos berechnen und sagen, ob es terminiert oder nicht. Das Halteproblem wird erst dann unberechenbar, wenn man *beliebige* Programme zulässt. Wenn man beliebige Programme zulässt, sind Menschen aber genauso überfordert wie Computer, was Terminierungsbeweise (oder Nichtterminierungs-Beweise) angeht.

    tphilipp schrieb:

    Mathematiker verfolgen ja auch konstruktive Ziele. Ist ja nicht so, als stellen die den ganzen Tag nur nutzlose Sätze auf, die keiner haben will. Auch sie wollen Probleme lösen. Dann kann man das als Formel hinschreiben oder auch als Algorithmus.

    Wie ich oben geschrieben habe: Es gibt Teilgebiete der Mathematik, die sich mit der Entwicklung von Algorithmen befassen; es ist also nicht so, dass Algorithmen der Mathematik fremd wären. Es ist aber IMHO nicht der Fall, dass sich der Großteil der Mathematiker mit Algorithmen beschäftigt.

    Ich denke übrigens nicht, dass man die Theoreme, die Mathematiker beweisen, wahlweise als Formel oder als Algorithmus aufschreiben kann. In den allermeisten Fällen (die mir bisher begegnet sind) ist ein bewiesener Satz nur eine Formel ohne Algorithmus dahinter.

    Allgemein kann man zwar manche (wenige) Aussagen durch Angabe eines Algorithmus beweisen. Das sind (grob gesagt) konstruktive Beweise. Konstruktive Mathematik ist aber heutzutage ein ziemlich kleiner Teil der Mathematik, die allermeiste Mathematik arbeitet nicht-konstruktiv.



  • tphilipp schrieb:

    Vorrausgesetzt, wir sind Computer?

    Die These bezieht sich doch auf allgemeinen Berechnungsverfahren. Allerdings ist "erforschen" ja ein bisschen mehr als sture Berechnungen durchzuführen; also z.B. das Lösen einer nicht berechenbaren Aufgabe. Und das können wir Menschen doch erstaunlich gut.

    Tatsächlich?

    Es ist eben die Frage, ob wir nur normale Computer sind, die das "Erforschen" und Lösen von mathematischen Problemen einfach mit Hilfe von geeigneten Algorithmen durchführen, die prinzipiell auch von jedem anderen turing-vollständigen Computer übernommen werden können, oder ob wir tatsächlich mehr können (wie z.B. nach Ansicht von Roger Penrose).



  • namespace invader schrieb:

    Es ist eben die Frage, ob wir nur normale Computer sind, die das "Erforschen" und Lösen von mathematischen Problemen einfach mit Hilfe von geeigneten Algorithmen durchführen, die prinzipiell auch von jedem anderen turing-vollständigen Computer übernommen werden können, oder ob wir tatsächlich mehr können (wie z.B. nach Ansicht von Roger Penrose).

    1. Wir sind keine "normalen Computer". Wenn Du Dir das menschliche Hirn ansiehst, dann siehst Du da jede Menge Neuronen, die noch viel mehr Verbindungen zu anderen Neuronen haben. Ich habe hier schon öfter mal gehört, dass sich Leute das als hochparallelen Computer vorstellen, aber das ist es nicht. Das neuronale Netzwerk in unserem Kopf funktioniert einfach anders. Wir führen zum Beispiel kein Programm aus. Unsere einzelnen Bauteile sind super unzuverlässig und so weiter. Man kann ja auch in der eigenen Wahrnehmung sehen, dass man als Mensch ganz andere Stärken und Schwächen als ein Computer hat. Wir können zum Beispiel problemlos durch eine Fußgängerzone gehen. Probier mal, das einem Roboter mit eingebautem Computer beizubringen. Andererseits können wir ganz schlecht sqrt(125367.92367*2145.26785) rechnen. Dabei kann man so etwas mit ganz wenig "Hardware" ruck-zuck rechnen. Aber in unserem Kopf sieht die Hardware eben anders aus.

    2. Deshalb stehen wir aber trotzdem nicht über allgemeinen Sätzen bezüglich Berechenbarkeit.

    3. Penrose... merkwürdig, den Namen von diesem Physiker höre ich ganz oft von Leuten, die keinerlei Ahnung von Physik haben und die sich dann Bücher von ihm kaufen, in denen 1000 komplizierte Formeln zu finden sind. Ich habe noch keinen Physiker erlebt, der irgendetwas zu Penrose gesagt hat. Aber ok, mal gucken, was wikipedia schreibt:

    http://de.wikipedia.org/wiki/Roger_Penrose

    Wie auch Stuart Hameroff auf der Suche nach „einer physikalischen Heimat für Bewusstsein“, schlägt er ein – kontrovers diskutiertes – Modell vor, nach dem dieses im Wesentlichen auf nichtrechnerischen, derzeit im Einzelnen noch unbekannten quantenmechanischen Effekten wie EPR-Phänomenen, Quantenverschränkung oder Quanten-Nichtlokalität und Quantenkohärenz beruht, die er in den Mikrotubuli des Zellskelletts und der Schnittstelle mit dem Neuron lokalisiert.

    Nach dieser Theorie führen subtile physikalische Prozesse auf Nanometerskala (10-9 m) im Grenzgebiet zwischen klassischer Physik und Quantenmechanik in einem hochentwickelten Nervensystem zu dem, was wir „Geist“ und „Bewusstsein“ nennen. Von anderen Quantenphysikern, Neurobiologen und Philosophen, wie Metzinger, Roth oder Koch, wird das Hameroff-Penrose-Modell allerdings abgelehnt.

    Ok, er steht mit seinen Ideen bezüglich des Bewusstseins also ziemlich allein da. Und ich kann seine Aussage auch nicht ganz nachvollziehen. Ich sehe zumindest nicht, inwiefern Quantenmechanik irgendetwas mit Bewusstsein zu tun haben sollte. "Bewusstsein" bringt man doch mit Lebewesen in Verbindung. Die Quantenmechanik hat aber insgesamt überhaupt keine direkte Verbindung zu "Leben".

    Christoph wird Dir im Zusammenhang mit diesem Thema vermutlich "Gödel, Escher, Bach" als Lektüre empfehlen.



  • Gregor schrieb:

    1. Wir sind keine "normalen Computer". Wenn Du Dir das menschliche Hirn ansiehst, dann siehst Du da jede Menge Neuronen, die noch viel mehr Verbindungen zu anderen Neuronen haben.

    Natürlich funktioniert das menschliche Gehirn anders als der Computer hier unter meinem Schreibtisch. Mit "normalem Computer" meinte ich, dass es auf Basis der selben physikalischen Prinzipien arbeitet und äquivalent im Sinne der Church-Turing-These dazu ist. Eben im Gegensatz zu den Vorstellungen von Penrose.

    Man kann ja auch in der eigenen Wahrnehmung sehen, dass man als Mensch ganz andere Stärken und Schwächen als ein Computer hat. Wir können zum Beispiel problemlos durch eine Fußgängerzone gehen. Probier mal, das einem Roboter mit eingebautem Computer beizubringen.

    Das geht (unter der Annahme oben) aber problemlos, man muss dazu nur einen Computer mit ausreichend Speicher alle Neuronen und sonstige Vorgänge des Gehirns simulieren lassen, dann kann er alles, was der Mensch auch kann, einschließlich mathematischer Intuition und so weiter. Ok, beim durch-die-Fußgängerzone-laufen muss es noch in Echtzeit funktionieren, aber das ist auch kein grundlegendes Problem.

    Deshalb stehen wir aber trotzdem nicht über allgemeinen Sätzen bezüglich Berechenbarkeit.

    Das ist die Frage...

    Ok, er steht mit seinen Ideen bezüglich des Bewusstseins also ziemlich allein da. Und ich kann seine Aussage auch nicht ganz nachvollziehen.

    Die Motivation dahinter ist, dass Menschen anscheinend/vermeintlich mehr können, als sie können dürften, wenn man sie als Computer auffasst, was dann eben durch besondere physikalische Vorgänge im Gehirn erklärt werden muss.

    Ich glaube ja auch nicht, dass er damit Recht hat, aber man kann es eben als Theorie hinnehmen, zumindest bis jemand tatsächlich das menschliche Gehirn vernünftig funktionierend "nachbaut".

    Wo wir bei Buchempfehlungen sind, ich empfehle an der Stelle "The Fabric of Reality" von David Deutsch, auch zu dem angesprochenen Zusammenhang von "Leben" und Dingen wie Quantenmechanik.



  • Gregor schrieb:

    Ich denke nicht, dass Algorithmen ein zentrales Thema der Mathematik sind. Klar, in der Mathematik fällt schon mal ein Algorithmus ab, aber das ist ja nicht das Ziel dieser Wissenschaft.

    Was sind denn zentrale Aspekte der Mathematik, was ist das Ziel der Mathematik? Wenn ich mir so "Algebra of Programming" etc. anschaue, dann ist das ganz klar Mathematik. Wenn ich mir das Lambda-Kalkuel anschaue, dann ist das ganz klar Mathematik, ...

    Wenn Beweisen so einfach algorithmisch durchführbar wäre, hätte man Mathematiker schon längst durch Maschinen ersetzt.

    Typinferenz und automatisches Beweisen sind aequivalent ("Theorems for Free"). Echtes "Beweisen" erfordert meist aber etwas Kreativitaet, das ist schwer algorithmisch umsetzbar.

    Es ist aber IMHO nicht der Fall, dass sich der Großteil der Mathematiker mit Algorithmen beschäftigt.

    Und welche Rolle spielt das? Vielleicht sind fallen die meisten Informatiker als Mathematiker deiner Meinung durch. Wahrscheinlich befasst sich auch der wenigste Teil der Informatiker mit Algorithmen.

    eben als Theorie hinnehme

    Mehr wohl als Hypothese.



  • Gregor schrieb:

    Ich habe hier schon öfter mal gehört, dass sich Leute das als hochparallelen Computer vorstellen, aber das ist es nicht. Das neuronale Netzwerk in unserem Kopf funktioniert einfach anders.

    Nicht grundlegend. Neuronen sind ein einfacher Eingabe-Ausgabemechanismus plus eine kodierte Lernregel. Dass wir nicht wissen, wie die Lernregel lautet, ändert nichts grundlegendes.

    Wir führen zum Beispiel kein Programm aus. Unsere einzelnen Bauteile sind super unzuverlässig und so weiter.

    Sie sind es nicht zwingend. Wir haben Neuronen, die zuverlässig wie ein Uhrwerk sind. Am Eindruckvollsten sind dabei die Neuronen von zum Beispiel Fledermäusen, die Echolot in Echtzeit mit unglaublicher Präzision durchführen. Unser visuelles System steht dem auch in nichts nach. Es sieht damit eher so aus, dass die Unzuverlässigkeit der Zellen im Gehirn einen Sinn hat.

    (Aus Experimenten mit dynamischen Systemen weiß man, dass man bestimmtes Menschliches Verhalten nur simulieren kann, wenn man in der Simulation ordentlich rauschen durch eine Zufallsfunktion gibt, deren Stärke ziemlich genau dem Rauschen im Gehirn entspricht. Aber das ist kein Hinderungsgrund, Zufallsrauschen können wir auch ziemlich gut annähern.)

    Der Vergleich mit einem massiv-parallelen Computer ist also nicht zu weit hergeholt. Die Algorithmen unterscheiden sich grundsätzlich von dem, was wir so verwenden, aber das kommt eben durch die Limitierungen des Neuronenprinzips. Und wir haben ja auch wenig Computer mit einer Million Prozessoren, von daher ist es nicht verwunderlich, dass unsere Algorithmen nur schwer übertragbar sind ;). Da ist es einfacher, neue Algorithmen zu entwerfen: Wo im visuellen System eine Featureanalyse durch die Zellen durchgeführt wird, machen wir halt ne Faltung. Das Ergebnis bleibt das Selbe.

    Man kann ja auch in der eigenen Wahrnehmung sehen, dass man als Mensch ganz andere Stärken und Schwächen als ein Computer hat. Wir können zum Beispiel problemlos durch eine Fußgängerzone gehen. Probier mal, das einem Roboter mit eingebautem Computer beizubringen.

    Inzwischen ginge das sogar. Mit dynamischen Systemen geht das zum Teil sehr einfach. Ist aber noch ein Forschungsgebiet. Dass unsere Roboter das noch nicht so gut können, liegt wohl eher daran, dass wir das Problem noch nicht vollständig verstanden haben. Da hat unser Gehirn eben doch ein paar Millionen Jahre Vorsprung.



  • knivil schrieb:

    Was sind denn zentrale Aspekte der Mathematik, was ist das Ziel der Mathematik?

    Ich sehe Mathematik als Strukturwissenschaft. Als solche untersucht sie abstrakte Strukturen. Wo die Strukturen herkommen, ist dabei erstmal nebensächlich. In der Vergangenheit gab es sicherlich eine ganze Menge Strukturen, die durch die Physik motiviert wurden. In Gegenwart und Zukunft sind sicherlich auch eine ganze Menge Strukturen dabei, die durch die Informatik motiviert werden. Aber genauso wie in der Informatik die Informationen, die verarbeitet werden, aus dem Kontext gerissen werden, um allgemeine Aussagen über die Verarbeitung treffen zu können, reißt natürlich auch die Mathematik die Strukturen aus ihrem Kontext. Die Mathematik versucht, Eigenschaften dieser Strukturen zu bestimmen und zu beweisen.

    Natürlich gibt es Überschneidungen der Mathematik mit der theoretischen Informatik. Viele Aspekte der theoretischen Informatik sehe ich auch durchaus als Mathematik an. Es gibt zumindest einige Themen, die man wohl beiden Disziplinen zuordnen könnte. Die Frage ist aber doch, warum die Themen in der jeweiligen Disziplin behandelt werden. In der theoretischen Informatik betrachtet man bestimmte abstrakte Strukturen, weil sie etwas mit Informationsverarbeitung zu tun haben. Für die Mathematik ist das Nebensache. Dort ist die Hauptsache, dass es sich um abstrakte Strukturen handelt, die aus irgendeinem Grund sehr interessant sind. Was ich sagen will ist, dass der Aspekt der Informationsverarbeitung in erster Linie nur für die Informatik wichtig ist. Und daran hängen dann auch die Algorithmen, die in der Informatik natürlich ein Hauptaspekt sind.

    Man sagt ja auch nicht, Mathematiker beschäftigen sich mit Physik, nur weil es gewisse Überschneidungen zwischen den beiden Disziplinen gibt. ...oder "Mathematiker befassen sich mit Wirtschaft".


Log in to reply