Как линейная алгебра используется в алгоритмах?

Question

Несколько моих коллег упоминали, что "линейная алгебра" очень важна при изучении алгоритмов.Я изучил множество алгоритмов и прослушал несколько курсов линейной алгебры, но не вижу связи.Итак, как линейная алгебра используется в алгоритмах?

Например, что интересного можно сделать с матрицей связности для графика?

Answer 1

Три конкретных примера:

• Линейная алгебра - это основа современной 3D-графики.По сути, это то же самое, чему вас учили в школе.Данные хранятся в 3d-пространстве, которое проецируется на 2d-поверхность, которую вы видите на своем экране.
• Большинство поисковых систем основаны на линейной алгебре.Идея состоит в том, чтобы представить каждый документ в виде вектора в гиперпространстве и посмотреть, как векторы соотносятся друг с другом в этом пространстве.Это используется проект lucene, среди прочих.Видишь ВСМ.
• Некоторые современные алгоритмы сжатия, такие как тот, который используется в формате ogg vorbis, основаны на линейной алгебре или, более конкретно, на методе, называемом Векторное Квантование.

В основном это сводится к тому факту, что линейная алгебра является очень мощным методом при работе с несколькими переменными, и есть огромные преимущества в использовании ее в качестве теоретической основы при разработке алгоритмов.Во многих случаях этот фундамент не так очевиден, как вы могли бы подумать, но это не значит, что его там нет.Вполне возможно, что вы уже внедрили алгоритмы, которые было бы невероятно трудно вывести без linalg.

Answer 2

Криптограф, вероятно, сказал бы вам, что понимание теории чисел очень важно при изучении алгоритмов.И он был бы прав - для своей конкретной области.Статистика тоже имеет свое применение - списки пропусков, хэш-таблицы и т.д.Полезность теории графов еще более очевидна.

Нет никакой внутренней связи между линейной алгеброй и алгоритмами;существует неотъемлемая связь между математика и алгоритмы.

Линейная алгебра - это область со многими приложениями, и алгоритмы, которые опираются на нее, следовательно, также имеют много применений.Вы не зря потратили свое время на его изучение.

Answer 3

Ха, я не могу удержаться, чтобы не выложить это здесь (хотя другие ответы хороши):

Собственный вектор стоимостью 25 миллиардов долларов.

Я не собираюсь лгать...Я даже никогда не читал это целиком...может быть, я сделаю это сейчас :-).

Answer 4

Я не знаю, можно ли сформулировать это так: "линейная алгебра очень важна при изучении алгоритмов".Я бы чуть было не сказал все наоборот.Многие, очень, очень многие задачи реального мира в конечном итоге требуют от вас решения набора линейных уравнений.Если вам в конечном итоге придется решать одну из этих задач, вам нужно будет знать о некоторых из многих алгоритмов для работы с линейными уравнениями.Многие из этих алгоритмов были разработаны, когда компьютеры были названием должности, а не машиной.Рассмотрим, например, исключение гаусса и различные алгоритмы матричного разложения.Существует много из очень сложной теории о том, как решать эти задачи, например, для очень больших матриц.

Большинство распространенных методов машинного обучения заканчиваются этапом оптимизации, который требует решения набора одновременных уравнений.Если вы не знаете линейную алгебру, вы полностью заблудитесь.

Answer 5

Многие алгоритмы обработки сигналов основаны на матричных операциях, напримерПреобразование Фурье, преобразование Лапласа, ...

Задачи оптимизации часто могут быть сведены к решению систем линейных уравнений.

Answer 6

Линейная алгебра также важна во многих алгоритмах компьютерной алгебры, как вы, возможно, догадались.Например, если вы можете свести задачу к утверждению, что многочлен равен нулю, где коэффициенты многочлена линейны по переменным x1, …, xn, тогда вы можете решить , для каких значений x1, …, xn сделайте многочлен равным 0, приравняв коэффициент каждого x^n слагаемое в 0 и решение линейной системы.Это называется методом неопределенных коэффициентов и используется, например, при вычислении разложения на частичные дроби или при интегрировании рациональных функций.

Для теории графов самая крутая вещь в матрице смежности заключается в том, что если вы берете n-ю степень матрицы смежности для невзвешенного графика (каждая запись равна либо 0, либо 1), M^n, затем каждая запись i,j будет равно количеству путей из вершины i к вершине j длины n.И если это не просто круто, то я не знаю, что это такое.

Answer 7

Все приведенные здесь ответы являются хорошими примерами линейной алгебры в алгоритмах.

В качестве мета-ответа я добавлю, что вы, возможно, используете линейную алгебру в своих алгоритмах, не зная об этом.Компиляторы, которые оптимизируют с помощью SSE(2), обычно векторизируют ваш код, параллельно обрабатывая множество значений данных.Это, по сути, элементарный Лос-Анджелес.

Answer 8

Это зависит от того, какой тип "алгоритмов".

Некоторые примеры:

• Алгоритмы машинного обучения /статистики:Линейные регрессии (метод наименьших квадратов, гребень, лассо).
• Сжатие сигналов с потерями и другая обработка (распознавание лиц и т.д.).Видишь Собственные поверхности

Answer 9

Например, что интересного можно сделать с матрицей связности для графика?

Многие алгебраические свойства матрицы инвариантны относительно перестановок вершин (например, abs (определитель)), поэтому, если два графика изоморфны, их значения будут равны.

Это источник для хорошей эвристики для определения, являются ли две диаграммы есть не изоморфно, поскольку, конечно, равенство не гарантирует существования изоморфизма.

Проверить алгебраическая теория графов для множества других интересных техник.