buzz_lightzyear

Hallo, ich hab hier folgendes Beispiel vor mir: T(n)= T(n-a)+n, T(n)=O(1) für n <= 1. Durch iteratives Einsetzen erhält man lt. Beispiel folgende Gleichungen: T(n)= T(n-2a)+2n, T(n)= T(n-4a)+4n, T(n)= T(n-8a)+8n, ... Ich setze also für die erste Gleichung für n (n-a) ein... soweit klar, auch bei den nächsten Schritten... aber wie zum Teufel bzw. warum hab ich dann 2n, bzw 4n usw. da stehen. Klar, 4 ist das doppelte von 2, 8 von 4 usw... aber warum nicht irgendeine andere Zahl... Sorry aber ich komm da echt nicht drauf... ;-( Danke für eure Hilfe! :-) lg buzzzzzz

Hallo nochmal, ich hab gleich noch eine Frage zu einem anderen Beispiel und zwar gehts hier um die Fibonacci-Folge (rekursiv). Die Rekursionsgleichung dazu lautet: T(n)=O(1) + T(n - 1) + T(n - 2)= //Rekursionsgleichung, alles klar =O(1) + O(1) + T(n - 2) + T(n - 3) + T(n - 2) Hier hab ich ein kleines Verständnisproblem und zwar: Ich bin hier einen Rekursionsschritt tiefer, sprich ich habe (n-1) für n in die erste Gleichung eingesetzt -> ok! Aber woher kommt das letzte T(n - 2)? Das kann ich nicht nachvollziehen... :-( Jemand einen Tipp für mich? :-) Thx & Lg buzz

Hallo, danke für deine Antwort, ja es ist O(n). Trotzdem weiß ich eben nicht, wo das T(1) = T(n-k) herkommt... Unser Prof. nimmt das eben immer als so einfach an, dass sowas nicht erwähnt werden muss. -.- Thx & Lg

Hallo, ich habe folgendes Beispiel vor mir liegen; es geht um die rekursive Berechnung der Fakultät: FAKULTAET_REKURSIV(n) 1: IF n= 1 THEN 2: RETURN 1 3: ELSE 4: RETURN(n*FAKULTAET_REKURSIV(n-1)) Soweit alles klar :-) Dann gehts zur Rekursionsgleichung: T(n) = O(1) + T(n-1) O(1): konstante Zeit, die die Zeilen 1-3 benötigen T(n-1): Laufzeit um eins verringert, da die Funktion ja mit (n-1) aufgerufen wird -> auch noch klar :-) Dann wird die Rekursionsgleichung gelöst und eine allgemeine Formel hergeleitet: k*O(1) + T(n-k) -> ja, das ist auch noch klar! :-) Aber jetzt kommt das Problem: Man will eine Lösung unabhängig von k. In dem Beispiel vor mir hab ich nun: "Mit T(1) = T(n-k) bekommt man n-k = 1 => k = n - 1 und setzt das in die obige allgemeine Formel ein." Warum setzt man hier T(1) = T(n-k)?? das ist ja mMn nicht das Gleiche?!? Kann mir vllt jemand erklären warum das so ist? Thx & Lg buzzzzzz

Hallo, ich stehe hier vor folgender noch-nicht ;-) LL(1) Grammatik: Das ganze soll einfache arithmetische Ausdrücke behandeln: E-> E + E E -> E * E E -> ( E ) E -> num Alles aus den grossen E s sind terminalsymbole. Nun hab ich folgendes als lösung: Hier wurden die Linksrekursionen entfernt: E -> num R E -> ( E ) R -> + ER R -> * ER R -> epsilon wieder ausser großbuchstaben alles Terminalymbole. Diese Lösung verstehe ich allerdings nicht ganz, ich dachte immer wenn die Linksrekursionen entfernt wurden, sollte alles 100% eindeutig sein... ist es meiner meinung aber nicht weil der parser ja nicht weiss welche E-> bzw. welches R-> er nehmen sollte. Hat da jemand einen Tipp für mich? danke & lg

Hallo, ich wollte heute Suse auf meinem Laptop installieren. Ich habe die SUse Installation leider unter Windows gestartet. Dann hat er irgendwas herumkopiert und mich zu einem neustart aufgefordert. Dann war ich in der Suse installation Leider ist die Installation wegen eines Paketfehler abgebrochen und ich wollte wieder in mein Vista zurück. leider schickt mich vista nach dem Start sofort wieder in die Suse-Installation und ich bekomm das nicht weg. ICh denke, dass ein paar zeilen in eine STartdatei geschrieben wurde die ich löschen müsste. Ich kann natürlich auch völlig falsch liegen. ;-) Kann mir wer einen Tipp geben wie ich mein Vista wieder auf Vordermann bringe? Danke & Lg

Cool! :-) Also ich hab da jetzt einfach die Umkehroperation angewendet. Ok, weiteres Problem: Wenn ichs nun für ein Monat ausrechne, bin ich bei 2.6784*10^12 Was soll man dann mit dem Zeug anfangen? aus dem die Wurzel ziehen?

Jetzt bin ich auch auf 1000 gekommen... juhu ein Fortschritt... :upps Also bei 1 Stunde komm ich auf 60000... wenn das stimmt dann hab ichs glaub ich endlich gecheckt

Ok, also ich hab jetzt mal ein bisschen rumgerechnet und bin bei einer Sekunde auf 1*10^12 gekommen... kann das richtig sein?

Also n² = 1000000??

Danke für deine Antwort. Aber ich glaube ich stehe hier auf der Leitung: Was meinst du genau mit "nur noch f(n) durch die gegebene Funktion ersetzen..." usw.? :confused: Komm da irgendwie nicht weiter... Danke dir & Lg :uli

Hallo, ich stehe hier vor folgendem Beispiel: Bestimmen Sie für jede Funktion f(n) und Zeit t in der folgenden Tabelle die maximale Problemgröße n max (t) welche in der Zeit t berechnet werden kann, wenn man annimt daß der Algorithmus bei Inputgröße n f(n) Mikrosekunden benötigt. Das Ganze für die Funktion n². In der Tabelle steht 1 Sekunde, 1 Stunde, 1 Monat, 1 Jhdt. Ich will mir hier nicht Arbeit ersparen und mir das Ausrechnen lassen, bitte nur um einen kurzen Ansatz wie ich das lösen könnte. Danke & Lg