Tipos De Algoritmos

TIPOS DE ALGORITMOS
  Cualitativos: Son aquellos en los que se describen los pasos utilizando palabras. Cuantitativos: Son aquellos en los que se utilizan cálculos numéricos para definir los pasos del proceso. Técnica de Vuelta Atrás o Backtracking El proceso general de este tipo de algoritmos se contempla como un método de prueba o búsqueda, que gradualmente construye, de forma sistemática,tareas básicas y las inspecciona para determinar si conducen a la solución del problema. Divide y vencerás: muchos problemas, particularmente aquellos cuya entrada consiste en un array, pueden solucionarse a través de sucesivas reducciones del problema en subproblemas menores y la posterior combinación de dichas soluciones en un único resultados. Los algoritmos de ordenación quicksort y mergesortson algunos ejemplos en los cuales esta técnica se aplica de forma sencilla. Vuelta atrás: casi cualquier problema puede representarse a través de un algoritmo de vuelta atrás. En esta técnica, se consideran todas las posibles elecciones para solucionar un problema y, recursivamente, se resuelven los subproblemas suponiendo una determinada elección. El conjunto de sucesivas llamadas genera un árboldonde cada rama representa una determinada secuencia de elecciones. Así, si existe solución al problema, esta se encontrará finalmente. En general, la vuelta atrás es un método de fuerza bruta muy ineficiente, pero es posible aplicar optimizaciones que reduzcan el tamaño del árbol y, consecuentemente, mejoren la eficiencia del algoritmo. Programación dinámica: se trata de una optimización paraalgoritmos de vuelta atrás. Cuando un determinado subproblema necesita tratarse varias veces (por ejemplo, ramas repetidas en el árbol generado), es posible ahorrar tiempo solucionando una sola vez el subproblema y almacenando la solución en una tabla. Algoritmos voraces: este tipo de algoritmos resultan de utilidad cuando se conoce suficiente información acerca de las posibles elecciones, de talforma que "el caso mejor" pueda determinarse sin necesidad de considerar todas las opciones. Típicamente, los algoritmos voraces no son difíciles de escribir, pero sí de demostrar su corrección. Algoritmos de escalada: la idea básica consiste en comenzar con una mala solución a un determinado problema y, repetidamente, aplicar optimizaciones a la misma hasta que esta sea óptima o satisfaga algúnotro requisito. Algoritmos probabilísticos: hacen uso del azar para alcanzar una solución, basándose en un análisis estadístico que indique que, en un número lo













suficientemente alto de ocasiones, se alcanzará una solución óptima al problema. Un algoritmo pueden además ser: Deterministico, sí en cada paso del algoritmo, es posible predecir la salida para una entradadada. No determinísticos, sí existe uno ó más pasos en el algoritmo, para el cual es posible predecir cual será la salida. Por esa razón se tienen los siguiente tipos de problemas: I) Polinomial: Existe al menos un algoritmo polinomial determinístico que lo resuelve. II) No -Polinomiales: Solo existen algoritmos polinomiales del tipo no deterministico que los resuelven.

DETERMINAR COMPLEJIDAD DEUN ALGORITMO
Aunque no existe una receta que siempre funcione para calcular la complejidad de un algoritmo, si es posible tratar sistematicamente una gran cantidad de ellos, basandonos en que suelen estar bien estructurados y siguen pautas uniformes. Loa algoritmos bien estructurados combinan las sentencias de alguna de las formas siguientes 1. 2. 3. 4. 5. sentencias sencillas secuencia (;)decisión (if) bucles llamadas a procedimientos

Sentencias sencillas Nos referimos a las sentencias de asignación, entrada/salida, etc. siempre y cuando no trabajen sobre variables estructuradas cuyo tamaño este relacionado con el tamaño N del problema. La inmensa mayoría de las sentencias de un algoritmo requieren un tiempo constante de ejecución, siendo su complejidad O(1). Secuencia (;) La...