From ec11a19cdd41fc7f969be44f6ac641bb95e2f52b Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 26 Feb 2007 12:51:54 +0100
Subject: [PATCH] Strassen.

---
 slides/Makefile     |  2 +-
 slides/slidemac.tex |  1 +
 slides/strassen.tex | 74 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 76 insertions(+), 1 deletion(-)
 create mode 100644 slides/strassen.tex

diff --git a/slides/Makefile b/slides/Makefile
index da9464a..d1c23ea 100644
--- a/slides/Makefile
+++ b/slides/Makefile
@@ -1,4 +1,4 @@
-all: growth.ps
+all: strassen.ps
 
 %.dvi: %.tex slidemac.tex
 	csplain $<
diff --git a/slides/slidemac.tex b/slides/slidemac.tex
index 3948e56..cbab061 100644
--- a/slides/slidemac.tex
+++ b/slides/slidemac.tex
@@ -68,3 +68,4 @@
 \def\:{\par\leavevmode\llap{$\bullet$\hskip 7pt}}
 \def\>{\par\leavevmode\llap{$\circ$\hskip 7pt}}
 \def\bbold{\bbfont\fam\bbfam}
+\def\O{{\cal O}}
diff --git a/slides/strassen.tex b/slides/strassen.tex
new file mode 100644
index 0000000..5902983
--- /dev/null
+++ b/slides/strassen.tex
@@ -0,0 +1,74 @@
+\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
-- 
2.39.2