hä? wo hat er da ein beispiel aufgeschrieben?
schnelle exponentiation heißt doch, man ersetzt das n in x^n durch 2^i (zumindest haben wir das in der tueb so gemacht). demnach ist der 2er-logarithmus gemeint.
die anzahl der multiplikationen ist nach diesem verfahren n + log(n!), damit ist auch die stelle gefunden, an der man die stirlingformel verwenden kann.
log ist (selbstverstaendlich) immer der duale Logarithmus. Alles andere macht ja in nem binaeren Zahlensystem gar keinen Sinn. Ausserdem unterscheidet sich das alles ja nur um einen Faktor und kann deswegen eigentlich ignoriert werden:
c * lg(n) = c * ld(n) / ld (10) = c’ * ld(n)
wenn ihr wisst was ich mein 
Hmm. Nicht ganz richtig. Du hast beim dynamischen Programmieren immer zwei Moeglichkeiten. Es kommt ja darauf an, dass du kleine ueberlappende Teilprobleme hast, die miteinander zusammenhaengen. Wenn Du zum Beispiel Merkel und Stoiber vergleichst, ist ein Teilproblem Merkel und Stoi.
Wenn Du weisst, wie diese Teilprobleme zusammenhaengen (wurde in der Tafeluebung erklaert), dann kannst Du die Matrix iterativ befuellen (hier von oben links nach unten rechts). Das nennt man dann Bottom-up Dynamic Programming.
jetzt waren die Zeichen voll, drum ein zweites Posting 
Also wenn Du aber nichts ueber den Zusammenhang der Teilprobleme weisst bzw. der Zusammenhang der Teilprobleme nicht ganz so einfach ist wie beim Levenshtein-Abstand, dann initialisiert man die Kostenmatrix mit einem Wert, der garantiert nicht vorkommen kann, hier koennte das zum Beispiel -1 sein.
Jetzt sucht man sich einen rekursiven Ansatz heraus, den kann man hier leicht bilden und fraegt in jedem Rekursionsschritt einfach in der Tabelle ab, ob beim gefragten Wert in der Tabelle -1 drinsteht. Falls ja, dann macht man einfach in der Rekursion weiter, falls nein, wird der Wert in der Tabelle (die ja zum Zwischenergebnisse speichern da ist) hergenommen.
Das nennt man dann top-down Dynamic Programming.
Die Tabellen schauen in beiden Faellen gleich aus, recht unten steht der guenstigste Weg drin.
Schaut Euch einfach mal die Folien zum Dynamic Programming an, die auf der ALGO-Homepage verlinkt sind.
zu Aufgabe 2-2 nochmal:
wenn ich jetzt die Anzahl der Multiplikationen für die beiden Verfahren habe (n für Horner und n+log(n) für Schnelle Exponentiation, oder?), wie vergleiche ich die dann mit der Stirling-Formel? Die ist doch eigentlich nur für Fakultäten!? Aber ich habe hier ja keine Fakultät. Was muss ich denn da wo einsetzen? Ich glaub ich steh grad irgendwie aufm Schlauch. :rolleyes:
also bei uns war des glaub ich nur log(n!) wo kommt das +n her?
ich steh bei den aufgaben total auf dem schlauch!!! :wand:
was heißt hier „iterativ“ sowohl das x^n als auch das ganze polynom iterativ?
wo hab ihr eigentlich alle das „n + log(n!)“ her?
sollte das * von ai * x^i sein
das Ganze kommt aus der 1.4:
die eine Mutliplikation von oben + log(i) für die Exponentiation
=> Σ from i=1 to n {(log i) + 1} = n + Σ from i=1 to n {log i} = n + log (product from i=1 to n { i } ) = n + log ( n! )
…meine errechneten Zahlen für die Anzahl der Multiplikationen kommen mir aber etwas komisch vor :#:
Das log(n!) kann man laut Stirling's Approximation to the log factorial function, and the gamma function mit der Stirling-Formel so vereinfachen:
allerdings ergibt das bei mir etwas andere Ergebnisse als log(n!)
… oder ich bin zu doof zum Taschenrechnerbedienen :vogel:
Hat schon jemand ein richtiges Ergebnis?
ich find des auch voll komisch, wieso rechnen wir nich einfach n! so aus?? bis 32 geht des doch noch locker
n + log(n!) liefert einem nur den Aufwand für Methode 1.4 nicht die wirkliche Anzahl der Multiplikationen! es ergibt sich wenn man die Sterling Formel einsetzt und umformt insg. O(n*log(n)).
für n > 4 ist die Anzahl der Multiplikationen die man allein für die Exponentationen braucht (ohne die Multp. von a_i * x^i) sicher grösser als log(n!).
das Problem ist folgendes: man muss ja alle Multiplikationen berücksichtigen die man für die Berechnung von x^1, x^2, x^3 … x^i … x^n braucht. nun wurde davon ausgegangen, dass man jeweils log(i) braucht, also zusammen Σi=1 … n über log(i) = log(n!) … das stimmt aber nicht, da man NUR dann genau log(i) Multiplikationen braucht, wenn i von der Form 2^k ist wobei k ∈ N (wie man in der 3. Aufgabe Blatt 8 zeigen musste), sonst sicher mehr! das ist praktisch der günstige “sonderfall” für i. lässt sich der Exponent i nicht immer schön durch 2 teilen, ist also keine 2er-Potenz, braucht man auf jeden Fall mehr multiplikationen, da man dann praktisch im algorithmus einen zwischenschritt i - 1 statt i/2 einlegen muss der einem aber ebenfalls eine extra Multiplikationen kostet und keine wirkliche reduktion von i bewirkt. ob man da auf die schnelle eine gute mathematische formel findet die einem für einen bel. exponenten i die anzahl der schritte sagt bis man bei 1 ist weiss ich nicht (hängt davon ab wie “ungerade” i ist). es is aber sicher nicht log(i) (eben nur für den spezial fall). somit ist n + log(n!) nur eine untere Schranke und eben nur dazu gut abzuschätzen von welchem typ der aufwand der methode ist. für grosse n ist die abweichung der echten anzahl d. multiplikationen von n + log(n!) schnell bei guten 30% mehr.
/edit: hat sich erledigt…
ich hats mir so ausgerechnet: erstmal alle produkte im log getrennt mit seperaten logs und + aufgeschrieben:
n + log(n!) = n + log[(n/e)^n * sqrt(2pin) * (1 + 1/(12n) + 1/(288n^2) + …)]
= n + log[(n/e)^n] + log[(2pin)^(1/2)] + log[1 + 1/(12n) + 1/(288n^2) + …]
/edit: der letzte log hat natürlich für n->∞ grenzwert 0, also argument 1 blind
= n + nlog[1/e * n] + 1/2 * log[2pi * n]
da die aufwände folgendermassen sortiert sind:
O(nlog(n)) > O(n) > O(log(n)) > O(1)
spielt für hinreichend grosse n nur das nlog[c * n] wirklich rein… somit O(n*log(n))
danke
mit dem ln wär’s noch schöner als mit dem ld, dann würde das e wirklich rausfallen…
lol 
Leider völlig falsch, ich glaube du stösst bei jeder suchmaschine darauf etc
und ich behaupte doch mal dass man dies viel besser lösen kann als mit ner kostenmatrix
denn
- brauchst du eine große matrix um lange strings zu vergleichen
- falls nicht eine große viele kleine
- dadurch darfst du mächtig viel speicher allocaten und deallocaten
um rauszufinden ob ein wort in einem anderen enthalten ist schau ich wo der erste buchstabe des einen worts im nächsten ist und vergleiche wieviele buchstaben in derselben reihenfolge kommen bis wieder ein verkehrter buchstabe kommt
…
is nurn beispiel
wobei ich da wohl noch bestimmte optimierungen machen würde um den speicherdurchsatz zu erhöhen und gewisse cpu spezifische befehlssätze
einsetzen würde
denn byteweise sowas zu vergleichen is auf 32 bit systemen wohl nicht das non plus ultra
zum beispiel wenn ich nen pointer auf nen byte buffer habe und 4 bytes checken will dann mach ich das nicht einzeln sondern ich mach nen pointer aufs erste byte und caste das zu nem pointer auf nen int32
und vergleiche die 4 bytes auf einmal
byteweise würde das so ausschauen
0.64 fürs vergleichen + 40.5 um den pointer zu incrementieren
mit meiner methode brauch ich nur
1.0 fürs casten + 0.6 da ich 4 bytes auf einmal vergleiche
- 0.5 für einmal pointer incrementieren
das is auf jeden fall schneller als dieses byte weise levenshtein
- ich referenziere die 4 bytes nur einmal in form von 32 bit und nicht 4x 8bit wo ich 24bit mit 0 auffüllen muss das is ebenfalls schneller
levenshtein = 4.2x zeitverbrauch rel. zu ner 32 bit assignment
meine methode = 2.1x zeitverbrauch rel … ^^^^^^^^^^^^
die werte sind dem buch tantalon entnommen welches sich mit game programming mit c++ beschäftigt und diverse optimierungs verfahren für c++ quellcode zeigt und mit profilings beweisst.
hinzu kommt das moderne cpus weitaus mehr für 32 optimiert sind als für 8bit und unsigned long64 sogar noch schneller ist nur wirste wohl selten mal nen 8 buchstaben langen string in ner suchmaschine auf matches vergleichen.
nach meinem verfahren schauste ob sie gleich sind falls ja ok falls nicht kannste byteweise wiederholen
wobei zuvor der text der mit nem suchstring verglichen wird in tokens zu parsen ist was kein großer aufwand weiter ist
jedenfalls musst du solange du suchst keine arrays von mxn allocaten und einzelne lookups machen
achja per ASM kannste dem rechner auch noch durch prefetch anweisungen sagen dass er den text und die suchstrings in den cache laden soll damit er nicht wartet bis sich der ram meldet
wieso enthalten, es geht doch darum, wie leicht man es ins andere wort umwandeln kann
in einer suchmaschine willste aber nicht nur wissen wie leicht du es umwandeln kannst sondern wie oft es auch komplett vorhanden ist
levenshtein is ja au net so für suchmaschinen gedacht…
die haben das eh alles vorsortiert, das is ne ganz andere geschichte
Ich finde Apfelmus viiieeel Besser als Levenshtein!
so!
:wand: