Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 2 von 2 Treffern

Autor

Beitrag

Thema: Verstaendnisproblem mit einem Beispielalgorithmus aus Knuth

Surma

Antworten:	2
Hits:	5.618

15.11.2007 17:18

Forum: Theoretische Informatik

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

Thema: Verstaendnisproblem mit einem Beispielalgorithmus aus Knuth

Surma

Antworten:	2
Hits:	5.618

Verstaendnisproblem mit einem Beispielalgorithmus aus Knuth 15.11.2007 11:24

Forum: Theoretische Informatik

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 [latex]Q[/latex]

die Untermengen [latex]I[/latex]

und $[latex]\Omega[/latex]$ enthaelt und $[latex]f: Q \rightarrow Q[/latex]$ gilt. $[latex]\Omega[/latex]$ sollen Fixpunkte von [latex]f[/latex]

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 [latex]x[/latex]

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 [latex]A[/latex]

die Menger aller Buchstaben und $[latex]A^\ast[/latex]$ sei die Menger aller Strings aus [latex]A[/latex]

, also alle [latex]x_1x_2x_3...x_n[/latex]

mit $[latex]n \ge 1[/latex]$ und $[latex]x_j \in A[/latex]$ mit $[latex] 1 \le j \le n[/latex]$ . [latex]N[/latex]

ist ein nicht-negativer Integer und [latex]Q[/latex]

ist die Menge aller $[latex](\sigma, j)[/latex]$ , wobei $[latex]\sigma \in A^\ast[/latex]$ und $[latex]0 \le j \le N[/latex]$ . [latex]I[/latex]

soll jetzt die Untermenge von [latex]Q[/latex]

sein, bei der [latex]j=0[/latex]

gilt, $[latex]\Omega[/latex]$ die mit [latex]j=N[/latex]

.
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]$ .
[latex]f[/latex]

ist nun definiert mit den beiden Strings $[latex]\theta_j[/latex]$ , $[latex]\Phi_j[/latex]$ und den beiden Integern [latex]a_j[/latex]

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 [latex]a_j[/latex]

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

Zeige Beiträge 1 bis 2 von 2 Treffern