Tema 8 Algoritmos de Programación en Python.pptx

Algoritmos de Programació n en Python EXPLORANDO EL USO DE LOS ALGORITMOS EN EL LENGUAJE PYTHON Contenido Recursividad Memorización Divide y vencerás Ordenamiento Búsqueda Paralelismo Presentac ión En esta presentación, se presenta...

Algoritmos de Programació n en Python EXPLORANDO EL USO DE LOS ALGORITMOS EN EL LENGUAJE PYTHON Contenido Recursividad Memorización Divide y vencerás Ordenamiento Búsqueda Paralelismo Presentac ión En esta presentación, se presentará una introducción a los algoritmos de programación y su aplicación en el lenguaje de programación Python. Se cubrirán los conceptos básicos de los algoritmos y cómo se pueden implementar en Python para resolver problemas complejos. Introducción Algoritmo es el término que usamos para referirnos a un método para hacer algo. Los científicos de computadoras estudian nuevos métodos (algoritmos) para realizar algo. Uno de los retos más comunes es el ordenamiento de datos, por lo que existen múltiples algoritmos de ordenamiento, los cuales pudieran desempeñarse de mejor o peor manera dependiendo de la situación. Introducción a ¿Qué son los algoritmos de programación? Los algoritmos de programación son secuencias lógicas de instrucciones que le los algoritmos dicen a una computadora cómo realizar una tarea. Estos algoritmos pueden de variar en complejidad y tamaño según la tarea que se quiera realizar. programación ¿Cómo funcionan los algoritmos de programación? Los algoritmos de programación funcionan mediante la entrada de datos, procesamiento y salida de los resultados. El proceso de entrada, procesamiento y salida se repite a medida que se ejecuta el algoritmo hasta que se alcanza la solución deseada. Ordenar una lista La tarea de ordenar una lista de elementos es común en la programación y se puede realizar mediante el uso de algoritmos como el de burbuja o el de selección. Encontrar el valor máximo Encontrar el valor máximo en una lista de elementos también es una tarea común en la programación y se puede realizar mediante el uso de algoritmos como el de búsqueda lineal o el de búsqueda binaria. Algoritmos Existen diferentes tipos de algoritmos de programación y técnicas de resolución de problemas: Cuantitativos – Su resultado es un valor específico que proviene de cálculos. Cualitativos – Resultan de la revisión de condiciones Recursividad ES UNA TÉCNICA DE UNA FUNCIÓN TODO PROBLEMA QUE RESOLVER UN PROBLEMA SE BASA EN LA SOLUCIÓN DE RECURSIVA ES UNA PUEDA SER RESUELTO DE MEDIANTE RECURSIÓN RECURRENCIA. PROBLEMAS. FUNCIÓN QUE SE LLAMA FORMA RECURSIVA, SIGNIFICA QUE LA A SÍ MISMA. PUEDE SER RESUELTO SOLUCIÓN DEPENDE DE USANDO CICLOS. LAS SOLUCIONES DE PEQUEÑAS INSTANCIAS DEL MISMO PROBLEMA. Construir un programa recurrente Cada llamada recurrente se debe definir sobre un problema de menor complejidad (algo más fácil de resolver). Ha de existir al menos un caso base para evitar que la recurrencia sea infinita. DRA. PERLA MARLENE VIERA GONZÁLEZ  función factorial: Ejemplo input: entero n de forma que n >= 0 de output: [n × (n-1) × (n-2) × … × 1] recursivid ad: 1. if n es 0, return 1 Factorial 2. else, return [ n × factorial(n-1) ] end factorial Algoritmos recursivos y algoritmos iterativos Llamaremos algoritmos recursivos a Todo algoritmo recursivo puede aquellos que realizan llamadas expresarse como iterativo y recursivas para llegar al resultado, viceversa. Sin embargo, según las y algoritmos iterativos a aquellos que condiciones del problema a resolver llegan a un resultado a través de una podrá ser preferible utilizar la iteración mediante un ciclo definido o solución recursiva o la iterativa. indefinido. Memorización (memoización) Técnica de optimización usada principalmente para acelerar programas de computadoras a través de almacenar los resultados de llamadas “costosas” a funciones y retornando el resultado almacenado en el caché cuando los mismos parámetros de entrada vuelven a ocurrir. Se considera un caso específico de optimización. Usos de la Se usa para acelerar el trabajo de traductores (parsers), es decir, en programas que interpretan lenguajes. memorizaci ón Es útil en todos los problemas donde el resultado de una operación reciente volverá a ser preguntado de nuevo. Algunos aceleradores de traducción de lenguajes almacenan los resultados de las llamadas a funciones automáticamente (auto memoización), para que la función no sea ejecutada la próxima vez que sea llamada. De aquí evolucionaron los búferes y se diseñó el algoritmo de reemplazo de páginas para sistemas operativos. Pivote Puede ser una variable temporal para solucionar un problema, como un intercambio de valores. También se define como un elemento específico de un arreglo o conjunto de datos que tomamos como referencia para hacer un determinado algoritmo a partir de él. Python no requiere pivotes para intercambio de valores a = int(input("Ingresa el valor de a: ")) b = int(input("Ingresa el valor de b: ")) (a,b) = (b,a) print('a: ',a) print('b: ',b) c = int(input("Ingresa el valor de c: ")) (a,b,c) = (c,a,b) print('a: ',a) print('b: ',b) print('c: ',c) Divide y Método basado en la solución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. vencerás (DYV) El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones de los problemas se combinan para dar una solución al problema original. Usos: algoritmos eficientes de ordenamiento (Quicksort, mergesort), multiplicar números grandes, análisis sintácticos y la transformada discreta de Fourier. Algoritmo DYV Función DYV(problema): Si el problema es trivial: resuélvelo Si no es trivial: Descomponer el problema en n subproblemas Para I = 1 hasta n hacer DYV(subproblema_i) Combinar soluciones PROCESO DE TRES PASOS – DIVIDE Y VENCERÁS 1. Divide / Este paso implica dividir el problema en subproblemas más pequeños. Break Los subproblemas deben representar una parte del problema original. Este paso generalmente toma un enfoque recursivo para dividir el problema hasta que ningún subproblema sea más divisible. En esta etapa, los subproblemas se vuelven de naturaleza atómica pero aún representan una parte del problema real 2. Vencer / Resolver Este paso recibe muchos En general, a este nivel, los subproblemas más pequeños que problemas se consideran deben resolverse. "resueltos" por sí mismos 3. Fusionar / Combinar Cuando se resuelven los subproblemas más pequeños, esta etapa los combina de manera recursiva hasta que formulan una solución del problema original. Este enfoque algorítmico funciona de forma recursiva y los pasos de conquistar y fusionar funcionan tan cerca que aparecen como uno solo. Algortimos de ordenamie nto Algoritmos Existen múltiples algoritmos para ordenamiento de arreglos, listas y otras de estructuras de datos. ordenamie Su complejidad puede variar drásticamente, nto así como sus tiempos de ejecución. En general, los algoritmos más sencillos de comprender y programar son los menos eficientes y viceversa. Además, existen algoritmos que funcionan de forma excelente con cantidades grandes de elementos, pero se vuelven ineficientes con cantidades pequeñas. Algoritmos de ordenamiento Los métodos de Para ordenar una lista ordenación pueden ser En la ordenación de de valores se deben internos o externos, datos la eficiencia es el considerar 2 criterios según que los factor que mide la para decidir que elementos a ordenar calidad y rendimiento algoritmo de ordenación estén en memoria de un algoritmo utilizar: principal o en memoria secundaria Cantidad de memoria El tiempo de ejecución utilizada Método de la El primer elemento se compara con el segundo, el burbuja segundo con el tercero y así sucesivamente; Si el elemento a comparar es más pequeño (o grande) que el primero, los elementos se intercambian. Después de la primera iteración, el elemento máximo (o mínimo) se coloca en la última posición. El proceso se repite para el segundo elemento y así sucesivamente. Algoritmo del método de la Burbuja Ordenamie nto por inserción ES UN MÉTODO MUY SIMILAR A CUANDO J U G A M O S C A R TA S 4 3 2 10 12 1 Algoritmo del método de inserción Merge Sort La ordenación por combinación es un algoritmo de ordenación que divide una lista en segmentos de un elemento y, a continuación, fusiona esos segmentos en una lista ordenada. Es un algoritmo de divide y vencerás que es de naturaleza recursiva. La ordenación por fusión funciona dividiendo una matriz de entrada por la mitad, luego ordenando cada mitad y fusionando las dos mitades. Algoritmo de ordenamiento Quick Sort Quick Sort es un algoritmo de ordenamiento muy veloz y eficiente. El algoritmo Quick Sort utiliza la técnica Divide y Vencerás. Quick Sort es un algoritmo de ordenamiento in-place, lo que significa que no se requiere memoria adicional. BÚSQUEDA Búsqueda secuencial o lineal En este tipo de búsqueda, se realiza una búsqueda secuencial de todos los elementos uno por uno. Se verifica cada elemento y si se encuentra una coincidencia, se devuelve ese elemento en particular; de lo contrario, la búsqueda continúa hasta el final de la estructura de datos. Búsqueda de interpolación Este algoritmo de búsqueda funciona en la posición de sondeo del valor requerido. Para que este algoritmo funcione correctamente, la recopilación de datos debe estar ordenada y distribuida equitativamente. Inicialmente, la posición de la sonda es la posición del elemento más intermedio de la colección. Si se produce una coincidencia, se devuelve el índice del elemento. Si el elemento central es mayor que el elemento, la posición de la sonda se calcula nuevamente en la matriz secundaria a la derecha del elemento central. De lo contrario, el elemento se busca en la submatriz a la izquierda del elemento central. Este proceso también continúa en la submatriz hasta que el tamaño de la submatriz se reduce a cero. Búsqueda binaria En la búsqueda binaria tomamos una lista ordenada de elementos y comenzamos a buscar un elemento en el medio de la lista. Si el valor de búsqueda coincide con el valor medio en la lista, completamos la búsqueda. De lo contrario, eliminamos la mitad de la lista de elementos eligiendo si procede con la mitad derecha o izquierda de la lista según el valor del elemento buscado. Esto es posible ya que la lista está ordenada y es mucho más rápida que la búsqueda lineal. Aquí dividimos la lista dada y conquistamos eligiendo la mitad adecuada de la lista. Repetimos esta aproximación hasta que encontremos el elemento o concluyamos sobre su ausencia en la lista. Búsqueda binaria usando recursividad Usamos una lista ordenada de elementos y diseñamos una función recursiva para incluir la lista junto con el índice inicial y final como entrada. Luego, la función de búsqueda binaria se llama a sí misma hasta encontrar el elemento buscado o concluye sobre su ausencia en la lista. PARALELISMO Paralelismo El Paralelismo en la informática, es una función que realiza el procesador para ejecutar varias tareas al mismo tiempo. Es decir, puede realizar varios cálculos simultáneamente, basado en el principio de dividir los problemas grandes para obtener varios problemas pequeños, que son posteriormente solucionados en paralelo. El empleo de la computación paralela se convierte cada día en más grande y rápida, muchos problemas considerados anteriormente muy largos y costosos se han podido solucionar. El paralelismo se ha utilizado para muchas temáticas diferentes, desde bioinformática para hacer plegamiento de proteínas, hasta economía para hacer simulaciones en matemática financiera. Paralelismo En Python el procesamiento en paralelo puede aumentar la cantidad de tareas realizadas por su programa, lo que reduce el tiempo de procesamiento general. Estos ayudan a manejar problemas a gran escala Paralelis mo