Fehler im Skript

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Fehler im Skript

Beitrag von Wambolo »

Habe gerade einen Fehler entdeckt: Kapitel 3 Aysmptotik, Seite 3, erster Absatz

dort steht:
f=O(g) <=> g=o(f)

sollte sicher heißen
f=O(g)<=> g=Groß-Omega(f)


Vielleicht könnten wir ja an dieser Stelle noch ein paar mehr Fehler sammeln, sofern es weitere gibt.
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Fehler im Skript

Beitrag von oren78 »

was ist an: f=O(g) <=> g=o(f) verkehrt ???

hab mit g=o(f) so ziemlich bei jeder aufgabe gearbeitet wo gezeigt werden sollte ob: f(n) = O(g(n)) ist...klappte ganz gut :-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Wang Tang
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 5. Dez 2006 17:57

Re: Fehler im Skript

Beitrag von Wang Tang »

oren78 hat geschrieben:was ist an: f=O(g) <=> g=o(f) verkehrt ???
Gegenbeispiel:

edit: yoink, der hat das tex ganz schön zerhauen, also halt ohne

f(x) = x
g(x) = x^2

f = O(g), da
x <= c * x^2, für alle x >= 1, mit c = 1

g != o(f), da
lim_{x->oo} g(x)/f(x) = lim_{x->oo} x = oo != 0

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Fehler im Skript

Beitrag von oren78 »

@Wang Tang

hmmm...also das buch gibt dir schon mal auf jeden fall recht, wie man auf der seite: 49 (unter: Austausch-Symmetrie) sehen kann.
...seltsamerweise habe ich immer das, was du geschrieben hast, immer UMGEKEHRT geschrieben:

also statt: lim_{x->oo} g(x)/f(x) hatte ich immer: lim_{x->oo} f(x)/g(x) deswegen hat es "immer funktioniert" :-)


deswegen wäre es gar nicht mal so schlecht zu erfahren, was die EXAKTE Notation ist (am besten gleich für alle fälle, also Omega, O, Theta..)
kann man sich auf die notation in wikipedia: http://de.wikipedia.org/wiki/Landau-Symbole verlassen ??

BITTE UM EINE ANTWORT VOM VERANSTALTER !
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

andre_w
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 125
Registriert: 14. Okt 2007 14:59
Wohnort: Kriftel
Kontaktdaten:

Re: Fehler im Skript

Beitrag von andre_w »

Ich denke, Wambolo hast recht. Wenn es stimmen würde, was im Skript steht, könnte man folgende Umformung machen:

f=O(g) <=> g=o(f) <=> f=w(g)

Erstes gwd. entspricht dem von oben, zweites gdw. steht im Skript direkt darunter (f=o(g) <=> g=w(f)). Das macht aber keinen Sinn, dann würde O und w das selbe aussagen und das stimmt sicherlich nicht.
let's be friends on twitter studivz facebook - my blog

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

Re: Fehler im Skript

Beitrag von ^Lara^ »

und die nächste Zeile ist doch auch falsch oder?
das war ja genau in der hausübung...

Benutzeravatar
Georg
Mausschubser
Mausschubser
Beiträge: 60
Registriert: 15. Okt 2007 19:02

Re: Fehler im Skript

Beitrag von Georg »

ich bin zwar kein Veranstalter, aber mir recht sicher, dass ich weiss wies "richtig" ist (man beachte, dass man "informierten mitstudierenden" nicht vertrauen soll, prüft es nochmal nach!)

ungeachtet dessen was im script steht, sagen alle (anderen) Quellen (ich lerne nach "introduction to algorithms") dass
\(f = o(g) \iff f < c * g\)
und
\(g = \omega(f) \iff g > c * f\)
im unterschied zu
\(f = O(g) \iff f \leq c * g\)
und
\(g = \Omega(f) \iff g \geq c * f\)

die jeweils grossen unterscheiden sich nur dahingehend von den kleinen, dass sie auch \(f = c * g\) ermöglichen

@lara: die 2te zeile ist also nicht falsch, es ist nur ein kleiner schreibfehler in der ersten zeile.
Alle Angaben ohne Gewähr
_________________
"there is no such word as 'impossible' in my dictionary. In fact, everything between 'herring' and 'marmalade' appears to be missing"
-- Dirk Gently

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Fehler im Skript

Beitrag von s!mon »

Vorsicht, das stimmt so nicht ganz. Es gibt noch eine weitere "Verschärfung" der Bedingungen:

O(n) verlangt ein c>0 für dass die Ungleichung für alle n >no gilt

o(n) verlangt, dass es für jedes c>0 ein bestimmtes n>no gibt, so dass die Ungleichung erfüllt.

Da solltest du drauf achten wenn du direkt mit den Definitionen arbeitest (und nicht mit mit dem Limes)

dahmen
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 26. Apr 2006 18:54

Re: Fehler im Skript

Beitrag von dahmen »

Wambolo hat geschrieben:Habe gerade einen Fehler entdeckt: Kapitel 3 Aysmptotik, Seite 3, erster Absatz

dort steht:
f=O(g) <=> g=o(f)

sollte sicher heißen
f=O(g)<=> g=Groß-Omega(f)
Richtig, das ist ein Fehler. Korrekt ist
f=O(g)<=> g=Groß-Omega(f)

Antworten

Zurück zu „Archiv“