Lösungen T4 und T5 online (nt)

MatthiasBein
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 130
Registriert: 15. Jun 2009 16:42

Lösungen T4 und T5 online (nt)

Beitrag von MatthiasBein »

.

thomas_kalbe
Nerd
Nerd
Beiträge: 570
Registriert: 10. Jun 2006 14:58

Re: Lösungen T4 und T5 online (nt)

Beitrag von thomas_kalbe »

wir haben die Lösungen nochmal leicht verbessert und erneut hochgeladen.

- t

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Re: Lösungen T4 und T5 online (nt)

Beitrag von banshee »

Ich hätte da mal eine Frage zur Lösung der 1b auf dem 4. Übungsblatt. Wieso kann man denn diese Umformung so einfach machen:

\(O(q_u^2 + q_v^2 + q_u^2q_v) < O(q_u^2 + q_v^2 + q_uq_v^2) <=> q_u^2 + q_v^2 + q_u^2q_v < q_u^2 + q_v^2 + q_uq_v^2\)

Denn mal angenommen, ich setze \(q_v = 2q_u\), dann gilt:

\(O(q_u^2 + q_v^2 + q_u^2q_v) = O(q_u^2 + q_v^2) + O(q_u^2q_v)
= O(q_u^2 + q_v^2) + O(2q_u^2q_v)
= O(q_u^2 + q_v^2) + O(4q_u^2q_u)
= O(q_u^2 + q_v^2) + O(q_uq_v^2)
= O(q_u^2 + q_v^2 + q_uq_v^2)\)


womit die Umformung nicht stimmt.

MatthiasBein
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 130
Registriert: 15. Jun 2009 16:42

Re: Lösungen T4 und T5 online (nt)

Beitrag von MatthiasBein »

banshee hat geschrieben: Wieso kann man denn diese Umformung so einfach machen:
\(O(q_u^2 + q_v^2 + q_u^2q_v) < O(q_u^2 + q_v^2 + q_uq_v^2) <=> q_u^2 + q_v^2 + q_u^2q_v < q_u^2 + q_v^2 + q_uq_v^2\)
Da sind uns einfach formale Fehler unterlaufen. Natürlich ist die wechselseitige Beziehung nicht richtig, wie folgendes Beispiel verdeutlicht:
Sei \(f(x) = 4x\) und
\(g(x) = 7x\), dann gilt
\(f(x) < g(x)\) für \(x > 0\).
Allerdings, wie jedem bekannt sein sollte, gilt auch
\(\mathcal{O}(f(x)) = \mathcal{O}(g(x)) = \mathcal{O}(x)\).

Zumal kann der Beweis nicht in der O-Notation erfolgen, da asymptotisch gesehen, beide Varianten kubische Komplexität besitzen.
Wenn \(q_u \rightarrow \infty\) und \(q_v \rightarrow \infty\), dann gilt
\(\mathcal{O}(q_u^2 q_v) = \mathcal{O}(q_u^3) = \mathcal{O}(q_v^3) = \mathcal{O}(q_u q_v^2)\),
wodurch auch dein zweiter Einwand richtig ist.
banshee hat geschrieben: Denn mal angenommen, ich setze \(q_v = 2q_u\), dann gilt:
\(O(q_u^2 + q_v^2 + q_u^2q_v) = O(q_u^2 + q_v^2) + O(q_u^2q_v)
= O(q_u^2 + q_v^2) + O(2q_u^2q_v)
= O(q_u^2 + q_v^2) + O(4q_u^2q_u)
= O(q_u^2 + q_v^2) + O(q_uq_v^2)
= O(q_u^2 + q_v^2 + q_uq_v^2)\)
Allerdings war es auch nicht verlangt das asymptotische Verhalten zu analysieren, sondern es galt zu zeigen, dass eine Variante weniger aufwendig ist, sprich weniger Operationen benötigt. Da man mit der O-Notation den Beweis nicht führen kann, ist der Hinweis über die Komplexität in der Aufgabenstellung wohl irreführend. Wir bitten dies zu entschuldigen und werden es für zukünftige Semester ausbessern.

Um möglichst allgemein zu bleiben, definieren wir hier eine Operation als ein gewichtetes Mittel im \(\mathbb{R}^d\). Nun wissen wir, dass eine Casteljau-Auswertung mit Grad \(q\) genau \(\frac{q(q+1)}{2}\) Operationen benötigt. Damit können wir beide Varianten vergleichen:
\(\begin{align*}
\text{Auswertung zuerst mit festem } u &< \text{Auswertung zuerst mit festem } v ~~\Leftrightarrow \\
(q_v+1)\frac{q_u(q_u+1)}{2} + \frac{q_v(q_v+1)}{2} &< (q_u+1)\frac{q_v(q_v+1)}{2} + \frac{q_u(q_u+1)}{2} ~~\Leftrightarrow \\
(q_v+1)q_u(q_u+1)+q_v(q_v+1) &< (q_u+1)q_v(q_v+1)+q_u(q_u+1) ~~\Leftrightarrow \\
q_v q_u(q_u+1) &< q_u q_v(q_v+1) ~~\Leftrightarrow \\
q_u+1 &< q_v+1 ~~\Leftrightarrow \\
q_u &< q_v ~~~~\text{q.e.d.}
\end {align*}\)

Antworten

Zurück zu „Archiv“