Informatiker Board | Theoretische Informatik | Verstaendnisproblem mit einem Beispielalgorithmus aus Knuth

Informatiker Board » Themengebiete » Theoretische Informatik » Verstaendnisproblem mit einem Beispielalgorithmus aus Knuth » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 3 Beiträge
Surma	Danke erstmal fuer die Latex-Hinweise. Das ganze ist (meiner Meinung nach) ungekuerzt, aber frei aus dem Englischen uebersetzt. Das ganze taucht im Kontext von "effizienten" Algorithmen auf. Da vor wurde in diesem Schema Euklid's ggT-Algorithmus gezeigt, der wohl ineffizient war. Den hab' ich aber problemlos verstanden (siehe Anhang). Ich habe mal die relevante Seite hier angehaengt, vielleicht hab' ich auch was relevantes uebersehen. Die mathematische Ausfuehrung fangt auf der ersten Seite letzter Absatz an. http://drebesium.org/~crock/stuff/knuth.pdf MfG Surma
Tobias	Abgesehen von deinen LaTeX-Fehlern (Statt A* lieber A^\ast, Indizes bitte vollständig klammern: nicht x_k+1 sondern x_{k+1}) ist das, höflich gesprochen, nicht sehr ausgiebig formuliert. Ist der Text aus dem Buch abgeschrieben oder hast du nach eigenem Belieben gekürzt? Soweit ich es verstanden habe geht die Funktion hin und ersetzt einen Teilstring $[latex]\theta_j[/latex]$ durch den String $[latex]\Phi_j[/latex]$ , falls dieser vorhanden ist und ersetzt dann j zu b_j. Falls der String nicht gefunden wird, wird nichts ersetzt aber j durch a_j ersetzt. Für jedes j sind Strings und a_j, b_j definiert. Ziel ist es wohl, die Funktion mehrfach hintereinander auszuführen und irgendwann in einen Fixpunkt hineinzulaufen. Ist in deinem Buch irgendwas über den Sinn des Algorithmus erzählt? In welchem Kontext taucht er auf?
Surma	Verstaendnisproblem mit einem Beispielalgorithmus aus Knuth Moin. Ich lese gerade den ersten Band von Donald E. Knuth's "The Art of Computer Programming"-Reihe. Ich bin zwar gerade erst am Anfang, jedoch kann ich einen Beispielalgorithmus von ihm nicht nachvollziehen. Das ganze ist wie folgt definiert: Ein Algorithmus soll durch $[latex](Q,I,\Omega,f)[/latex]$ definiert werden koennen, wobei die Untermengen und $[latex]\Omega[/latex]$ enthaelt und $[latex]f: Q \rightarrow Q[/latex]$ gilt. $[latex]\Omega[/latex]$ sollen Fixpunkte von sein, es soll also gelten $[latex]f(\omega)=\omega\bigwedge_{\omega \in \Omega}[/latex]$ . $[latex](Q,I,\Omega,f)[/latex]$ repraesentieren dabei den Berechnungsstatus, den Input, den Output und die Berechnungsregel (i.d.Reihenfolge). Dabei soll fuer jedes gelten: und $[latex]x_{k+1}=f(x_k)[/latex]$ fuer $[latex]k \ge 0[/latex]$ Nun Knuth nach diesem System einen Beispielalgorithmus aufgestellt, der wie folgt definiert ist: Sei die Menger aller Buchstaben und $[latex]A^\ast[/latex]$ sei die Menger aller Strings aus , also alle mit $[latex]n \ge 1[/latex]$ und $[latex]x_j \in A[/latex]$ mit $[latex] 1 \le j \le n[/latex]$ . ist ein nicht-negativer Integer und ist die Menge aller $[latex](\sigma, j)[/latex]$ , wobei $[latex]\sigma \in A^\ast[/latex]$ und $[latex]0 \le j \le N[/latex]$ . soll jetzt die Untermenge von sein, bei der gilt, $[latex]\Omega[/latex]$ die mit . Wenn $[latex]\theta[/latex]$ und $[latex]\sigma[/latex]$ jetzt aus $[latex]A^\ast[/latex]$ sind, dann sagt man, $[latex]\theta[/latex]$ kommt in $[latex]\sigma[/latex]$ vor, wenn $[latex]\sigma[/latex]$ die Form $[latex]\alpha\theta\omega[/latex]$ hat, mit $[latex]\alpha[/latex]$ und $[latex]\omega[/latex]$ aus $[latex]A^\ast[/latex]$ . ist nun definiert mit den beiden Strings $[latex]\theta_j[/latex]$ , $[latex]\Phi_j[/latex]$ und den beiden Integern , mit $[latex]0 \le j \le N[/latex]$ als: $[latex]f\left((\sigma,j)\right)=(\sigma,a_j)[/latex]$ Wenn $[latex]\theta_j[/latex]$ nicht in $[latex]\sigma[/latex]$ auftaucht, $[latex]f\left((\sigma,j)\right)=(\alpha\Phi_j\omega,b_j)[/latex]$ Wenn $[latex]\alpha[/latex]$ der kuerzeste String ist, fuer den gilt $[latex]\sigma=\alpha\theta_j\omega[/latex]$ $[latex]f\left((\sigma,N)\right)=(\sigma,N)[/latex]$ Mein Problem ist, dass ich die Rolle von und nicht verstehe. Ihre Werte oder ihr Sinn werden nicht genannt und ich kann sie mir auch nicht denken. Und wo ist der Unterschied, ob ich jetzt $[latex]\sigma[/latex]$ erhalte, oder $[latex]\alpha\theta_j\omega[/latex]$ , denn Wertetechnisch ist das doch ein und das Selbe? Ich bitte euch, mir da ein wenig auf die Spruenge zu helfen. MfG Surma