Seite 1 von 1

Theorietestat #3: Mathematische Definition der Landau-Symbole für mehrere Variablen

Verfasst: 10. Jun 2017 19:49
von LukasPhysiker
Ich hatte in diesem Thread ein paar Verwirrungen bezüglich der Vereinfachungen von asymtotischen Komplexitäten bei mehreren Variablen. Mir ist klar geworden, dass die Zweideutigkeit nur dadurch entstehen konnte, dass die Landau-Symbole nur für jeweils eine Variable definiert wurde, obwohl wir oft mit mehreren Variablen zu tun haben. Wikipedia beschreibt, dass man diese reelle (bei uns natürliche) Variable samt ihrem Grenzwert zu einem topologischen Raum verallgemeinern könnte (in unserem Fall also \mathbb{N}^k). In unserem Fall, wo wir unsere Variablen immer gegen unendlich streben lassen, würde ich das so interpretieren, dass die Definition des Groß-O bei zwei Variablen n und m folgendermaßen aufgeschrieben werden kann:

Code: Alles auswählen

\begin{equation}
f \in \mathcal{O}(g) \Leftrightarrow (\exists c \in \mathbb{R}^+) (\exists n_0 \in \mathbb{N}) (\exists m_0 \in \mathbb{N}) (\forall n > n_0) (\forall m > m_0) \quad f(n,m) \leq c \cdot g(n,m)
\end{equation}
Eine andere Art, das zu verallgemeinern, was aber eine stärkere Behauptung wäre, ist die folgende:

Code: Alles auswählen

\begin{align}
f \in \mathcal{O}(g) \Leftrightarrow& (\exists c \in \mathbb{R}^+) (\exists n_0 \in \mathbb{N}) (\forall n > n_0) \quad f(n,m) \leq c \cdot g(n,m)\\
\wedge& (\exists c \in \mathbb{R}^+) (\exists m_0 \in \mathbb{N}) (\forall m > m_0) \quad f(n,m) \leq c \cdot g(n,m)
\end{align}
Diese zweite Definition würde bedeuten, dass im verlinkten Thread das + n nicht wegfallen würde. Da das laut Prof aber wegfällt, würde ich sagen, dass die erste Definition diejenige ist, mit der wir in der Vorlesung arbeiten, korrekt? Ich möchte um eine Bestätigung von offizieller Seite bitten.

Tut mir leid, dass ich den LaTeX-Code einfach so hingeknallt habe, aber die tex-Tags funktionieren in diesem Forum anscheinend nicht. Wer will, kann das ja in LaTeX kompilieren, dann kann man die Formeln ordentlich sehen.

Re: Theorietestat #3: Mathematische Definition der Landau-Symbole für mehrere Variablen

Verfasst: 12. Jun 2017 13:34
von invariant
Hallo,

Möchte ich akut keine Aussage darüber treffen, werde das aber Rücksprechen und dann entsprechend kommunizieren.

Gruß

Re: Theorietestat #3: Mathematische Definition der Landau-Symbole für mehrere Variablen

Verfasst: 18. Jun 2017 21:52
von LukasPhysiker
Gibt es schon Ergebnisse? Falls die Frage anderswo beantwortet wurde, habe ich das nicht mitbekommen.

Re: Theorietestat #3: Mathematische Definition der Landau-Symbole für mehrere Variablen

Verfasst: 29. Jun 2017 19:18
von LukasPhysiker
Es wäre schön, hier irgendwann auch mal eine Antwort zu bekommen. Es geht mir natürlich auch darum, dass ich mich in der Klausureinsicht auf diesen Thread berufen kann, falls in der Klausur in so einem Fall zu meinen Ungunsten entschieden wird.

Es mag sein, dass sich sonst nicht viele für diese genaue mathematische Definition interessieren, aber mit einer solchen Definition kann man dann immer eindeutig sagen, was man vereinfachen kann und was nicht und kann sich dann in der Klausureinsicht auf diese Definition berufen.

Re: Theorietestat #3: Mathematische Definition der Landau-Symbole für mehrere Variablen

Verfasst: 29. Jun 2017 21:08
von Prof. Karsten Weihe
LukasPhysiker hat geschrieben:
10. Jun 2017 19:49
Diese zweite Definition würde bedeuten, dass im verlinkten Thread das + n nicht wegfallen würde. Da das laut Prof aber wegfällt, würde ich sagen, dass die erste Definition diejenige ist, mit der wir in der Vorlesung arbeiten, korrekt? Ich möchte um eine Bestätigung von offizieller Seite bitten.
Bestätige ich hiermit.
LukasPhysiker hat geschrieben:
10. Jun 2017 19:49
Tut mir leid, dass ich den LaTeX-Code einfach so hingeknallt habe, aber die tex-Tags funktionieren in diesem Forum anscheinend nicht.
Quelltexte lesen ist eine informatische Kernkompetenz, daher kein Grund für's Leid tun. :wink:

KW

Re: Theorietestat #3: Mathematische Definition der Landau-Symbole für mehrere Variablen

Verfasst: 29. Jun 2017 21:16
von LukasPhysiker
Danke für Ihre Antwort! Damit sind die Mehrdeutigkeiten jetzt geklärt.