\input slidemac.tex

\language=\czech
\chyph

\slide{Strassenùv algoritmus: vzorce}

\def\\{\noalign{\vskip 7pt}}

$$
\pmatrix{A & B \cr\\ C & D \cr}
\cdot
\pmatrix{P & Q \cr\\ R & S \cr}
=
\pmatrix{
T_1 + T_4 - T_5 + T_7 &
T_3 + T_5 \cr\\
T_2 + T_4 &
T_1 - T_2 + T_3 + T_6 \cr
},$$

kde:

$$\vbox{\halign{$#$\hfil\qquad &$#$\hfil\qquad \cr
T_1 = (A+D)\cdot(P+S)		& T_5 = (A+B)\cdot S \cr\\
T_2 = (C+D)\cdot P		& T_6 = (C-A)\cdot (P+Q) \cr\\
T_3 = A\cdot(Q-S)		& T_7 = (B-D)\cdot (R+S) \cr\\
T_4 = D\cdot(R-P)					 \cr
}}$$

\medskip

7 násobení místo 8 $\Rightarrow$ èasová slo¾itost $\O(n^{\log_2 7}) = \O(n^{2.808})$.

\medskip

[Zatím nejlep¹í výsledek: $\O(n^{2.376})$ \uv{s~opravdu velkým~$\O$.}]

\endslide

\slide{Strassenùv algoritmus: dùkaz}

\def\bbb#1{\vbox to 10pt{\vss\hbox to 10pt{\hss\tenrm #1\hss}\vss}}
\def\bb#1{\ifx#1.\bbb{$\cdot$}\else\bbb#1\fi}
\def\zz#1#2#3#4{\bb#1\bb#2\bb#3\bb#4}
\def\qq#1#2#3#4{{\offinterlineskip\vcenter{\halign{\vrule ##\vrule \cr\noalign{\hrule}\zz#1\cr\zz#2\cr\zz#3\cr\zz#4\cr\noalign{\hrule}}}}}

$$
T_1 = \qq{+..+}{....}{....}{+..+} \qquad
T_2 = \qq{....}{....}{+...}{+...} \qquad
T_3 = \qq{.+.-}{....}{....}{....} \qquad
T_4 = \qq{....}{....}{....}{-.+.}
$$
$$
T_5 = \qq{...+}{...+}{....}{....} \qquad
T_6 = \qq{--..}{....}{++..}{....} \qquad
T_7 = \qq{....}{..++}{....}{..--}
$$

\medskip

\def\\{\noalign{\vskip 7pt}}
$$
\eqalign{
T_1 + T_4 - T_5 + T_7 &= \qq{+...}{..+.}{....}{....} = AP + BR \cr\\
T_3 + T_5 &= \qq{.+..}{...+}{....}{....} = AQ + BS \cr\\
T_2 + T_4 &= \qq{....}{....}{+...}{..+.} = CP + DR \cr\\
T_1 - T_2 + T_3 + T_6 &= \qq{....}{....}{.+..}{...+} = CQ + DS \cr
}
$$

\endslide

\end
