algoritmia_2_6.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# <center>Complejidad Algoritmica (Parte 6)</center>"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## <center>Análisis Matemático de Algoritmos No Recursivos</center>\n",
        "\n",
        "* Decide sobre un parámetro (o parametros) que indiquen el tamaño de la entrada.\n",
        "* Identifica la operación básica del algoritmo. (Como regla, se localiza en el ciclo más interno.)\n",
        "* Revisa si el número de veces que se realiza la operación básica depende sólo del tamaño de la entrada.\n",
        "* Establece una suma que exprese el número de veces que la operación básica del algoritmo es ejecutada.\n",
        "* Usando fórmulas estandar y reglas de manipulación de sumas ecuentra una fórmula para el conteo de las operaciones o establece su orden de crecimiento."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## <center>Algunas Reglas Básicas para Manipulación de Sumas</center>\n",
        "\n",
        "$$\\sum_{i=l}^{u}ca_{i} = c\\sum_{i=l}^{u}a_{i}$$\n",
        "$$\\sum_{i=l}^{u}(a_{i} \\pm b_{i}) = \\sum_{i=l}^{u}a_{i} \\pm \\sum_{i=l}^{u}b_{i}$$\n",
        "\n",
        "## <center>Algunas Fórmulas de Sumas</center>\n",
        "\n",
        "$$\\sum_{i=l}^{u}1=u-l+1$$\n",
        "$$\\sum_{i=0}^{n}i = \\sum_{i=1}^{n}i = 1 + 2 + \\cdots + n = n\\frac{(n+1)}{2} \\approx \\frac{1}{2}n^2 \\in \\Theta(n^2)$$\n",
        "$$\\sum_{i=1}^{n}i^2 = 1^{2} + 2^{2} + \\cdots + n^{2} = \\frac{n(n+1)(2n+1)}{6} \\approx \\frac{1}{3}n^{3} \\in \\Theta(n^3)$$"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <center>Ejemplo 9</center>\n",
        "```\n",
        "elementosUnicos(A[0...n-1])\n",
        "//Determina si los elementos en un arreglo son únicos.\n",
        "//Entrada: Un arreglo A[0...n-1].\n",
        "//Salida: verdadero si todos los elementos en A son distintos, falso en otro caso.\n",
        "\n",
        "desde i <- 0 hasta n - 2 \n",
        "    desde j <- i + 1 hasta n - 1\n",
        "        si A[i] = A[j]\n",
        "            regresar falso\n",
        "regresar verdadero\n",
        "```"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <center>Solución 9</center>\n",
        "\n",
        "Realicemos el análisis para el peor caso $\\mathrm{O}$.\n",
        "\n",
        "**Tamaño de entrada**: $n$\n",
        "\n",
        "**Operación Básica**: ```A[i] = A[j]```\n",
        "\n",
        "\n",
        "$$c(n) = \\sum_{i=0}^{n-2} \\sum_{j=i+1}^{n-1} 1$$\n",
        "\n",
        "Para resolver la suma descrita anteriormente la solución debe comenzar desde la suma más interna hacia la externa, es decir, de derecha a izquierda. Revisando las fórmulas de sumas nos damos cuenta que la suma más interna es la suma de 1 por lo tanto la resolvemos de esa forma. Reemplazando con los datos de nuestro algoritmo y resolviendo tenemos:\n",
        "\n",
        "$$c(n) = \\sum_{i=0}^{n-2} n - 1 - i$$\n",
        "\n",
        "Ahora tenemos la suma de $n - 1 - i$, si revisamos en nuestras fórmulas de sumas no existe una que cumpla con ese patrón, sin embargo lo que podemos hacer es intentar que se parezca a una de ellas y para conseguirlo usaremos la segunda regla de las sumas que establece que podemos separar una suma de varios términos en distintas sumas. En nuestro caso consideraremos $n - 1$ como un primer término e $i$ como un segundo término de forma que podamos después resolver ambas sumas de manera independiente. Ahora tendremos:\n",
        "\n",
        "$$c(n) = \\sum_{i=0}^{n-2} n - 1 - \\sum_{i=0}^{n-2} i$$\n",
        "\n",
        "Desarrollando ambas sumas y uniendo sus resultados en uno solo tenemos la siguiente expresión:\n",
        "\n",
        "$$c(n) = (n^2 - 2n + 1) - (\\frac{n^{2}-3n+2}{2})$$\n",
        "\n",
        "Resolviendo:\n",
        "\n",
        "$$c(n) = \\frac{2(n^2 - 2n + 1) - (n^{2}-3n+2)}{2}$$\n",
        "$$c(n) = \\frac{2n^{2} - 4n + 2 - n^{2}+3n-2}{2}$$\n",
        "$$c(n) = \\frac{n^{2} - n}{2} \\in \\mathrm{O}(n^{2})$$"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Ahora revisemos un ejemplo con tres ciclos anidados."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <center>Ejemplo 10</center>\n",
        "```\n",
        "multiplicacionMatricial(A[0...n-1,0...n-1], B[0...n-1,0...n-1])\n",
        "//Multiplica dos matrices cuadradas de orden n por el algoritmo de definición.\n",
        "//Entrada: Dos matrices de nxn A y B.\n",
        "//Salida: matriz C = AB.\n",
        "\n",
        "desde i <- 0 hasta n - 1\n",
        "    desde j <- 0 hasta n - 1\n",
        "        C[i,j] <- 0.0\n",
        "        desde k <- 0 hasta n - 1 hacer\n",
        "            C[i,j] <- C[i,j] + A[i,k] * B[k,j]\n",
        "regresar C\n",
        "```"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <center>Solución 10</center>\n",
        "\n",
        "**Tamaño de entrada**: $n$\n",
        "\n",
        "**Operación Básica**: ```A[i,k] * B[k,j]```\n",
        "\n",
        "Nuestro algoritmo tiene ciclos anidados y para poder expresarlos en notación sigma lo que haremos es escribirlos en el orden en que los encontramos. Cuando se tienen ciclos anidados nuestras expresiones se verán como sumas de sumas siendo la última en ser escrita la que tenga la expresión que representa el conteo de veces que suceda la operación básica en ese ciclo. Dicho lo anterior, nuestro algoritmo se representará como:\n",
        "\n",
        "$$c(n) = \\sum_{i=0}^{n-1} \\sum_{j=0}^{n-1} \\sum_{k=0}^{n-1} 1$$\n",
        "\n",
        "Para resolver la suma descrita anteriormente la solución debe comenzar desde la suma más interna hacia la externa, es decir, de derecha a izquierda. Revisando las fórmulas de sumas nos damos cuenta que la suma más interna es la suma de 1 por lo tanto la resolvemos de esa forma:\n",
        "\n",
        "$$\\sum_{i=l}^{u}1=u-l+1$$\n",
        "\n",
        "Reemplazando con los datos de nuestro algoritmo y resolviendo tenemos:\n",
        "\n",
        "$$u = n-1$$\n",
        "$$l = 0$$\n",
        "$$c(n) = u - l + 1 = n - 1 - 0 + 1 = n$$\n",
        "\n",
        "por lo tanto ahora la solución para nuestro algoritmo se ve de la siguiente forma:\n",
        "\n",
        "$$c(n) = \\sum_{i=0}^{n-1} \\sum_{j=0}^{n-1} n$$\n",
        "\n",
        "Lo cual podemos reescribir como:\n",
        "\n",
        "$$c(n) = n \\sum_{i=0}^{n-1} \\sum_{j=0}^{n-1} 1$$\n",
        "\n",
        "Nuevamente tenemos la suma de 1 por lo que podemos resolver con la fórmula que ya conocemos. Ahora nuestra suma se verá de la siguiente forma:\n",
        "\n",
        "$$c(n) = n \\sum_{i=0}^{n-1} n$$\n",
        "\n",
        "Reescribiendo para sacar $n$ como constante y tener nuevamente la suma de 1:\n",
        "\n",
        "$$c(n) = n^{2} \\sum_{i=0}^{n-1} 1$$\n",
        "\n",
        "Resolviendo la última suma tenemos:\n",
        "\n",
        "$$c(n) = n^{3} \\in \\Theta(n^{3})$$\n",
        "\n",
        "Con lo cual podemos concluir que el algoritmo de definición para multiplicar matrices es de orden cúbico. Tal vez te preguntes cómo se ve su crecimiento, pues bien, con la siguiente gráfica interactiva lo puedes inspeccionar."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import ipywidgets as widgets\n",
        "from ipywidgets import interact\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "size = np.arange(1, 10, 1)\n",
        "\n",
        "def cn(n = 4):\n",
        "    size = np.arange(1, n, 1)\n",
        "    plt.xlabel('Tamaño de entrada')\n",
        "    plt.ylabel('pasos')\n",
        "    plt.title('multiplicacionMatricial(A[0...n-1,0...n-1], B[0...n-1,0...n-1])')\n",
        "    plt.plot(size, size**3, label='θ(n^3)')\n",
        "    plt.plot(size, size**3, '.', label='c(n) = n³')\n",
        "    plt.legend()\n",
        "    print(f'Pasos necesitados: {n**3}')\n",
        "\n",
        "interact(cn, n = (4, 1000, 1))"
      ],
      "outputs": [],
      "execution_count": null,
      "metadata": {
        "collapsed": true,
        "jupyter": {
          "source_hidden": false,
          "outputs_hidden": false
        },
        "nteract": {
          "transient": {
            "deleting": false
          }
        },
        "execution": {
          "iopub.status.busy": "2020-09-29T20:53:11.062Z",
          "iopub.execute_input": "2020-09-29T20:53:11.084Z",
          "iopub.status.idle": "2020-09-29T20:53:11.762Z",
          "shell.execute_reply": "2020-09-29T20:53:11.814Z"
        },
        "tags": []
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <center>Ejercicio</center>\n",
        "\n",
        "Completa el análisis del siguiente bloque de código\n",
        "\n",
        "```\n",
        "suma <- 0\n",
        "desde i <- 1 hasta n\n",
        "    desde j <- 1 hasta n\n",
        "        desde k <- 1 hasta n\n",
        "            suma <- i + j + k\n",
        "```"
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <center>Solución</center>\n",
        "\n",
        "**Tamaño de entrada**: $n$\n",
        "\n",
        "**Operación Básica**: ```i + j + k```\n",
        "\n",
        "Desarrolla en tu cuaderno la solución para el conteo de operaciones. Dentro de la operación básica existen dos sumas, por lo cual podemos considerar que la operación básica (una suma) sucede dos veces, desarrolla tu solución teniendo esto en cuenta."
      ],
      "metadata": {
        "nteract": {
          "transient": {
            "deleting": false
          }
        }
      }
    }
  ],
  "metadata": {
    "kernel_info": {
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.7.3",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "kernelspec": {
      "argv": [
        "python",
        "-m",
        "ipykernel_launcher",
        "-f",
        "{connection_file}"
      ],
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "nteract": {
      "version": "0.25.1"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}