Hindi subtitles

← 05-07 Matrix Multiplication

Get Embed Code
3 Languages

Showing Revision 1 created 03/23/2013 by Nirmal Khatua.

  1. यदि आप मैट्रिक्स गुणन के साथ परिचित हो बस एक त्वरित अलग रूप में,
  2. इस छोटे एल्गोरिथ्म के बीच एक बहुत ही अच्छा संबंध है
  3. कि हम अभी पर काम कर रहे हैं और मैट्रिक्स गुणन।
  4. कि की सराहना करते हैं करने के लिए, आप समझने की जरूरत है पहली बात यह है कि
  5. यदि हम एक मैट्रिक्स के रूप में नोड्स का एक सेट पर एक ग्राफ का प्रतिनिधित्व कर सकते हैं
  6. और यह एक मैट्रिक्स कि सभी 0s और 1s के होते हैं और ज्यादातर शून्य कहते हैं कि अगर यह एक विरल ग्राफ, है है।
  7. अगर नोड के बीच एक कड़ी है, लेकिन मैं और नोड J,
  8. तब मैट्रिक्स में इसी स्थिति के एक नंबर है यह में, संख्या 1।
  9. कि 1 वहाँ का मतलब है कि मैं से एक लिंक जे करने के लिए
  10. रेखांकन कि हम लिंक के बारे में बात कर रहा है द्विदिशात्मक कर रहे हैं।
  11. अगर इस मैं-J की स्थिति में एक 1 है, तो वहाँ है तो भी एक 1 में जम्मू-मैं स्थिति,
  12. इस चित्र में जो लगता था जैसे यह सच में पास, जिसका मतलब है कि इस मैट्रिक्स सममित,
  13. और मैं यदि आप इसे से परिचित हो मैट्रिक्स शब्दावली में लेकिन फिर से प्राप्त करने के लिए नहीं जा रहा हूँ,
  14. आप को पहचान लेंगे क्या एक symmetric मैट्रिक्स है।
  15. यदि आप अन्य तरह बातें फ्लिप अपने आप एक मैट्रिक्स बराबरी रूपांतरित करें।
  16. तो मूल रूप से यह स्वाभाविक है, यह मतलब है बस नोड्स के लिए interchanging
  17. द्वि-दिशा कनेक्शन कर रहे हैं के बाद से, हम एक ही मैट्रिक्स फिर से करना होगा।
  18. तो हम कहते हैं यह मैट्रिक्स (M) और हम के बारे में क्या लगता है कि यह खुद (M) बार गुणा करने का मतलब है।
  19. मैट्रिक्स गुणन में, जिस तरह हम उत्पाद की मैं-J प्रविष्टि में भरें,
  20. हम मुझे ले लो पहले मैट्रिक्स और दूसरा मैट्रिक्स के J स्तंभ की पंक्ति
  21. और जब भी मैं मैट्रिक्स गुणन के बारे में लगता है कि मैं हमेशा दो हाथ की जरूरत
  22. और आप एक ही समय में यह एक नीचे और यह एक भर में।
  23. और हम इस मामले के बाद से यह सभी शून्य है और लोगों को और यह है एक वर्ग मैट्रिक्स क्या,
  24. लेकिन क्या हम के माध्यम से जा रहे हैं और यह पता लगाने।
  25. जहां कहीं भी है एक 0 और 1, और एक 0 और दूसरे, यह 0 होने जा रहा है।
  26. सिर्फ अगर वहाँ है एक 1 दोनों में, यह एक उत्पाद है कि नहीं किया जा रहा है 0।
  27. तो इस पंक्ति इस स्तंभ टाइम्स के इस गुणा की संख्या 1 के की संख्या के ठीक है
  28. दो वैक्टर वास्तव में एक ही स्थिति है कि।
  29. उन्हें एक 1 की एक ही स्थिति में होना करने के लिए इसका क्या मतलब है? चलो की जाँच करें।
  30. हम सोच भी है कि स्थिति में K यहाँ और एक ही समय में कश्मीर की स्थिति में यहाँ एक 1।
  31. यहाँ इस स्थिति का मतलब है कि हमारे ग्राफ़ कश्मीर मैं से एक कड़ी थी
  32. वहाँ है, कि क्या इसका मतलब यह है कि वहाँ एक 1 वहाँ है है।
  33. और इसी प्रकार, यदि इस स्थिति में एक 1 है, तो यह कि बहुत ही ग्राफ कि हम के बारे में बात कर रहे हैं मतलब है
  34. इस ग्राफ है कि (M) का प्रतिनिधित्व भी J K से लिंक है
  35. और हम क्या कर रहे हैं के गुण है कि सभी एस ऊपर भरोसा है
  36. कि वे आप के रूप में ले जाएगा से मैं उन लोगों में से एक के लिए और फिर उन में से एक से जम्मू के लिए प्राप्त कर सकते हैं।
  37. यह उन सभी को जोड़ने के लिए जा रहा है। कि वास्तव में क्या मैट्रिक्स गुणा करता है।
  38. यहाँ यह मान ठीक से मैं 2-चरण पथ जे करने के लिए की संख्या से भरा जा रहा है
  39. जो वास्तव में है क्या हम में है कि हम मूल रूप से गिनती कर रहे हैं अन्य उदाहरण टोपी चाहिए
  40. हास्य किताबें है कि कुछ के बीच असामान्य हैं चरित्र मैं और कुछ चरित्र जे
  41. चमत्कार हास्य पुस्तक अक्षर के त्रिपक्षीय ग्राफ के मामले में,
  42. किसी भी 2-चरण का रास्ता है कि एक चरित्र पर शुरू होता है एक हास्य पुस्तक और फिर एक चरित्र के माध्यम से चला जाता है।
  43. तो यह बिल्कुल हास्य पुस्तकें कि मैं और जम्मू में दोनों कर रहे हैं की संख्या की गिनती है।
  44. वहाँ हम जाओ, वर्ग मैट्रिक्स जो का प्रतिनिधित्व करता है के
  45. ग्राफ के कनेक्शन वास्तव में हमें एक ही जवाब देता है।
  46. इस एल्गोरिथ्म, का समय चल रहा बेशक, n³ है,
  47. क्योंकि हम हम भरने के लिए जा रहे हैं इस मैट्रिक्स की प्रविष्टियों में से प्रत्येक के लिए के माध्यम से पाशन हैं
  48. और उन्हें करने के लिए n² है, हम इस पंक्ति स्तंभ गुणा जो भी समय में ले जाता है द्वारा कर रहे हैं।
  49. तो यह में cubed है। कलन विधि कि हम बस के बारे में बात कर रहा हूँ।
  50. अधिक संख्या किनारों की तरह कुछ नोड्स की संख्या के बार।
  51. तथ्य यह है कि हम पर पाश से किनारों यहाँ की संख्या आती है
  52. हम स्पष्ट रूप से संग्रहीत है चरित्र पुस्तक संयोजनों में से प्रत्येक।
  53. और फिर उन में से प्रत्येक के लिए, हम जांच की कौन सा अक्षर वहाँ यह करने के लिए जुड़े हुए हैं।
  54. यह N * M के रूप में के रूप में बुरा हो सकता है। यदि घने मैट्रिक्स (M) है, तो यह है (N) ²,
  55. तो यह एल्गोरिथ्म में किया जा रहा समाप्त हो गया लेकिन अगर यह एक विरल मैट्रिक्स है फिर से, cubed,
  56. तो किनारों की संख्या उदाहरण के लिए रेखीय planar ग्राफ में, की तरह है,
  57. तो यह है (जो वास्तव में एक बहुत बेहतर है N) ²।