simultane Polynomauswertung < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:07 Mo 24.10.2011 | | Autor: | julsch |
| Aufgabe | Sei f(x) ein Polynom vom Grad n-1, wobei n eine Zweierpotenz ist. Im Folgenden mod das Modulo auf dem Ring der Polynome von x. Wir setzen vorraus, dass man g(x) mod h(x) für beliebige Polynome des Grades höchstens n-1 in Zeit O(n log n) berechnen kann. Gegeben seien f(x) und n Stellen [mm] x_{0},...,x_{n-1}. [/mm] Zu berechnen ist [mm] f(x_{i}) [/mm] für i=0,...,n-1.
Für 0 [mm] \le [/mm] i [mm] \le [/mm] j [mm] \le [/mm] n-1 definieren wir [mm] p_{ij}(x)=\produkt_{m=i}^{j}(x-x_{m}) [/mm] und [mm] p_{ij}(x)=f(x) [/mm] mod [mm] p_{ij}(x).
[/mm]
(a) Zeigen Sie, dass f(x) mod (x-z) = f(z) für alle z.
(b) Zeigen Sie, dass [mm] q_{kk}(x)=f(X_{k}) [/mm] und [mm] q_{0,n-1}(x)=f(x) [/mm] mod [mm] p_{ij}(x).
[/mm]
(c) Zeigen Sie, dass für i [mm] \le [/mm] k [mm] \le [/mm] j gilt [mm] q_{ik}(x)=q_{ij}(x) [/mm] mod [mm] p_{ik}(x) [/mm] und [mm] q_{kj}(x)=q_{ij}(x) [/mm] mod [mm] p_{kj}(x).
[/mm]
(d) Konstruieren Sie einen Algorithmus, der in Zeit O(n [mm] log^{2} [/mm] n) die Werte [mm] f(x_{0}),...,f(x_{n-1}) [/mm] berechnet. Beweisen Sie Korrektheit und Laufzeit.
Hinweis: Realisieren Sie eine Divide-and-Conquer Strategie. Benutzen Sie (a)-(c). |
Hallo zusammen,
ich sitze grade über der Aufgabe, habe zu (a) nicht unbedingt viele Ideen, (b) und (c) hab ich glaub ich dafür Lösungen oder Lösungsansätze.
Zu (b) habe ich mir überlegt, dass
[mm] q_{kk}(x)=f(x) [/mm] mod [mm] p_{kk}(x) [/mm] = f(x) mod [mm] \produkt_{m=k}^{k}(x-x_{m})=f(x) mod(x-x_{k})=f(x_{k}) [/mm] nach (a)
bei dem zweiten bin ich mir nciht sicher, ob ich das so machen kann:
[mm] q_{0,n-1}(x)=f(x) [/mm] mod [mm] p_{0,n-1}(x) [/mm] = f(x) mod [mm] \produkt_{m=0}^{n-1}(x-x_{m}) [/mm] = 1*y
y ist nun gesucht. Aus der Zahlentheorie weiß ich, dass es eine lösung für y gibt, wenn [mm] ggT(1,\produkt_{m=0}^{n-1}(x-x_{m}))=1 [/mm] gilt.
Wir können somit y und z finden mit [mm] 1*y+\produkt_{m=0}^{n-1}(x-x_{m})*z=f(x).
[/mm]
Es gilt
[mm] ggT(1,\produkt_{m=0}^{n-1}(x-x_{m}))=1=0*\produkt_{m=0}^{n-1}(x-x_{m})+1*1
[/mm]
Multiplikation mit f(x) liefert
f(x) = [mm] 0*\produkt_{m=0}^{n-1}(x-x_{m})+f(x)*1
[/mm]
Somit ist y=f(x) und z=0 und die Behauptung gezeigt.
Kann man das so machen?
(c) war mit der Überlegung, dass [mm] p_{ik}(x) [/mm] eine Teiler von [mm] p_{ij}(x) [/mm] ist recht einfach zu lösen.
(d) hab ich leider gar keine Ahnung, weil ich nichts mit der Zeit anzufangen weiß, wäre schön, wenn mir jemand eine Erklärung dazu geben kann.
(a) hab ich mir nur überlegt, dass f(x)=l(x)*(x-z)+f(z) gelten muss, nur warum weiß ich leider nicht. Kann mir jemand einen Tipp geben?
Liebe Grüße
Julsch
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:06 Di 25.10.2011 | | Autor: | felixf |
Moin Julia!
> Sei f(x) ein Polynom vom Grad n-1, wobei n eine
> Zweierpotenz ist. Im Folgenden mod das Modulo auf dem Ring
> der Polynome von x. Wir setzen vorraus, dass man g(x) mod
> h(x) für beliebige Polynome des Grades höchstens n-1 in
> Zeit O(n log n) berechnen kann. Gegeben seien f(x) und n
> Stellen [mm]x_{0},...,x_{n-1}.[/mm] Zu berechnen ist [mm]f(x_{i})[/mm] für
> i=0,...,n-1.
> Für 0 [mm]\le[/mm] i [mm]\le[/mm] j [mm]\le[/mm] n-1 definieren wir
> [mm]p_{ij}(x)=\produkt_{m=i}^{j}(x-x_{m})[/mm] und [mm]p_{ij}(x)=f(x)[/mm]
> mod [mm]p_{ij}(x).[/mm]
Das letzte soll wohl [mm] $q_{ij}(x) [/mm] = f(x) [mm] \mod p_{ij}(x)$ [/mm] heissen, oder?
> (a) Zeigen Sie, dass f(x) mod (x-z) = f(z) für alle z.
> (b) Zeigen Sie, dass [mm]q_{kk}(x)=f(X_{k})[/mm] und
> [mm]q_{0,n-1}(x)=f(x)[/mm] mod [mm]p_{ij}(x).[/mm]
> (c) Zeigen Sie, dass für i [mm]\le[/mm] k [mm]\le[/mm] j gilt
> [mm]q_{ik}(x)=q_{ij}(x)[/mm] mod [mm]p_{ik}(x)[/mm] und [mm]q_{kj}(x)=q_{ij}(x)[/mm]
> mod [mm]p_{kj}(x).[/mm]
> (d) Konstruieren Sie einen Algorithmus, der in Zeit O(n
> [mm]log^{2}[/mm] n) die Werte [mm]f(x_{0}),...,f(x_{n-1})[/mm] berechnet.
> Beweisen Sie Korrektheit und Laufzeit.
>
> Hinweis: Realisieren Sie eine Divide-and-Conquer Strategie.
> Benutzen Sie (a)-(c).
> Hallo zusammen,
>
> ich sitze grade über der Aufgabe, habe zu (a) nicht
> unbedingt viele Ideen, (b) und (c) hab ich glaub ich dafür
> Lösungen oder Lösungsansätze.
Zu a): du kannst $f(x) = q(x) [mm] \cdot [/mm] (x - z) + r(x)$ schreiben mit $q(x), r(x)$ Polynomen mit [mm] $\deg [/mm] r(x) < [mm] \deg [/mm] (x - z) = 1$, d.h. $r(x)$ ist ein Element des Koerpers. Jetzt ist $r(x) = f(x) [mm] \mod [/mm] (x - z)$.
Setze in die Gleichung $f(x) = q(x) [mm] \cdot [/mm] (x - z) + r(x)$ mal $x = z$ ein.
> Zu (b) habe ich mir überlegt, dass
> [mm]q_{kk}(x)=f(x)[/mm] mod [mm]p_{kk}(x)[/mm] = f(x) mod
> [mm]\produkt_{m=k}^{k}(x-x_{m})=f(x) mod(x-x_{k})=f(x_{k})[/mm] nach
> (a)
![[ok]](/images/smileys/ok.gif "[ok]")
> bei dem zweiten bin ich mir nciht sicher, ob ich das so
> machen kann:
> [mm]q_{0,n-1}(x)=f(x)[/mm] mod [mm]p_{0,n-1}(x)[/mm] = f(x) mod
> [mm]\produkt_{m=0}^{n-1}(x-x_{m})[/mm] = 1*y
> y ist nun gesucht. Aus der Zahlentheorie weiß ich, dass
> es eine lösung für y gibt, wenn
> [mm]ggT(1,\produkt_{m=0}^{n-1}(x-x_{m}))=1[/mm] gilt.
> Wir können somit y und z finden mit
> [mm]1*y+\produkt_{m=0}^{n-1}(x-x_{m})*z=f(x).[/mm]
Das liest sich sehr abenteuerlich. Ich glaube nicht, dass du das so machen kannst.
> Es gilt
>
> [mm]ggT(1,\produkt_{m=0}^{n-1}(x-x_{m}))=1=0*\produkt_{m=0}^{n-1}(x-x_{m})+1*1[/mm]
> Multiplikation mit f(x) liefert
> f(x) = [mm]0*\produkt_{m=0}^{n-1}(x-x_{m})+f(x)*1[/mm]
> Somit ist y=f(x) und z=0 und die Behauptung gezeigt.
> Kann man das so machen?
Geh doch wie folgt vor: du hast [mm] $q_{0,n-1} \equiv [/mm] f [mm] \pmod{p_{0,n-1}}$. [/mm] Zeige, dass [mm] $p_{ij}$ [/mm] ein Teiler von [mm] $p_{0,n-1}$ [/mm] ist: dann gilt doch auch [mm] $q_{0,n-1} \equiv [/mm] f [mm] \pmod{p_{ij}}$.
[/mm]
> (c) war mit der Überlegung, dass [mm]p_{ik}(x)[/mm] eine Teiler von
> [mm]p_{ij}(x)[/mm] ist recht einfach zu lösen.
> (d) hab ich leider gar keine Ahnung, weil ich nichts mit
> der Zeit anzufangen weiß, wäre schön, wenn mir jemand
> eine Erklärung dazu geben kann.
Berechne doch erstmal $f(x)$ modulo [mm] $p_{0,n/2-1}$ [/mm] und dann modulo [mm] $p_{n/2,n-1}$. [/mm] Dann hat der erste Rest alle Informationen ueber die Werte von $f$ bei [mm] $x_0, \dots, x_{n/2-1}$, [/mm] und der zweite Rest alle Informationen ueber die Werte von $f$ bei [mm] $x_{n/2}, \dots, x_{n-1}$.
[/mm]
Dann mach rekursiv weiter mit beiden Resten.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 19:18 Di 25.10.2011 | | Autor: | julsch |
Hallo Felix,
was bringt es mir bei der (b) zu zeigen, dass [mm] p_{ij} [/mm] ein Teiler von [mm] p_{0,n-1}? [/mm] Ich muss ja irgendwie zeigen, dass [mm] q_{0,n-1}=f(x) [/mm] ist, also dass f(x) mod [mm] p_{0,n-1} [/mm] = f(x) gilt. Ich versteh den Zusammenhang noch nicht so ganz.
(d) versuch ich mal so, nur was sagt mir die Zeit allgemein? Darf ich nicht mehr als (n [mm] log^{2} [/mm] n) Schritte benutzen für den Algorithmus? Wie genau zeige ich Korrektheit bzw. auch Laufzeit hinterher?
Liebe Grüße und danke für die Hilfe,
Julia
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:20 Mi 26.10.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:37 Mi 26.10.2011 | | Autor: | felixf |
Hallo Julia
> was bringt es mir bei der (b) zu zeigen, dass [mm]p_{ij}[/mm] ein
> Teiler von [mm]p_{0,n-1}?[/mm] Ich muss ja irgendwie zeigen, dass
> [mm]q_{0,n-1}=f(x)[/mm] ist, also dass f(x) mod [mm]p_{0,n-1}[/mm] = f(x)
> gilt. Ich versteh den Zusammenhang noch nicht so ganz.
Hmm, die Frage ist, was eure Notation $a = b [mm] \mod [/mm] c$ ueberhaupt heisst. Wenn es bedeutet, $a$ ist gleich dem Rest von $b$ bei Division durch $c$, dann ist die Aussage [mm] $q_{0,n-1} [/mm] = f(x) [mm] \mod p_{ij}$ [/mm] eigentlich nur fuer $i = 0$ und $j = n-1$ richtig.
Wenn $a = b [mm] \mod [/mm] c$ jedoch bedeutet, dass $a$ und $b$ bei Division durch $c$ den gleichen Rest haben, sprich dass $b - a$ durch $c$ teilbar ist (eigentlich schreibt man dann $a [mm] \equiv [/mm] b [mm] \pmod{c}$), [/mm] dann stimmt die Aussage: es gilt [mm] $q_{0,n-1} \equiv [/mm] f(x) [mm] \pmod{p_{0,n-1}}$, [/mm] und wegen [mm] $p_{ij} \mid p_{0,n-1}$ [/mm] folgt auch [mm] $q_{0,n-1} \equiv [/mm] f(x) [mm] \pmod{p_{ij}}$.
[/mm]
> (d) versuch ich mal so, nur was sagt mir die Zeit
> allgemein? Darf ich nicht mehr als (n [mm]log^{2}[/mm] n) Schritte
> benutzen für den Algorithmus? Wie genau zeige ich
Du darfst auch ein konstantes Vielfaches von $n [mm] \log^2 [/mm] n$ Schritten brauchen, so als Oberschranke.
> Korrektheit bzw. auch Laufzeit hinterher?
Dazu brauchst du die Aussagen (a)-(c)  Wie genau das geht haengt von deinem Algorithmus ab.
Du hast $n = [mm] 2^t$ [/mm] Stellen [mm] $x_1, \dots, x_{n-1}$, [/mm] und du willst $f$ an all diesen Stellen auswerten. In der Aufgabenstellung steht etwas von Divide-and-Conquer-Strategie, also wird wohl gemeint sein, dass du den Algorithmus rekursiv machen sollst, dass du ihn also auf [mm] $x_1, \dots, x_{n/2-1}$ [/mm] und dann auf [mm] $x_{n/2}, \dots, x_{n-1}$ [/mm] anwendest. Dazu muss $f$ jeweils auch einen kleinen Grad haben, was du mit (a)-(c) jedoch hinbekommen kannst.
Du musst dir jetzt ueberlegen, wie genau du vorgehst. Probier es doch evtl. mal im Fall $n = 4$ aus.
LG Felix
|
|
|
|
