| rdfs:comment
| - En informatique, un algorithme de multiplication de matrices enchaînées est un algorithme d'optimisation qui sert à trouver un ordre dans lequel calculer un produit de plusieurs matrices de façon à minimiser le nombre de multiplications scalaires à effectuer. (fr)
- Problem nawiasowania ciągu macierzy – problemem znalezienia takiego nawiasowania iloczynu macierzy by zminimalizować łączny koszt wszystkich mnożeń. Nawiasowanie takie nazywa się optymalnym. Mówimy, że iloczyn macierzy ma ustalone nawiasowanie, jeżeli tworzy go pojedyncza macierz lub iloczyn dwóch iloczynów macierzy o ustalonym nawiasowaniu. (pl)
- 矩阵链乘积（英語：Matrix chain multiplication，或Matrix Chain Ordering Problem，MCOP）是可用動態規劃解决的最佳化问题。給定一序列矩陣，期望求出相乘這些矩陣的最有效方法。此問題並不是真的去執行其乘法，而只是決定執行乘法的順序而已。 因為矩陣乘法具有結合律，所有其運算順序有很多種選擇。換句話說，不論如何括號其乘積，最後結果都會是一樣的。例如，若有四個矩陣、、和，將可以有： 但括號其乘積的順序是會影響到需計算乘積所需簡單算術運算的數目，即其效率。例如，設為一矩陣，為矩陣與為矩陣，則：
* 有個運算
* 有個運算 明顯地，第一種方式要有效多了。既然已確認過此問題了，那要如何決定n個矩陣相乘的最佳順序呢？可以比較每一順序的運算量（使用蠻力），但這將需要時間O(2n)，是一種非常慢且對大n不實在的方法。那解決方法，如我們將看到的，是將問題分成一套相關的子問題。以解答子問題一次而再使用其解答數次，即可以徹底地得出其所需時間。此一方法稱為動態規劃。 (zh)
- Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов совпадает с количеством строк матрицы). (ru)
- ضرب سلسلة مصفوفات هو ليس فقط عملية ضرب ومحصلة ولكن يلزم ان يفهم القارئ اولا ماهو الهدف من المصفوفة حتي يستطيع ان يبدع في هذا المجال. للشرح المبسط نأخذ المثال التالي: فرضا ان لديك صوت لمدة ثانية والصوت يتغير وقد تم أخذ عينية من الصوت كل عشر من الثانية. عليه يكون لديك عشرة ارقام تمثل تغير الصوت في هذة الثانية. يمكن كتابة الأرقام بجاور بعضهم في شكل مصفوفة احادية. الآن نفترض اننا نريد إجراء عملية حسابية لتغيير ارتفاع الصوت، ابسط شيء سوف تقول نضرب المصفوفة في رقم ثابت. الشكل الأولي للمصفوفة المثالية الصوت : [5 3 1 3 5 7 6 5 2 3]الزيادة: [5 5 5 5 8 8 8 3 3 3] الزيادة : [3338885555 ] (ar)
- Matrix-Kettenmultiplikation bezeichnet die Multiplikation von mehreren Matrizen. Da die Matrizenmultiplikation assoziativ ist, kann man dabei beliebig klammern. Dadurch wächst die Anzahl der möglichen Berechnungswege überpolynomial mit der Länge der Matrizenkette an. Mit der Methode der dynamischen Programmierung kann die Klammerung der Matrix-Kette optimiert werden, so dass die Gesamtanzahl arithmetischer Operationen minimiert wird. Der Algorithmus hat eine Laufzeit von . Die Anzahl der möglichen Klammerungen für Matrizen lässt sich mit der Catalan-Zahl Cn-1 bestimmen. (de)
- Matrix chain multiplication (or the matrix chain ordering problem) is an optimization problem concerning the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved. The problem may be solved using dynamic programming. ((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD)). If A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix, then (en)
- Multiplicação de cadeia de matrizes (ou problema da ordenação de cadeia de matrizes) é um problema de otimização que pode ser resolvido usando programação dinâmica. Dada uma sequência de matrizes, o objetivo é encontrar a forma mais eficiente de multiplicar essas matrizes. O problema não é na realidade para realizar a multiplicação, mas apenas para decidir a sequência de multiplicações das matrizes envolvidas. ((AB)C)D = (A(A(BC))D) = (AB)(CD) = A(A(BC)D) = A(B(CD)). (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operaçõesA(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operações. (pt)
|
| has abstract
| - ضرب سلسلة مصفوفات هو ليس فقط عملية ضرب ومحصلة ولكن يلزم ان يفهم القارئ اولا ماهو الهدف من المصفوفة حتي يستطيع ان يبدع في هذا المجال. للشرح المبسط نأخذ المثال التالي: فرضا ان لديك صوت لمدة ثانية والصوت يتغير وقد تم أخذ عينية من الصوت كل عشر من الثانية. عليه يكون لديك عشرة ارقام تمثل تغير الصوت في هذة الثانية. يمكن كتابة الأرقام بجاور بعضهم في شكل مصفوفة احادية. الآن نفترض اننا نريد إجراء عملية حسابية لتغيير ارتفاع الصوت، ابسط شيء سوف تقول نضرب المصفوفة في رقم ثابت. الشكل الأولي للمصفوفة المثالية مثلا :الصوت كل عشر من الثانية ممثل برقم [5 3 1 3 5 7 6 5 2 3] اتجاه الكتابة من اليسار الي اليمين. لتعلية الصوت كل الوقت بنفس المقدار يلزم ضرب مقدار الصوت كل عشر من الثانية في رقم ثابت وليكن 4 اضعافالنتيجة: [5 3 1 3 5 7 6 5 2 3] * 4 = [20 12 4 12 20 28 24 20 8 12] مثال اخر للتوضيح:افرض اننا نحتاج ان نزيد الصوت ارتفاعا ولكن ليس كل الوقت بنفس المقدار كما في المثال السابق ولكن أول ثلاثة اعشار من الثانية بمقدار 3 اضعاف ثم ثاني ثلاثة اعشار بقدار 8 ثم اخر أربعة اعشار بمقدار 5 اضغافابسط وسلية هي ضرب المصفوفات الصوت : [5 3 1 3 5 7 6 5 2 3]الزيادة: [5 5 5 5 8 8 8 3 3 3] رياضيا لا يمكن كتابة شكل الزيادة كمصفوفة عرضية لذلك تكتب كمصفوفه طولية الزيادة : [3338885555 ] المحصلة تكون ضرب الصف في الصوت في عمود الزيادة بمعني كل عنصر يضرب في العنصر المقابل الحل = [25 15 5 15 40 42 48 15 6 9] ضرب سلسلة مصفوفات هي مسألة استمثالية، يمكن حلها باستعمال . بمعلومية تعاقب معين من المصفوفات، يتعين علينا البحث عن أفضل السبل . المسألة ليست في الحقيقة إجراء عملية الضرب، بل هي مجرد اتخاذ الترتيب المناسب لإجراء عملية الضرب. لدينا العديد من الخيارات بفضل خاصية التجميع للضرب. بعبارة، بغض النظر عن كيفية إدراج الأقواس ستكون النتيجة واحدة. مثلاً، لو أن لدينا أربع مصفوفات A, B, C, and D، فسنجد أن: (ABC)D = (AB)(CD) = A(BCD) = A(BC)D =.... مع ذلك سنلاحظ أن عملية ترتيب هذه الأقواس يؤثر على عدد العمليات البسيطة المراد استعمالها في حساب عملية الضرب، أو «الكفاءة».لنفرض مثلاً أن لدينا A هي مصفوفة، 10 × 30، B هي مصفوفة 30 × 5 مصفوفة, وC هي مصفوفة a 5 × 60. حينئذ، (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 عمليةA(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 عملية. يبدو جلياً أن الطريقة الأولى أكثر كفاءة ونكون بها قد عينّا الطريقة الأمثل. (ar)
- Matrix-Kettenmultiplikation bezeichnet die Multiplikation von mehreren Matrizen. Da die Matrizenmultiplikation assoziativ ist, kann man dabei beliebig klammern. Dadurch wächst die Anzahl der möglichen Berechnungswege überpolynomial mit der Länge der Matrizenkette an. Mit der Methode der dynamischen Programmierung kann die Klammerung der Matrix-Kette optimiert werden, so dass die Gesamtanzahl arithmetischer Operationen minimiert wird. Der Algorithmus hat eine Laufzeit von . Die Anzahl der möglichen Klammerungen für Matrizen lässt sich mit der Catalan-Zahl Cn-1 bestimmen. Beispiel: Sei eine 10×30 Matrix, eine 30×5 Matrix und eine 5×60 Matrix. Dann gibt es zwei verschiedene Arten, das Matrizenprodukt zu klammern: Die Anzahl der grundlegenden Operationen berechnet sich wie folgt: (de)
- En informatique, un algorithme de multiplication de matrices enchaînées est un algorithme d'optimisation qui sert à trouver un ordre dans lequel calculer un produit de plusieurs matrices de façon à minimiser le nombre de multiplications scalaires à effectuer. (fr)
- Matrix chain multiplication (or the matrix chain ordering problem) is an optimization problem concerning the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved. The problem may be solved using dynamic programming. There are many options because matrix multiplication is associative. In other words, no matter how the product is parenthesized, the result obtained will remain the same. For example, for four matrices A, B, C, and D, there are five possible options: ((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD)). Although it does not affect the product, the order in which the terms are parenthesized affects the number of simple arithmetic operations needed to compute the product, that is, the computational complexity. The straightforward multiplication of a matrix that is X × Y by a matrix that is Y × Z requires XYZ ordinary multiplications and X(Y − 1)Z ordinary additions. In this context, it is typical to use the number of ordinary multiplications as a measure of the runtime complexity. If A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix, then computing (AB)C needs (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations, whilecomputing A(BC) needs (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations. Clearly the first method is more efficient. With this information, the problem statement can be refined as "how to determine the optimal parenthesization of a product of n matrices?" Checking each possible parenthesization (brute force) would require a run-time that is exponential in the number of matrices, which is very slow and impractical for large n. A quicker solution to this problem can be achieved by breaking up the problem into a set of related subproblems. (en)
- Problem nawiasowania ciągu macierzy – problemem znalezienia takiego nawiasowania iloczynu macierzy by zminimalizować łączny koszt wszystkich mnożeń. Nawiasowanie takie nazywa się optymalnym. Mówimy, że iloczyn macierzy ma ustalone nawiasowanie, jeżeli tworzy go pojedyncza macierz lub iloczyn dwóch iloczynów macierzy o ustalonym nawiasowaniu. (pl)
- Multiplicação de cadeia de matrizes (ou problema da ordenação de cadeia de matrizes) é um problema de otimização que pode ser resolvido usando programação dinâmica. Dada uma sequência de matrizes, o objetivo é encontrar a forma mais eficiente de multiplicar essas matrizes. O problema não é na realidade para realizar a multiplicação, mas apenas para decidir a sequência de multiplicações das matrizes envolvidas. Temos muitas opções, pois a multiplicação de matrizes é associativa. Em outras palavras, não importa como por entre parênteses o produto, o resultado obtido será o mesmo. Por exemplo, se tivéssemos quatro matrizes A, B, C, e D, teríamos: ((AB)C)D = (A(A(BC))D) = (AB)(CD) = A(A(BC)D) = A(B(CD)). No entanto, a ordem em que se põe entre parênteses o produto afeta o número de operações aritméticas simples necessárias para calcular o produto, ou a eficiência. Por exemplo, suponha que A é uma matriz 10 × 30, B é uma matriz 30 × 5, e C é uma matriz 5 × 60. Então, (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operaçõesA(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operações. Claramente, o primeiro método é mais eficiente. Com esta informação, o enunciado do problema pode ser refinado, como podemos determinar a melhor parentização de um produto de n matrizes? Poderíamos tentar todas as parentizações possíveis (força bruta), exigindo um tempo de execução que é exponencial no número de matrizes, o que é muito lento e impraticável para grandes valores de n. Uma solução mais rápida para este problema pode ser obtida dividindo o problema em um conjunto de subproblemas relacionados . Através da resolução de subproblemas uma vez e da reutilização dessas soluções, podemos reduzir drasticamente o tempo de execução necessário. Este conceito é conhecido como programação dinâmica. (pt)
- 矩阵链乘积（英語：Matrix chain multiplication，或Matrix Chain Ordering Problem，MCOP）是可用動態規劃解决的最佳化问题。給定一序列矩陣，期望求出相乘這些矩陣的最有效方法。此問題並不是真的去執行其乘法，而只是決定執行乘法的順序而已。 因為矩陣乘法具有結合律，所有其運算順序有很多種選擇。換句話說，不論如何括號其乘積，最後結果都會是一樣的。例如，若有四個矩陣、、和，將可以有： 但括號其乘積的順序是會影響到需計算乘積所需簡單算術運算的數目，即其效率。例如，設為一矩陣，為矩陣與為矩陣，則：
* 有個運算
* 有個運算 明顯地，第一種方式要有效多了。既然已確認過此問題了，那要如何決定n個矩陣相乘的最佳順序呢？可以比較每一順序的運算量（使用蠻力），但這將需要時間O(2n)，是一種非常慢且對大n不實在的方法。那解決方法，如我們將看到的，是將問題分成一套相關的子問題。以解答子問題一次而再使用其解答數次，即可以徹底地得出其所需時間。此一方法稱為動態規劃。 (zh)
- Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов совпадает с количеством строк матрицы). (ru)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
