Wie erfinde ich mathematische Algorithmen???

Wolfgang Windsteiger

RISC Linz

Universität Linz / Schloss Hagenberg

Wie beweise ich mathematische Algorithmen???

Ausgangslage

Lösung

Lösung 1

Show[
      Graphics[{PointSize[0.03], Line[{{3, 1}, {9, 2}}], Point[{3, 1}], 
          Point[{9, 2}]}], Axes -> True]

Lösung 2

g: (({{3}, {1}}))+ t·(({{6}, {1}}))

Lösung 3

g[x] := (x/6) + (1/2)

?

Wir sehen schon …

Gegeben … Gesucht …

Beispiel

“ g ist eine Gerade zwischen (({{(Subscript[x, 1])}, {(Subscript[y, 1])}})) und (({{(Subscript[x, 2])}, {(Subscript[y, 2])}})) ”

“ g ist lineares Polynom ”

“ Wert von g = ⟨(Subscript[p, 1]), 
          (Subscript[p, 2])⟩ an der Stelle a ”

Wert[⟨p1_, p2_⟩, a_] := 
      p1 + p2*a

Lösung

z.B. durch Probieren

g = ⟨(1/2), 
        (1/6)⟩

g = ⟨(1/2), (1/6)⟩;

weil:

Wert[g, 3]

Wert[g, 9]

Lösung eines konkreten Problems

ABER …

ALGORITHMEN

Lösung eines Problems

Wir suchen einen Algorithmus α, sodass α[x] eine Lösung des Problems ist, aber für alle x, d.h.

\(∀ \+x\ Ψ\_x\  => \ Φ\_\(x, α[x]\)\)

Eine Problemstellung P mit Eingaben x und Ausgaben y schreibe ich als (Subscript[P, x, y]) und meine damit:

(Subscript[Ψ, x])  =>  (Subscript[Φ, x, y])

Beispiel

Wir suchen einen Algorithmus “Gerade”, sodass Gerade[(Subscript[x, 1]), (Subscript[y, 1]), (Subscript[x, 2]), (Subscript[y, 2])] eine Lösung des Problems ist, d.h.

(Underscript[∀ , x]) (Subscript[x, 1]), (Subscript[y, 1]), (Subscript[x, 2]), 
    (Subscript[y, 2]) ∈ ℝ  =>  
        Wert[Gerade[(Subscript[x, 1]), (Subscript[y, 1]), (Subscript[x, 2]), (Subscript[y, 2])], (Subscript[x, 1])] = (Subscript[y, 1])  ∧ 
          Wert[Gerade[(Subscript[x, 1]), (Subscript[y, 1]), (Subscript[x, 2]), (Subscript[y, 2])], (Subscript[x, 2])] = 
        (Subscript[y, 2])

