<jupyter_start><jupyter_text>USM Numérica Algoritmos y Funciones Objetivos1. Conocer los conceptos de algoritmo, código y pseudo-código.1. Conectar los conceptos anteriores con la generación de algoritmos y funciones en Python. MotivaciónImagine que Ud. es un trabaja en una compañía de seguros para la cual es necesario evaluar constantemente el nivel de riesgo de un cliente en base a sus antecedentes antes de negociar un producto. ¿Será posible automatizar el proceso con el fin de trabajar menos, mejorar los tiempos de evaluación y hacer el proceso más eficiente?La respuesta a esta y muchas otras preguntas se encuentra en la creación de algoritmos de programación.  0.1 InstruccionesInstrucciones de [instalación](https://github.com/usantamaria/ipynb_para_docencia/wiki/Instalacion) y [utilización](https://github.com/usantamaria/ipynb_para_docencia/wiki/Utilizacion) de un ipython notebook.Recuerden:* Desarrollar los problemas de manera secuencial.* Guardar constantemente con *`Ctr-S`* para evitar sorpresas.* Reemplazar en las celdas de código donde diga *`FIX_ME`* por el código correspondiente.* Ejecutar cada celda de código utilizando *`Ctr-Enter`* 0.2 Licenciamiento y ConfiguraciónEjecutar la siguiente celda mediante *`Ctr-Enter`*.<jupyter_code>"""
IPython Notebook v4.0 para python 3.0
Librerías adicionales: 
Contenido bajo licencia CC-BY 4.0. Código bajo licencia MIT. 
(c) <NAME>, <NAME>, <NAME>, <NAME>.
"""
# Configuración para recargar módulos y librerías dinámicamente
%reload_ext autoreload
%autoreload 2

# Configuración para graficos en línea
%matplotlib inline

# Configuración de estilo
from IPython.core.display import HTML
HTML(open("./style/style.css", "r").read())<jupyter_output><empty_output><jupyter_text>1. Definiciones y conceptos básicos.Entenderemos por **algoritmo** a una serie de pasos que persiguen un objetivo específico. Intuitivamente lo podemos relacionar con una receta de cocina: una serie de pasos bien definidos (sin dejar espacio para la confusión del usuario) que deben ser realizados en un orden específico para obtener un determinado resultado.   En general un buen algoritmo debe poseer las siguientes características:    1. No debe ser ambiguo en su implementación para cualquier usuario.  2. Debe definir adecuadamente datos de entrada (inputs).  3. Debe producir datos de salida (outputs) específicos.  4. Debe poder realizarse en un número finito de pasos y por ende, en un tiempo finito. ( Ver [The Halting Problem](https://es.wikipedia.org/wiki/Problema_de_la_parada) ).Por otra parte, llamaremos **código** a la materialización, en base a la implementación en la sintaxis adecuada de un determinado lenguaje de programación, de un determinado algoritmo. Entonces, para escribir un buen código y que sea eficiente debe tratar de respetar las ideas anteriores: se debe desarrollar en un número finito de pasos, ocupar adecuadamente las estructuras propias del lenguaje, se debe poder ingresar y manipular adecuadamente los datos de entrada y finalmente entregar el resultado deseado.  A diferencia de lo anterior, una idea un poco menos estructurada es el concepto de **pseudo-código**. Entenderemos por el anterior a la descripción informal de un determinado algoritmo en un determinado lenguaje de programación. Sin embargo, no debe perder las características esenciales de un algoritmo como claridad en los pasos, inputs y outputs bien definidos, etc. de tal forma que permita la implementación directa de éste en el computador.Una vez implementado un algoritmo viene el proceso de revisión de éste. Para realizar adecuadamente lo anterior se recomienda contestar las siguentes preguntas: 1. ¿Mi algoritmo funciona para todos los posibles datos de entrada? 2. ¿Cuánto tiempo tomará en correr mi algoritmo? ¿Cuánta memoria ocupa en mi computador? 3. Ya que sé que mi algoritmo funciona: ¿es posible mejorarlo? ¿Puedo hacer que resuelva mi problema más rápido?  2. Un ejemplo sencillo: Programa para números primos.A continuación estudiamos el problema de determinar si un número entero $N\geq 2$ es primo o no. Consideremos los siguientes números: 8191 (primo), 8192 (compuesto), 49979687 (primo), 49979689 (compuesto).  2.1 Primer programaNuestro primer **algoritmo** para determinar si un numero es primo es: verificar que *ningún* número entre $2$ y $N-1$ sea divisor de $N$.El **pseudo-código** es:1. Ingresar un determinado número $N$ mayor a 1.2. Si el número es 2 o 3, el numero es primo. Sino, se analizan los restos de la división entre $2$ y $N-1$. Si ningún resto es cero, entonces el numero $N$ es primo. En otro caso, el número no es primo.El **código** es el siguiente:<jupyter_code>N = int(raw_input("Ingrese el numero que desea estudiar "))
if N<=1:
    print("Numero N tiene que ser mayor o igual a 2")
elif 2<=N<=3:
    print("{0} es primo".format(N))
else:
    es_primo = True
    for i in range(2, N):
        if N%i==0:
            es_primo = False
    if es_primo:
        print("{0} es primo".format(N))
    else:
        print("{0} es compuesto".format(N))<jupyter_output>Ingrese el numero que desea estudiar 49979689
49979689 no es primo<jupyter_text>2.2 Segundo ProgramaAl utilizar números grandes ($N=10^7$, por ejemplo) nos damos cuenta que el algoritmo anterior tarda mucho tiempo en ejecutar, y que recorre todos los numeros. Sin embargo, si se encuentra un divisor ya sabemos que el número no es primo, pudiendo detener inmediatamente el algoritmo. Esto se consigue utilizando únicamente una línea extra, con una sentencia `break`. El **algoritmo** para verificar si un numero no primo es: verificar si *algún* numero entre $2$ y $N-1$ es divisor de $N$.El **pseudo-código** es:1. Ingresar un determinado número $N$ mayor a 1.2. Si el número es 2 o 3, el numero es primo. Sino, se analizan los restos de la división entre $2$ y $N-1$. Si alguno de los restos es cero, entonces el numero $N$ es divisible, y no es primo.Mientras que el **código** es el siguiente:<jupyter_code>N = int(raw_input("Ingrese el numero que desea estudiar "))
if N<=1:
    print("Numero N tiene que ser mayor o igual a 2")
elif 2<=N<=3:
    print("{0} es primo".format(N))
else:
    es_primo = True
    for i in range(2, N):
        if N%i==0:
            es_primo = False
            break
    if es_primo:
        print("{0} es primo".format(N))
    else:
        print("{0} es compuesto".format(N))<jupyter_output>Ingrese el numero que desea estudiar 49979689
49979689 no es primo<jupyter_text>La ejecución de números grandes compuestos se detiene en el primer múltiplo cuando el número es compuesto. Sin embargo, para numeros grandes y primos tarda bastante.  2.3 Tercer ProgramaUn último truco que podemos utilizar para verificar más rápidamente si un número es primo es verificar únicamente parte del rango de los múltiplos. Esto se explica mejor con un ejemplo. Consideremos el número 16: los multiplos son 2, 4 y 8. Como el número es compuesto, nuestro algoritmo anterior detecta rápidamente que 2 es un factor, detiene el algoritmo e indica que el número 12 no es primo. Consideremos ahora el numero 17: es un número primo y no tiene factores, por lo que el algoritmo revisa los numeros 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 y 16. Sin embargo, sólo es necesario revisar los números 2, 3, 4, 5 y 6 porque para que exista un factor mayor a 6, tiene que simultáneamente haber un factor menor a 6 tal que la multiplicación sea 17. Esto es, basta revisar los factores más pequeños, donde la cota está dada por el entero más cercano a $\sqrt{17}$ o en general, $\sqrt{N}$. El **algoritmo** para verificar si un numero no primo es: verificar si *algún* numero entero entre $2$ y $\sqrt{N}$ es divisor de $N$.El **pseudo-código** es:1. Ingresar un determinado número $N$ mayor a 1.2. Si el número es 2 o 3, el numero es primo. Sino, se analizan los restos de la división para cada número entre $2$ y $\sqrt{N-1}$. Si alguno de los restos es cero, entonces el numero $N$ es divisible, y no es primo.Mientras que el **código** es el siguiente:<jupyter_code>N = int(raw_input("Ingrese el numero que desea estudiar "))
if N<=1:
    print("Numero N tiene que ser mayor o igual a 2")
elif 2<=N<=3:
    print("{0} es primo".format(N))
else:
    es_primo = True
    for i in range(2, int(N**.5)):
        if N%i==0:
            es_primo = False
            break
    if es_primo:
        print("{0} es primo".format(N))
    else:
        print("{0} no es primo".format(N))<jupyter_output>Ingrese el numero que desea estudiar 49979687
49979687 es primo<jupyter_text>3. Midiendo la complejidadComo dijimos anteriormente luego de hacer que un algoritmo funcione, una de las preguntas más importantes es la revisión de éste haciendo énfasis en la medición del tiempo que necesita para resolver el problema. Así, la primera interrogante es: ¿cómo podemos medir el tiempo que tarda un algoritmo en relación al tamaño del problema que resuelve? Esto se denomina usualmente como complejidad temporal o, en inglés, como **time complexity** o **escalability**.Sin embargo es importante notar que medir la complejidad temporal de un algoritmo puede resultar un poco complejo puesto que: **(a)** El tiempo que toma al computador realizar las distintas operaciones en general es heterogeneo, es decir, realizar una suma es mucho más rápido que hacer una división, **(b)** Computadores distintos puede realizar un determinado experimento en tiempos distintos.La notación estándar para la complejidad de un algoritmo es mediante la letra mayúscula **O**, por lo que la complejidad de alguna función la podemos expresar por O("función"), lo que podemos interpretar como que el número de operaciones es proporcional a la función por una determinada constante. Las complejidades más importantes son:1. O(1) es un algoritmo de complejidad temporal constante, es decir, el número de operaciones del algoritmo realmente no varía mucho si el tamaño del problema crece.2. O(log(n)) es la complejidad logarítmica.3. O(n) significa que la complejidad del problema es lineal, es decir, doblar el tamaño del problema dobla el tamaño requerido para su solución.4. O($n^2$) significa complejidad cuadrática, es decir, doblar el tamaño del problema cuatriplica el tiempo requerido para su solución.5. O($2^n$) y en general O($a^n$), $a>1$, posee complejidad exponencial.En nuestros algoritmos anteriormente desarrollados:1. El primer algoritmo tiene complejidad $O(N)$: siempre tarda lo mismo.2. El segundo algoritmo tiene complejidad variable: si el numero es compuesto tarda en el mejor de los casos O($1$) y O($\sqrt{N}$) en el peor de los casos (como 25, o cualquier numero primo al cuadrado), pero si es primo tarda O($N$), pues verifica todos los posibles múltiplos.2. El segundo algoritmo tiene complejidad variable: si el numero es compuesto tarda en ambos casos a lo más O($\sqrt{N}$), pues verifica solo los multiplos menores.  Desafío1. A2. B3. C  FuncionesCuando un algoritmo se utiliza muy seguido, resulta conveniente encapsular su utilización en una función. Ahora bien, resulta importante destacar que en informática una función no tiene el mismo significado que en matemáticas. Una función (en python) es simplemente una sucesión de acciones que se ejecutan sobre un conjunto de variables de entrada para producir un conjunto de variables de salida.La definición de funciones se realiza de la siguiente forma:```def nombre_de_funcion(variable_1, variable_2, variable_opcional_1=valor_por_defecto_1, ...):    accion_1    accion_2    return valor_1, valor_2```A continuación algunos ejemplos.<jupyter_code>def sin_inputs_ni_outputs():
    print "<NAME>"
    
def sin_inputs():
    return "42"

def sin_outputs(a,b):
    print a
    print b

def con_input_y_output(a,b):
    return a+b

def con_tuti(a,b,c=2):
    return a+b*c<jupyter_output><empty_output><jupyter_text>La función `sin_inputs_ni_outputs` se ejecuta sin recibir datos de entrada ni producir datos de salida (Y no es muy útil).<jupyter_code>sin_inputs_ni_outputs()<jupyter_output>H<NAME><jupyter_text>La función `sin_inputs` se ejecuta sin recibir datos de entrada pero si produce datos de salida.<jupyter_code>x = sin_inputs()
print("El sentido de la vida, el universo y todo lo demás es: "+x)<jupyter_output>El sentido de la vida, el universo y todo lo demás es: 42<jupyter_text>La función `con_input_y_output` se ejecuta con datos de entrada y produce datos de salida. Cabe destacar que como python no utiliza tipos de datos, la misma función puede aplicarse a distintos tipos de datos mientras la lógica aplicada dentro de la función tenga sentido (y no arroje errores).<jupyter_code>print con_input_y_output("uno","dos")
print con_input_y_output(1,2)
print con_input_y_output(1.0, 2)
print con_input_y_output(1.0, 2.0)<jupyter_output>unodos
3
3.0
3.0<jupyter_text>La función `con_tuti` se ejecuta con datos de entrada y valores por defecto, y produce datos de salida.<jupyter_code>print con_tuti(1,2)
print con_tuti("uno","dos")
print con_tuti(1,2,c=3)
print con_tuti(1,2,3)
print con_tuti("uno","dos",3)<jupyter_output>5
unodosdos
7
7
unodosdosdos
{'fraction_non_alphanumeric': 0.0720293622878116, 'fraction_numerical': 0.019804251414589386, 'mean_word_length': 4.718845649322256, 'pattern_counts': {'":': 0, '<': 45, '<?xml version=': 0, '>': 37, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '303663', 'license': 'MIT', 'n_tokens_mistral': 4505, 'n_tokens_neox': 4431, 'n_words': 1821, 'path': '02_python/algoritmos_y_funciones.ipynb', 'repo_name': 'sebastiandres/workshop_unsa_ar', 'size': '13120'}