Ich habe vor kurzem angefangen, mich mit mathematischer Optimierung zu beschäftigen und liebe es. Es scheint, dass viele Optimierungsprobleme leicht als lineare Programme ausgedrückt und gelöst werden können (z. B. Netzwerkflüsse, Kanten- / Scheitelpunktabdeckung, reisender Verkäufer usw.). Ich weiß, dass einige von ihnen NP-hart sind, aber der Punkt ist, dass sie es können 'als lineares Programm gerahmt', wenn nicht optimal gelöst.
Das brachte mich zum Nachdenken: Wir haben in der gesamten Schule / Hochschule immer Systeme linearer Gleichungen und linearer Algebra gelernt. Und die Fähigkeit von LPs zu sehen, verschiedene Algorithmen auszudrücken, ist irgendwie faszinierend.
Frage: Obwohl überall um uns herum nichtlineare Systeme vorherrschen, wie / warum sind lineare Systeme für die Informatik so wichtig? Ich verstehe, dass sie das Verständnis vereinfachen und die meiste Zeit rechnerisch nachvollziehbar sind, aber ist es das? Wie gut ist diese "Annäherung"? Vereinfachen wir uns zu stark und sind die Ergebnisse in der Praxis noch aussagekräftig? Oder ist es nur "Natur", dh die faszinierendsten Probleme sind tatsächlich einfach linear?
Wäre es sicher, dass "lineare Algebra / Gleichungen / Programmierung" die Eckpfeiler von CS sind? Wenn nicht, was wäre dann ein guter Widerspruch? Wie oft beschäftigen wir uns mit nichtlinearen Dingen (ich meine nicht unbedingt theoretisch, sondern auch vom Standpunkt der Lösbarkeit aus, dh nur zu sagen, dass es NP nicht schneidet; es sollte eine gute Annäherung an das Problem geben und würde es landen up linear sein?)
Antworten:
Die Prämisse der Frage ist ein wenig fehlerhaft: Es gibt viele, die argumentieren würden, dass Quadratics die eigentliche "Grenze" für Traktabilität und Modellierung sind, da Probleme mit kleinsten Quadraten fast so "einfach" sind wie lineare Probleme. Es gibt andere, die argumentieren würden, dass Konvexität (oder in bestimmten Fällen sogar Submodularität) die Grenze für die Traktierbarkeit ist.
Diese Gedächtnislosigkeit verleiht Effizienz: Ich kann Dinge in Stücke zerbrechen oder iterativ arbeiten, und ich verliere dadurch nicht. Ich kann immer noch schlechte Entscheidungen treffen (siehe gierige Algorithmen), aber das Aufteilen der Dinge selbst tut mir nicht weh.
Dies ist ein Grund, warum Linearität eine solche Kraft hat. Es gibt wahrscheinlich viele andere.
quelle
" Obwohl nichtlineare Systeme überall um uns herum vorherrschen, wie / warum sind lineare Systeme für die Informatik so wichtig?"
Hier ist eine teilweise Antwort in meinem Kopf: Ich denke, das liegt daran, dass die Natur reich an Objekten / Phänomenen ist - darstellbar durch Funktionen, die, obwohl sie auf ihren Operanden nichtlinear sind, tatsächlich Mitglieder linearer Räume sind. Die Welle funktioniert in einem Hilbert-Raum, die Komponenten in einem Fourier-Spektrum, Polynomringe, stochastische Prozesse - alle verhalten sich so. Selbst sehr allgemeine Definitionen von gekrümmten Räumen bestehen aus der Erstellung kleiner Diagramme flacher Räume (Mannigfaltigkeiten, Riemann-Flächen usw.). Darüber hinaus ist die Natur voller Symmetrien, und das Studium von Symmetrien befasst sich ausnahmslos mit linearen Operatoren (die Repräsentationstheorie schleicht sich meiner Meinung nach allgegenwärtig in viele Bereiche der Informatik ein).
Dies gilt zusätzlich zu den Fällen, in denen die Operatoren selbst linearer Natur sind.
Ein großer Teil der Probleme, für die wir Computerprogramme benötigen, tritt entweder direkt als natürlich auftretende Phänomene auf oder wird von diesen abstrahiert. Vielleicht sollte das Studieren / Lösen linearer Systeme doch keine große Überraschung sein?
quelle