Obige Problemstellung P schreibe ich als \(TraditionalForm\`P\_\(⟨x\_1, y\_1, x\_2, y\_2⟩, ⟨p\_1, p\_2⟩\)\) und meine damit:

(Subscript[x, 1]), (Subscript[y, 1]), (Subscript[x, 2]), 
    (Subscript[y, 2]) ∈ ℝ  =>  
        Wert[⟨(Subscript[p, 1]), (Subscript[p, 2])⟩, 
          (Subscript[x, 1])] = (Subscript[y, 1])  ∧ 
          Wert[⟨(Subscript[p, 1]), (Subscript[p, 2])⟩, (Subscript[x, 2])] = 
        (Subscript[y, 2])

Wie löse ich ein Problem (Subscript[P, x, y]) ???

Rekursion

(Subscript[P, S[x],y]) => (Subscript[P, x,F[y]])                 α[x]:=F[α[S[x]]]

(Subscript[P, S[x],y]) => (Subscript[P, x,F[x, y]])                 α[x]:=F[x,α[S[x]]]                       \((\(⟶\)\(\ \)\(Potenzieren\))\)

(Subscript[P, x, y]) => (Subscript[P, C[x],F[y]])                 α[C[x]]:=F[α[x]]

(Subscript[P, (Subscript[x, 1]), (Subscript[y, 1])]) ∧  (Subscript[P, (Subscript[x, 2]), (Subscript[y, 2])]) => (Subscript[P, C[(Subscript[x, 1]), (Subscript[x, 2])],F[(Subscript[y, 1]), (Subscript[y, 2])]])                 α[C[(Subscript[x, 1]), (Subscript[x, 2])]]:=F[α[(Subscript[x, 1])], α[(Subscript[x, 2])]]           \((\(⟶\)\(\ \)\(Differenzieren\))\)

Potenzieren

Pot[a_, 0] := 1

Pot[a_, n_] := a*Pot[a, n - 1]

Pot[2, 16]

Neue Problemstellung: Evaluieren von Polynomen

Wert[p_, 
        a_] := (∑_(i = 1)^(Length[p]))p[[
            i]]*(a^(i - 1))

Wert[⟨3435, 34, -245, 4⟩, 
      3]

Wie finde ich einen Algorithmus ???

(Subscript[P, ⟨p, a⟩, W]) => (Subscript[P, ⟨C[p, (Subscript[p, 0])],a⟩,F[(Subscript[p, 0]), a, W]])                 α[C[p, (Subscript[p, 0])],a]:=F[(Subscript[p, 0]), a, α[p, a]]

Wert[p + q, a] = 
      Wert[p, a] + Wert[q, a]

Wert[⟨(Subscript[p, 0])⟩, a] = 
      (Subscript[p, 0])

Wert[Shift[p], a] := a*Wert[p, a]

\(Shift[⟨p\_1, p\_2, …, 
            p\_n⟩] + ⟨p\_0⟩ = ⟨p\_0, p\_1, p\_2, …, 
        p\_n⟩\)

Shift[⟨(Subscript[p, 1]), (Subscript[p, 2]), …, 
          (Subscript[p, n])⟩] := ⟨0, (Subscript[p, 1]), 
        (Subscript[p, 2]), …, (Subscript[p, n])⟩

Nehme an:

(Subscript[P, ⟨p, a⟩, W])

Wert[p, a] = W

Zu beweisen:

(Subscript[P, ⟨C[p, (Subscript[p, 0])],a⟩,F[(Subscript[p, 0]), a, W]])

Wert[C[p, (Subscript[p, 0])],a]\( = \&?\)F[(Subscript[p, 0]), a, W]

Wähle C:

C[p, (Subscript[p, 0])] := 
      Shift[p] + ⟨(Subscript[p, 0])⟩

dann

Wert[C[p, (Subscript[p, 0])],a]=Wert[Shift[p] + ⟨(Subscript[p, 0])⟩, 
          a]=\(\(\(Wert[Shift[p], a]\)\+⏟\)\+\(a*Wert[p, a]\) + \(\(Wert[⟨p\_0⟩, a]\)\+⏟\)\+\(p\_0\)\)=a*(Underscript[((Underscript[(Wert[p, a]), ⏟])), W]) + (Subscript[p, 0])=a*W + (Subscript[p, 0])\( = \&?\)F[(Subscript[p, 0]), a, W]

Wähle F:

F[(Subscript[p, 0]), a, W] := a*W + (Subscript[p, 0])

Lösungsalgorithmus:

α[C[p, (Subscript[p, 0])],a]:=F[(Subscript[p, 0]), a, α[p]]

Eval[Shift[p] + ⟨(Subscript[p, 0])⟩, a] := 
      a*Eval[p, a] + (Subscript[p, 0])

Clear[Eval]

Eval[⟨p0_, p__⟩, a_] := 
      a*Eval[⟨p⟩, a] + p0

Eval[⟨p0_⟩, a_] := p0

Eval[⟨3435, 34, -245, 4⟩, 
      3]

Neue Problemstellung

(Underscript[∀ , i = 1, …, n])Wert[⟨(Subscript[p, 1]), 
            (Subscript[p, 2]), (Subscript[p, 3]), …, (Subscript[p, n])⟩, (Subscript[x, i])] = 
      (Subscript[a, i])

(Underscript[∀ , i = 1, …, n])Wert[
          Interpol[⟨(Subscript[x, 1]), (Subscript[x, 2]), (Subscript[x, 3]), …, 
              (Subscript[x, n])⟩, ⟨(Subscript[a, 1]), (Subscript[a, 2]), 
              (Subscript[a, 3]), …, (Subscript[a, n])⟩], (Subscript[x, i])] = 
      (Subscript[a, i])

Probiere Rekursionsschema

\(P\_\(S\_1[⟨x, a⟩], y\_1\)\ \  ∧ \ \ P\_\(S\_2[⟨x, a⟩], y\_2\)\ \ \  => \ \ \ P\_\(⟨x, a⟩, F[⟨x, a⟩, y\_1, y\_2]\)\)

Interpol[x, a] := 
      F[x, Interpol[(Subscript[S, 1])[x, a]], Interpol[(Subscript[S, 2])[x, a]]]

mit

({{(Subscript[S, 1])[⟨x, a⟩]:=\(⟨x\_\(1 ⇥ ⬚\), 
              a\_\(1 ⇥ ⬚\)⟩\)}, {(Subscript[S, 2])[⟨x, a⟩]:=\(⟨x\_\(\(-1\) ⇥ ⬚\), 
              a\_\(\(-1\) ⇥ ⬚\)⟩\)}, {F[⟨x, a⟩, (Subscript[y, 1]), 
                (Subscript[y, 2])]:=((⟨-(Subscript[x, 1]), 1⟩*
                    (Subscript[y, 1]) - ⟨-(Subscript[x, -1]), 
                      1⟩*(Subscript[y, 2]))/((Subscript[x, -1]) - (Subscript[x, 1])))}})

\(P\_\(⟨⟨x\_1⟩, ⟨a\_1⟩⟩, ⟨a\_1⟩\)\ \ \ \ \ \ \((elementarer\ Fall)\)\)

\(P\_\(S\_1[⟨x, a⟩], y\_1\)\ \  ∧ \ \ P\_\(S\_2[⟨x, a⟩], y\_2\)\ \ \  => \ \ \ P\_\(⟨x, a⟩, F[⟨x, a⟩, y\_1, y\_2]\)\)

Der Algorithmus

Interpol[⟨x1_⟩, ⟨a1_⟩] := ⟨a1⟩

Interpol[x_, 
        a_] := (⟨-x[[1]], 1⟩*
              Interpol[Drop[x, 1], 
                Drop[a, 
                  1]] - ⟨-x[[-1]], 1⟩*
              Interpol[Drop[x, -1], 
                Drop[a, -1]])/(x[[-1]] - 
            x[[1]])

Hilfsprogramme: Polynom–Arithmetik

coef[p_, i_] /; Abs[i] < Length[p] := 
      p[[i + 1]]

coef[p_, i_] := 0

Clear[AngleBracket]

AngleBracket /: x_AngleBracket*y_AngleBracket := 
      AngleBracket @@ 
        Table[(∑_(j = 0)^i) coef[x, j]*coef[y, i - j], {i, 0, 
            Length[x] + Length[y] - 2}]

AngleBracket /: x_AngleBracket + y_AngleBracket := 
      AngleBracket @@ 
        Table[coef[x, i] + coef[y, i], {i, 0, 
            Max[Length[x], Length[y]] - 1}]

AngleBracket /: λ_?NumberQ* x_AngleBracket := 
      Map[λ*# &, x]

Beispiele

Interpol[⟨3, 
        9⟩, ⟨1, 
        2⟩]

x = AngleBracket @@ Table[i, {i, 1, 10}]

a = AngleBracket @@ Table[Random[Real, {0, 10}], {i, 1, 10}]

p = Interpol[x, a]

Plot[Eval[p, y], {y, 0, 11}, 
      Epilog -> {PointSize[0.02], RGBColor[0, 0, 1], 
          Map[Point, Transpose[{List @@ x, List @@ a}]]}]