كيف يتم استخدام الجبر الخطي في الخوارزميات؟

Question

ذكر العديد من أقراني أن "الجبر الخطي" مهم للغاية عند دراسة الخوارزميات. لقد درست مجموعة متنوعة من الخوارزميات وأخذت بعض دورات الجبر الخطية ولا أرى الاتصال. إذن كيف تستخدم الجبر الخطي في الخوارزميات؟

على سبيل المثال، ما الأشياء المثيرة للاهتمام يمكن للآخر مع مصفوفة الاتصال للحصول على الرسم البياني؟

Answer 1

ثلاثة أمثلة ملموسة:

• الجبر الخطي هو أساس الرسومات ثلاثية الأبعاد الحديثة. هذا هو في الأساس نفس الشيء الذي تعلمته في المدرسة. يتم الاحتفاظ بالبيانات في مساحة ثلاثية الأبعاد المتوقعة في سطح ثنائي الأبعاد، وهو ما تراه على الشاشة.
• تعتمد معظم محركات البحث على الجبر الخطي. تتمثل الفكرة في تمثيل كل وثيقة بمثابة متجه في مساحة فرط وشاهد كيف يرتبط المتجه ببعضها البعض في هذه المساحة. يستخدم هذا من قبل مشروع لوسين, ، من بين آخرين. يرى vsm..
• يعتمد بعض خوارزميات الضغط الحديثة مثل تلك التي يستخدمها تنسيق OGG Vorbis على Algebra الخطي، أو أكثر تحديدا طريقة تسمى نوع متجه.

في الأساس يأتي إلى حقيقة أن الجبر الخطي هي طريقة قوية للغاية عند التعامل مع متغيرات متعددة، وهناك فوائد هائلة لاستخدام هذا كأساس نظرية عند تصميم الخوارزميات. في كثير من الحالات، هذه الأساس ليست مظاهرة كما قد تفكر، لكن هذا لا يعني أنه ليس هناك. من الممكن أن تقوم بالفعل بتنفيذ الخوارزميات التي كانت من شأنها أن تكون من الصعب للغاية الاستغناء عن Linalg.

Answer 2

من المحتمل أن يخبرك بالتشفير أن فهم نظرية الأرقام مهم للغاية عند دراسة الخوارزميات. وسوف يكون صحيحا - لحقله الخاص. تحتوي الإحصاءات على استخداماتها أيضا - Skip Lists، وجداول التجزئة، إلخ. فائدة نظرية الرسم البياني أكثر وضوحا.

لا يوجد صلة متأصلة بين الجبر الخطي والخوارزميات؛ هناك صلة متأصلة بين الرياضيات والخوارزميات.

الجبر الخطي هو حقل مع العديد من التطبيقات، والخوارزميات التي تعتمد ذلك لها الكثير من التطبيقات أيضا. لقد لم تضيع وقتك في دراسة ذلك.

Answer 3

ها، لا أستطيع مقاومة وضع هذا هنا (على الرغم من أن الإجابات الأخرى جيدة):

يبلغ 25 مليار دولار eigenvector.

لن أكذب ... لم أقرأ أبدا كل شيء ... ربما سأفعل الآن :-).

Answer 4

لا أعرف إذا كنت عبارة أنها "الجبر الخطي" مهم جدا عند دراسة الخوارزميات ". لقد وضعت ذلك تقريبا في الاتجاه الآخر. كثير، كثير، العديد من مشاكل العالم الحقيقي ينتهي بهم المطاف أن يحل منك حل مجموعة من المعادلات الخطية. إذا انتهى بك الأمر إلى معالجة واحدة من هذه المشكلات، فستحتاج إلى معرفة بعض الخوارزميات العديدة للتعامل مع المعادلات الخطية. تم تطوير العديد من تلك الخوارزميات عندما كانت أجهزة الكمبيوتر مسمى وظيفة، وليس آلة. النظر في القضاء غاوسي وخوارزميات تحلل مصفوفة مختلفة على سبيل المثال. هناك كثيرا من نظرية متطورة للغاية حول كيفية حل هذه المشاكل للمصفوفات الكبيرة جدا على سبيل المثال.

معظم الأساليب الشائعة في تعلم الجهاز في نهاية المطاف لها خطوة تحسين تتطلب حل مجموعة من المعادلات المتزامنة. إذا كنت لا تعرف الجبر الخطي، فستفقد تماما.

Answer 5

تعتمد العديد من خوارزميات معالجة الإشارات على عمليات مصفوفة، مثل تحويل فورييه، تحويل لابلاس، ...

غالبا ما يتم تخفيض مشاكل التحسين لحل أنظمة المعادلات الخطية.

Answer 6

الجبر الخطي مهم أيضا في العديد من الخوارزميات في الجبر الكمبيوتر، كما قد تخمنت. على سبيل المثال، إذا استطعت تقليل مشكلة قول إن مادة متعدد الحدود صفرية، حيث تكون معاملات متعدد الحدود خطية في المتغيرات x1, …, xn, ، ثم يمكنك حل لقيم x1, …, xn اجعل متعدد الحدود يساوي 0 من خلال مساواة معامل كل منهما x^n الفصل إلى 0 وحل النظام الخطي. وهذا ما يسمى طريقة المعاملات غير المحددة، ويستخدم على سبيل المثال في حوسبة تحلل الكسر الجزئي أو في دمج الوظائف العقلانية.

بالنسبة لنظرية الرسم البياني، وأروع شيء في مصفوفة مجاورة هو أنه إذا كنت تأخذ قوة NTH لمصفوفة مجاورة للحصول على رسم بياني غير مرجح (كل إدخال إما 0 أو 1)، M^n, ، ثم كل إدخال i,j سيكون عدد المسارات من Vertex i إلى قمة الرأس j الطول n. وبعد وإذا لم يكن هذا رائعا، فأنا لا أعرف ما هو.

Answer 7

جميع الإجابات هنا أمثلة جيدة على الجبر الخطي في الخوارزميات.

كإجابة meta، سأضيف أنك قد تستخدم الجبر الخطي في خوارزمياتك دون معرفة ذلك. التحويل البرمجيات التي تتحسن مع SSE (2) عادة ما يتجه الكود الخاص بك من خلال وجود العديد من قيم البيانات المعالجة بالتوازي. هذا هو أساسا lederal la.

Answer 8

ذلك يعتمد نوع "الخوارزميات".

بعض الأمثلة:

• خوارزميات التعلم / الإحصاءات: التراجع الخطي (المربعات الصغرى، Ridge، Lasso).
• وضع ضغط الإشارات وغيرها من المعالجة (الاعتراف بالوجه، إلخ). يرى eigenfaces.

Answer 9

على سبيل المثال، ما الأشياء المثيرة للاهتمام يمكن للآخر مع مصفوفة الاتصال للحصول على الرسم البياني؟

هناك الكثير من الخصائص الجبرية للمصفوفة ثابتة تحت التباديل من القمم (على سبيل المثال ABS (محدد))، لذلك إذا كانت الرسوم البيانية هي Isomorphic، ستكون قيمها متساوية.

هذا مصدر لاستدلال جيدة لتحديد ما إذا كانت الرسوم البيانية اثنين ليس ISOMORPHIC، نظرا لأن المساواة بالطبع لا يضمن وجود الأيزيومورفية.

يفحص نظرية الرسم البياني الجبري للحصول على الكثير من التقنيات الأخرى المثيرة للاهتمام.