Comecei a me envolver com a otimização matemática recentemente e estou adorando. Parece que muitos problemas de otimização podem ser facilmente expressos e resolvidos como programas lineares (por exemplo, fluxos de rede, cobertura de borda / vértice, vendedor ambulante etc.). Sei que alguns deles são difíceis de NP, mas o ponto é que eles podem ser 'enquadrado como um programa linear' se não for resolvido da melhor maneira.
Isso me fez pensar: sempre aprendemos sistemas de equações lineares, álgebra linear em toda a escola / faculdade. E ver o poder dos LPs em expressar vários algoritmos é meio fascinante.
Pergunta: Embora tenhamos sistemas não lineares predominantes ao nosso redor, como / por que os sistemas lineares são tão cruciais para a ciência da computação? Entendo que eles ajudam a simplificar o entendimento e são tratáveis computacionalmente na maioria das vezes, mas é isso? Quão boa é essa 'aproximação'? Estamos simplificando demais e os resultados ainda são significativos na prática? Ou é apenas "natureza", ou seja, os problemas mais fascinantes são de fato simplesmente lineares?
Seria seguro que 'álgebra linear / equações / programação' sejam as pedras angulares do CS? Se não, então o que seria uma boa contradição? Quantas vezes lidamos com coisas não lineares (eu não necessariamente quero dizer teoricamente, mas também do ponto de vista da 'solvabilidade', ou seja, apenas dizer que o NP não é suficiente; deve haver uma boa aproximação ao problema e ele chegaria sendo linear?)
Respostas:
A premissa da pergunta é um pouco falha: muitos argumentam que os quadráticos são o verdadeiro "limite" para tratabilidade e modelagem, uma vez que os problemas dos mínimos quadrados são quase tão "fáceis" quanto os problemas lineares. Outros argumentam que a convexidade (ou mesmo submodularidade em certos casos) é o limite para a tratabilidade.
Essa falta de memória confere eficiência: eu posso quebrar as coisas em pedaços ou trabalhar iterativamente, e não perco em virtude disso. Ainda posso tomar más decisões (cf. algoritmos gananciosos), mas o ato de dividir as coisas em si não me machuca.
Essa é uma das razões pelas quais a linearidade tem esse poder. Provavelmente existem muitos outros.
fonte
" Embora tenhamos sistemas não lineares predominantes ao nosso redor, como / por que os sistemas lineares são tão cruciais para a ciência da computação?"
Aqui está uma resposta parcial em minha mente: Eu acho que é porque a natureza é abundante em objetos / fenômenos - representáveis por funções que, embora não lineares em seus operandos, são na verdade membros de espaços lineares. A onda funciona em um espaço de Hilbert, os componentes em um espectro de quatro camadas, anéis polinomiais, processos estocásticos - todos se comportam dessa maneira. Até definições muito gerais de espaços curvos são construídas para compor pequenos gráficos de espaços planos (variedades, superfícies de Riemann, ..). Além disso, a natureza é cheia de simetrias e o estudo de simetrias invariavelmente entra em estudo de operadores lineares (a teoria da representação, em minha opinião, está se infiltrando em muitas áreas da ciência da computação de maneira tão onipresente).
Isso ocorre além dos casos em que os próprios operadores são de natureza linear.
Uma grande fração dos problemas para os quais precisamos de programas de computador surge diretamente como ou é abstraída de fenômenos que ocorrem naturalmente. Talvez estudar / resolver sistemas lineares não deva ser uma grande surpresa, afinal?
fonte