slides/growth.tex

   1 \input slidemac.tex
   2 \input epsf.tex
   3
   4 \language=\czech
   5 \chyph
   6
   7 \slide{Srovnání rychlostí algoritmù (pøedpokládáme $10^9$ operací za sekundu)}
   8
   9 \def\[#1]{\,\hbox{#1}}
  10 $$\vbox{
  11 \halign{$#$ \hfil&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$\cr
  12 \hbox{funkce / $n=$\hskip-2em}& 10              & 20            & 30            & 50            & 100           & 1\,000        & 1\,000\,000 \cr
  13 \noalign{\medskip\hrule\bigskip}
  14 \log_2 n        & 3.3\[ns]      & 4.3\[ns]      & 4.9\[ns]      & 5.6\[ns]      & 6.6\[ns]      & 10.0\[ns]     & 19.9\[ns]     \cr
  15 n               & 10\[ns]       & 20\[ns]       & 30\[ns]       & 50\[ns]       & 100\[ns]      & 1\[$\mu$s]    & 1\[ms]        \cr
  16 n\cdot\log_2 n\hskip-1em        & 33\[ns]       & 86\[ns]       & 147\[ns]      & 282\[ns]      & 664\[ns]      & 10\[$\mu$s]   & 20\[ms]       \cr
  17 n^2             & 100\[ns]      & 400\[ns]      & 900\[ns]      & 2.5\[$\mu$s]  & 100\[$\mu$s]  & 1\[ms]        & 1\,000\[s]    \cr
  18 n^3             & 1\[$\mu$s]    & 8\[$\mu$s]    & 27\[$\mu$s]   & 125\[$\mu$s]  & 1\[ms]        & 1\[s]         & 10^9\[s]      \cr
  19 2^n             & 1\[$\mu$s]    & 1\[ms]        & 1\[s]         & 10^6\[s]      & 10^{21}\[s]   & 10^{292}\[s]  & \approx\infty \cr
  20 n!              & 10^6\[s]      & 10^{18}\[s]   & 10^{32}\[s]   & 10^{64}\[s]   & 10^{158}\[s]  & 10^{2567}\[s] & \approx\infty \cr
  21 }}$$
  22
  23 \bigskip
  24
  25 \halign{#\hfil&\quad #\hfil\cr
  26 Pro pøedstavu:  &$1\,000\[s]$ je asi tak ètvrt hodiny\cr
  27                 &$1\,000\,000\[s]$ je necelých 12 dní\cr
  28                 &$10^9\[s]$ je 31 let\cr
  29                 &$10^{18}\[s]$ je asi tak stáøí Vesmíru. \cr}
  30
  31 \endslide
  32
  33 \slide{Poèítaèe se nám zrychlují aneb Mooreùv zákon}
  34
  35 \bigskip
  36
  37 \uv{Ka¾dé dva roky se výkon poèítaèù zdvojnásobí} -- Gordon Moore (prý)
  38
  39 \bigskip
  40 \bigskip
  41
  42 \qquad \dots\ Není tedy lep¹í chvíli poèkat ne¾ vymý¹let lep¹í algoritmus? :-)
  43
  44 \bigskip
  45 \bigskip
  46
  47 $$\vbox{\halign{\hfil$#$\quad&\hfil$#$\quad&\hfil$#$\qquad&#\hfil\cr
  48 \hbox{funkce} & 10^6\;\hbox{op.} & 2\cdot10^6\;\hbox{op.} & zmìna \cr
  49 \noalign{\medskip\hrule\bigskip}
  50 n       &1\,000\,000    &2\,000\,000    &2-krát více            \cr
  51 n^2     &1\,000         &1\,414         &$\sqrt{2}\approx 1.41$-krát více       \cr
  52 n^3     &100            &126            &$\root3\of2\approx 1.26$-krát více     \cr
  53 2^n     &20             &21             &o 1 více       \cr
  54 }}$$
  55
  56 \endslide
  57
  58 \slide{Asymptotický rùst funkcí}
  59
  60 \centerline{\epsfxsize=0.85\hsize\epsfbox{funcs.eps}}
  61
  62 \endslide
  63
  64 \slide{Asymptotický rùst funkcí: èleny ni¾¹ích øádù se schovají do konstant}
  65
  66 \centerline{\epsfxsize=0.85\hsize\epsfbox{funcs2.eps}}
  67
  68 \endslide
  69
  70 \end