Theorietestat #3: Schreibweise mit Gleichheitszeichen bei mehreren Landau-Symbolen

[LukasPhysiker]

Im Theorietestat 3 wird auf S.4 extra noch betont, dass Schreibweisen wie f(n) = O(g(n)) genau genommen falsch sind und man eigentlich

Code: Alles auswählen

f(n) \in \mathcal{O}(g(n))

schreiben sollte. Ich kann mich mit der Schreibweise f(n) = O(g(n)) noch anfreunden, da man weiß was gemeint ist und in der Physik schreibt man auch gerne z.B. einen Summanden + O(x^4) in eine Gleichung, aber in Abschnitt 3.1 werden ständig die Landau-Symbole selbst gleichgesetzt. Am Ende von 3.1.1 steht z.B. Omega(n) = O(n) = Theta(n). Hier werden ja einfach drei Mengen gleichgesetzt, die nicht gleich sind! Ich hätte eher gedacht, dass man das so aufschreiben sollte:

Code: Alles auswählen

f(n) \in \Omega(n) \wedge f(n) \in \mathcal{O}(n) \wedge f(n) \in \Theta(n) 

Oder auch:

Code: Alles auswählen

f(n) \in \Omega(n), \mathcal{O}(n), \Theta(n) 

Ist das so üblich, das so zu schreiben wie in Abschnitt 3.1? Dürfen wir uns das auch angewöhnen? Wird das in der Klausur so akzeptiert? Falls nicht, wäre es schön, wenn in den Beispielen die korrekte Schreibweise benutzt werden würde.



EDIT: Die tex-Tags funktionieren überhaupt nicht, also habe ich sie durch code-Tags ersetzt, damit man wenigstens erahnen kann, was ich schreiben wollte.

[invariant]

Hallo,

kann ich akut nicht beantworten. Wird nochmal intern geklärt.

Gruß

[LukasPhysiker]

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

[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.

[Prof. Karsten Weihe]

Ist das so üblich, das so zu schreiben wie in Abschnitt 3.1? Dürfen wir uns das auch angewöhnen?

Wenn Sie erklären können, wie es eigentlich richtig wäre und warum das eigentlich mathematisch falsch ist...

Wird das in der Klausur so akzeptiert?

In der Klausur dürfte ggf. klar sein, was erwartet wird.

EDIT: Die tex-Tags funktionieren überhaupt nicht

Ja, das Problem habe ich leider auch.

KW

[LukasPhysiker]

Wenn Sie erklären können, wie es eigentlich richtig wäre und warum das eigentlich mathematisch falsch ist...

Habe ich das nicht in meinem ersten Post getan? In der zweiten Code-Box steht drin, wie ich es für richtig halte. Die Landau-Symbole beschreiben ja eigentlich Mengen. Mit der Schreibweise Omega(n) = O(n) = Theta(n) wird ja eigentlich behauptet, dass diese drei Mengen gleich sind, d.h. die Menge der Funktionen die asymptotisch mindestens so schnell wächst wie n sei gleich der Menge der Funktionen, die asymptotisch genau so schnell wächst wie n und gleich der Menge der Funktionen, die asymptotisch höchstens so schnell wächst wie n. Das ist ja offensichtlich falsch. Was gemeint ist, ist ja, dass fer die Komplexitätsfunktion des Algorithmus in allen drei Mengen enthalten ist, was ich ja in meiner zweiten Code-Box mathematisch aufgeschrieben habe.

[Prof. Karsten Weihe]

Wenn Sie erklären können, wie es eigentlich richtig wäre und warum das eigentlich mathematisch falsch ist...

Habe ich das nicht in meinem ersten Post getan?

Sorry, ich meinte: Wenn Sie (oder jemand anderes) das im Testat erklären können, können Sie (kann er/sie) das im Testat benutzen. Ich wollte nicht bezweifeln, dass Sie das erklären können bzw. erklärt haben.

KW

[LukasPhysiker]

Ach so, sorry, dann habe ich Sie falsch verstanden. Danke für Ihre Antwort. Dann bleibt nur noch die Frage: Kann man in der Klausur auch einfach Omega(n) = O(n) = Theta(n) schreiben? Da das ja schneller von der Hand geht als das was in meiner zweiten Code-Box steht, könnte ich mir vorstellen, dass ich das unter Zeitdruck machen würde, aber nur wenn ich wüsste, dass mir das dann keine Punkte kostet.

[Prof. Karsten Weihe]

Kann man in der Klausur auch einfach Omega(n) = O(n) = Theta(n) schreiben?

Ich denke, meine Frageweise wird so präzise sein, dass Sie nicht in diese Verlegenheit kommen werden.

KW