Estructuras de Datos y Análisis de Algoritmos
Clase #1
Pasos para resolver computacionalmente un Problema
1. Formulación y Especificación del Problema:
Es el paso más importante. Se nos plantea y hay que entender el problema. Se debe usar abstracción para ver la esencia del problema, de manera que se identifiquen los modelos matemáticos con base en los cuales hacemos una descripción formal del problema. Este es un paso totalmente lógico, se hace con lápiz y papel.
2. Diseño de la Solución:
Escribir un algoritmo en pseudocódigo y en forma general, en términos del o los modelos identificados en el paso #1. Luego viene un proceso de refinamiento del algoritmo hasta llegar a cierto nivel de detalle, esto a gusto del cliente o el programador. Es también un paso lógico, a base de papel y lápiz, independiente de una máquina o un lenguaje.
3. Implementación, Prueba y Depuración:
Escoger la máquina, el lenguaje y el compilador. Esta es la etapa física. Luego hay una etapa de traducción del pseudocódigo al lenguaje elegido. Traducir el o los modelos, los operadores básicos de dicho modelo y el algoritmo, a partir de aquí obtenemos entonces el programa. Para traducir el modelo se necesita una estructura de datos, con la cual ideamos como representar en la computadora al modelo. Debe ser una estructura de datos eficaz, consistente; eficiente y simple. Aquí hay una cierta competitividad entre la eficiencia y la simpleza; debemos decidir hacia cual inclinarnos de acuerdo con la situación real en la que nos encontremos, claro está que lo mejor es encontrar un equilibrio entre ambas. En el caso de la eficiencia, nos encontramos con dos tipos: eficiencia en espacio y eficiencia en tiempo; aquí aparece otra vez el problema de elegir hacia cual de los dos tipos inclinarnos, la escogencia depende del problema y las circunstancias; la desición debe se conciente y justificable.
Después de tener la estructura de datos, se buscan los operadores básicos del modelo. Las herramientas más básicas. Se decide si se quiere tener herramientas primitivas, que es lo mejor, o si se desea tener opciones más elaboradas. Lo mejor es tener algo intermedio, pero nunca algo muy complicado, muy grande. Una vez con los operadores básicos en orden, se traducen al lenguaje, obviamente van de la mano con la estrutura de datos. Si se cambia la estructura de datos, se debe cambiar también los operadores básicos. Después debemos implementar el algoritmo, haciéndolo de manera independiente de la estructura de datos. El código fuente debe ser único, debe funcionar con cualquier estructura de datos. Con todo esto traducido al lenguaje, se obtiene el programa, luego se prueba y se depura.
4. Análisis de la solución:
Ver que sea consistente con el problema planteado. De manera muy básica.
Clase #2
Función de Tiempo de Ejecución de un Algoritmo
Es muy importante que los algoritmos sean eficientes en tiempo, dos algortimos A1 y A2 se comparan según su función de tiempo de ejecución para elegir entre uno y otro.
Cómo calcular la función del tiempo de ejecución de un algoritmo?
La función de tiempo f( ... ) a la que llamaremos T( ... ), está dada por diversos factores que afectan el tiempo de ejecución, a saber:
1. Cantidad de Datos ( Elementos ) o tamaño de la Entrada ==> ( CD ).
2. Cantidad y tipo de instrucciones, analisando la esencia misma del algoritmo, dependiendo de la habilidad del programador ==> ( CTI ).
3. Capacidad del Ejecutor ( máquina, compilador, lenguaje, persona ) ==> ( CE ).
4. Tipo de Entrada; cómo vienen ordenados los datos ==> ( TE ).
Todo lo anterior implica una función con las variables ==> T( CD, CTI, CE, TE ); ahora bien, analisaremos los algoritmos en la misma base del ejecutor, lo que nos interesa en realidad es la esencia base del algoritmo, con un CTI ideal, programador e instrucciones ideales, nos quedan las variables CD = N (n) = cantidad de Datos o Tamaño del problema o Tamaño de la Entrada y el TE ==> T( N, TE ). Según el tipo de entrada podemos encontrar:
- T( N ) = T( n ) ==> Peor tipo de entrada: Es cuando el algortimo dura el mayor tiempo posible, es el tipo de entrada que se debe usar a no ser que se especifique lo contrario.
- T( N ) = T( n ) para el mejor tipo de entrada ==> En este caso es cuando el algoritmo durará lo menos posible, y se debe escribir de forma explícita que es para el mejor tipo de entrada.
- T( N ) = T( n ) para tipo de entrada promedio ==> es un cálculo promedio de la duración, se hace en pocos casos y se debe escribir de manera explícita también.
==> Por ejemplo, sean A1 y A2 dos algoritmos que resuelven el mismo problema, para A1--> T( n) = n^2 + n + k + n2^n + log n + n^2log n + n! + n^n. En la función puede haber cualquier cosa entre sumas y multiplicaciones, mas nunca deben haber restas ni divisiones. Para A2 --> T( n) = n + nlog n + 3^n + n^1.5 + n^0.3, entonces, como pueden ser funciones muy raras, las simplificamos un poco más, haciendo que n tienda a infinito, ya que nos interesan cantidades enormes de datos, entonces reducimos la función a lo que nos dice qué tan rápido crece cuando n tiene a infinito, así obtenemos para A1 --> T( n ) = n^n y para A2 --> T( n ) = 3^n, y así concluimos que es mejor A2 --> 3^n < n^n <-- A1.
Órdenes de Duración
Los típicos son:
- O(1) = función de orden de duración constante, no dependen de "n".
- O(log n) = búsqueda binaria.
- O(n)
- O(n^2)
- O(2^n)
- O(n!)
- O(n^n) = Coloreo de grafos.
----------------------------------------------------
Encontramos dos tipos de algoritmos: Iterativos --> funciones polinomiales, y Recursivos --> logarítmicos, polinomiales, exponenciales, factoriales, entre otros.
Nota: Para información del curso, puede ingresar a la página http://www.ecci.ucr.ac.cr/~skikut/Estructuras%20de%20Datos/ , pagina de la Profesora Sandra Kikut.