Как линейная алгебра используется в алгоритмах?
Это должно объединить много ответов.
# Convert dot to png via graphviz
dot -Tpng filename.dot -o filename.png
# Convert dot to svg via graphviz
dot -Tsvg filename.dot -o filename.svg
# Convert dot to eps via graphviz
dot -Tps filename.dot -o filename.eps
Имейте в виду, что на OSX (MAC) вам необходимо установить homebrew , чтобы установить graphviz, чтобы иметь возможность использовать приведенные выше команды точек.
brew install graphviz
Также возможно установить Graphviz (и использовать приведенные выше команды) с помощью функции менеджера пакетов conda, если у вас установлена Anaconda.
conda install python-graphviz
9 ответов
Три конкретных примера:
- Линейная алгебра - это основа современной трехмерной графики. По сути, это то же самое, чему вы научились в школе. Данные хранятся в трехмерном пространстве, которое проецируется на двумерную поверхность, которую вы видите на своем экране.
- Большинство поисковых систем основаны на линейной алгебре. Идея состоит в том, чтобы представить каждый документ как вектор в гиперпространстве и посмотреть, как вектор соотносится друг с другом в этом пространстве. Это используется, среди прочего, в проекте lucene . См. VSM .
- Некоторые современные алгоритмы сжатия, такие как тот, который используется в формате ogg vorbis, основаны на линейной алгебре, или, более конкретно, на методе, называемом векторном квантовании .
По сути, все сводится к тому, что линейная алгебра - очень мощный метод при работе с несколькими переменными, и использование этого метода в качестве теоретической основы при разработке алгоритмов дает огромные преимущества. Во многих случаях этот фундамент не t так очевидно, как вы можете подумать, но это не значит, что его там нет. Вполне возможно, что вы уже реализовали алгоритмы, которые было бы невероятно сложно получить без linalg.
All of the answers here are good examples of linear algebra in algorithms.
As a meta answer, I will add that you might be using linear algebra in your algorithms without knowing it. Compilers that optimize with SSE(2) typically vectorize your code by having many data values manipulated in parallel. This is essentially elemental LA.
Ha, I can't resist putting this here (even though the other answers are good):
The $25 billion dollar eigenvector.
I'm not going to lie... I never even read the whole thing... maybe I will now :-).
Криптограф, вероятно, скажет вам, что понимание теории чисел очень важно при изучении алгоритмов. И он будет прав - в своей конкретной области. Статистика тоже имеет свои применения - списки пропусков, хеш-таблицы и т. Д. Полезность теории графов еще более очевидна.
Нет внутренней связи между линейной алгеброй и алгоритмами; существует внутренняя связь между математикой и алгоритмами.
Линейная алгебра - это область с множеством приложений, и поэтому алгоритмы, использующие ее, также имеют множество приложений. Вы не зря потратили время на его изучение.
Наиболее распространенные методы машинного обучения имеют этап оптимизации, который требует решения набора одновременных уравнений. Если вы не знаете линейной алгебры, вы совершенно заблудитесь.
Это зависит от типа «алгоритмов».
Некоторые примеры:
- Алгоритмы машинного обучения / статистики: линейная регрессия (метод наименьших квадратов, гребень, лассо).
- Сжатие сигналов с потерями и другая обработка (распознавание лиц и т. Д.). См. Eigenfaces
Многие алгоритмы обработки сигналов основаны на матричных операциях, например, преобразование Фурье, преобразование Лапласа, ...
Проблемы оптимизации часто можно уменьшить к решению систем линейных уравнений.
Например, что интересного можно сделать с матрицей связности для графа?
Многие алгебраические свойства матрицы инвариантны относительно перестановок вершин (например, abs (определитель)) , поэтому, если два графика изоморфны, их значения будут равны.
Это источник хорошей эвристики для определения того, действительно ли два графика не изоморфны, поскольку, конечно, равенство не гарантирует существования изоморфизма.
Проверьте теорию алгебраических графов , чтобы узнать о множестве других интересных методов.
Криптограф, вероятно, скажет вам, что понимание теории чисел очень важно при изучении алгоритмов. И он будет прав - в своей конкретной области. У статистики тоже есть свои применения - списки пропусков, хеш-таблицы и т. Д. Полезность теории графов еще более очевидна.
Нет внутренней связи между линейной алгеброй и алгоритмами; существует внутренняя связь между математикой и алгоритмами.
Линейная алгебра - это область с множеством приложений, и поэтому алгоритмы, использующие ее, также имеют множество приложений. Вы не зря потратили время на его изучение.
Полезность теории графов еще более очевидна.Нет никакой внутренней связи между линейной алгеброй и алгоритмами; существует неотъемлемая связь между математикой и алгоритмами.
Линейная алгебра - это область со многими приложениями, и поэтому алгоритмы, использующие ее, также имеют множество приложений. Вы не зря потратили время на его изучение.
Полезность теории графов еще более очевидна.Нет никакой внутренней связи между линейной алгеброй и алгоритмами; существует внутренняя связь между математикой и алгоритмами.
Линейная алгебра - это область с множеством приложений, и поэтому алгоритмы, использующие ее, также имеют множество приложений. Вы не зря потратили время на его изучение.
Как вы уже догадались, линейная алгебра также важна во многих алгоритмах компьютерной алгебры. Например, если вы можете свести задачу к тому, чтобы сказать, что многочлен равен нулю, где коэффициенты многочлена линейны по переменным x1,…, xn , то вы можете решить, для каких значений ] x1,…, xn делают полином равным 0, приравнивая коэффициент каждого члена x ^ n к 0 и решая линейную систему. Это называется методом неопределенных коэффициентов и используется, например, при вычислении разложения на частичные дроби или при интегрировании рациональных функций.
Для теории графов самая крутая вещь в матрице смежности заключается в том, что если вы возьмете n-ю степень матрицы смежности для невзвешенного графа (каждая запись равна 0 или 1), M ^ n , то каждая запись i, j будет числом путей от вершины i до вершины j длины n . И если это не просто круто, то я не знаю, что это такое.