Diskussion:Landau-Symbole

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis 1 Singularregel 2 Asymptotisches Verhalten 3 Knuth-Definition 4 Landau-Symbole in der Komplexitaetstheorie 5 Beispiele 6 TeX oder Text, das ist die Frage 7 Verständlichket dieser Seite 8 Frage 9 Struktur der Landau-Mengen

[Bearbeiten] Singularregel

Spricht etwas dagegen, den Artikel wegen der Singularregel [1] auf "Landau-Symbol" umzubennen? --NeoUrfahraner 05:40, 6. Mär 2005 (CET)

Der Begriff wird recht selten im Singular benutzt. Für mich spricht gegen eine Verschiebung aber hauptsächlich der Aufwand um die vorhandenen Redirects anzupassen. Vielleicht kann das ja jemand mit einem Bot machen. Gruß, JuergenL 10:31, 6. Mär 2005 (CET)

Da es sich ja um mehrere verschiedene Symbole handelt, würde ich eine Beibehaltung des Plurals bevorzugen. Denn es handelt sich ja nicht einfach um eine Mehrzahl von ein und demselben "Gegenstand", sondern tatsächlich um unterschiedliche Symbole, die unter einem Begriff zusammengefasst werden. Man beachte auch, dass die Singularregel zahlreiche Ausnahmen hat und daher nicht zu streng ausgelegt werden darf. --Mkleine 19:47, 8. Mär 2005 (CET)

ACK. Wenn jemand "Landau-Symbol" sagt, frag ich mich gleich: "welches?" - der Artikel sollte das Plural-Lemma behalten. -- D. Dÿsentrieb ⇌ 22:51, 8. Mär 2005 (CET)

PS: Das mit der Asymptotischen Laufzeit ist in der Tat unglücklich - es kann ja genausogut Asymptotischer Platzbedarf sein - man sollte den Artikel wohl entsprechend umschreiben. -- D. Dÿsentrieb ⇌ 22:52, 8. Mär 2005 (CET)

[Bearbeiten] Asymptotisches Verhalten

Ich habe jetzt den Link von "asymptotisches Verhalten" auf Asymptotische Analyse gesetzt, den ich (analog zur englischen Version) neu angelegt habe; der Link auf "asymptotisches Verhalten" war dabei ein vergessener Zwischenzustand. REDIRECT von "Asymptotisches Verhalten" auf Asymptotische Analyse (wie in der englischen Version) halte ich nicht für notwendig. In Asymptotische Analyse wird als ein Beispiel weiter auf Asymptotische Laufzeit verwiesen, wenn es einen Artikel zum asymptotischer Platzbedarf gibt, gehört der sinnvollerweise wohl ebenfalls damit verlinkt. --NeoUrfahraner 23:57, 8. Mär 2005 (CET)

Prima so! Grüße --Mkleine 12:10, 9. Mär 2005 (CET)

[Bearbeiten] Knuth-Definition

Wo findet sich die Knuth-Definition der Landau-Symbole? TAOCP? Sind f und g positiv, so stimmt die Definition mit der mir bekannten überein; ist eines der beiden negativ, gibt es aber wesentliche Unterschiede. Kann jemand bitte nachprüfen, ob die Definition wirklich so stimmt, wie sie hier steht. Danke, --NeoUrfahraner 00:46, 9. Mär 2005 (CET)

Ich habe vorerst im Artikel bei der Knuth-Definition gefordert, dass f und g nichtnegativ sind; das ist jednefalls der interessante Fall und damit sind wir auf der sicheren Seite. Falls jemand die genaue Knuth-Definition für den negativen Fall findet, kann er die Änderung gerne rückgängig machen. --NeoUrfahraner 17:15, 9. Mär 2005 (CET)

Habe sie rausgenommen. Das war ein Überbleibsel aus der ursprünglichen Version; die Definitionen Knuth zuzuschreiben, erscheint mir ziemlich fragwürdig, 1892 hat Knuth noch nicht gelebt.-- Gunther 14:53, 18. Apr 2005 (CEST)

[Bearbeiten] Landau-Symbole in der Komplexitaetstheorie

In der Informatik werden sie insbesondere in der Komplexitätstheorie verwendet, um verschiedene Probleme und Algorithmen danach zu vergleichen, wie "schwierig" sie zu berechnen sind.

Ich behaupte mal ganz frech, dass die Landau-Symbole in der Komplexitaetstheorie relativ selten verwendet werden.

Betrachtet man Probleme bzgl. ihrer Komplexitaet, so werden eher die Komplexitaetsklassen wie P, NP, PSPACE, EXPTIME usw. herangezogen.

In der Informatik werden die Landau-Symbole v.a. bei der Laufzeitanalyse bzw. der Analyse des Speicherplatzbedarfs von konkreten Algorithmen eingesetzt.

--zeno 14:22, 18. Apr 2005 (CEST)

Wie nennt man das Teilgebiet der Informatik, dass sich mit "der Laufzeitanalyse bzw. der Analyse des Speicherplatzbedarfs von konkreten Algorithmen" beschäftigt? --NeoUrfahraner 08:56, 1. Jun 2005 (CEST)

Algorithmik? ---

Zu diesem Stichwort gibt es (noch?) keinen Eintrag in der Wikipedia. --NeoUrfahraner 12:37, 23. Nov 2005 (CET)

Wie wäre es mit Computeralgebra? Das Problem ist, dass die Fragestellung genau im Grenzgebiet zwischen Mathematik und Informatik liegt.--JFKCom 13:02, 22. Okt. 2006 (CEST)

[Bearbeiten] Beispiele

am besten sind Beispiele.

Wie lautet beispielsweise die Komplexität:

