Teile und Herrsche < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:19 Do 18.10.2018 | | Autor: | Hela123 |
| Aufgabe | Ein fundamentales Problem ist die Multiplikation zweier Matrizen [mm]A, B \in \IR^{n \times n}[/mm] Der Einfachheit halber nehmen wir an, dass n eine Zweierpotenz ist. Der Standardalgorithmus berechnet dazu jeden Koeffizienten [mm]c_{ij}[/mm] von C einzeln nach der Formel:
[mm]c_{ij} = \summe_{k=1}^{n} a_{ik} b_{kj}[/mm]
1) Wie viele Multiplikationen und Additionen werden zur Berechnung von C mit dem Standardalgorithmus durchgeführt?
2) Statt des Standardalgorithmus möchten wir nun das Paradigma "Divide-and-Conquer" ("Teile und Herrsche") anwenden. Dazu unterteilen wir die Matrizen in jeweils vier Blockmatrizen der Größe [mm]\frac{n}{2} \times \frac{n}{2}[/mm]:
[mm]\begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{pmatrix}
\begin{pmatrix}
B_{11} & B_{12} \\
B_{21} & B_{22}
\end{pmatrix}
=\begin{pmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22}
\end{pmatrix}[/mm]
Jede der vier Blockmatrizen [mm]C_{ij}[/mm] ergibt sich wegen
[mm]C_{ij} = A_{i1} B_{1j} + A_{i2} B_{21}[/mm]
durch Multiplikation von zwei Matrizen der Größe [mm]\frac{n}{2} \times \frac{n}{2}[/mm]. Stellen Sie eine Rekursionsgleichung auf, welche die Laufzeit des Divide-and-Conquer Algorithmus beschreibt. Berücksichtigen Sie dazu Multiplikationen und Additionen in der Rekursionsgleichung und finden Sie eine geschlossene Form.
3) Wie verändert sich die Gesamtlaufzeit des Divide-and-Conquer Algorithmus, wenn sich im Conquer Schritt die Anzahl der Additionen konstant erhöht und dafür eine Multiplikation eingespart werden kann? |
Hallo Forum,
Meine Überlegungen für Teil 1):
Wir haben [mm]n*n[/mm] von [mm]c_{ij}[/mm] zu berechnen mit jeweils n Additionen. Deswegen werden für die Berechnung [mm]n^3[/mm] Additionen und Multiplikationen durchgeführt.
Ist es korrekt?
Meine Überlegungen für Teil 2):
Ich weiß nicht wirklich, wie ich aus der Aufgabenstellung eine Rekursionsgleichung ableiten kann. Für diesen Fall käm eals die kleinste Matrix die Matrix Größe 2x2 in Frage (weil wir diese in 4 Teile zerlegen). Das wäre, glaube ich, unserer Rekursionsanker. Beim unteren Term bin ich mir sehr unsicher.
[mm]T(n)=\left\{\begin{matrix}
12, & \mbox{falls }n=2\mbox \\
4T(n/4)+c, & \mbox{falls }n \ge 2
\end{matrix}\right.[/mm]
Ich möchte an der Stelle nicht weiter machen, bevor ich weiß, ob meine bisherige Überlegungen Sinn machen.
Kann mir vielleicht jemand helfen und ein Tipp geben?
Danke im Voraus!
Hela123
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Fr 26.10.2018 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
