01 Introducción.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1 Introducción\n",
    "El objetivo de este capítulo es ver los conceptos básicos de programación que luego utilizaremos a lo largo de todo el curso. Esto incluye ver tanto los datos que vamos a manejar, como las instrucciones que operan sobre ellos, así como las técnicas básicas de programación.\n",
    "Para la implementación de los algoritmos que vamos a ver utilizaremos el lenguaje Python, sin perjuicio de que los conceptos que veremos son independientes del lenguaje específico utilizado.\n",
    "\n",
    "En primer lugar, veremos algunos de los tipos de datos básicos de Python.\n",
    "Las variables cambian de tipo dinámicamente según el tipo del valor que tengan en un instante dado."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Datos numéricos\n",
    "Python distingue entre números enteros (``int``) y números de punto flotante (``float``)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 <class 'int'>\n",
      "3.14 <class 'float'>\n"
     ]
    }
   ],
   "source": [
    "n=5 # int\n",
    "print(n, type(n))\n",
    "x=3.14 # float\n",
    "print(x, type(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sobre estos datos se pueden ejecutar las operaciones aritméticas habituales."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "2.5\n",
      "2\n",
      "9.8596\n"
     ]
    }
   ],
   "source": [
    "print(n+1)\n",
    "print(n/2) # noten la diferencia con Python 2.7\n",
    "print(n//2) # división entera\n",
    "print(x**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Datos lógicos\n",
    "Los valores de verdad son `True` y `False`. Las operaciones lógicas se indican con palabras en lugar de símbolos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "t=True\n",
    "f=False\n",
    "print(t and f)\n",
    "print(t and not f)\n",
    "print(n>0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Strings\n",
    "Los strings se escriben entre comillas simples o dobles, y existen muchas operaciones definidas para ellos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hola\n",
      "4\n",
      "Hola mundo\n",
      "HOLA\n"
     ]
    }
   ],
   "source": [
    "h=\"Hola\"\n",
    "print(h)\n",
    "print(len(h))\n",
    "m='mundo'\n",
    "print(h + \" \" + m)\n",
    "print(h.upper())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Listas\n",
    "Una lista es una secuencia de datos, posiblemente de distintos tipos, de largo variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 2, 1]\n",
      "[3, 2, 1, 0]\n",
      "[3, 2, 1]\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "L=[3,2,1]\n",
    "print(L)\n",
    "L.append(0)\n",
    "print(L)\n",
    "x=L.pop()\n",
    "print(L)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Los elementos de la lista se indexan partiendo desde cero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "1\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "print(L[0])\n",
    "print(L[2])\n",
    "print(L[-1]) # contando desde el extremo derecho"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Una lista se puede construir en base a iterar una fórmula:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 4, 9, 16, 25, 36]\n"
     ]
    }
   ],
   "source": [
    "C = [n**2 for n in range(1,7)]\n",
    "print(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Una lista se puede recorrer a través de sus subíndices:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "9\n",
      "16\n",
      "25\n",
      "36\n"
     ]
    }
   ],
   "source": [
    "for i in range(0,len(C)):\n",
    "    print(C[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "O bien iterando sobre los elementos de la lista:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "9\n",
      "16\n",
      "25\n",
      "36\n"
     ]
    }
   ],
   "source": [
    "for v in C:\n",
    "    print(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Funciones predefinidas\n",
    "Hay funciones que están disponibles para ser utilizadas:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.0\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "a=3\n",
    "b=4\n",
    "c=math.sqrt(a**2+b**2)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Funciones\n",
    "Uno puede definir sus propias funciones:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.0\n"
     ]
    }
   ],
   "source": [
    "def hipotenusa(a,b):\n",
    "    import math\n",
    "    c=math.sqrt(a**2+b**2)\n",
    "    return c\n",
    "print(hipotenusa(3,4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expresiones condicionales\n",
    "Una expresión de la forma\n",
    "```python\n",
    "valor_si_verdadero if condicion else valor_si_falso\n",
    "```\n",
    "permite por ejemplo definir funciones por tramos, como por ejemplo:\n",
    "\n",
    "$$\n",
    "|x| =\n",
    "\\begin{cases}\n",
    "-x & \\text{si } x<0 \\\\\n",
    "x & \\text{en caso contrario}\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 5\n"
     ]
    }
   ],
   "source": [
    "def valor_absoluto(x):\n",
    "    return -x if x<0 else x\n",
    "print(valor_absoluto(-5), valor_absoluto(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diccionarios\n",
    "Un diccionario es similar a una lista, pero los elementos se indexan con datos no necesariamente numéricos. Por ejemplo, supongamos que queremos convertir \"piedra\", \"papel\" y \"tijera\" a una representación numérica 0, 1, 2, respectivamente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "p_a_n = {\"piedra\":0, \"papel\":1, \"tijera\":2} # para convertir de palabra a número\n",
    "print(p_a_n[\"papel\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La conversión inversa se puede hacer simplemente con una lista:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "papel\n"
     ]
    }
   ],
   "source": [
    "n_a_p = [\"piedra\", \"papel\", \"tijera\"] # para convertir de número a palabra\n",
    "print(n_a_p[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Con esto podemos hacer una función en que el programa juegue \"cachipún\" contra el usuario:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def juega():\n",
    "    from random import randint\n",
    "    programa=randint(0,2)\n",
    "    usuario=p_a_n[input(\"¿piedra, papel o tijera? \")]\n",
    "    resultado=\"Empate\" if programa==usuario else\\\n",
    "        \"Gana Usuario\" if (programa+1)%3==usuario else \"Gana Programa\"\n",
    "    print(\"Usuario juega\", n_a_p[usuario])\n",
    "    print(\"Programa juega\", n_a_p[programa])\n",
    "    print(\"Resultado:\", resultado)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "¿piedra, papel o tijera? piedra\n",
      "Usuario juega piedra\n",
      "Programa juega tijera\n",
      "Resultado: Gana Usuario\n"
     ]
    }
   ],
   "source": [
    "juega()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instrucción condicional: if\n",
    "La instrucción `if` permite elegir entre distintas alternativas de instrucciones a ejecutar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "# Encontrar el máximo entre dos valores\n",
    "def max2(a, b):\n",
    "    if a>b:\n",
    "        m=a\n",
    "    else:\n",
    "        m=b\n",
    "    return m\n",
    "print(max2(3,7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Esto se puede generalizar a 3 valores, pero el resultado no es muy elegante:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "# Encontrar el máximo entre tres valores\n",
    "def max3(a, b, c):\n",
    "    if a>b:\n",
    "        if a>c:\n",
    "            m=a\n",
    "        else:\n",
    "            m=c\n",
    "    else:\n",
    "        if b>c:\n",
    "            m=b\n",
    "        else:\n",
    "            m=c\n",
    "    return m\n",
    "print(max3(4,3,7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Una mejor alternativa la podemos obtener si vamos obteniendo aproximaciones sucesivas al máximo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "# Encontrar el máximo entre dos valores\n",
    "def max2(a, b):\n",
    "    m=a\n",
    "    if b>m:\n",
    "        m=b\n",
    "    return m\n",
    "print(max2(3,7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Esto se generaliza de manera mucho más simple a tres (o más) valores:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "# Encontrar el máximo entre tres valores\n",
    "def max3(a, b, c):\n",
    "    m=a\n",
    "    if b>m:\n",
    "        m=b\n",
    "    if c>m:\n",
    "        m=c\n",
    "    return m\n",
    "print(max3(4,3,7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cuando hay preguntas encadenadas, se puede usar la cláusula `elif` (abreviatura de `else if`, pero que no abre un nuevo nivel de indentación):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False True True\n"
     ]
    }
   ],
   "source": [
    "# Dice si un año dado es bisiesto\n",
    "def es_bisiesto(a):\n",
    "    if a%400==0:   # Los múltiplos de 400 siempre son bisiestos\n",
    "        b=True\n",
    "    elif a%100==0: # Los demás múltiplos de 100 no son bisiestos\n",
    "        b=False\n",
    "    elif a%4==0:   # De los restantes, los múltiplos de 4 son bisiestos\n",
    "        b=True\n",
    "    else:          # Cualquier otro año no es bisiesto\n",
    "        b=False\n",
    "    return b\n",
    "print(es_bisiesto(1900), es_bisiesto(2000), es_bisiesto(2020))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instrucciones iterativas: for\n",
    "La instrucción `for` itera con una variable que toma valores de una lista dada. A menudo, esa lista se especifica mediante `range`.\n",
    "Ilustraremos su uso generalizando los algoritmos que vimos antes para encontrar el máximo de un conjunto de dos o tres números, al caso de un conjunto con un número cualquiera de elementos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "93\n"
     ]
    }
   ],
   "source": [
    "# Encuentra el máximo de una lista a\n",
    "def maximo(a):\n",
    "    m=a[0]\n",
    "    # Al comenzar cada iteración, se cumple que m==max(a[0],...,a[k-1])\n",
    "    for k in range(1,len(a)):\n",
    "        if a[k]>m:\n",
    "            m=a[k]\n",
    "    return m\n",
    "print(maximo([25, 42, 93, 17, 54, 28]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El comentario que aparece junto al `for` describe lo que se llama el **invariante** del ciclo, y es muy útil para poder argumentar la correctitud del programa, así como para poder ayudar a su diseño.\n",
    "\n",
    "El invariante una afirmación lógica que debe ser verdadera cada vez que se intenta iniciar una nueva iteración, lo cual incluye tanto la primera vez como el último intento, en que se detecta que el rango ya se ha agotado y el ciclo termina.\n",
    "\n",
    "* La validez del invariante la primera vez la deben asegurar las instrucciones previas al ciclo, que se llaman instrucciones de *inicialización*. En este ejemplo, al comenzar el ciclo se tiene que $k=1$, y por lo tanto trivialmente se cumple que $m=\\max(a[0])$.\n",
    "\n",
    "* Las instrucciones al interior del ciclo (el \"cuerpo de ciclo\") parten de la premisa de que el invariante se cumple al inicio, y deben garantizar que se cumpla al final (para dejar todo listo para la próxima iteración). Esto se llama _preservar el invariante_. En este ejemplo, para asegurar que $m=\\max(a[0],\\ldots,a[k])$ sabiendo que ya era cierto que $m=\\max(a[0],\\ldots,a[k-1])$, se debe modificar $m$ solo en el caso de que $a[k]$ sea mayor que $m$, o dejarlo igual si no.\n",
    "\n",
    "* Cuando se detecta que el rango se ha agotado, el invariante igualmente se cumple, y ambas cosas juntas deben asegurar que haya logrado el objetivo final deseado. En este ejemplo, cuando $k$ llega a ser igual a $len(a)$, el invariante implica que $m=\\max(a[0],\\ldots,a[len(a)-1])$, o sea, es el máximo de toda la lista."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 1.1\n",
    "\n",
    "La función ``maximo`` hace $n-1$ comparaciones de elementos para encontrar el máximo de un conjunto de tamaño $n$.\n",
    "\n",
    "Supongamos que se desea escribir una función ``minmax`` que al ser llamada con una lista de números, retorne un par ordenado (tupla) ``(min,max)``, con el mínimo y el máximo elemento del conjunto, respectivamente. Escriba a continuación esa función haciendo dos pasadas sobre los datos: una para encontrar el mínimo y otra para encontrar el máximo, y pruébela sobre una lista de ejemplo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minmax(a):\n",
    "    # escribir la función aquí\n",
    "    \n",
    "    return(minimo,maximo)\n",
    "\n",
    "# Probarla acá"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La función anterior debería hacer $2n-2$ comparaciones de elementos ($2n-3$ si se evita comparar el elemento seleccionado en la primera pasada). ¿Será posible encontrar el mínimo y el máximo haciendo muchas menos comparaciones?\n",
    "\n",
    "¡La respuesta es que sí! Veámoslo con un ejemplo. Para simplificar, supongamos que la lista es de largo par:\n",
    "\n",
    "$$\n",
    "[45,21,34,67,55,89,44,12]\n",
    "$$\n",
    "\n",
    "Luego comparemos cada elemento que está en una posición par con su vecino de la derecha, e intercambiémoslos de modo que el par quede en orden ascendente (recuerde que las posiciones comienzan desde cero):\n",
    "\n",
    "$$\n",
    "[21,45,34,67,55,89,12,44]\n",
    "$$\n",
    "\n",
    "Luego hagamos una pasada solo sobre las posiciones pares para encontrar el mínimo ($12$), y otra pasada solo entre las posiciones impares para encontrar el máximo ($89$). ¡Listo!\n",
    "\n",
    "Programe este nuevo algoritmo, pruébelo y diga cuántas comparaciones hace en total:\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minmax(a):\n",
    "    # escribir la función aquí\n",
    "    \n",
    "    return(minimo,maximo)\n",
    "\n",
    "# Probarla acá"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instrucciones iterativas: while\n",
    "La instrucción `while` ejecuta instrucciones mientra la condición especificada sea verdadera:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True True False False True\n"
     ]
    }
   ],
   "source": [
    "# Dice si un número dado es primo o no\n",
    "def es_primo(n):\n",
    "    if n==2:\n",
    "        return True # 2 es primo\n",
    "    if n%2==0:\n",
    "        return False # ningún otro par es primo\n",
    "    k=3\n",
    "    while k**2<=n: # no es necesario buscar posibles factores más allá de sqrt(n)\n",
    "        if n%k==0:\n",
    "            return False # n es divisible por k => no es primo\n",
    "        k+=2 # probamos solo los impares\n",
    "    # si no se encontró ningún factor menor que raíz de n, es primo\n",
    "    return True\n",
    "print(es_primo(2), es_primo(7), es_primo(9), es_primo(79823492843), es_primo(79823492869))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo de programación con invariantes: particionar un conjunto\n",
    "\n",
    "Supongamos que se tiene un conjunto de datos en una lista $a[0],\\ldots,a[n-1]$ y un valor de corte $p$, y se desea reordenar los datos dentro de la lista, de modo que queden a la izquierda todos los que son menores que $p$, y a la derecha los que son mayores. Por simplicidad, supondremos que en la lista no hay ningún valor igual a $p$. Este es un problema cuya utilidad veremos más adelante, cuando estudiemos el algoritmo de ordenación Quicksort.\n",
    "\n",
    "La solución clásica para este problema es la de **Hoare**, el autor de Quicksort, y se basa en ir identificando elementos menores o mayores que $p$, y moviéndolos hacia el extremo izquierdo o derecho de la lista, según corresponda. Esto corresponde al siguiente invariante:\n",
    "\n",
    "![particio-Hoare](particion-Hoare.png)\n",
    "\n",
    "En este invariante, $i$ y $j$ son los primeros elementos desconocidos (esto es, aún no identificados como menores o mayores), viniendo desde cada extremo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def particionHoare(a,p):\n",
    "    # retorna el punto de corte, el número de elementos <p y la lista particionada\n",
    "    n=len(a)\n",
    "    (i,j)=(0,n-1) #inicialmente todos los elementos son desconocidos\n",
    "    while i<=j: # aún quedan elementos desconocidos\n",
    "        if a[i]<p:\n",
    "            i+=1\n",
    "        elif a[j]>p:\n",
    "            j-=1\n",
    "        else:\n",
    "            (a[i],a[j])=(a[j],a[i]) # intercambio\n",
    "            i+=1\n",
    "            j-=1\n",
    "    return (p,i,a)   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para ayudarnos a verificar que la partición se realiza correctamente, definiremos una función auxiliar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def verifica_particion(t): # imprime y chequea partición\n",
    "    (p,m,a)=t\n",
    "    # p=punto de corte, m=número de elementos <p, a=lista completa particionada\n",
    "    print(a[0:m],p,a[m:])\n",
    "    print(\"Partición OK\" if (m==0 or max(a[0:m])<p) and (m==len(a) or min(a[m:])>p)\n",
    "          else \"Error\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[36, 21, 34, 15, 37] 50 [56, 77, 65, 82, 98, 73]\n",
      "Partición OK\n"
     ]
    }
   ],
   "source": [
    "verifica_particion(particionHoare([73,21,34,98,56,37,77,65,82,15,36],50))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[] 0 [73, 21, 34, 98, 56, 37, 77, 65, 82, 15, 36]\n",
      "Partición OK\n"
     ]
    }
   ],
   "source": [
    "verifica_particion(particionHoare([73,21,34,98,56,37,77,65,82,15,36],0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[73, 21, 34, 98, 56, 37, 77, 65, 82, 15, 36] 100 []\n",
      "Partición OK\n"
     ]
    }
   ],
   "source": [
    "verifica_particion(particionHoare([73,21,34,98,56,37,77,65,82,15,36],100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 1.2\n",
    "\n",
    "Existe un algoritmo alternativo, que resulta en una codificación más sencilla. Este algoritmo, debido a **Lomuto**, se basa en el siguiente invariante:\n",
    "\n",
    "![particion-Lomuto](particion-Lomuto.png)\n",
    "\n",
    "En este algoritmo, en cada iteración, si $a[j]<p$, se intercambian $a[i]$ con $a[j]$ y se incrementa $i$, porque ahora hay un elemento más en el grupo de los menores que $p$. Después de esto, se incrementa $j$, *incondicionalmente* (¿por qué es correcto hacer eso?).\n",
    "\n",
    "Programe la partición de Lomuto en el recuadro siguiente y pruébela."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def particionLomuto(a,p):\n",
    "    # retorna el punto de corte, el número de elementos <p y la lista particionada\n",
    "    \n",
    "    # escribir acá el algoritmo de partición de Lomuto\n",
    "    \n",
    "    return (p,i,a) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "verifica_particion(particionLomuto([73,21,34,98,56,37,77,65,82,15,36],50))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "verifica_particion(particionLomuto([73,21,34,98,56,37,77,65,82,15,36],0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "verifica_particion(particionLomuto([73,21,34,98,56,37,77,65,82,15,36],100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo de programación con invariantes: Calcular $y = x^n$\n",
    "\n",
    "Supongamos que no tuviéramos una operación de elevación a potencia, y que necesitáramos calcular $x^n$ para $n$ entero no negativo.\n",
    "El algoritmo obvio es calcular $x*x*\\cdots *x$ ($n$ veces):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def potencia(x, n):\n",
    "    y=1\n",
    "    for k in range(0,n):\n",
    "        y*=x\n",
    "    return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1024\n"
     ]
    }
   ],
   "source": [
    "print(potencia(2,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El invariante, esto es, lo que se cumple al comenzar cada nueva iteración es $y = x^k$. Así, al inicio, cuando $k=0$, se tiene $y=1$ (inicialización), y al término, cuando $y=n$, se tiene la condición final buscada. La preservación del invariante consiste en multiplicar $y$ por $x$, porque así se sigue cumpliendo el invariante cuando $k$ se incrementa en $1$.\n",
    "\n",
    "Este algoritmo ejecuta $n$ multiplicaciones para calcular $x^n$ y, si tomamos en cuenta todo lo que hace, es evidente que demora un tiempo proporcional a $n$, lo cual escribiremos $O(n)$ y lo leeremos \"del orden de $n$\". (Más adelante definiremos precisamente esta notación, y veremos que podríamos ser más precisos todavía al describir el tiempo que demora un algoritmo)\n",
    "\n",
    "¿Será posible calcular una potencia de manera más eficiente?\n",
    "\n",
    "Para ver cómo podríamos mejorar el algoritmo, comenzaremos por reescribirlo de modo que la variable $k$ vaya disminuyendo en lugar de ir aumentando, usando para ello la instrucción `while`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def potencia(x, n):\n",
    "    y=1\n",
    "    k=n\n",
    "    while k>0:\n",
    "        y*=x\n",
    "        k-=1\n",
    "    return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1024\n"
     ]
    }
   ],
   "source": [
    "print(potencia(2,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El invariante en este caso sería $y = x^{n-k}$ o, lo que es lo mismo, $y * x^k = x^n$.\n",
    "\n",
    "El reescribirlo de esta manera nos permite hacer el siguiente truco: vamos a introducir una variable $z$, cuyo valor inicial es $x$, y reformular el invariante como $y * z^k = x^n$ y preservarlo aprovechando que $y*z^k = (y*z)*z^{k-1}$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def potencia(x, n):\n",
    "    y=1\n",
    "    k=n\n",
    "    z=x\n",
    "    while k>0:\n",
    "        y*=z\n",
    "        k-=1\n",
    "    return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1024\n"
     ]
    }
   ],
   "source": [
    "print(potencia(2,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este cambio podría parecer ocioso, pero gracias a él ahora tenemos un grado adicional de libertad: en efecto, podemos modificar la variable $z$ en la medida que eso no haga que el invariante deje de cumplirse.\n",
    "\n",
    "En particular, una oportunidad de hacer esto aparece cuando $k$ es par. En ese caso, como $z^n=(z^2)^{n/2}$, si elevamos $z$ al cuadrado y al mismo tiempo dividimos $k$ a la mitad, ambos cambios se complementan para hacer que el invariante se preserve. El algoritmo resultante se llama el *algoritmo binario*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def potencia(x, n):\n",
    "    y=1\n",
    "    k=n\n",
    "    z=x\n",
    "    while k>0:\n",
    "        if k%2==0: # caso k par\n",
    "            z=z*z\n",
    "            k//=2\n",
    "        else:      # caso k impar\n",
    "            y*=z \n",
    "            k-=1\n",
    "    return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1024\n"
     ]
    }
   ],
   "source": [
    "print(potencia(2,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este algoritmo admite todavía una pequeña optimización. Cuando $k$ se divide por $2$, no solo se preserva el invariante, sino que además $k$ sigue siendo $>0$, y por lo tanto no es necesario en ese caso volver a preguntar por la condición del `while`. El algoritmo queda como sigue:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def potencia(x, n):\n",
    "    y=1\n",
    "    k=n\n",
    "    z=x\n",
    "    while k>0:\n",
    "        while k%2==0: # caso k par\n",
    "            z=z*z\n",
    "            k//=2\n",
    "        y*=z # aquí estamos seguros que k es impar\n",
    "        k-=1\n",
    "    return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1024\n"
     ]
    }
   ],
   "source": [
    "print(potencia(2,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este algoritmo (en cualquiera de las dos últimas versiones) se llama el *algoritmo binario*, y es mucho más eficiente que el algoritmo inicial. Cada vez que se da el caso par, $k$ disminuye a a mitad, y eso ocurre al menos la mitad de las veces. Pero si $k$ comienza con el valor $n$, la operación de dividir por $2$ se puede ejecutar a lo más $\\log_2{n}$ veces, por lo tanto el tiempo total de ejecución es $O(\\log_2{n})$, en lugar de $O(n)$. \n",
    "\n",
    "Decimos que el algoritmo original era de tiempo lineal, y que el algoritmo binario es de tiempo logarítmico. Para $n$ grande, la diferencia de eficiencia es muy grande en favor del algoritmo binario.\n",
    "\n",
    "Una observación importante es que para que el algoritmo binario funcione, solo es necesario que $x$ $y$, $z$ pertenezcan a un conjunto para el cual hay definida una operación multiplicativa que sea asociativa y que tenga un elemento neutro. Por lo tanto, este algoritmo no solo sirve para elevar a potencia números enteros o reales, sino que además, por ejemplo, para calcular potencias de *matrices*. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ¿Por qué se llama \"algoritmo binario\"?\n",
    "\n",
    "Existe una relación muy interesante entre el funcionamiento de este algoritmo y la representación binaria del número $n$.\n",
    "\n",
    "Para quienes no lo recuerden (o lo estén viendo por primera vez), cuando un número se escribe en base $10$, por ejemplo, el número $2019$, esto significa\n",
    "\n",
    "$$\n",
    "(2019)_{10} = 2 \\cdot 10^3 + 0 \\cdot 10^2 + 1 \\cdot 10^1 + 9 \\cdot 10^0\n",
    "$$\n",
    "\n",
    "De manera análoga, un número escrito en base $2$, por ejemplo $110101$ significa\n",
    "\n",
    "$$\n",
    "(110101)_2 = 1 \\cdot 2^5 + 1 \\cdot 2^4 + 0 \\cdot 2^3 + 1 \\cdot 2^2 + 0 \\cdot 2^1 + 1 \\cdot 2^0 \n",
    "$$\n",
    "\n",
    "lo cual equivale a 53 en decimal.\n",
    "\n",
    "Más en general, un número puede estar escrito en base $b$:\n",
    "\n",
    "$$\n",
    "(\\ldots d_3 d_2 d_1 d_0)_b = \\sum_{k \\ge 0}{d_k b^k}\n",
    "$$\n",
    "\n",
    "donde $0\\le d_k \\le b-1$ para todo $k$.\n",
    "\n",
    "Volviendo ahora al problema de calcular $y=x^n$, consideremos como ejemplo de $n=53$.\n",
    "Si escribimos el exponente en binario, tenemos que\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "x^{53} &= x^{(110101)_2}\\\\\n",
    "  &=x^{1 \\cdot 2^5 + 1 \\cdot 2^4 + 0 \\cdot 2^3 + 1 \\cdot 2^2 + 0 \\cdot 2^1 + 1 \\cdot 2^0}\\\\\n",
    "  &=x^{2^5}\\cdot x^{2^4}\\cdot x^{2^2}\\cdot x^{2^0}\\\\\n",
    "  &=x^{32}\\cdot x^{16}\\cdot x^{4}\\cdot x^{1}\\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Como vemos, el valor final calculado es el producto de los $x$ elevados a aquellas potencias de 2 que corresponden exactamente adonde hay un dígito $1$ en la representación binaria del número $n$. Veremos que eso es exactamente lo que hace al algoritmo.\n",
    "\n",
    "Si examinamos el algoritmo, en su primera versión, podemos ver que su estado se puede representar por una terna $(k,z,y)$, la cual tiene el valor inicial $(n,x,1)$. En cada iteración tenemos dos casos:\n",
    "\n",
    "Caso $k$ par:\n",
    "$$\n",
    "(k,z,y) \\rightarrow (\\frac{k}{2},z^2,y)\n",
    "$$\n",
    "\n",
    "Caso $k$ impar:\n",
    "$$\n",
    "(k,z,y) \\rightarrow (k-1,z,yz)\n",
    "$$\n",
    "\n",
    "Estas reglas adquieren una forma mucho muy simple si el número $k$ se considera escrito en binario. En esta base un número es *par* si termina en $0$ y es *impar* si termina en 1. Además, restarle $1$ a un número impar es equivalente a sustituir el $1$ de más a la derecha por un $0$, y dividir por $2$ un número par es equivalente a eliminar el $0$ de más a la derecha.\n",
    "\n",
    "Con esto, podemos reformular nuestras reglas, suponiendo que el número $k$ se escribe en binario en la forma $(\\alpha X)_2$, donde $X$ es el dígito de más a la derecha y $\\alpha$ es la secuencia de dígitos que lo preceden. Entonces\n",
    "\n",
    "Caso $k$ terminado en $0$:\n",
    "$$\n",
    "((\\alpha 0)_2,z,y) \\rightarrow ((\\alpha)_2,z^2,y)\n",
    "$$\n",
    "\n",
    "Caso $k$ terminado en $1$:\n",
    "$$\n",
    "((\\alpha 1)_2,z,y) \\rightarrow ((\\alpha 0)_2,z,yz)\n",
    "$$\n",
    "\n",
    "En palabras: la variable $z$ va tomando sucesivamente los valores $x^1,x^2,x^4,x^8,\\ldots$, y el valor final calculado es $x$ elevado a la suma aquellas potencias que corresponden exactamente adonde hay un dígito $1$ en la representación binaria del número $n$.\n",
    "\n",
    "La siguiente tabla muestra la ejecución del algoritmo para $n=53$:\n",
    "\n",
    "| $k$ | $z$ | $y$ |\n",
    "| --- | --- | --- |\n",
    "| $(110101)_2$ | $x^1$ | $1$ |\n",
    "| $(110100)_2$ | $x^1$ | $x^1$ |\n",
    "| $(11010)_2$ | $x^2$ | $x^1$ |\n",
    "| $(1101)_2$ | $x^4$ | $x^1$ |\n",
    "| $(1100)_2$ | $x^4$ | $x^{1+4}=x^5$ |\n",
    "| $(110)_2$ | $x^8$ | $x^{1+4}=x^5$ |\n",
    "| $(11)_2$ | $x^{16}$ | $x^{1+4}=x^5$ |\n",
    "| $(10)_2$ | $x^{16}$ | $x^{1+4+16}=x^{21}$ |\n",
    "| $(1)_2$ | $x^{32}$ | $x^{1+4+16}=x^{21}$ |\n",
    "| $(0)_2$ | $x^{32}$ | $x^{1+4+16+32}=x^{53}$ |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo de programación con invariantes: Evaluación de un polinomio\n",
    "\n",
    "Supongamos que se tiene un polinomio\n",
    "\n",
    "$$\n",
    "P(x) = \\sum_{0<=k<=n}{a_k x^k}\n",
    "$$\n",
    "\n",
    "y se desea calcular su valor en un punto dado $x$.\n",
    "\n",
    "Una solución trivial se puede obtener directamente de la fórmula anterior:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evalp(a,x):\n",
    "    \"\"\"Evalúa en el punto x el polinomio cuyos coeficientes son a[0], a[1],...\n",
    "    Retorna el valor calculado\n",
    "    \"\"\"\n",
    "    P=0\n",
    "    for k in range(0,len(a)):\n",
    "        # Invariante: P=a[0]+a[1]*x+...+a[k-1]*x**(k-1)\n",
    "        P += a[k]*x**k\n",
    "    return P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos probar esta función evaluando el polinomio\n",
    "\n",
    "$$\n",
    "P(x) = 5+2x-3x^2+4x^3\n",
    "$$\n",
    "\n",
    "en el punto $x=2$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "29\n"
     ]
    }
   ],
   "source": [
    "print(evalp([5,2,-3,4],2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El problema es que este algoritmo puede ser ineficiente. Si el sistema calcula ``x**k`` de manera simple, el tiempo total de ejecución sería del orden de $n^2$, y si lo calcula usando el algoritmo binario, el tiempo sería del orden de $n\\log{n}$. Veremos que esto se puede reducir a tiempo lineal.\n",
    "\n",
    "Para esto, vamos a introducir una variable adicional, digamos $y$, que almacene el valor de $x^k$ necesario para cada iteración. Para preservar este invariante, al final de cada vuelta del ciclo debemos dejarla multiplicada por $x$, para que tenga el valor correcto al iniciarse la siguiente iteración:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evalp(a,x):\n",
    "    \"\"\"Evalúa en el punto x el polinomio cuyos coeficientes son a[0], a[1],...\n",
    "    Retorna el valor calculado\n",
    "    \"\"\"\n",
    "    P=0\n",
    "    y=1\n",
    "    for k in range(0,len(a)):\n",
    "        # Invariante: P=a[0]+a[1]*x+...+a[k-1]*x**(k-1) and y=x**k\n",
    "        P += a[k]*y\n",
    "        y *= x\n",
    "    return P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "29\n"
     ]
    }
   ],
   "source": [
    "print(evalp([5,2,-3,4],2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 1.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un polinomio se puede evaluar en tiempo lineal sin necesidad de una variable auxiliar si observamos que $P(x)$ se puede factorizar como:\n",
    "\n",
    "$$\n",
    "P(x) = a_0 +x(a_1+x(\\cdots+x(a_{n-1}+x(a_n))\\cdots))\n",
    "$$\n",
    "\n",
    "Por ejemplo,\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "P(x) &= 5+2x-3x^2+4x^3\\\\\n",
    " &=5+x(2+x(-3+x(4)))\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Programe un algoritmo iterativo que evalúe el polinomio utilizando esta idea. Comience desde el paréntesis más interno y vaya avanzando hacia la izquierda. Indique cuál es el invariante que utiliza. El algoritmo resultante se llama la **Regla de Horner**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evalp(a,x):\n",
    "    \"\"\"Evalúa en el punto x el polinomio cuyos coeficientes son a[0], a[1],...\n",
    "    utilizando la Regla de Horner\n",
    "    Retorna el valor calculado\n",
    "    \"\"\"\n",
    "    # Escriba aquí su algoritmo\n",
    "    \n",
    "    return P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(evalp([5,2,-3,4],2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Numpy y Arreglos\n",
    "\n",
    "Numpy es la principal biblioteca para computación científica en Python.\n",
    "\n",
    "Una de las características de Numpy es que provee arreglos multidimensionales de alta eficiencia. Mientras la gran flexibilidad de las listas de Python puede hacer que no sea muy eficiente el acceso a elementos específicos, los arreglos de Numpy aseguran el acceso a cada elemento en tiempo constante. Por esa razón, utilizaremos estos arreglos cuando necesitemos asegurar la eficiencia de la implementación de los algoritmos.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.6\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "a = np.array([6.5, 5.2, 4.6, 7.0, 4.3])\n",
    "print(a[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "print(len(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hay varias formas de crear arreglos inicializados con ceros, unos, valores constantes o valores aleatorios."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]\n"
     ]
    }
   ],
   "source": [
    "b = np.ones(10)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 0 0 0 0 0 0]\n"
     ]
    }
   ],
   "source": [
    "c = np.zeros(7,dtype=int)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En los dos ejemplos anteriores mostramos la diferencia que se produce al explicitar el tipo de datos del arreglo. En el primero, obtenemos el *default*, que es flotante, mientras en el segundo forzamos a que sea entero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2 2 2 2 2]\n"
     ]
    }
   ],
   "source": [
    "c = np.full(5, 2)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.96086121 0.31006032 0.78951795 0.14162147 0.72680238 0.03081408]\n"
     ]
    }
   ],
   "source": [
    "d = np.random.random(6)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "También es posible crear y manejar arreglos de varias dimensiones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1 2 3]\n",
      " [4 5 6]]\n"
     ]
    }
   ],
   "source": [
    "a = np.array([[1,2,3],[4,5,6]])\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "print(a[0,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3\n"
     ]
    }
   ],
   "source": [
    "(m,n)=np.shape(a)\n",
    "print(m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0. 0. 0.]\n",
      " [0. 0. 0.]\n",
      " [0. 0. 0.]]\n"
     ]
    }
   ],
   "source": [
    "b = np.zeros((3,3))\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 0. 0.]\n",
      " [0. 1. 0.]\n",
      " [0. 0. 1.]]\n"
     ]
    }
   ],
   "source": [
    "c = np.eye(3)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplos de programación con invariantes: Ordenación"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ordenación por inserción\n",
    "\n",
    "Supongamos que se tiene un arreglo $a$, de tamaño $n$, y queremos reordenar los datos almacenados en su interior de modo que queden en orden ascendente.\n",
    "\n",
    "El método de **Ordenación por Inserción** se basa en formar en el sector izquierdo del arreglo un subconjunto ordenado, en el cual se van insertando uno por uno los elementos restantes. Para la inicialización, comenzamos con un subconjunto ordenado de tamaño 0, y el proceso termina cuando el subconjunto ordenado llega a tener tamaño $n$. El invariante se puede visualizar como:\n",
    "\n",
    "![insercion](insercion.png)\n",
    "\n",
    "La variable $k$ indica el tamaño del subconjunto ordenado. Equivalentemente, $k$ es el subíndice del primer elemento todavía no ordenado, y que será el que se insertará en esta oportunidad."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ordenación Por Inserción\n",
    "def ordena_insercion(a):\n",
    "    n=len(a)\n",
    "    for k in range(0,n):\n",
    "        insertar(a,k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este algoritmo todavía no es ejecutable, porque falta definir la función `insertar`, que se encarga de tomar $a[k]$ e insertarlo entre los anteriores. La forma más simple de hacer esto es a través de intercambios sucesivos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Insertar a[k] entre los elementos anteriores preservando el orden ascendente (versión 1)\n",
    "def insertar(a, k):\n",
    "    j=k # señala la posición del elemento que está siendo insertado\n",
    "    while j>0 and a[j]<a[j-1]:\n",
    "        (a[j], a[j-1]) = (a[j-1], a[j])\n",
    "        j-=1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para poder probar este algoritmo, generemos un arreglo con números aleatorios y ordenémoslo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.21698872 0.31136108 0.0676283  0.6468421  0.4082596  0.78409654]\n",
      "[0.0676283  0.21698872 0.31136108 0.4082596  0.6468421  0.78409654]\n"
     ]
    }
   ],
   "source": [
    "a = np.random.random(6)\n",
    "print(a)\n",
    "ordena_insercion(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si observamos el algoritmo de inserción, podemos ver que en los intercambios siempre uno de los dos elementos involucrados es el que se está insertando, el cual pasa por muchos lugares provisorios hasta llegar finalmente a su ubicación definitiva. Esto sugiere que podemos ahorrar trabajo si en lugar de hacer todos esos intercambios, sacamos primero el elemento a insertar hacia una variable auxiliar, luego vamos moviendo los restantes elementos hacia la derecha, y al final movemos directamente el nuevo elemento desde la variable auxiliar hasta su posición definitiva:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Insertar a[k] entre los elementos anteriores preservando el orden ascendente (versión 2)\n",
    "def insertar(a, k):\n",
    "    b=a[k] # b almacena transitoriamente al elemento a[k]\n",
    "    j=k # señala la posición del lugar \"vacío\"\n",
    "    while j>0 and b<a[j-1]:\n",
    "        a[j]=a[j-1]\n",
    "        j-=1\n",
    "    a[j]=b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.63169534 0.51338201 0.75754562 0.11005649 0.81951851 0.5797447 ]\n",
      "[0.11005649 0.51338201 0.5797447  0.63169534 0.75754562 0.81951851]\n"
     ]
    }
   ],
   "source": [
    "a = np.random.random(6)\n",
    "print(a)\n",
    "ordena_insercion(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para analizar la eficiencia de este algoritmo, podemos considerar varios casos:\n",
    "* Mejor caso: Si el arreglo ya viene ordenado, el ciclo de la función `insertar` termina de inmediato, así que esa función demora tiempo constante, y el proceso completo demora tiempo $O(n)$, lineal en $n$.\n",
    "* Peor caso: Si el arreglo viene originalmente en orden decreciente, el ciclo de la función `insertar` hace el máximo de iteraciones ($k$), y la suma de todos esos costos da un total de $O(n^2)$, cuadrático en $n$.\n",
    "* Caso promedio: Si el arreglo viene en orden aleatorio, el número promedio de iteraciones que hace el ciclo de la función `insertar` es aproximadamente $k/2$, y la suma de todos esos costos igual da un total de $O(n^2)$. Esto es, el costo promedio también es cuadrático."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ordenación por Selección\n",
    "\n",
    "El método de **Ordenación por Selección** se basa en extraer el máximo elemento y moverlo hacia el extremo derecho del arreglo, y repetir este proceso entre los elementos restantes hasta que todos hayan sido extraídos. El invariante se puede visualizar como:\n",
    "\n",
    "![ord-seleccion](seleccion.png)\n",
    "\n",
    "La variable $k$ indica el tamaño del subconjunto que todavía falta por procesar. Equivalentemente, es el subíndice del primer elemento que ya pertenece al subconjunto ordenado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ordenación por Selección\n",
    "def ordena_seleccion(a):\n",
    "    n=len(a)\n",
    "    for k in range(n,1,-1): # Paramos cuando todavía queda 1 elemento \"desordenado\" (¿por qué está bien eso?)\n",
    "        j=pos_maximo(a,k) # Encuentra posición del máximo entre a[0],...,a[k-1]\n",
    "        (a[j],a[k-1])=(a[k-1],a[j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Encuentra posición del máximo entre a[0],...,a[k-1]\n",
    "def pos_maximo(a, k):\n",
    "    j=0 # j señala la posición del máximo\n",
    "    for i in range(1,k):\n",
    "        if a[i]>a[j]: # Encontramos un nuevo máximo\n",
    "            j=i\n",
    "    return j"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nuevamente, probamos nuestro algoritmo con un arreglo aleatorio:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.91088675 0.55781357 0.6422284  0.80222542 0.49612172 0.32394811]\n",
      "[0.32394811 0.49612172 0.55781357 0.6422284  0.80222542 0.91088675]\n"
     ]
    }
   ],
   "source": [
    "a = np.random.random(6)\n",
    "print(a)\n",
    "ordena_seleccion(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En este algoritmo, siempre se recorre todo el conjunto de tamaño $k$ para encontrar el máximo, de modo que la suma de todos estos costos de un total de $O(n^2)$, en todos los casos.\n",
    "\n",
    "Más adelante veremos que hay maneras mucho más eficientes de calcular el máximo de un conjunto, una vez que se ha encontrado y extraído el máximo la primera vez.\n",
    "\n",
    "Piensen por ejemplo en un típico torneo de tenis, en donde los jugadores se van eliminando por rondas, hasta que en la final queda solo un jugador invicto: el campeón. Si hay $n$ jugadores, ese proceso requiere exactamente $n-1$ partidos. **Pero** una vez que se ha jugado todo ese torneo, hagamos un experimento mental y pensemos que habría sucedido si el primer día el campeón no hubiera podido jugar por alguna causa. Para determinar quién habría resultado campeón en esas circunstancias (o sea, para encontrar al subcampeón), **no sería necesario repetir todo el torneo, sino solo volver a jugar los partidos en los que habría participado el campeón**. Ese número de partidos es mucho menor a $n$, y en realidad no es difícil ver que es logarítmico. Y eso puede repetirse para encontrar al tercero, al cuarto, etc., siempre con el mismo costo logarítmico.\n",
    "\n",
    "Si sumamos todos esos costos, da un total de $O(n\\log{n})$, en el peor caso.\n",
    "\n",
    "Lo anterior es una \"demostración de factibilidad\" de que existen algoritmos de ordenación de costo $O(n\\log{n})$, más eficientes que $O(n^2)$. Más adelante en el curso veremos algoritmos prácticos que alcanzan esta eficiencia."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ordenación de la Burbuja\n",
    "\n",
    "Este algoritmo se basa en ir haciendo pasadas sucesivas de izquierda a derecha sobre el arreglo, y cada vez que encuentra dos elementos adyacentes fuera de orden, los intercambia. Así, el arreglo va quedando cada vez \"más ordenado\", hasta que finalmente esté totalmente ordenado.\n",
    "\n",
    "Analizando el efecto de una pasada de izquierda a derecha, vemos que, aparte de los pequeños desórdenes que pueda ir arreglando por el camino, una vez que el algoritmo se encuentra con el máximo, los intercambios lo empiezan a trasladar paso a paso hacia la derecha, hasta que finalmente queda en el extremo derecho del arreglo. Eso significa que ya ha llegado a su posición definitiva, y no necesitamos volver a tocarlo. Por lo tanto, el algoritmo puede ignorar esos elementos al extremo derecho, los que por construcción están ordenados y son mayores que todos los de la izquierda. Esto lo podemos visualizar como:\n",
    "\n",
    "![ord-seleccion](seleccion.png)\n",
    "\n",
    "¡El mismo invariante que la Ordenación por Selección! Sin embargo, el algoritmo resultante es distinto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ordenación de la Burbuja (versión 1)\n",
    "def ordena_burbuja(a):\n",
    "    n=len(a)\n",
    "    k=n # número de elementos todavía desordenados\n",
    "    while k>1:\n",
    "        # Hacer una pasada sobre a[0],...,a[k-1]\n",
    "        # intercambiando elementos adyacentes desordenados\n",
    "        for j in range(0,k-1):\n",
    "            if a[j]>a[j+1]:\n",
    "                (a[j],a[j+1])=(a[j+1],a[j])\n",
    "        # Disminuir k\n",
    "        k-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.67980575 0.47893026 0.29847223 0.97584905 0.07176052 0.9138015 ]\n",
      "[0.07176052 0.29847223 0.47893026 0.67980575 0.9138015  0.97584905]\n"
     ]
    }
   ],
   "source": [
    "a = np.random.random(6)\n",
    "print(a)\n",
    "ordena_burbuja(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este algoritmo demora siempre tiempo $O(n^2)$, ¡incluso si se le da para ordenar un arregla que ya viene ordenado!\n",
    "\n",
    "No cuesta mucho introducir una variable booleana que señale si en una pasada no se ha hecho ningún intercambio, y usar esa variable para terminar el proceso cuando eso ocurre. Pero hay una manera mejor de modificar el algoritmo para aumentar su eficiencia.\n",
    "\n",
    "Para esto, introducimos una variable $i$ que recuerda el punto donde se hizo el último intercambio (el cual habría sido entre $a[i-1]$ y $a[i]$. Si a partir de ese punto ya no se encontraron elementos fuera de orden, eso quiere decir que $a[i-1]<a[i]$ y luego a partir de ahí todos los elementos están ordenados, **hasta el final del arreglo**. Por lo tanto, el invariante se preserva si hacemos $k=i$.\n",
    "\n",
    "¿Qué pasa si no hubo ningún intercambio? Para este caso, si le damos a la variable $i$ el valor inicial cero, al hacer $k=i$ tendríamos $k=0$ y el proceso terminaría automáticamente. El algoritmo resultante es el siguiente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ordenación de la Burbuja (versión 2)\n",
    "def ordena_burbuja(a):\n",
    "    n=len(a)\n",
    "    k=n # número de elementos todavía desordenados\n",
    "    while k>1:\n",
    "        # Hacer una pasada sobre a[0],...,a[k-1]\n",
    "        # intercambiando elementos adyacentes desordenados\n",
    "        i=0\n",
    "        for j in range(0,k-1):\n",
    "            if a[j]>a[j+1]:\n",
    "                (a[j],a[j+1])=(a[j+1],a[j])\n",
    "                i=j+1 # recordamos el lugar del último intercambio\n",
    "        # Disminuir k\n",
    "        k=i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.20877349 0.71209819 0.30996714 0.91145577 0.3479466  0.08197456]\n",
      "[0.08197456 0.20877349 0.30996714 0.3479466  0.71209819 0.91145577]\n"
     ]
    }
   ],
   "source": [
    "a = np.random.random(6)\n",
    "print(a)\n",
    "ordena_burbuja(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este algoritmo aprovecha mejor el orden previo que puede trar el arreglo, y en particular ordena arreglos ordenados en tiempo lineal. Pero tanto su peor caso como su caso promedio siguen siendo cuadráticos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursividad\n",
    "\n",
    "El poder escribir funciones que se llamen a sí mismas es una herramienta muy poderosa de programación. Veremos algunos ejemplos de aplicaciones de este concepto, y más adelante veremos cómo puede conducir al diseño de algoritmos muy eficientes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo: Calcular $y=x^n$\n",
    "Revisemos nuevamente este problema, pero ahora desde un punto de vista recursivo. Una potencia se puede definir recursivamente de la siguiente manera:\n",
    "\n",
    "$$\n",
    "x^n =\n",
    "\\begin{cases}x * x^{n-1} & \\mbox{si }n>0 \\\\\n",
    "1 & \\mbox{si }n=0\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "lo cual se puede implementar directamente como una función recursiva:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def potencia(x,n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        return x * potencia(x,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1024\n"
     ]
    }
   ],
   "source": [
    "print(potencia(2,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El algoritmo resultante demora tiempo $O(n)$, pero  puede mejorarse si el caso $n$ par lo tratamos aparte:\n",
    "\n",
    "$$\n",
    "x^n =\n",
    "\\begin{cases}\n",
    "\\left(x^2\\right)^{n/2} & \\mbox{si }n>0\\mbox{, par} \\\\\n",
    "x * x^{n-1} & \\mbox{si }n>0\\mbox{, impar} \\\\\n",
    "1 & \\mbox{si }n=0\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "y la función que lo implementa es:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def potencia(x,n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    elif n%2==0:\n",
    "        return potencia(x*x,n//2)\n",
    "    else:\n",
    "        return x * potencia(x,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1024\n"
     ]
    }
   ],
   "source": [
    "print(potencia(2,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El resultado es el algoritmo binario, que demora tiempo $O(\\log{n})$, en versión recursiva."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursividad vs. Iteración\n",
    "Todo algoritmo iterativo puede escribirse recursivamente. En particular, cualquier ciclo de la forma\n",
    "```python\n",
    "while C:\n",
    "    A\n",
    "```\n",
    "puede implementarse como\n",
    "```python\n",
    "def f():\n",
    "    if C:\n",
    "        A\n",
    "        f()\n",
    "f()\n",
    "```\n",
    "Por cierto, en la llamada recursiva se le debe entregar a la función el contexto en que habría operado en la siguiente iteración del ciclo.\n",
    "\n",
    "Por ejemplo, si queremos imprimir uno por uno los elementos de un arreglo $a$, una forma iterativa de hacerlo sería:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def imprimir(a):\n",
    "    k=0\n",
    "    while k<len(a):\n",
    "        print(a[k])\n",
    "        k+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.7033836563496955\n",
      "0.6452018723083637\n",
      "0.7390309665914873\n",
      "0.7347873655983367\n",
      "0.7866498089752649\n",
      "0.6219100789368107\n"
     ]
    }
   ],
   "source": [
    "a=np.random.random(6)\n",
    "imprimir(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En forma recursiva, esto queda como:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def imprimir(a):\n",
    "    imprimir_recursivo(a,0)\n",
    "    \n",
    "def imprimir_recursivo(a,k): # imprimir desde a[k] en adelante\n",
    "    if k<len(a):\n",
    "        print(a[k])\n",
    "        imprimir_recursivo(a,k+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.48983219759773877\n",
      "0.32335914035360247\n",
      "0.9701200719987955\n",
      "0.6556528043143391\n",
      "0.5783404506167958\n",
      "0.7588468412552624\n"
     ]
    }
   ],
   "source": [
    "a=np.random.random(6)\n",
    "imprimir(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este proceso es reversible: cuando una función recursiva lo último que hace es llamarse a sí misma, lo que se llama \"recursividad a la cola\" (\"*tail recursion*\"), eso se puede reemplazar por un `while`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def imprimir(a):\n",
    "    imprimir_recursivo(a,0)\n",
    "    \n",
    "def imprimir_recursivo(a,k): # imprimir desde a[k] en adelante, ahora NO recursivo\n",
    "    while k<len(a): # reemplazó a \"if k<len(a):\"\n",
    "        print(a[k])\n",
    "        k+=1 # reemplazó a \"imprimir_recursivo(a,k+1)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.5879986363022844\n",
      "0.22292489446199648\n",
      "0.3649081383243461\n",
      "0.0760636478498492\n",
      "0.6282506237409337\n",
      "0.9933423327883073\n"
     ]
    }
   ],
   "source": [
    "a=np.random.random(6)\n",
    "imprimir(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pero ahora la función `imprimir_recursivo` es llamada desde un único lugar, con k=0, y por lo tanto, en ese lugar podemos sustituir la llamada por el código de la función, con lo que el resultado es:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def imprimir(a):\n",
    "    # Esto reemplaza a \"imprimir_recursivo(a,0)\"\n",
    "    k=0\n",
    "    while k<len(a): # reemplazó a \"if k<len(a):\"\n",
    "        print(a[k])\n",
    "        k+=1 # reemplazó a \"imprimir_recursivo(a,k+1)\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.2796059938546853\n",
      "0.7140250823437458\n",
      "0.27114927650914356\n",
      "0.1913138660755075\n",
      "0.3131581564588708\n",
      "0.13509564673494912\n"
     ]
    }
   ],
   "source": [
    "a=np.random.random(6)\n",
    "imprimir(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "¡Con lo cual hemos vuelto al punto de partida!\n",
    "\n",
    "Sin embargo, esto solo funciona para eliminar la \"recursividad a la cola\". Si hay llamadas recursivas que **no** son lo último que ejecuta la función, no pueden eliminarse con esta receta, y como veremos más adelante, requerirá el uso de una estructura llamada una \"pila\" (*stack*).\n",
    "\n",
    "El siguiente ejemplo ilustra un caso en que esto ocurre."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo: Torres de Hanoi\n",
    "\n",
    "![Torres de Hanoi](ColorHanoi.jpg)\n",
    "\n",
    "Este puzzle consiste en trasladar $n$ discos desde la estaca 1 a la estaca 3, respetando siempre las dos reglas siguientes:\n",
    "* Solo se puede mover de a un disco a la vez, y\n",
    "* Nunca puede haber un disco más grande sobre uno más chico\n",
    "Esto se puede resolver recursivamente de la siguiente manera:\n",
    "\n",
    "![Torres de Hanoi](hanoi.gif)\n",
    "\n",
    "Para mover $n$ discos desde $a$ hasta $c$ (usando la estaca $b$ como auxiliar):\n",
    "* Primero movemos (recursivamente) $n-1$ discos desde la estaca $a$ a la estaca $b$\n",
    "* Una vez despejado el camino, movemos 1 disco desde $a$ hasta $c$\n",
    "* Finalmente, movemos de nuevo (recursivamente) los $n-1$ discos, ahora desde $b$ hasta $c$ (usando $a$ como auxiliar)\n",
    "\n",
    "El caso base es $n=0$, en cuyo caso no se hace nada."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Hanoi(n, a, b, c): # Mover n discos desde \"a\" a \"c\", usando \"b\" como auxiliar\n",
    "    if n>0:\n",
    "        Hanoi(n-1, a, c, b)\n",
    "        print(a, \"-->\", c) # Mueve 1 disco desde \"a\" hasta \"c\"\n",
    "        Hanoi(n-1, b, a, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 --> 3\n",
      "1 --> 2\n",
      "3 --> 2\n",
      "1 --> 3\n",
      "2 --> 1\n",
      "2 --> 3\n",
      "1 --> 3\n"
     ]
    }
   ],
   "source": [
    "Hanoi(3, 1, 2, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este algoritmo es muy claro y bastante intuitivo. Si aplicamos la regla de eliminación de \"recursividad a la cola\", lo que resulta es un algoritmo equivalente, pero mucho menos trivial de entender:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Hanoi(n, a, b, c): # Mover n discos desde \"a\" a \"c\", usando \"b\" como auxiliar\n",
    "    while n>0: # reemplaza a \"if n>0:\"\n",
    "        Hanoi(n-1, a, c, b)\n",
    "        print(a, \"-->\", c) # Mueve 1 disco desde \"a\" hasta \"c\"\n",
    "        n-=1\n",
    "        (a,b)=(b,a) # reemplaza a \"Hanoi(n-1, b, a, c)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 --> 3\n",
      "1 --> 2\n",
      "3 --> 2\n",
      "1 --> 3\n",
      "2 --> 1\n",
      "2 --> 3\n",
      "1 --> 3\n"
     ]
    }
   ],
   "source": [
    "Hanoi(3, 1, 2, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "¿Puede usted dar una explicación intuitiva de por qué funciona este algoritmo?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diagramas de Estados\n",
    "\n",
    "Consideremos una instrucción iterativa con un invariante \"I\", que se inicializa con instrucciones \"B\", con condición de continuación \"C\", con un cuerpo del ciclo consistente de instrucciones \"A\" y con el objetivo de lograr que se cumpla una afirmación lógica \"F\". Esto tendría la estructura siguiente:\n",
    "```python\n",
    "B\n",
    "while C: # invariante I\n",
    "    A\n",
    "    \n",
    "# al terminar se debería cumplir F\n",
    "``` \n",
    "\n",
    "Anotando con un poco más de precisión, podemos identificar lo que se cumple en cada punto:\n",
    "```python\n",
    "B\n",
    "# aquí se cumple el invariante \"I\" por primera vez\n",
    "while C:\n",
    "    # aquí se cumple \"I and C\"\n",
    "    A\n",
    "    # acá se debe cumplir nuevamente \"I\"\n",
    "    \n",
    "# al terminar el ciclo se cumple \"I and not C\"\n",
    "# y eso debe implicar que se cumple F\n",
    "```\n",
    "\n",
    "Esto se puede visualizar de manera más sencilla en un **diagrama de estados** como el siguiente:\n",
    "\n",
    "![Diagrama de Estados 1](state-diagram-1.png)\n",
    "\n",
    "En este diagrama:\n",
    "* Los estados (círculos) representan el estado del proceso en ese momento, descrito por la afirmación lógica correspondiente. En un ciclo, esa afirmación lógica es lo que hemos llamado invariante.\n",
    "* Un doble círculo representa a un estado final.\n",
    "* Las flechas pueden llevar como rótulo un \"if\" con una condición, que debe cumplirse para que se siga esa flecha, y también pueden estar rotuladas con una instrucción (o un bloque de instrucciones), que se ejecuta al hacer esa transición."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Una ventaja de modelar un algoritmo en base a un diagrama de estados es que no estamos restringidos solo a los diagramas simples que corresponden a ciclos `while`, sino que podemos construir diagramas mucho más complejos, con múltiples estados y transiciones.\n",
    "\n",
    "Piensen por ejemplo en cómo modelar el funcionamiento de un **cajero automático**:\n",
    "\n",
    "* El cajero está originalmente en un estado inicial, que es además el estado al cual regresa cada vez que concluye la atención de un cliente.\n",
    "* Cuando llega un cliente e inserta su tarjeta, el cajero debe verificar que la tarjeta es legible y si no es, debe devolverla con un mensaje de error y volver al estado inicial.\n",
    "* Si la tarjeta es legible, debe pedir que ingrese el PIN y pasar a otro estado en que espera que el cliente ingrese dicha clave.\n",
    "* Si la clave es incorrecta, debe pedir que la ingrese de nuevo y seguir en ese estado. Pero eso tiene un límite, porque si el usuario comete muchos errores, el cajero debe dar un mensaje de error, retener la tarjeta y volver al estado inicial.\n",
    "* Si la clave es correcta, debe mostrar un menú de posibles operaciones y esperar que el cliente seleccione una.\n",
    "* Si el cliente selecciona \"Retirar dinero\", debe pasar a otro estado en que le pregunta el monto que quiere sacar.\n",
    "* Etc., etc., etc.,\n",
    "\n",
    "En realidad, el diagrama de estados de un cajero automático es enorme, porque en cada estado hay múltiples opciones que conducen a realizar acciones y trasladarse a otros estados. Además, hay \"timeouts\" que interrumpen el proceso si una operación se demora demasiado. El diagrama de estados es la herramienta que permite modelar este tipo de procesos complejos.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo: Contar palabras\n",
    "\n",
    "Supongamos que tenemos un string que contiene una frase y queremos contar cuántas palabras contiene. Para simplificar, supondremos que una palabra es cualquier secuencia de caracteres distintos de un espacio en blanco. Por ejemplo, el string\n",
    "```python\n",
    "\"    Algoritmos y    Estructuras  de   Datos   \"\n",
    "```\n",
    "contiene 5 palabras.\n",
    "\n",
    "Para resolver este problema, iremos examinando uno a uno los caracteres del string, y para cada uno deberemos decidir si ese caracter es el comienzo de una nueva palabra o no. Esto depende de si estábamos FUERA de una palabra (en cuyo caso sí es el inicio y hay que incrementar el contador de palabars) o si estábamos DENTRO de una palabra (en cuyo caso no se incrementa).\n",
    "\n",
    "Esto sugiere tener un diagrama de estados con dos estados (FUERA y DENTRO), más un tercer estado final FIN, al que se llega cuando se agota el string.\n",
    "\n",
    "El siguiente diagrama modela este proceso, donde el caracter que se está examinando en cada momento es $s[k]$. Para simplificar, suponemos que las transiciones hacia FIN tienen prioridad. Además, como en cada transición se examina un nuevo caracter, dejaremos implícita la inicialización $k=0$ y el incremento $k+=1$ que hay después de cada transición.\n",
    "\n",
    "![Diagrama de Estados 2](state-diagram-2.png)\n",
    "\n",
    "Una vez modelado el proceso mediante un diagrama de estados, debemos escribirlo en forma de un programa. Veremos a continuación que **hay más de una manera de hacerlo**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Contar palabras, versión 1 con variables de estado\n",
    "def contar_palabras(s):\n",
    "    np=0\n",
    "    estado=\"FUERA\"\n",
    "    for k in range(0,len(s)):\n",
    "        if estado==\"FUERA\":\n",
    "            if s[k]!=' ':\n",
    "                np+=1\n",
    "                estado=\"DENTRO\"\n",
    "        else: # estado==\"DENTRO\"\n",
    "            if s[k]==' ':\n",
    "                estado=\"FUERA\"\n",
    "    return np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s=input(\"Escriba frase: \")\n",
    "print(\"Hay\", contar_palabras(s), \"palabras\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Contar palabras, versión 2 con variables de estado\n",
    "def contar_palabras(s):\n",
    "    np=0\n",
    "    estado=\"FUERA\"\n",
    "    for k in range(0,len(s)):\n",
    "        if s[k]==' ':\n",
    "            estado=\"FUERA\"\n",
    "        else: # s[k]!=' '\n",
    "            if estado==\"FUERA\":\n",
    "                np+=1\n",
    "            estado=\"DENTRO\"\n",
    "    return np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s=input(\"Escriba frase: \")\n",
    "print(\"Hay\", contar_palabras(s), \"palabras\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Contar palabras, versión sin variables de estado\n",
    "def contar_palabras(s):\n",
    "    np=0\n",
    "    k=0\n",
    "    while k<len(s):\n",
    "        # Estamos en el estado FUERA\n",
    "        if s[k]!=' ':\n",
    "            np+=1\n",
    "            k+=1\n",
    "            # Ahora estamos en el estado DENTRO\n",
    "            while k<len(s) and s[k]!=' ':\n",
    "                k+=1\n",
    "            if k==len(s):\n",
    "                break\n",
    "            # Por descarte, s[k]==' '\n",
    "        k+=1\n",
    "    return np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s=input(\"Escriba frase: \")\n",
    "print(\"Hay\", contar_palabras(s), \"palabras\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 1.4\n",
    "\n",
    "Se le llama \"Camel Case\" a la convención de escribir una frase sin espacios, pero marcando el inicio de cada palabra poniendo su primera letra en mayúscula. Por ejemplo, la frase\n",
    "```\n",
    "\"  Algoritmos y    estructuras de   datos   \"\n",
    "```\n",
    "transformada a Camel Case queda así:\n",
    "```\n",
    "\"AlgoritmosYEstructurasDeDatos\"\n",
    "```\n",
    "\n",
    "Escriba una función que transforme a Camel Case y pruébela:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CamelCase(s):\n",
    "    \"\"\"Retorna un string conteniendo la versión Camel Case del string s\"\"\"\n",
    "    # escriba aquí su algoritmo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(CamelCase(\"    Algoritmos y    estructuras de   datos   \"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}