for (i=5;i<n*n;i++){ i=i+1; for (j=0;j<i;j++){ a=sqrt(c*c - b*b) }

}

oder:

for (i=5;i<n;i++){ i=i+1; }

for (j=0;j<i;j++){ a=sqrt(c*c - b*b) }

Besser wären wohl ein paar konkrete Algorithmen, beispielsweise ein dynamisch wachsendes Array; wenn man immer Blöcke fester Länge allokiert, hat das Einfügen am Ende O(n) Aufwand; wenn man die Blockgröße immer verdoppelt, hat das Einfügen am Ende im Durchschnitt O(1) Aufwand. --NeoUrfahraner 09:02, 1. Jun 2005 (CEST)

[Bearbeiten] TeX oder Text, das ist die Frage

@Squizzz: Ich hatte im letzten Abschnitt die TeX-Formatierungen durch Text ersetzt, weil sich dadurch der ganzen Textabschnitt erstens schöner lesen lesen, und desweiteren der Text schön gleichmäßig aussah. In manchen Fällen ist TeX wohl eine bessere Variante, das gebe ich zu, doch hier fand ich es wirklich schöner. Zumal für diesen Abschnitt wirklich für jedes TeX-Zeichen ein Textzeichen existierte. Was hast du gegen Text-Zeichen???

Vielleicht können auch noch andere Leute ihre Meinung zu "TeX-oder Textzeichen" äußern. Danke.--217.233.162.55 22:59, 28. Mär 2006 (CEST)

Das wurde schon x-mal diskutiert: Konsens ist, dass keine Formeln von TeX in HTML/Wiki-Markup umgeschrieben werden sollen. Hoffentlich bald kann man dann auch die Darstellung mit MathML auswählen, dann springen die Formeln nicht mehr so aus der Zeile.--Gunther 23:17, 28. Mär 2006 (CEST)

[Bearbeiten] Verständlichket dieser Seite

Liebe Landau-Symbol-Editoren: Ich habe soeben von der End-Rekursion her auf diese Seite verlinkt, weil wir dort die Gross-O-Notation für die Bezeichnung der Laufzeitklassen benötigen. Aber wenn nun ein Laie von der End-Rekursion her diese Seite anklickt, dann wird er den Computer verkaufen und Gärtner! Da bin ich überzeugt (Gärtner ist im Übrigen auch ein schöner Beruf)

Ich kenne die Gepflogenheiten bzgl. sprachübergreifender Links, bzw. Kopien (mit Übersetzungen) aus einer anderen Sprache von Wikipedia nicht, aber: Die englische Seite bzgl. der O-notation beinhaltet eine kleine Tabelle (Common orders of functions) der geläufigen Laufzeit-klassen. Könnte die hier noch 'reingeoperiert' werden?

Nicht, dass die Seite dadurch für Laien erheblich beruhigender wirken würde, aber es wäre ein Anfang und genau das, was von unserem Link her erwartet würde.

[Bearbeiten] Frage

Hi,
ich hab mal n Frage und bitte um schnelle Antwort:
ist O(x) - O(x) = 0 oder = O(x)

vielen Dank

مبتدئ 04:45, 22. Okt. 2006 (CEST)

Wo ist das Problem? ist doch offensichtlich. (Wenn Du die Frage nicht an zig Stellen gespammt hättest, hätt ich Dir glatt ’ne ausführlichere Antwort gegeben, so hab ich aber keine Lust dazu. *feix*) —mnh·∇· 06:10, 22. Okt. 2006 (CEST)

Erste Aussage ist falsch. Siehe ausführliche Antwort auf meiner Diskseite. --Schlurcher ??? 10:54, 22. Okt. 2006 (CEST)

Auch ich bin Opfer des Mehrfach-Spammens und habe geantwortet.--JFKCom 13:04, 22. Okt. 2006 (CEST)

Danke Mnh: es findet sich immer ein nette Wikipedianer der die Fragen beantwortet. Ich weiss das es in etwa sowas wie vernachlässigbar heisst, nur leider brauche ich das Symbol für die Reduktion von Systemen auf Zentrumsmannigfaltigkeiten und da muss ich den Restfehler oder Restdynamik schon Richtig Abschätzen und nicht einfach Null setzen. Danke JFKCom und sorry für das Spam nur leider brauche ich die Infos für in 2 Tagen deswegen bin ich etwas in Eile. Thanx مبتدئ 03:59, 23. Okt. 2006 (CEST)

[Bearbeiten] Struktur der Landau-Mengen

Ich beziehe mich auf einige der oben gestellten Fragen (Verständlichkeit).
Die Mengen, die eigentlich mit den Landau-Symbolen O(g) und o(g) gemeint sind, haben ja eine "natürliche Struktur" als Funktionenräume bzw. sogar als Algebren. Einige der formalen Eigenschaften (die mit den vielen Quantoren drin) ließen sich unter diesem Gesichtspunkt leichter formulieren, bzw. wären sogar selbstverständlich. Vielfache, Summe usw. von linearen Räumen. Dann würden auch die in Beweisen gern verwandten assymmetrischen Gleichheitszeichen der Art:

x + O(log(x)) = O(x)

(weil der Autor die bessere Abschätzung mit log nicht braucht) richtiger als Element- bzw. Teilraumbeziehungen interpretieren:

Problem dabei: Ob Landau die Symbole so gemeint hat, ist fraglich. Und das asymmetrische "=", das zumindest in der Zahlentheorie verbreitet ist, bleibt ein Ärgernis, das nicht via Enzyklopädie getadelt oder gar beseitigt werden kann.--KleinKlio 22:18, 26. Okt. 2006 (CEST)