Eficiencia de algoritmos
Se centra en el análisis de bucles, la eficiencia es función del número de instrucciones que contiene. (Depende de la velocidad de las computadoras).
– Implica diversos tipos de memoria:
* principal, caché, flash, archivos, HDD, etc.
——La eficiencia como factor espacio-tiempo debe estar relacionada con la buena calidad, el funcionamiento y la facilidad de mantener un programa————
Formato general:
F(n)=eficiencia
Se examina como una función del numero de elementos a ser procesados
* El número de iteraciones es directamente proporcional al factor del bucle n F(n)= n
F(n)=n/2 —– F(n)= log2n
Formulas:
Lineal logarítmica = F(n)= n log2 n
Dependiente cuadrática = F(n)=n(n+1)/2
Cuadrática F(n)=n2
Resolución de ecuaciones recurrentes:
–
Una ecuación recurrente es un tipo específico de relación de recurrencia.
a0,a1,a2,….
– Es una ecuación que relaciona an con alguno de sus predecesores.
a0,a1,….An-1.
Algoritmos Voraces
Se emplean para resolver problemas de optimización.
-Elementos:
* Conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc.).
* Conjunto de decisiones ya tomadas (candidatos ya escogidos).
* Una función que determina si un conjunto de candidatos es una solución al problema (aunque no tiene porqué ser la óptima).
*una función completable, si añadiendo a este conjunto nuevos candidatos es posible alcanzar una solución al problema, si existe.
*
función de selección, escoge el candidato mas prometedor.
*
función objetivo, da valor/coste de una solución y que es la que se pretende maximizar o minimizar.
Divide y vencerás
Se basa en reducir un problema en dos o más subproblemas, volviendo a aplicar el mismo método sobre los resultados hasta alcanzar la solución.
– Pasos a seguir
Identificar los subproblemas del mismo tipo.
* Resolver recursivamente cada sub.
* Combinar las soluciones en una única solución.
Condiciones
– P debe ser divisible en subproblemas.
– Todos los Pi deben ser de la misma naturaleza que P, pero de menor tamaño.
– cada uno de los Pi se puede resolver para obtener soluciones Si.
– Con la combinación de todas las Si se obtiene la solución S al problema original P.
Programación Dinámica
Es un enfoque para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema.
– Se basa en el principio de Optimalidad de Bellman:
Cualquier secuencia optima debe ser, a su vez, secuencia optima.
Algoritmos probabilistas.
A veces es preferible hacer una elección aleatroiamente en vez de perder el tiempo en decidir cual elección es la correcta.
En este caso se habla de tiempo esperado de ejecución y no de orden de complejidad.
Clasificación:
– Numéricos: Solución aproximada.
– Monte Carló: Solución exacta; pero a veces se equivocan
– Las Vegas: nunca devuelven una solución errónea, pero a veces no la encuentran.
– Sherwood: siempre encuentran la solución y siempre es correcta.
Backtracking
Algoritmo recursivo que realizan recorridos en anchura y profundidad, que prueban todos los posibles casos de un problema hasta encontrar la solución. Asegura que si hay solución, la encuentra.
* No tiene secuencia, busca todos los posibles caminos hasta encontrar la solución y si no existe da una vuelta atrás para continuar.
* dentro del árbol de expansión, cada nodo de nivel X representa una parte de la solución y está formado por X etapas. Sus hijos son las prolongaciones posibles cuando se añade una nueva etapa.
– En el recorrido solo existen dos probabilidades:
-> que tenga éxito y encuentre la hoja del árbol (solución). Si lo único que buscamos era una solución al problema, finaliza aquí.
-> Si lo que se busca era todas las posibles soluciones o la mejor de entre todas ellas, el algoritmo seguirá explorando el árbol en busca de soluciones alternativas.
Ventajas:
consume menos memoria que el método divide y vencerás.
Si existe una solución siempre la encuentran.
Desventajas:
Bastante ineficientes.
Lento
Algoritmo paralelo
Puede ser ejecutado por partes en el mismo instante de tiempo por varias unidades de procesamiento, par afinalmente unir todas las partes y obtener un resultado(ejemplo de las listas del 1 al 100, y dividirlo para obtener los números primos).
Clases P y NP
Un problema de decisión pertenece a la clase P si podemos encontrar una solución del problema que sea fácil.
– Problema de decisión aquel qu epodemos contestar con una respuesta de si o no.
Un problema de decisión pertenece a NP si la comprobación de la solución es fácil. Uno de los problemas más conocidos es el «Problema del Agente Viajero».
Reducción polinomica
Cuando existen problemas NP mas difíciles de resolver que otros.
Si una función es computable en un tiempo polinomial depende del largo de la entrada:
L1<=pol>=pol>
NP Completos
P= problemas que se pueden resolver en tiempo polínómico.
NP= los problemas que se pueden comprobar en tiempo polínómico
– Los NP-completos parecen intratables.
– Nadie ha sabido demostrar que los NP-completos son intratables.
NP-Difíciles
para resolverlos de forma exacta necesitan:
– la realización de una búsqueda en un espacio que es de tamaño exponencial.
* Los problemas NP son encontrados en el área de la Inteligencia.
*
No es NP Difícil si existe un algoritmo rápido para un problema, pues no se consideraría que el problema requiera inteligencia.
*
Es NP-Difícil si en base al problema tenemos un algoritmo que encuentra la solución de forma rápida y casi siempre correcta. Así se considera que el algoritmo es «inteligente». (no se tendrá una búsqueda rápida y sin errores).
***Problema de la parada ****
No determinista
Algoritmo que con la misma entrada ofrece muchos posibles resultados. No se sabe cual será el resultado.
–
Uso:
emplean modelos de computación como la maquina de turing.