03. Алгоритмы.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline\n",
    "import seaborn as sns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Алгоритмы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## План лекции\n",
    "1. Алгоритм как совокупность операций\n",
    "1. Массивы\n",
    "1. Случайные числа"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Итеративный алгоритм\n",
    "\n",
    "- операция повторяется многократно\n",
    "- условие прекращения \n",
    "\n",
    "Вложенные итерации увеличивают число операций кратно."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Жадный алгоритм\n",
    "\n",
    "перебор всех вариантов по очереди от начала до конца.\n",
    "\n",
    "<b class=tag>Greedy algorythm</b>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Условия начала и конца\n",
    "\n",
    "Вариант - очередь в реальном времени:\n",
    "- заканчиваются данные, но потом снова появляются.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Потоки данных: входящий и выходящий\n",
    "вход и выход\n",
    "труба к трубе (pipeline)\n",
    "\n",
    "<b class=tag>конвеер</b>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## FIFO, LIFO\n",
    "\n",
    "![](fifolifo.png)\n",
    "\n",
    "труба, стопка"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Конечный массив\n",
    "\n",
    "есть начало, конец, размер."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Виды массивов в Python\n",
    "- list\n",
    "- numpy.array\n",
    "- pandas.DataFrame, pandas.Series"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "список - последовательность любых объектов, к которым можно обращаться перебором по-одному.\n",
    "\n",
    "массив - N-мерный с однотипными объектами\n",
    "\n",
    "табличка с данными: по строкам - отдельные наблюдения, по колонкам - характеристики.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Линейная алгебра (ЛА)\n",
    "\n",
    "*Матрица* $A_{m,n}$ - набор чисел в ячейках размером $m$ на $n$\n",
    "\n",
    "Если $m==1$ или $n==1$, то такая матрица называется *вектор*.\n",
    "\n",
    "Если $m==1$ **и** $n==1$, то такая матрица называется *скаляр* (скалярная величина, обычное единичное число).\n",
    "\n",
    "Специальная операция - cкалярное произведение (перемножение матриц, dot-product)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Причины, почему этот раздел включен в курс для биологов:\n",
    "- использование эффективных библиотек для матричных вычислений\n",
    "- понимание обсуждения алгоритмов в среде математиков;\n",
    "- расширение кругозора"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Математические условности\n",
    "\n",
    "Переменные (вектора):  $x, y, z$ или $a, b, c, d$ или  $v,u$\n",
    "\n",
    "Переменные (Матрицы):  $A,B$ или $U,V$ или $M$ или $X, Y, Z$ \n",
    "\n",
    "Размеры:  $n$, если две - $n,m$\n",
    "\n",
    "Порядковые номера:  $i, j, k$  -  i-th, k-th [итый, житый, катый]\n",
    "\n",
    "Углы: $\\theta, \\varphi, \\alpha, \\beta$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Маленькая-маленькая пороговая величина: $\\varepsilon$ (эпсилон)\n",
    "\n",
    "Коэффицинты:  $k, а$, например, $k_i a_{ij}$\n",
    "\n",
    "Функции:  $f, \\gamma$\n",
    "\n",
    "Моменты распределения:  $\\mu, \\sigma, ...$\n",
    "\n",
    "$\\Game \\Box   \\varPhi \\varPsi  \n",
    "\\varpi\n",
    "\\varPi \\varXi $\n",
    "$$ \\heartsuit  $$\n",
    "$\\Box \\maltese \\Box \\left(\\left(\\left( \\bigodot \\right)\\right)\\right) \\Box\\maltese\\Box$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Геометрическая интерпретация\n",
    "\n",
    "Вектор (строчка матрицы) - это координаты конца стрелочки (arrow head), если начало вектора (хвостик, tail) при этом в нулевой точке. Но, если сместить вектор в пространстве, не меняя направления, то это тот же вектор, значит числа отражают разницу между концом и началом вдоль осей координат.\n",
    "\n",
    "Размер вектора ( длина, расстояние между началом и концом) вычисляют по теореме Пифагора (для 2-мерного пространства L2-norm)\n",
    "\n",
    "$$ L = |X|_p = \\left(\\sum{x_i^p}\\right)^{1/p}, p=2$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "a=array([.5,4,5,6])\n",
    "norm(a,2), sqrt(3**2 + 4**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Матрицы можно только умножать.\n",
    "Вместо деления - инверсия.\n",
    "\n",
    "$$\\frac{B}{A} = A^{-1}B $$\n",
    "\n",
    "```py\n",
    "dot(inv(A), B)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "inv(array([[10,0], [ 0, 4]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Умножение на диагональную матрицу - растяжение (stretching, scaling)\n",
    "\n",
    "Умножение на ортонормальную (unitary) матрицу - вращение (rotating)\n",
    "\n",
    "SVD-разложение: $U, \\Sigma, V$ - вращение, растяжение, вращение\n",
    "\n",
    "- для обратного вращения - транспонированная матрица вращения $U^T$\n",
    "\n",
    "- для обратного растяжения - инвертированная матрица весов $\\Sigma^{-1}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$X$ - матрица размером $N$ x $K$: $N$ наблюдений и $K$ признаков (dimensions).\n",
    "\n",
    "$X$ может быть разложена на:\n",
    "\n",
    "$U\\Sigma V^T = \\frac {1} {\\sqrt{N-1}}X$, где $V^T$ и $U$ - матрицы вращения, а $\\Sigma$ - растяжения.\n",
    "\n",
    "$C_X = \\frac{1}{N-1}X^TX = R C_Y R^T = R \\Sigma^2 R$ (ковариционная матрица)\n",
    "\n",
    "$M_X = \\frac{1}{N-1}XX^T = U \\Sigma^2 U^T$ (корреляционная матрица)\n",
    "\n",
    "где R - сингулярные векторы (eigenvectors, principal components), диагональные значения $C_Y$ определяют количество вариации, содержащейся в каждом компоненте."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$R=V=\\frac{1}{\\sqrt{N-1}} X^T U \\Sigma^{-1}$\n",
    "\n",
    "<img src='PCA_steps.png' width=600>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**3 способа выделения главных компонент (PCA)**\n",
    "\n",
    "- SVD исходной матрицы $X$\n",
    "- сингулярное разложение (eigenvalue decomposition) ковариционной матрицы $C_X$\n",
    "- сингулярное разложение корреляционной матрицы $M_X$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Косинусное расстояние\n",
    "\n",
    "Между  двумя  векторами  образуется  угол  и \n",
    "значение  косинуса  этого  угла  –  это \n",
    "нормализованное  скалярное  произведение: \n",
    "\n",
    "$$cos(\\theta)=\\frac{a*b}{||a|| ||b||}=\\frac{\\sum_{i=1}^n a_i * b_i}{\\sqrt{\\sum_{i=1}^n a_i^2} * \\sqrt{\\sum_{i=1}^n a_i^2}} $$\n",
    "\n",
    "<!--![](cos_formula.png)-->\n",
    "\n",
    "правую часть можно реализовать через циклы,\n",
    "левую - через векторные операции."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<img src=cosine.png width=90%>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1 = array([0,0,1,1,1]);\n",
    "a2 = array([1,0,0,1,1]);\n",
    "dot(a1,a2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Согласование размерностей\n",
    "\n",
    "![](numpy_broadcasting.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Согласование размерностей\n",
    "\n",
    "<img src=\"http://www.astroml.org/_images/fig_broadcast_visual_1.png\">\n",
    "\n",
    "([image source](http://www.astroml.org/book_figures/appendix/fig_broadcast_visual.html))\n",
    "\n",
    "**Broadcasting rules:**\n",
    "\n",
    "1. If the two arrays differ in their number of dimensions, the shape of the array with fewer dimensions is *padded* with ones on its leading (left) side.\n",
    "\n",
    "2. If the shape of the two arrays does not match in any dimension, the array with shape equal to 1 in that dimension is *stretched* to match the other shape.\n",
    "\n",
    "3. If in any dimension the sizes disagree and neither is equal to 1, an error is raised."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Интервалы\n",
    "\n",
    "- открытые\n",
    "- закрытые\n",
    "- полуоткрытые\n",
    "\n",
    "полуоткрытые используются при индексации массивов в Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Индексация массивов полуоткрытая\n",
    "\n",
    "- по-умолчанию от 0\n",
    "- разность конца и начала = размеру подмассива\n",
    "- логичное определение пустых интервалов `v[0:0]`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Визуализация матриц - изображение\n",
    "\n",
    "Двоичные операции с массивами (bitwise)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAEKdJREFUeJzt3V+MXHd5xvHvgxwnJJGiFK8TR6oxjQIELkqcTfjXiqAGRKxWIlJQpVaCJGotbnKBKCCZqIqiSgiJPyo3UQ1CIYrKBU6RiAoUO7LTIBTDJi2Rm9gxIY64qMmmgotAHBT57cWeNMN2dvfs7lnP2L/vRxrtnJl3Zx4fn3125syc2VQVkqRz3+smHUCSdGZY+JLUCAtfkhph4UtSIyx8SWqEhS9JjVhV4Sf5VJIjS1y3K8mRJMeS7BkmniRpKL0LP8l7gb9a4rqLgHuAG4G3Azcl2TlIQknSIHoVfpItwJeBjy8xcj3weFWdrKpXgH3ArmEiSpKGsGmlgSQBvgF8GvjlEmNXAM+PLM8DVy1xe7uB3d3itb2TSpIAXqiqmbV8Y59H+J8AflRVh1aYO71oefO4oaraW1WzVTXb474lSb/vubV+Y5/CfxPw0SRHgYeAq5I8smjmJLBlZHmmu0ySNCVWLPyquqOq3lJVbwX+DDheVX+a5JIk27uxw8B1SbYm2QTcwsIvB0nSlFjP+/BvBu4DqKoXgTuAg8CTwP6qenj98SRJQ8kkPx45iZ/NLEmr89haXwP1SFtJaoSFL0mNsPAlqREWviQ1wsKXpEZY+JLUCAtfkhph4UtSIyx8SWqEhS9JjbDwJakRFr4kNcLCl6RGWPiS1AgLX5IaYeFLUiMsfElqhIUvSY3oVfhJ7k9yvDs9kOSiMTOHkpxIcrQ73Tl8XEnSWvV9hH8v8Oaqugp4GfjIEnO3VNVbu9M/DBFQkjSMTX2GquoAQPfIfgZ4aiNDSZKG13sffpLbgZPAT4EfjxkpYF+SY0m+kqTXLxNJ0pnRu/Cr6uvApcBW4GNjRm6qqh3ANcA2YPe420myO8lckrnVx5UkrdWq3qVTVa8AB4DZMded6r7+FngQuHqJ29hbVbNV9f9uQ5K0cVYs/CSXJvlAd/484MPAXJJLkmzvLr8gyQ0jMzcDj25YaknSqvV5hB9gT5ITwJPACeA+Fkr9vpGZu5M8CxwBngG+OXRYSdLapaomd+fJ5O5cks5Oj611l7hH2kpSIyx8SWqEhS9JjbDwJakRFr4kNcLCl6RGWPiS1AgLX5IaYeFLUiMsfElqhIUvSY2w8CWpERa+JDXCwpekRlj4ktQIC1+SGmHhS1IjLHxJaoSFL0mN6FX4Se5Pcrw7PZDkojEzu5IcSXIsyZ7ho0qS1qPvI/x7gTdX1VXAy8BHRq/sfgHcA9wIvB24KcnOAXNKktapV+FX1YGqqq7YZ4CnFo1cDzxeVSer6hVgH7Br2KiSpPXY1Hcwye3APwL/BPx40dVXAM+PLM8DVy1xO7uB3QDbt2/nueeeW01eLSHJpCOcM6pq0hHOKW6b06P3i7ZV9XXgUmAr8LExI6cXLW9e4nb2VtVsVc3OzMz0DipJWp9VvUun211zAJhddNVJYMvI8kx3mSRpSqxY+EkuTfKB7vx5wIeBuSSXJNnejR0GrkuyNckm4BbgoY0KLUlavT6P8APsSXICeBI4AdwH3Nx9papeBO4ADnYz+6vq4Q3IK0lao0zyBarZ2dmam5ub2P2fS3xhbDi+aDsst83BPVZVi3er9+KRtpLUCAtfkhph4UtSIyx8SWqEhS9JjbDwJakRFr4kNcLCl6RGWPiS1AgLX5IaYeFLUiMsfElqhIUvSY2w8CWpERa+JDXCwpekRlj4ktQIC1+SGtHnj5hfkORAkmeSPJ1kzxJzJ5IcT3K0O902fFxJ0lpt6jn3+aran+T1wKNJvltV/zlm7t1V9cKA+SRJA1nxEX5Vnaqq/d35l4CfAZdtdDBJ0rBWtQ8/yWXAu4DDY64+DRxO8lSSO5e5jd1J5pLMzc/Pry6tJGnNehd+kvOBbwGfrapfjxl5W1VdCbwH+FCSXeNup6r2VtVsVc3OzMysKbQkafV6FX6SzcADwPeq6t5xM1V1qvv6K+AHwNUDZZQkDaDPu3QuBB4EHqmqz41cviXJtu781iTXdOcvBnYxfrePJGlC+rxL53rgBuCNI2+1/DbwMrADuBU4H9ib5A3A74CvVdUPhw4rSVq7FQu/qg6xUOjLzfwCuG6gTJKkDeCRtpLUCAtfkhph4UtSIyx8SWqEhS9JjbDwJakRFr4kNcLCl6RGWPiS1AgLX5IaYeFLUiMsfElqhIUvSY2w8CWpERa+JDXCwpekRlj4ktQIC1+SGtHnj5hfkORAkmeSPJ1kzxJztyd5qjvdNm5GkjQ5fR/hf76qrgT+GPjLJO8YvTLJDuAzwCwLf9v200m2DphTkrROKxZ+VZ2qqv3d+ZeAnwGXLRp7P/DdqvpNVb0IfB/44NBhJUlrt6p9+EkuA94FHF501RXA8yPL88DlS9zG7iRzSebm5+dXc/eSpHXoXfhJzge+BXy2qn49ZuT0ouXN426nqvZW1WxVzc7MzPRPKklal16Fn2Qz8ADwvaq6d8zISWDLyPJMd5kkaUr0eZfOhcCDwCNV9bmRy7ck2dYtHgT+PMmFSS4GbuoukyRNiU09Zq4HbgDeOPJ2y28DLwM7gFur6udJvgQ8BgT4QlU9O3xcSdJarVj4VXUIOL/H3FeBrw6QSZK0ATzSVpIaYeFLUiMsfElqhIUvSY2w8CWpERa+JDXCwpekRlj4ktQIC1+SGmHhS1IjLHxJaoSFL0mNsPAlqREWviQ1wsKXpEZY+JLUCAtfkhph4UtSI3oXfpKdSZ5Y5vpDSU4kOdqd7hwmoiRpCH3+iDlJvgjcCvz3CqO3VNXcekNJkobX6xF+VX0SuHaDs0iSNtCQ+/AL2JfkWJKvJBn77CHJ7iRzSebm5+cHvHtJ0nKGLPybqmoHcA2wDdg9bqiq9lbVbFXNzszMDHj3kqTlDFb4VXWq+/pb4EHg6qFuW5K0fmsu/CSXJNnenb8gyQ3d+fOAm4FHB0koSRpEr8JPcjfwHeDKbv/7+1go9fteHQHuTvIscAR4BvjmBuSVJK1Rqmpidz47O1tzc76LcwhJJh3hnDHJn4lzkdvm4B6rqtm1fKNH2kpSIyx8SWqEhS9JjbDwJakRFr4kNcLCl6RGWPiS1AgLX5IaYeFLUiMsfElqhIUvSY2w8CWpERa+JDXCwpekRlj4ktQIC1+SGmHhS1IjLHxJakTvwk+yM8kTy1y/K8mRJMeS7BkmniRpKH3/iPkXgf1LzSe5CLgHuBF4O3BTkp1DhZQkrV+vwq+qTwLXLjNyPfB4VZ2sqleAfcCuAfJJkgYy1D78K4DnR5bngcvHDSbZnWQuydz8/PxAdy9JWsmQL9qeXrS8edxQVe2tqtmqmp2ZmRnw7iVJyxmq8E8CW0aWZ7rLJElTYs2Fn+SSJNu7xcPAdUm2JtkE3AI8NERASdIw+r5L527gO8CV3f739wE3A/cBVNWLwB3AQeBJYH9VPbwxkSVJa5Gqmtidz87O1tzc3MTu/1ySZNIRzhmT/Jk4F7ltDu6xqppdyzd6pK0kNcLCl6RGWPiS1AgLX5IaYeFLUiMsfElqhIUvSY2w8CWpERa+JDXCwpekRlj4ktQIC1+SGmHhS1IjLHxJaoSFL0mNsPAlqREWviQ1wsKXpEb0/Zu2u5IcSXIsyZ4lZk4kOZ7kaHe6bdiokqT12LTSQJKLgHuAdwIvAAeTfL+qHh8z/u6qemHgjJKkAfR5hH898HhVnayqV4B9wK6NjSVJGlqfwr8CeH5keR64fMzcaeBwkqeS3DlEOEnScPq+aHt60fLmMTNvq6orgfcAH0oy9llAkt1J5pLMzc/PryKqJGk9+hT+SWDLyPJMd9nvqapT3ddfAT8Arh53Y1W1t6pmq2p2ZmZm9YklSWvSp/APA9cl2ZpkE3AL8FCSLUm2AXTXXdOdv5iFffyHNyq0JGn1VnyXTlW9mOQO4CBwHnB/VT2c5C5gB3ArcD6wN8kbgN8BX6uqH25UaEnS6q1Y+ABV9SDw4KLL7ho5/wvgukGTSZIG5ZG2ktQIC1+SGmHhS1IjLHxJaoSFL0mNsPAlqREWviQ1wsKXpEZY+JLUCAtfkhph4UtSIyx8SWqEhS9JjbDwJakRFr4kNcLCl6RGWPiS1AgLX5IaYeFLUiN6FX6SXUmOJDmWZM8SM7cneao73TZsTEnSeq34R8yTXATcA7wTeAE4mOT7VfX4yMwO4DPATiDAT5L8a1U9vxGhJUmr1+cR/vXA41V1sqpeAfYBuxbNvB/4blX9pqpeBL4PfHDYqJKk9VjxET5wBTD6SH0euKrHzOXjbizJbmB3t/hykiP9ok7MFhae2Uw7cw4kCZwFOTvmHNbZkPMta/3GPoUPcHrR8uY1zlBVe4G9AEnmqmq2Z4aJOBsygjmHZs5hmXM4SebW+r19dumcZOG33qtmustWOyNJmqA+hX8YuC7J1iSbgFuAh5JsSbKtmzkI/HmSC5NcDNzUXSZJmhIr7tKpqheT3MFCgZ8H3F9VDye5C9gB3FpVP0/yJeAxFt6l84WqerbH/e9dc/Iz52zICOYcmjmHZc7hrDljqmrIIJKkKeWRtpLUCAtfkhqx4YV/tnwsQ8+cJ5IcT3K0O00q684kTyxz/Yr/lo3WI+Ohbn2+ui7vPJP5ugwXJDmQ5JkkT0/j9rmKjBPfNpPc32U4nuSB7ij9xTPTsG32yTnx7XMky6eWOl5p1euzqjbsBFwEPMfCQVibgEeAnYtmdgDHutmLgaeArRuZay05u7kTwJYzmW1Mhi8C/wMcWc+/ZZIZu5lDwOyE1+UFwAe6868Hfgq8Y9HMRLfPPhm766Zh27yR114X/GcW3tAxVdtmn5zd5RPfPrsc7wX+Y9zP0lrW50Y/wj9bPpahT86pUFWfBK5dZmTi/5YeGadCVZ2qqv3d+ZeAnwGXLRqb6PbZM+NUqKoDVVXdI+YZFn45jpr4ttkz51RIsgX4MvDxJUZWvT43uvD7fORC749l2EB9M5wGDndP7Sf2FG8F07A++yhgX/dU9CvdMR4Tk+Qy4F0sHHcyamrW5zIZYUq2zSS3s3DQ5U+BHy+6eprW5XI5YcLbZxY+3+MbwKeBXy4xtur1eSZetB3sYxk2WJ8Mb6uqK4H3AB9KMpXPApiO9bmSm6pqB3ANsI3XPl/pjEtyPvAt4LNV9esxIxNfnz0yTsW2WVVfBy4FtgIfGzMy8XUJvXJOevv8BPCjqjq0wtyq1udGF/7Z8rEMvTJU1anu66+AHwBXn5F0qzMN63NFI+vyt8CDTGhdJtkMPAB8r6ruHTMy8fXZI+NUbZvd7oUDwOLPpJn4uhy1TM5p2D7fBHw0yVHgIeCqJI8smln9+tzgFxwuZuHFpK289qLC+7qQ27qZP2JhH9qF3fxR4E1n+IWRPjm3AteMzD8K/MmZzDmSdwcjL+IAlwDbl/u3TFnGC4AbuvPnAd8G/noCGS8E/g34zKLLp2b77Jlx4tsmC4+WX31x+TzgX4Bbp23b7JlzKrbPkcz/97O03vV5JsL+BfBfwNPA33eX3QXcOzLzt90P1VHgbya0UpfNCfwh8BPg513Ov5tQzruBJ4CXgDkWfjHdChxa7t8yTRlZeLfJvwPPsvAOmC8Ar5tAzhuAl7v/z1dPn5um7bNPxmnYNoE/YOHjV04Ax4EvsbAHYdq2zRVzTsv2OZJ5B68V/rrWpx+tIEmN8EhbSWqEhS9JjbDwJakRFr4kNcLCl6RGWPiS1AgLX5Ia8b/ppfwfCFZp6gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x = np.arange(16).reshape((4, 4))\n",
    "pcolor((x < 12) & (x % 2 == 0), cmap='gray');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Индексирование по нескольким измерениям\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 4])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[(0, 1), (1, 0)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0,  5, 10, 15])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[range(4), range(4)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0,  5, 10, 15])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.diagonal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[100,   1,   2,   3],\n",
       "       [  4, 100,   6,   7],\n",
       "       [  8,   9, 100,  11],\n",
       "       [ 12,  13,  14, 100]])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[range(4), range(4)] = 100\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0,  1,  2],\n",
       "       [-2, -1,  0]])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i2=vstack([arange(3),arange(3)-2])\n",
    "i2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[[ 0,  1,  2,  3],\n",
       "        [ 4,  5,  6,  7],\n",
       "        [ 8,  9, 10, 11]],\n",
       "\n",
       "       [[ 8,  9, 10, 11],\n",
       "        [12, 13, 14, 15],\n",
       "        [ 0,  1,  2,  3]]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[i2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Генерация паттернов"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 0, 2, 0, 3, 0],\n",
       "       [0, 1, 0, 2, 0, 3]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=array([1,2,3])\n",
    "b=array([[1,0],[0,1]])\n",
    "kron(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "pcolor(_); colorbar();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAD8CAYAAABuHP8oAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAADSdJREFUeJzt3FGMXOdZxvH/W+zEcVIF07gmvkpa3FKohIlNXVE1XZRGlishtaLQKpZKKdK6F+SiLalEWsXr3AQkSlFBIBkpclBMgCZS1SAZJ26yxSjUlQ1OZKgTN4q5oWkpdRFRnKDAy8WcJStrfc6ZZM7MvPD/SSOfOd+3s4/Ofn58fGbORmYiSarnDbMOIEl6bSxwSSrKApekoixwSSrKApekoixwSSqqV4FHxHJEnI+Is83j80MHkyS1WzfG3A9n5snBkkiSxuIlFEkqqu8ZeAIPRsTLwFHg05n5yuoJEbEILI6erd8B100w5v9RP7K1e85//cvwObrc2CPnc7PPec2Oa1rHXzj1wpSStNu24z9ax8+deuOUkrTbse07reOnzl0/pSTtdlzVkfPifOS8nvac34HvZ+bmcV4z+txKHxEbMvOliNgI3Ac8npl/dPn5WxP2jZPj/6dN+7vnXDgwfI4uh3vk3Dv7nAu5q3V8OU5MKUm7I7ncOr4nFqaSo0seXWodj93t49OS25dax+N0+/i0LLHUMc6pzNw5zmv2uoSSmS81f74IPAy8Y5xvIkmavM4Cj4gNEaNTgohYD3wI+MbAuSRJHfqcgQdwd0Q8B5wBngUeGDSVJKlT55uYmXkRuHkKWSRJY/BjhJJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJU1FgFHhF3RMSZocJIkvrrXeAR8R7gtgGzSJLG0KvAI+I64IvAJ4eNI0nqa13XhIgI4D7gs8B3W+YtAoujZ9dOJl11m/a3j184MJ0cXQ535Nw7HzkXclfr+HKcmFKSdkdyuXV8TyxMJUebPLrUOSd2d88ZWm7vzhCnu+cMbYnuDN1zul/jUn3OwD8FPJHZvioz82Bm7szMnbBx7CCSpPH0KfAbgY9FxFnga8C2iDg+bCxJUpfOSyiZefvKdkTcAPxVZr53wEySpB78HLgkFdV5Br5aZp4H3jlMFEnSODwDl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKqpXgUfE/RFxrnk8FBFXDx1MktSu7xn4IeBtmbkNeBn45cESSZJ6WddnUmYeA2jOvDcD3xoylCSpW+9r4BHxCeB54Engm2uML0bEyYg4CS9OMKIkaS2Rmf0nR6wD7gUey8xDl5+3NWHf60837zbtbx+/cGA6Oboc7si5d/Y5F3JX55zlODGFJO2O5HLnnD2xMHiOLnl0qXU8drePT0tuX2odj9Pt49OyxNLrGu/5XU5l5s5xvmKsT6Fk5ivAMWCsbyJJmrzOAo+ITRFxa7O9HvggcHLoYJKkdn3OwAO4MyLOA/8EnAf+dMBMkqQeOj+Fkpk/AH5hClkkSWPwTkxJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKqqzwCNiQ0Qci4hnI+KZiLhzGsEkSe36noH/Tma+FfgZ4CMRsX3ATJKkHjoLPDNfysxHm+2LwLeBLUMHkyS1WzfO5IjYArwb+PU1xhaBxdGzaycQbcY27e+ec+HA8Dm6HO6Rc+/scy7krtbx5TgxpSTtjuRy6/ieWJhKji55dKl1PHa3j09Lbl9qHY/T7ePTsER3hj5zZqH3m5gRcSXwZeBzmfnDS8cz82Bm7szMnbBxkhklSWvoVeARcQXwEHAkMw8NmkiS1EufT6FsBB4GjmfmPcNHkiT10ecM/F3AAvBrEXG2eVjkkjRjnW9iZuYycOXwUSRJ4/BOTEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKIscEkqygKXpKJ6F3hE3BQRTw0ZRpLUX68Cj4gvAI/2nS9JGl6vQs7MzwA7Bs4iSRrDukm9UEQsAoujZ9dO6mUlSZcxsQLPzIPAQYCIrTmp1x3Mpv3t4xcOTCdHl8MdOffOR86F3NU6vhwnppTk8o7kcuecPbEweI4ueXSpc07s7p4ztNzenSFOd88Z2hLtGbrG55nXtCWpKAtckorq+ymUu4GvAm+NiJMR8b5hY0mSuvS6Bp6ZdwF3DZxFkjQGL6FIUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlEWuCQVZYFLUlG9CjwiPhARZyLi6Yi4c+hQkqRunQUeEVcDfwy8H/hpYE9E3DR0MElSuz5n4O8C/j4zn8/MV4AHgQ8MG0uS1CUys31CxF7g5szc1zy/Dfj5zPyNS+YtAovN03cCZyYfd6KuA74/6xA9mHOyzDlZ5pyct2fmG8f5gnU95/33Jc+vuHRCZh4EDgJExMnM3DlOkGmrkBHMOWnmnCxzTk5EnBz3a/pcQnme0b9eKzY3+yRJM9SnwE8APxcRb46IdcCHga8NG0uS1KXzEkpmvhARtwOPA+uB+zPz6x1fdnAS4QZWISOYc9LMOVnmnJyxM3a+iSlJmk/eiSlJRVngklTURAu8yi33EbEcEecj4mzz+PysM62IiJsi4qlVz98UEX8dEc80f/7YLPOtWCPnxyPiwqpjemrG+TZExLGIeLY5dnc2+98SEU80+x6IiA1zmnMpIr636nh+dZY5m0z3R8S55vFQRFw9j+vzMjnnan2uiIg7IuJMsz3+sczMiTyAq4F/Bn6c0Zujx4GbJvX6k3wAy8DOWedYI9cXgH8Dzqzady+wr9neB3xpTnN+HPjDWWdblWcDcGuzfRXwJLAdeAzY3ey/B/j0nOZcAn5z1sfxkqzv59X3zf6s+ZnP4/pcK+dcrc8m23uAf1j5e/RajuUkz8C95f51yszPADsu2X0L8BfN9p8zB8f0MjnnSma+lJmPNtsXgW8DWxjdJfxIM23mx7Ml59zJzGOZmc3vR9oMfIv5XJ9r5ZwrEXEd8EXgk6t2j30sJ1ngW4HvrXr+r4zOxudRAg82l3q+1Hy+fV69KTN/CJCZ/w7M/L+oLW5r/tv6aET81KzDrIiILcC7Gf16hwvZnOIwZ2t0Vc4Tza47muP5lYjYOsNo/ysiPsHoRr4ngW8yp+tzjZwwJ+szIgK4D/gs8N1VQ2Mfy0m/idl5y/2c2JOZNwA/C1zPq7/DZR5d+jnPeT2mDzBagNuAPwEOzTbOSERcCXwZ+Fyzay7X6OqczV/i387MLcDbgL8Ffn+W+VZk5r3AJuDNwK8yp+tzjZzztD4/BTyRmcuX7B/7WE6ywMvccp+ZLzV/vgg8DLxjtolaXYiIawAi4lrgBzPOs6bMfHnVme2DwLZZ5gGIiCuAh4AjmXmI0Rn3j66aMhdrdI2cq9doAn/JHK3R5hLpMWAnc7w+V+ecs/V5I/CxiDjL6K72bRFxnNdwLCdZ4CVuuW/e9V9ottcDHwK+MdNQ7R4DPtJsf5Q5PKYAEXFzRFzVPP0lYOxfzDPhPBsZ/eN8PDPvAcjM/wSejohbmmkzP55r5Wz237Lq0t6vMOM1GhGbIuLWZns98EFGP+O5Wp+XyzlP6zMzb8/Mt2fmTzK67n0uM9/LazmWE35X9ReBfwSeAe6a9bu8l8l4FfA3wHPA08DvAm+Yda4m293AU8BFRgvsfYzOEh9pjukjwOY5zflbwHlg5aziLTPOuAC83ORZedwD/ATwd8A5Rm8YbZzTnH/A6FNdTwNfmfXPndH12Mebn/E54PcYnQDO1fpsyTlX63NV3ht49VMoYx9Lb6WXpKK8E1OSirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySivofBlku8rk3AVgAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "a=arange(8)\n",
    "b=eye(5)\n",
    "pcolor(kron(a,b), cmap='jet');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAD8CAYAAABuHP8oAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAADKBJREFUeJzt3H/sXXddx/HnG9ut69BZWKn0DzPA8kOWiOtXYiSMmrFYSEwg8sOUBJA/vuUP98fA2TjI+u3+mY0iBhtNarIUsziVLSFsCbUr21drJpAWuqVKt7JQEyMTkSEha2cW3/5xz9fefPn2nHPLvb3nbZ+P5Kbn3vO5575yvp++enrOPd/ITCRJ9bxk3gEkSZfGApekoixwSSrKApekoixwSSrKApekonoVeEQsR8TZiDjdPD4562CSpHbrJhj7nsw8PrMkkqSJeApFkorqewSewAMR8QLwt8DHMvPF8QERsQgsjp6t3w7XTzGmpCvST2ztHvOz7atf+rIftK5/Jd/u/Iif+sEP2wf8a+cm+Ldz7eu/Dd/NzM3dW7og+txKHxEbMvN8RGwEPgs8lpl/evHxWxN2T5JDkn7Upr3dYw60r96x63Dr+j3s7/yInUeW2wfs6dwE+062r1+CE5m50L2lC3qdQsnM882fzwMPAW+Y5EMkSdPXWeARsSEidjTL64F3A1+ecS5JUoc+R+AB3B0R3wJOAc8A9880lSSpU+dFzMw8B9x8GbJIkibg1wglqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqSgLXJKKssAlqaiJCjwi7oiIU7MKI0nqr3eBR8RbgF0zzCJJmkCvAo+I64FPAx+dbRxJUl+Rme0DIgJ4GPgD4CzwcGbeuMa4RWBx9Oy67XD7lKNKV4hNe7vHHGhfvWPX4db1e9jf+RE7jyy3D9jTuQn2nWxfv8RS90auGEsnMnNhknf0OQK/HXg8M5fbBmXmwcxcGAXYOEkGSdIl6FPgrwI+GBGngS8B2yLi2GxjSZK6rOsakJm3rSxHxA2MTqG8dYaZJEk9+D1wSSqq8wh8XGaeBX7kAqYk6fLzCFySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJakoC1ySirLAJamoXgUeEfdFxJnm8WBEXDvrYJKkdn2PwA8Br83MbcALwHtnlkiS1Mu6PoMy8yhAc+S9GfjGLENJkrr1PgceER8BngWeAL66xvrFiDgeEcfh+SlGlCStJTKz/+CIdcC9wKOZeeji47Ym7P7x0+nKsWlv95gD7at37Drcun4P+zs/YueR5fYBezo3wb6T7euXWOreiK5ASycyc2GSd0z0LZTMfBE4Ckz0IZKk6ess8IjYFBG3NsvrgXcBx2cdTJLUrs8ReAB3RsRZ4J+Bs8BfzDCTJKmHzm+hZOb3gF+9DFkkSRPwTkxJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKqqzwCNiQ0QcjYhnIuLpiLjzcgSTJLXrewS+PzNfA/wC8P6IeNMMM0mSeugs8Mw8n5mPNMvngG8CW2YdTJLULjKz/+CILcDXgDdm5vdXrVsEFkfPrtsOt08v5f9Xm/Z2jznQvnrHrsOdm9jD/tb1O48sd22g076T7euXWOreiHRFWzqRmQuTvKP3RcyIuBr4HPCJ1eUNkJkHM3NhFGDjJBkkSZegV4FHxFXAg8AXM/PQTBNJknrp8y2UjcBDwLHMvGf2kSRJffQ5An8zsAP4rYg43Twsckmas3VdAzJzGbh69lEkSZPwTkxJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6SiLHBJKsoCl6Siehd4RNwUEU/OMowkqb9eBR4RnwIe6TtekjR7vQo5Mz8ObJ9xFknSBNZNa0MRsQgsjp5dN63NSpIuIjKz38CIG4CHM/PG7rFbE3avvXLT3u4PO9C+eseuw52b2MP+1vU7jyx3baDTvpPt65dY6t6IJAGwdCIzFyZ5h+e0JakoC1ySiur7LZS7gS8Ar4mI4xHxttnGkiR16XURMzPvAu6acRZJ0gQ8hSJJRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRVngklSUBS5JRfUq8Ih4Z0ScioinIuLOWYeSJHXrLPCIuBb4M+DtwBuBd0TETbMOJklq1+cI/M3A1zLz2cx8EXgAeOdsY0mSukRmtg+I+ABwc2bubp7vAn4lM3971bhFYLF5eiNwavpxp+p64LvzDtGDOafLnNNlzul5XWb+5CRvWNdz3P+sen7V6gGZeRA4CBARxzNzYZIgl1uFjGDOaTPndJlzeiLi+KTv6XMK5VlG/3qt2Ny8Jkmaoz4F/hXglyLiFRGxDngP8KXZxpIkdek8hZKZP4yI24DHgPXAfZn5dx1vOziNcDNWISOYc9rMOV3mnJ6JM3ZexJQkDZN3YkpSURa4JBU11QKvcst9RCxHxNmION08PjnvTCsi4qaIeHLs+csj4nBEPN38+bJ55luxRs4PR8RzY/v0xJzzbYiIoxHxTLPv7mxef3VEPN68dn9EbBhozqWI+M7Y/vzCPHM2me6LiDPN48GIuHaI8/MiOQc1P1dExB0RcapZnnxfZuZUHsC1wL8AP8Po4ugx4KZpbX+aD2AZWJh3jjVyfQr4T+DU2Gv3Arub5d3AZwaa88PAgXlnG8uzAbi1Wb4GeAJ4E/Ao8GvN6/cAHxtoziXgd+a9H1dlfTsXrpv9ZfMzH+L8XCvnoOZnk+0twNdX/h5dyr6c5hG4t9z/mDLz48D2VS/fAvx1s/xXDGCfXiTnoGTm+cx8pFk+B3wT2MLoLuEjzbC578+WnIOTmUczM5vfj7QZ+AbDnJ9r5RyUiLge+DTw0bGXJ96X0yzwrcB3xp7/B6Oj8SFK4IHmVM9nmu+3D9XLM/P7AJn5X8Dc/4vaYlfz39ZHIuLn5x1mRURsAX6Z0a93eC6bQxwGNkfHcn6leemOZn9+PiK2zjHa/4mIjzC6ke8J4KsMdH6ukRMGMj8jIoDPAr8L/PvYqon35bQvYnbecj8Q78jMG4BfBF7Jhd/hMkSrv+c51H16P6MJuA34c+DQfOOMRMTVwOeATzQvDXKOjuds/hL/fmZuAV4L/APwx/PMtyIz7wU2Aa8APsRA5+caOYc0P28HHs/M5VWvT7wvp1ngZW65z8zzzZ/PAw8Bb5hvolbPRcRLASLiOuB7c86zpsx8YezI9gFg2zzzAETEVcCDwBcz8xCjI+6fHhsyiDm6Rs7xOZrA3zCgOdqcIj0KLDDg+Tmec2Dz81XAByPiNKO72rdFxDEuYV9Os8BL3HLfXPXf0SyvB94NfHmuodo9Cry/Wf5NBrhPASLi5oi4pnn6G8DEv5hnynk2MvrH+Vhm3gOQmf8NPBURtzTD5r4/18rZvH7L2Km99zHnORoRmyLi1mZ5PfAuRj/jQc3Pi+Uc0vzMzNsy83WZ+XpG573PZOZbuZR9OeWrqr8O/BPwNHDXvK/yXiTjNcDfA98CngL+EHjJvHM12e4GngTOMZpgb2N0lHik2adHgM0Dzfl7wFlg5aji1XPOuAN4ocmz8rgH+DngH4EzjC4YbRxozj9h9K2up4DPz/vnzuh87GPNz/gM8EeMDgAHNT9bcg5qfo7lvYEL30KZeF96K70kFeWdmJJUlAUuSUVZ4JJUlAUuSUVZ4JJUlAUuSUVZ4JJU1P8CLuESn1uOgBMAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pcolor(kron(b,a), cmap='jet');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Случайное перемешивание"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 8, 1, 5, 4, 9, 6, 3, 7])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = np.arange(10)\n",
    "np.random.shuffle(i)\n",
    "i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# EM-алгоритм\n",
    "\n",
    "На каждой итерации проводится два шага:\n",
    "\n",
    "### E - evalution\n",
    "Оценка текущего состояния\n",
    "\n",
    "### M - maximisation \n",
    "Максимизация параметров. Т.е. \"подгонка\" модели под текущую выборку объектов. Например, путем минимизации ошибки."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![](emalg.png) \n",
    " \n",
    "Иллюстрация применения ЕМ-алгоритма для разделения смеси нормальных распределений\n",
    "с двумя компонентами. На рис. а показана исходная выборка и начальное приближение для двух\n",
    "компонент. На рис. b показан результат Е шага. При этом цвета объектов соответствуют значениям\n",
    "γ nk . На рис. c-f показаны результаты вычислений после 1, 2, 5 и 20 итераций."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Варианты ЕМ-алгоритма:\n",
    "- K-means\n",
    "- Фильтр Кальмана\n",
    "- Алгоритмы оптимизации"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Оценка текущего состояния\n",
    "\n",
    "Требования:\n",
    "- одно число - сумма отклонений\n",
    "- предел при полном совпадении - 0\n",
    "\n",
    "Mетод наименьших квадратов (введен в практику Гауссом)              + регуляризация\n",
    "\n",
    "<b class=\"tag\">RMSE</b>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Приведение к нахождению минимума\n",
    "\n",
    "- функция потерь (loss function)\n",
    "- минимизация \n",
    "\n",
    "если потери = 0, то идеальное решение, иначе оптимальное."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Алгоритмы\n",
    "\n",
    "Жесткие | Нежесткие\n",
    "-|-\n",
    "однозначная траектория | приблизительная траектория\n",
    "перебор всех вариантов | неполный случайный выбор вариантов\n",
    "скорость предопределена | скорость в пределах от и до\n",
    "решение гарантировано | лучше усреднить несколько проходов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Динамическое программирование\n",
    "\n",
    "Подход к решению задач, при котором есть перекрытие между подзадачами и исходной задачей, т.е. они замыкаются друг на друга (рекурсия). Процесс решения включает этапы:\n",
    "1. Выделение фрагментов задачи.\n",
    "2. Разбор примитивных случаев с простыми решениями (с конца).\n",
    "3. Запоминание вариантов решений в таблицу или задание порядка пересчета.\n",
    "4. Подбор пошаговых решений из таблицы или переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Бионические алгоритмы\n",
    "\n",
    "Изначально механистические, которые часто \"заходят в тупик\" в сложных ситуациях. Поиск новых алгоритмов черпает вдохновение в живых системах:\n",
    "\n",
    "<b class=tag>biologically plausible</b>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Рой пчел (Artificial bee colony algorithm)\n",
    "\n",
    "![](bees_anim.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Сначала из улея вылетают в случайно направлении какое-то количество пчел-разведчиков, которые пытаются отыскать участки, где есть нектар. Через какое-то время пчелы возвращаются в улей и особым образом сообщают остальным где и сколько они нашли нектара.\n",
    "После этого на найденные участки отправляются другие пчелы, причем чем больше на данном участке предполагается найти нектара, тем больше пчел летит в этом направлении. А разведчики опять улетают искать другие участки, после чего процесс повторяется. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Иммунный ответ\n",
    "\n",
    "- данные = антигены\n",
    "- популяция антител эволюционирует для наилучшего распознования\n",
    "\n",
    "![](Iris_Dim_Pairs.jpg)\n",
    "\n",
    "<b class=tag>VALIS</b> <b class=tag>AIRS</b> <b class=tag>CLONALG</b>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "### +++\n",
    "\n",
    "[Почему индексация от 0](http://gestaltrevision.be/wiki/python/zerobased)\n",
    "\n",
    "#### Python\n",
    "[Whirlwind Tour Of Python](http://nbviewer.jupyter.org/github/jakevdp/WhirlwindTourOfPython/blob/master/00-Introduction.ipynb)\n",
    "\n",
    "[Python Data Science Handbook](http://nbviewer.jupyter.org/github/jakevdp/PythonDataScienceHandbook/blob/master/notebooks/Index.ipynb)\n",
    "\n",
    "Reference Book: [Think Python: How to Think Like a Computer Scientist](http://greenteapress.com/thinkpython/html/index.html)\n",
    "\n",
    "[Jupyter ](http://nbviewer.jupyter.org/github/jupyter/ngcm-tutorial/blob/master/Index.ipynb)\n",
    "\n",
    "\n",
    "https://python-packaging.readthedocs.io/en/latest/"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {
    "height": "546px",
    "width": "341px"
   },
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}