Я начал заниматься математической оптимизацией совсем недавно и мне это нравится. Кажется, многие проблемы оптимизации могут быть легко выражены и решены в виде линейных программ (например, сетевые потоки, покрытие краев / вершин, коммивояжёр и т. Д.). Я знаю, что некоторые из них являются NP-сложными, но суть в том, что они могут быть «оформлена как линейная программа», если не решена оптимально.
Это заставило меня задуматься: нас всегда учили системам линейных уравнений, линейной алгебре на протяжении всей школы / колледжа. И увидеть мощь LP для выражения различных алгоритмов это довольно увлекательно.
Вопрос: Хотя вокруг нас распространены нелинейные системы, как / почему линейные системы так важны для информатики? Я понимаю, что они помогают упростить понимание и в большинстве случаев поддаются вычислению, но так ли это? Насколько хорошо это «приближение»? Мы слишком упрощаемся, и результаты все еще значимы на практике? Или это просто «природа», то есть проблемы, которые являются наиболее захватывающими, действительно просто линейны?
Будет ли безопасно гарантировать, что «линейная алгебра / уравнения / программирование» является краеугольным камнем CS? Если нет, то в чем было бы хорошее противоречие? Как часто мы имеем дело с нелинейными вещами (я имею в виду не обязательно теоретически, но также и с точки зрения «решаемости», то есть просто говоря, что это NP, не сокращает его; должно быть хорошее приближение к проблеме, и она приземлится быть линейным?)
источник
Ответы:
Суть вопроса несколько ошибочна: многие утверждают, что квадратики являются реальной «границей» для управляемости и моделирования, поскольку задачи наименьших квадратов почти так же «легки», как и линейные задачи. Есть другие, которые утверждают, что выпуклость (или даже субмодульность в некоторых случаях) является границей для управляемости.
Возможно, что более актуально, так это «почему линейные системы допускают управляемые решения?» что не совсем то, что вы просили, но связано. Одной из точек зрения на это является составность. Поскольку определяющим свойством линейной системы является то, чтое( х + у) = f( х ) + ф( у) это придает системе некое подобие памяти. Чтобы создать решение проблемы, я могу сосредоточиться на отдельных частях и комбинировать их без штрафа. Действительно, предпосылка большинства алгоритмов для потока именно такова.
Это отсутствие памяти придает эффективность: я могу разбивать вещи на части или работать итеративно, и я не проигрываю благодаря этому. Я все еще могу принимать плохие решения (например, жадные алгоритмы), но сам процесс деления вещей не повредит мне.
Это одна из причин, почему линейность обладает такой силой. Есть, вероятно, много других.
источник
« Хотя вокруг нас распространены нелинейные системы, как / почему линейные системы так важны для информатики?»
Вот частичный ответ в моем уме: я думаю, что это потому, что природа изобилует объектами / явлениями - представляемыми функциями, которые, хотя и являются нелинейными по своим операндам, на самом деле являются членами линейных пространств. Волновые функции в гильбертовом пространстве, компоненты в спектре Фурье, кольца полиномов, случайные процессы - все они ведут себя таким образом. Даже очень общие определения искривленных пространств строятся из составления небольших диаграмм плоских пространств (многообразий, римановых поверхностей и т. Д.). Более того, природа полна симметрий, и изучение симметрий неизменно входит в изучение линейных операторов (теория представлений, на мой взгляд, проникает во многие области информатики повсеместно).
Это в дополнение к случаям, когда сами операторы имеют линейный характер.
Большая часть проблем, для которых нам нужны компьютерные программы, возникают либо непосредственно, либо абстрагируются от естественных явлений. Возможно, изучение / решение линейных систем не должно быть большим сюрпризом, в конце концов?
источник