Ankündigung

Einklappen
Keine Ankündigung bisher.

User helfen Usern - Mathe

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

    Zitat von moonylo
    Zitat von fapescalation
    Bin mit dem Problem wohl nicht alleine

    http://www.gute-mathe-fragen.de/?qa=blob&qa_blobid=3508025764457553629


    HELP :D

    Hört sich jetzt nicht so kompliziert an. Wenn man das natürlich mit Äquivalenzumformungen machen will, dann wirds wohl kompliziert.

    -> Doppelte Inklusion zeigen. Also
    1) Wenn k € S(L(n),n), dann folgt dass k € T(n)
    2) Wenn k € T(n), dann folgt dass k € S(L(n),n)

    Andere Frage: Was soll T(n) sein ? Und die Defintion von der P(n) Menge ist auch wirr :(

    Ah |P sind wohl die Primzahlen, |N die natürlichen Zahlen. Nur T(n) ist noch unklar.
    T wird die Teilermenge (menge aller teiler von n) sein nehm ich an, würd zumindest im zusammenhang sinn machen

    Kommentar


      Bin das mal im Kopf durchgegangen, sollte wirklich gehen mit 1) und 2). Noch kurz zur Erklärung der doppelten Inklusion:

      Wenn man 2) zeigt, dann ist also die Menge T(n) enthalten in der Menge S(L(n),n).
      Wenn man 1) zeigt, dann ist also die Menge S(L(n),n) enthalten in der Menge T(n).

      Wenn die jeweils ineinander enthalten sind, dann sind die Mengen gleich.

      Muss man halt nur Schritt für Schritt durchgehen. Zu 2):

      a) Wenn t € T(n), dann ist t ein Teiler von n. Sei t^2 n, dann ist | n/t | € L(n) und damit auch in S(L(n),n). Warum ist | n/t | € L(n) ? Nennen wir | n/t | mal k. also |t|*k = |n|. Damit ist k schonmal ein Teiler von n. Also müssen wir noch zeigen, dass k^2 n (aus der Fallunterscheidung) folgt.

      1) Darfst du selber machen :)

      Die andere Teilaufgabe würde ich genau so angehen und schauen wann du nicht mehr weiterkommst und ob das überhaupt sein kann. Dann findet sich da an der Stelle auch ein Gegenbeispiel - oder es geht durch und es stimmt ;)

      Kommentar


        Zitat von moonylo
        Bin das mal im Kopf durchgegangen, sollte wirklich gehen mit 1) und 2). Noch kurz zur Erklärung der doppelten Inklusion:

        Wenn man 2) zeigt, dann ist also die Menge T(n) enthalten in der Menge S(L(n),n).
        Wenn man 1) zeigt, dann ist also die Menge S(L(n),n) enthalten in der Menge T(n).

        Wenn die jeweils ineinander enthalten sind, dann sind die Mengen gleich.

        Muss man halt nur Schritt für Schritt durchgehen. Zu 2):

        a) Wenn t € T(n), dann ist t ein Teiler von n. Sei t^2 n, dann ist | n/t | € L(n) und damit auch in S(L(n),n). Warum ist | n/t | € L(n) ? Nennen wir | n/t | mal k. also |t|*k = |n|. Damit ist k schonmal ein Teiler von n. Also müssen wir noch zeigen, dass k^2 n (aus der Fallunterscheidung) folgt.

        1) Darfst du selber machen :)

        Die andere Teilaufgabe würde ich genau so angehen und schauen wann du nicht mehr weiterkommst und ob das überhaupt sein kann. Dann findet sich da an der Stelle auch ein Gegenbeispiel - oder es geht durch und es stimmt ;)
        danke für die ausführlichen schritte :-)

        Kommentar


          Zitat von moonylo
          Das zweite ohne Induktion würde ich so gelten lassen. Aber um das korrekt aufzuschreiben fehlt da noch etwas:

          1) Wenn du das mit Äquivalenzumformungen machst, dann fang immer mit der Gleichung an, die korrekt ist. Sprich du musst, wenn du den Beweis hinschreibst, die letzte Gleichung zuerst hinschreiben.
          Ich fand das auch immer bescheuert, als mein Prof mir das gesagt hat, aber irgendwo hat er recht. Denn wenn man das mit Worten erklärt, dann würde man bei deiner Form sagen:

          Wenn 2 * F(n) >= F(n+1) gelten würde, dann würde auch gelten, dass
          .... und dann auch das
          .... und dann würde auch gelten dass
          F(n-2) >= 0. Und das gilt und deshalb gilt auch die erste Gleichung.

          Das hört sich absolut bescheuert an :) Viel besser:

          Es gilt F(n-2) >= 0. Daraus folgt, dass
          ... Und daraus folgt, dass
          ... und damit ist
          2 F(n) >= F(n+1).

          Wenn man dann nur bestimmte n € N nimmt, hört sich das erste noch blöder an.

          2) Du bist noch schuldig, dass F(n-2) > 0 ist für alle n >= 2 (oder 3 oder was auch immer). Keine große Sache das zu zeigen, aber fehlt halt noch (Sowas ist bei Induktion implizit mit drin).

          ------

          Bei der "Induktion", also erster Teil, ist da die zweite Zeile falsch. Mal unabhängig von dem was ich in 1) gesagt hab:

          2*F(n) >= F(n+1) = F(n) + F(n-1)
          F(n) >= F(n-1)

          Im Endeffekt brauchen wir dafür aber keine Induktion mehr, sondern wie bei 2) noch eine zusätzliche Gleichung, die wir allgemein zeigen müssen bzw auch können.
          Zum ersten Teil gebe ich dir vollkommen recht.

          Ich sehe allerdings den Fehler in der zweiten Zeile der ersten Aufgabe nicht. Natürlich kann man die Aufgabe auch so ohne Verwendung der Induktionsannahme lösen, wie du es vorzeigst. Allerdings ist meine Herleitung mit Induktionsannahme deswegen ja nicht falsch, oder?

          Kommentar


            Sitze auch gerade an Induktionsbeiweisen. Leider sind meine Umformungsskills etwas eingerostet. Hab die Induktion quasi fertig, aber im letzten Schritt muss ich die Gleichheit ja irgendwie ersichtlich machen (via Taschenrechner geprüft ist sie schon). X € N

            -2^(-X-1) = -2^(-X) + 2^(-X-1)

            Jemand ne Idee ?

            Kommentar


              schreib die -2^-1 als -1+ 2^-1

              denke wird dir was bringen nicht ganz angeschaut

              Kommentar


                taschenrechner approved :D

                du hast auf beiden seiten 2^(-X-1) stehen, dadurch fällt das -1 im exponenten direkt weg

                Kommentar


                  werf doch einfach mal einen logarithus drauf dann kannst du alles zusammenfassen :D

                  Kommentar


                    Multiplizier die Gleichung doch einfach mal mit 2^X.

                    Kommentar


                      Zitat von Stone
                      Multiplizier die Gleichung doch einfach mal mit 2^X.
                      super, danke :) man rostet so schnell ein bei mathe, wenn man's mal ne weile nicht macht. danke auch an die anderen.

                      Kommentar


                        Zitat von Hagi
                        Zum ersten Teil gebe ich dir vollkommen recht.

                        Ich sehe allerdings den Fehler in der zweiten Zeile der ersten Aufgabe nicht. Natürlich kann man die Aufgabe auch so ohne Verwendung der Induktionsannahme lösen, wie du es vorzeigst. Allerdings ist meine Herleitung mit Induktionsannahme deswegen ja nicht falsch, oder?
                        Ich meinte da nur, dass du da was falsch gerechnet hast. Und dann raffe ich auch nicht wo du die Induktionsannahme anwendest (mit korrigiertem Fehler) :(

                        Kommentar


                          Zitat von moonylo
                          Zitat von Hagi
                          Zum ersten Teil gebe ich dir vollkommen recht.

                          Ich sehe allerdings den Fehler in der zweiten Zeile der ersten Aufgabe nicht. Natürlich kann man die Aufgabe auch so ohne Verwendung der Induktionsannahme lösen, wie du es vorzeigst. Allerdings ist meine Herleitung mit Induktionsannahme deswegen ja nicht falsch, oder?
                          Ich meinte da nur, dass du da was falsch gerechnet hast. Und dann raffe ich auch nicht wo du die Induktionsannahme anwendest (mit korrigiertem Fehler) :(
                          Deine beiden Sätze sind wohl nicht komplett unabhängig.

                          Bis hier sind wir uns ja einig:
                          2 F(n) >= F(n+1)
                          = F(n) + F(n-1)
                          = 2 F(n-1) + F(n-2)

                          jetzt verwende ich die Induktionsannahme, 2 F(n-1) >= F(n), das gibt dann

                          2 F(n) >= F(n) + F(n-2)

                          und nach Vereinfachung

                          F(n) >= F(n-2)

                          Da hat es doch keinen Fehler drin, oder?

                          Kommentar


                            Ah jetzt versteh ich, danke! Sieht für mich richtig aus, bis auf die gleichen 2 Sachen, die ich auch zum direkten Beweis gesagt hab :)

                            Kommentar


                              function Order1(v)
                              if v = null then return
                              else
                              Print(v)
                              Order1(leftChild)
                              Order1(rightChild)
                              end if
                              end function


                              function Order2(v)
                              if v = null then return
                              else
                              Order2(leftChild)
                              Print(v)
                              Order2(rightChild)
                              end if
                              end function


                              function Order3(v)
                              if v = null then return
                              else
                              Order3(leftChild)
                              Order3(rightChild)
                              Print(v)
                              end if
                              end function


                              Als Eingabe erhalten die Algorithmen einen binären Baum. Jetzt soll ich dazu die Laufzeiten bestimmen. Die Print Operation kostet O(1)
                              Folgender Lösung hab ich:

                              T(n) = 2T(n/2) + O(1) => O(n), durch Master-Theorem.

                              Das kann doch irgendwie nicht sein oder?

                              Kommentar


                                Sollst du die Laufzeit bestimmen, oder den Aufwand der elementaren Operationen bestimmen?

                                Weil wenn es echt die Laufzeit ist, dann musst du folgendes bestimmen:
                                1) Codierungslänge Input (bei dir der binäre Baum, kommt dann auf Speichermethode an)
                                2) #elementarer Operationen
                                3) Codierungslänge größte Zahl

                                Laufzeitfunktion f ist dann #elementarer Operationen * Codierungslänge der größten Zahl

                                Kommentar

                                Lädt...
                                X