Resumen Parcial 5 PDF

FICHA 14 Introducción La recursividad es una técnica de programación donde una función se llama a sí misma para resolver un problema. Es útil para problemas que pueden dividirse en subproblemas más pequeños del mismo tipo. Definiciones Recursivas Una definición es recursiva si el objeto o concepto q...

FICHA 14 Introducción La recursividad es una técnica de programación donde una función se llama a sí misma para resolver un problema. Es útil para problemas que pueden dividirse en subproblemas más pequeños del mismo tipo. Definiciones Recursivas Una definición es recursiva si el objeto o concepto que se define aparece en la propia definición. Es crucial evitar la recursión infinita, asegurando que haya una condición base que termine la recursión. Programación Recursiva En programación, una función recursiva incluye una o más llamadas a sí misma. Es esencial que estas funciones tengan una condición de corte para evitar bucles infinitos. Un ejemplo clásico es el cálculo del factorial de un número. Seguimiento de la Recursividad El seguimiento de una función recursiva implica entender cómo se asigna memoria para cada llamada recursiva y cómo se gestionan las instancias en la pila de ejecución. Cada llamada recursiva crea una nueva instancia con sus propias variables locales. Aplicaciones de la Recursividad La recursividad se puede usar para resolver problemas complejos de manera más sencilla y compacta. Un ejemplo es una función que imprime mensajes numerados de forma ascendente sin usar bucles. Consideraciones Generales La recursividad puede ser difícil de entender al principio, pero con práctica se vuelve más intuitiva. Es importante plantear correctamente la condición de corte y ser consciente del consumo de memoria y tiempo de ejecución. Caso de Análisis: Sucesión de Fibonacci La sucesión de Fibonacci es un ejemplo clásico de recursividad, donde cada término es la suma de los dos anteriores. La versión recursiva es más simple de entender pero puede ser ineficiente en términos de tiempo de ejecución. Aplicaciones Avanzadas: Gráficos Fractales La recursividad es útil para generar gráficos fractales, que son figuras compuestas por versiones más pequeñas de sí mismas. Un ejemplo es la pirámide fractal, que se puede dibujar usando una función recursiva en Python. FICHA 22 Tema Principal: Algoritmos de ordenamiento y sus clasificaciones. La ficha presenta una introducción detallada a los algoritmos de ordenamiento, clasificándolos en dos categorías principales: Algoritmos Simples o Directos  Intercambio Directo (Burbuja): Compara elementos adyacentes e intercambia si están en el orden incorrecto. Repite este proceso hasta que el arreglo esté ordenado.  Selección Directa: Encuentra el elemento mínimo en cada pasada y lo coloca en su posición correcta.  Inserción Directa: Construye un subarreglo ordenado y en cada iteración inserta el siguiente elemento en su posición correcta dentro del subarreglo ordenado. Estos algoritmos son fáciles de entender e implementar, pero su eficiencia disminuye significativamente a medida que aumenta el tamaño del arreglo. Algoritmos Compuestos o Mejorados  Quicksort: Divide el arreglo en dos subarreglos, uno con elementos menores que un pivote y otro con elementos mayores. Aplica recursivamente el mismo proceso a los subarreglos.  Heapsort: Utiliza una estructura de datos llamada heap para ordenar los elementos.  Shellsort: Es una mejora del algoritmo de inserción directa que utiliza incrementos decrecientes para reducir el número de comparaciones. Estos algoritmos son más eficientes que los simples, especialmente para grandes conjuntos de datos. Características clave de cada algoritmo:  Quicksort: Generalmente el más rápido, pero su eficiencia depende de la elección del pivote.  Heapsort: Garantiza un tiempo de ejecución de O(n log n) en el peor caso, pero es más complejo de implementar.  Shellsort: Un buen compromiso entre eficiencia y simplicidad. Puntos Clave:   Complejidad: La eficiencia de un algoritmo se mide en términos de su complejidad temporal, que indica cómo aumenta el tiempo de ejecución del algoritmo a medida que aumenta el tamaño de la entrada.  Comparaciones e intercambios: El número de comparaciones e intercambios realizados por un algoritmo afecta directamente a su tiempo de ejecución.  Elección del algoritmo: La elección del algoritmo de ordenamiento adecuado depende del tamaño del conjunto de datos, la naturaleza de los datos y los requisitos de tiempo y espacio FICHA 27 Notación Big O La notación Big O se utiliza para expresar el rendimiento de un algoritmo en términos de su tiempo de ejecución o espacio de memoria en función del tamaño del problema (n). Las funciones de orden más comunes son:  O(1): Tiempo constante, independiente del tamaño del problema.  O(log(n)): Tiempo logarítmico, típico en algoritmos que dividen el problema en partes más pequeñas.  O(n): Tiempo lineal, donde cada dato se procesa una vez.  O(nlog(n))*: Algoritmos que dividen el problema y combinan las soluciones.  O(n²): Tiempo cuadrático, común en algoritmos con ciclos anidados.  O(n³): Tiempo cúbico, en algoritmos con tres ciclos anidados.  O(2^n): Tiempo exponencial, en algoritmos que exploran todas las combinaciones posibles. Ejemplos de Algoritmos  Búsqueda Secuencial: O(n) en el peor caso, cuando el valor buscado está al final o no está en el arreglo.  Búsqueda Binaria: O(log(n)) en el peor caso, dividiendo el arreglo en dos partes sucesivamente.  Ordenamiento por Selección Directa: O(n²) en el peor caso, con dos ciclos anidados.   Quicksort: O(n*log(n)) en el caso promedio, pero puede ser O(n²) en el peor caso.  Multiplicación de Matrices: O(n³) en el peor caso, con tres ciclos anidados. Consideraciones Prácticas Para analizar un algoritmo, se debe: 1. Determinar el tamaño del problema (n). 2. Identificar la instrucción crítica que se ejecuta más veces. 3. Realizar un análisis asintótico para encontrar el término dominante y expresar el tiempo de ejecución en notación Big O. Otras Notaciones  Omega (Ω): Indica un límite inferior para el tiempo de ejecución.  Theta (Θ): Indica que el tiempo de ejecución está acotado tanto superior como inferiormente por una función.  o(): Indica una relación de menor estricto, útil para expresar que un algoritmo es subcuadrático, por ejemplo FICHA 28: Tipos Nativos y Tipos Abstractos Los lenguajes de programación, como Python, ofrecen estructuras de datos nativas como tuplas, listas y diccionarios. Sin embargo, a veces los programadores necesitan crear estructuras abstractas específicas para sus problemas, como un tipo Libro para una biblioteca. Estructuras de Datos Lineales y No Lineales Las estructuras de datos lineales, como pilas y colas, tienen un único sucesor y antecesor inmediato. En cambio, las estructuras no lineales, como árboles y grafos, pueden tener múltiples sucesores o antecesores. Pilas Una pila es una estructura LIFO (Last In, First Out), donde el último elemento en entrar es el primero en salir. Las operaciones principales son push() para insertar y pop() para eliminar el elemento del frente. Las pilas son útiles para invertir secuencias de entrada. Colas Una cola es una estructura FIFO (First In, First Out), donde el primer elemento en entrar es el primero en salir. Las operaciones principales son add() para insertar y remove() para eliminar el elemento del frente. Las colas son útiles para simular situaciones de espera. Implementación en Python Tanto pilas como colas pueden implementarse usando arreglos unidimensionales en Python. Los métodos append() y del facilitan la gestión dinámica de estos arreglos. Aplicaciones de Pilas Las pilas pueden usarse para verificar si una cadena es capicúa (se lee igual de izquierda a derecha y viceversa). El proceso implica almacenar la mitad de la cadena en una pila y luego comparar con la otra mitad. FICHA 29 Introducción Los árboles binarios de búsqueda son estructuras de datos no lineales que permiten organizar y gestionar datos de manera eficiente. Son especialmente útiles cuando el conjunto de datos crece de forma impredecible y se requiere un acceso rápido para inserciones, eliminaciones y búsquedas. Definiciones y Conceptos Un árbol binario es una estructura de datos en la que cada nodo tiene como máximo dos hijos, denominados hijo izquierdo e hijo derecho. La raíz es el nodo principal del árbol, y cada subárbol también es un árbol binario. Los nodos se organizan de manera que el subárbol izquierdo contiene valores menores que la raíz, y el subárbol derecho contiene valores mayores. Árboles Binarios de Búsqueda Un árbol binario de búsqueda (BST) es un tipo de árbol binario que mantiene sus nodos en un orden específico para facilitar la búsqueda. En un BST, para cada nodo, todos los valores en el subárbol izquierdo son menores que el valor del nodo, y todos los valores en el subárbol derecho son mayores. Operaciones Básicas 1. Inserción: Para insertar un valor en un BST, se compara el valor con la raíz y se decide si debe ir al subárbol izquierdo o derecho, repitiendo el proceso recursivamente hasta encontrar la posición correcta.  2. Búsqueda: Similar a la inserción, se compara el valor buscado con la raíz y se sigue el camino correspondiente (izquierda o derecha) hasta encontrar el valor o llegar a un nodo nulo. 3. Eliminación: La eliminación de un nodo en un BST puede ser más compleja y se divide en tres casos: o Nodo sin hijos (hoja): Se elimina directamente. o Nodo con un solo hijo: Se reemplaza el nodo por su hijo. o Nodo con dos hijos: Se encuentra el sucesor inorden (el menor valor en el subárbol derecho) y se reemplaza el nodo a eliminar por este sucesor. Recorridos de Árboles Existen tres tipos principales de recorridos en un árbol binario: 1. Preorden: Se visita la raíz, luego el subárbol izquierdo y finalmente el subárbol derecho. 2. Inorden: Se visita el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho. En un BST, este recorrido produce los valores en orden ascendente. 3. Postorden: Se visita el subárbol izquierdo, luego el subárbol derecho y finalmente la raíz. Implementación en Python El documento incluye una implementación básica de un BST en Python, con clases para representar nodos (TreeNode) y el árbol (SearchTree). Los métodos principales incluyen add() para insertar, remove() para eliminar, y contains() para buscar valores en el árbol. Consideraciones Finales La eficiencia de un BST depende de su balance. Un árbol desbalanceado puede degradarse a una estructura lineal, perdiendo las ventajas de tiempo de búsqueda O(log(n)). Para mantener el balance, existen variantes como los árboles AVL y los árboles rojo-negro, que ajustan automáticamente la estructura del árbol durante las inserciones y eliminaciones. FICHA 30 Introducción Los grafos son estructuras de datos no lineales que permiten modelar relaciones entre objetos. Son útiles en problemas donde las relaciones entre elementos son tan importantes como los elementos mismos, como en sociología o en la optimización de rutas de transporte. Tipos de Grafos 1. Grafos Dirigidos: Los arcos tienen una dirección, indicando un punto de partida y uno de llegada. 2. Grafos No Dirigidos: Los arcos no tienen dirección, representando una relación bidireccional. 3. Grafos Ponderados: Los arcos tienen un peso o valor asociado, que puede representar distancia, costo, etc. Definiciones y Terminología Básica  Vértices: Los nodos del grafo.  Arcos: Las conexiones entre los vértices.  Camino: Una secuencia de arcos que conecta dos vértices.  Ciclo: Un camino que comienza y termina en el mismo vértice.  Grafo Conexo: Un grafo donde existe al menos un camino entre cualquier par de vértices.  Componente Conexa: Subgrafo en el que cualquier par de vértices está conectado. Implementación Matricial de Grafos Los grafos pueden implementarse usando una matriz de adyacencia, donde las filas representan los vértices de partida y las columnas los vértices de llegada. En un grafo dirigido, un valor True en la matriz indica la existencia de un arco entre dos vértices. En un grafo no dirigido, la matriz es simétrica. Implementación en Python El documento incluye ejemplos de implementación de grafos dirigidos y no dirigidos en Python, utilizando matrices de adyacencia. Se presentan métodos para agregar y eliminar arcos, verificar la existencia de arcos, y calcular el grado de los nodos. FICHA 31 Tema principal: Algoritmo Quicksort y la estrategia Divide y Vencerás Quicksort es un algoritmo de ordenamiento eficiente que utiliza la estrategia Divide y Vencerás. Esta estrategia consiste en dividir un problema en subproblemas más pequeños, resolverlos de forma recursiva y luego combinar las soluciones. Cómo funciona Quicksort: 1. Selección de un pivote: Se elige un elemento del arreglo (el pivote). 2. Particionamiento: Se reorganizan los elementos del arreglo de modo que todos los elementos menores al pivote estén a su izquierda y los mayores a su derecha. 3. Llamadas recursivas: Se aplica el mismo proceso a las sublistas resultantes de la partición. 4. Combinación: Al llegar a sublistas de tamaño 1, el arreglo queda ordenado. Ventajas de Quicksort:  Eficiencia: En promedio, tiene un tiempo de ejecución de O(n log n), lo que lo hace muy eficiente para grandes conjuntos de datos.  Flexibilidad: Se puede adaptar a diferentes tipos de datos y estructuras. Desventajas de Quicksort:  Peor caso: En el peor caso, su tiempo de ejecución puede ser cuadrático (O(n²)).  Recursividad: El uso de recursividad puede consumir mucha memoria en casos extremos. Mejoras en Quicksort:  Selección del pivote: o Mediana de tres: Se selecciona el pivote como la mediana de los elementos inicial, central y final de la partición, reduciendo la probabilidad de caer en el peor caso.  Optimizaciones: Existen otras técnicas para mejorar el rendimiento de Quicksort, como la optimización de la partición y el uso de algoritmos de ordenamiento más simples para sublistas pequeñas. Estrategia Divide y Vencerás:   Aplicabilidad: Se puede aplicar a una amplia variedad de problemas, como búsqueda, ordenamiento, multiplicación de matrices, etc.  Eficiencia: Al dividir el problema en subproblemas más pequeños, se puede reducir la complejidad del algoritmo.  Recursividad: La recursividad es una herramienta clave para implementar esta estrategia. Conclusiones:  Quicksort es un algoritmo de ordenamiento poderoso y versátil, pero su eficiencia depende de la elección del pivote y de la implementación.  La estrategia Divide y Vencerás es una herramienta fundamental en el diseño de algoritmos eficientes.  Al comprender los principios de Quicksort y la estrategia Divide y Vencerás, se pueden desarrollar algoritmos más eficientes para resolver una amplia variedad de problemas. FICHA 32 Introducción El documento aborda diversas estrategias para resolver problemas algorítmicos, destacando la importancia de la paciencia, creatividad y disciplina en la programación. Se mencionan varias técnicas básicas que ayudan a plantear algoritmos eficientes. Estrategias Principales 1. Fuerza Bruta: Explora todas las posibles combinaciones de soluciones, siendo intuitiva pero generalmente ineficiente. 2. Recursión: Permite que un proceso se invoque a sí mismo, útil para problemas complejos, pero puede ser costosa en términos de memoria y tiempo. 3. Backtracking: Explora soluciones parciales y descarta aquellas que no pueden ser válidas, eficiente para problemas de optimización combinatoria. 4. Algoritmos Ávidos: Toman decisiones locales óptimas con la esperanza de encontrar una solución global óptima, aunque no siempre garantizan la mejor solución.  5. Divide y Vencerás: Divide el problema en subproblemas más pequeños, los resuelve recursivamente y combina las soluciones. 6. Programación Dinámica: Almacena soluciones de subproblemas en una tabla para evitar cálculos redundantes, útil en problemas de optimización. 7. Randomización: Utiliza elementos aleatorios para encontrar soluciones aproximadas en problemas donde los algoritmos deterministas son ineficientes. Ejemplos y Aplicaciones  Problema del Cambio de Monedas: Se presentan soluciones utilizando algoritmos ávidos y programación dinámica.  Problema de las Ocho Reinas: Se utiliza backtracking para encontrar todas las soluciones posibles en un tablero de ajedrez.