Hace poco comencé a involucrarme con la Optimización matemática y me encanta. Parece que muchos problemas de optimización se pueden expresar y resolver fácilmente como programas lineales (por ejemplo, flujos de red, cobertura de borde / vértice, vendedor ambulante, etc.) Sé que algunos de ellos son NP-hard, pero el punto es que pueden ser 'enmarcado como un programa lineal' si no se resuelve de manera óptima.
Eso me hizo pensar: siempre nos han enseñado sistemas de ecuaciones lineales, álgebra lineal en toda la escuela / universidad. Y ver el poder de los LP para expresar varios algoritmos es algo fascinante.
Pregunta: Aunque tenemos sistemas no lineales predominantes a nuestro alrededor, ¿cómo / por qué los sistemas lineales son tan cruciales para la informática? Entiendo que ayudan a simplificar la comprensión y son manejables computacionalmente la mayoría de las veces, pero ¿es eso? ¿Qué tan buena es esta 'aproximación'? ¿Estamos simplificando demasiado y los resultados siguen siendo significativos en la práctica? ¿O es simplemente "naturaleza", es decir, los problemas que son más fascinantes son simplemente lineales?
¿Sería seguro asegurar que 'álgebra lineal / ecuaciones / programación' son las piedras angulares de CS? Si no, ¿cuál sería una buena contradicción? ¿Con qué frecuencia tratamos con cosas no lineales? hasta ser lineal?)
Respuestas:
La premisa de la pregunta es un poco defectuosa: hay muchos que argumentan que las cuadráticas son el "límite" real para la trazabilidad y el modelado, ya que los problemas de mínimos cuadrados son casi tan "fáciles" como los problemas lineales. Hay otros que argumentan que la convexidad (o incluso la submodularidad en ciertos casos) es el límite para la capacidad de seguimiento.
Quizás lo que es más relevante es "¿por qué los sistemas lineales admiten soluciones manejables?" que no es exactamente lo que pediste, pero está relacionado. Una perspectiva sobre esto es la componibilidad. Dado que la propiedad definitoria de un sistema lineal es que , esto imparte una especie de "falta de memoria" al sistema. Para construir una solución a un problema, puedo concentrarme en piezas individuales y combinarlas sin penalización. De hecho, la premisa de la mayoría de los algoritmos para el flujo es precisamente eso.F( x + y) = f( x ) + f( y)
Esta falta de memoria imparte eficiencia: puedo romper cosas en pedazos, o trabajar de forma iterativa, y no pierdo en virtud de hacerlo. Todavía puedo tomar malas decisiones (cf algoritmos codiciosos) pero el acto de dividir las cosas en sí no me duele.
Esta es una razón por la cual la linealidad tiene tanto poder. Probablemente hay muchos otros.
fuente
" Aunque tenemos sistemas no lineales predominantes a nuestro alrededor, ¿cómo / por qué los sistemas lineales son tan cruciales para la informática?"
Aquí hay una respuesta parcial en mi mente: creo que es porque la naturaleza está llena de objetos / fenómenos, representables por funciones que, aunque no son lineales en sus operandos, son en realidad miembros de espacios lineales. La onda funciona en un espacio de Hilbert, los componentes en un espectro de Fourier, anillos polinomiales, procesos estocásticos, todos se comportan de esa manera. Incluso las definiciones muy generales de espacios curvos se construyen a partir de componer pequeños cuadros de espacios planos (colectores, superficies de Riemann, ...). Además, la naturaleza está llena de simetrías y el estudio de las simetrías invariablemente entra en el estudio de los operadores lineales (la teoría de la representación, en mi opinión, se está infiltrando en muchas áreas de la informática de manera muy ubicua).
Estos se suman a los casos en que los operadores mismos son de naturaleza lineal.
Una gran parte de los problemas para los cuales necesitamos programas de computadora, surgen directamente como un fenómeno natural o se abstraen de él. ¿Quizás estudiar / resolver sistemas lineales no debería ser una gran sorpresa, después de todo?
fuente