Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 5.2 : Rechenregel
Hallo,
Ich sitze grad vor dieser Aufgabe und probiere diesen Beweis durchzuführen.
Gegeben sei f : N → R+ und g : N → R+ . Es gilt f (n) ∈ Θ(s(n)), g(n) ∈ Θ(r(n)).
Beweisen Sie f (n) · g(n) ∈ Θ(s(n) · r(n)).
Nur leider weiß ich garnicht, wo ich da ansetzen soll.
Hat jemand einen Tip für mich?
Bin echt am verzweifeln.
Danke!
Ging mir genauso. Ob ich den Beweis jetzt richtig gemacht habe, kann ich nicht sagen, aber ich bin über die Potenzen der Funktionen gegangen, falls dir das weiterhilft.
Danke für die schnelle Antwort.
Wenn ich ehrlich bin, weiß ich leider nicht, was du damit genau meinst und wie ich vorgehen sollte.
Vielleicht findet sich ja noch eine Erklärung.
Ich kann euch nicht sagen, wie genau ihr diesen Beweis führen sollt, aber trotzdem kann ich einen Tipp geben. Es ist gegeben, dass f(n) Element von Groß Theta von s(n) ist. Macht euch klar was genau das heißt, was Groß Theta, Groß Omega und Groß O genau aussagt. Dann sollte schnell klar werden, wie man den Beweis machen soll.
Alternativ einfach “Beweisen Sie” mit “Daraus folgt” ersetzen.
f : N → R+ und g : N → R+
Soll das bedeuten, dass es eine Funktion f gibt, die natürliche Zahlen auf positive reelle Zahlen abbildet? Und entsprechend zur Funktion g?
Ich kann schon mit diesem Pfeil zwischen N und R+ nicht wirklich was anfangen… geschweige denn mit dem Rest der Aufgabe.
Ich glaub das soll einfach nur bedeuten, dass die Funktionen im Allgemeinen Natürliche Zahlen auf Reelle Zahlen abbilden
ich komme mit dem beweis auch nicht zurecht.
Find es auch langsam nervig dauernd etwas zu beweisen. Reicht doch, wenn man weiß, dass es die Regel gibt.
Der Sinn, dass wir so viele Beweise machen müssen ist, dass wir verstehen warum wir diese Regeln anwenden dürfen. Es macht einen gewaltigen Unterschied ob du gelernt hast, dass du die Rechenregel und andere anwenden darfst, oder ob du verstanden hast, warum diese Regeln stimmen. Denn wenn du verstanden hast, warum diese Regeln gelten, dann wirst du sie nicht so schnell vergessen. Außerdem lernst du nebenbei andere Regeln anzuwenden, wenn du einen Beweis führst.
Ps: Wenn ihr euch anschaut, was ich davor geschrieben habe und die Grundlogik, wie man Ungleichungen umformt und verbindet, dann kann man den Beweis recht schnell lösen, bin ich der Meinung. Sollte es dann immer noch nicht gehen, fragt etwas spezifischer, dann kann man vielleicht gezielter helfen.
Ja, so ungefähr. Das ist eine Standardangabe in der Mathematik, wenn man von Funktionen spricht, um sie möglichst allgemein zu charakterisieren.
f : X → Y heißt einfach, dass f eine Funktion ist, die auf der Menge X definiert ist und in die Menge Y (X, Y z.B. N, R, R+, etc.) abbildet.
Man will dabei nicht sagen, WIE die Funktion genau definiert ist, also keine Funktionsvorschrift angeben, sondern nur sozusagen die „Funktionssignatur“ (Eingabe aus X, Ausgabe aus Y).
Und muss man wissen, wofür theta steht? Oder hat es überhaupt irgendeine Bedeutung?
Momentan sieht die Aufgabe für mich so aus:
Beweise, dass das produkt zweier Funktionen dem Produkt ihrer Obermengen entspricht.
Ja, man sollte wissen wofür Theta steht. Schau einfach mal in den Vorlesungsfolien nach, da steht es drin was genau das bedeutet.
Ich habe die Folien zu Kapitel 5 eigentlich durchgeblättert, konnte da aber kein Theta finden. Oder ist es das, was auf den Folien immer O heißt?
Siehe 5-45, und vor allem 5-51
evtl. ist auch 5-54 ganz interessant
darf man den beweis stark an den für die Summenregel in den Folien anlehnen?
Stark ist so relativ.
Wenn Du den Beweis verstanden hast, solltest Du in der Lage sein, den in der Aufgabe verlangten aufzustellen.
Schau dir vielleicht mal den Wikipedia-Artikel zur Landau-Notation (oder entsprechend andere Internetseiten) an.
darf mana uch über die abletungen argumentieren?
Alles was richtig ist, ist erlaubt, denke ich mal. Ist die Frage, ob das dann nicht eher verkompliziert wird…