USM Numérica

Algoritmos y Funciones

Objetivos

1. Conocer los conceptos de algoritmo, código y pseudo-código.
2. Conectar los conceptos anteriores con la generación de algoritmos y funciones en Python.

Motivación

Imagine 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 Instrucciones

Instrucciones de instalación y utilización 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ón

Ejecutar la siguiente celda mediante Ctr-Enter.

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 ).

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 programa

Nuestro 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:

2.2 Segundo Programa

Al 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:

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 Programa

Un ú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:

3. Midiendo la complejidad

Como 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.
3. 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ío

1. A
2. B
3. C

Funciones

Cuando 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.

La función sin_inputs_ni_outputs se ejecuta sin recibir datos de entrada ni producir datos de salida (Y no es muy útil).

La función sin_inputs se ejecuta sin recibir datos de entrada pero si produce datos de salida.

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).

La función con_tuti se ejecuta con datos de entrada y valores por defecto, y produce datos de salida.

Desafio

1. a
2. b