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

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

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

Beitrag von LukasPhysiker » 10. Jun 2017 19:49

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.

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

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

Beitrag von invariant » 12. Jun 2017 13:34

Hallo,

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

Gruß

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

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

Beitrag von LukasPhysiker » 18. Jun 2017 21:52

Gibt es schon Ergebnisse? Falls die Frage anderswo beantwortet wurde, habe ich das nicht mitbekommen.

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

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

Beitrag von LukasPhysiker » 29. Jun 2017 19:18

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.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

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

Beitrag von Prof. Karsten Weihe » 29. Jun 2017 21:08

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

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

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

Beitrag von LukasPhysiker » 29. Jun 2017 21:16

Danke für Ihre Antwort! Damit sind die Mehrdeutigkeiten jetzt geklärt.

Antworten

Zurück zu „Archiv“