Eficiencia de Algoritmos

El análisis de algoritmos se centra en la eficiencia, que es función del número de instrucciones que contiene. Esta eficiencia depende de la velocidad de las computadoras.

Implica diversos tipos de memoria:

• Principal
• Caché
• Flash
• Archivos
• HDD

Eficiencia como Factor Espacio-Tiempo

La eficiencia como factor espacio-tiempo debe estar relacionada con la buena calidad, el funcionamiento y la facilidad de mantenimiento de un programa.

Formato General

F(n) = Eficiencia

Se Examina como una Función del Número 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) = log₂n

Fórmulas

• Lineal logarítmica = F(n) = n log₂ n
• Dependiente cuadrática = F(n) = n(n+1)/2
• Cuadrática F(n) = n²

Resolución de Ecuaciones Recurrentes

Una ecuación recurrente es un tipo específico de relación de recurrencia.

a₀, a₁, a₂,….

Es una ecuación que relaciona a_n con alguno de sus predecesores.

a₀, a₁,….a_n-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 por qué 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 más 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

1. Identificar los subproblemas del mismo tipo.
2. Resolver recursivamente cada subproblema.
3. Combinar las soluciones en una única solución.

Condiciones

• P debe ser divisible en subproblemas.
• Todos los P_i deben ser de la misma naturaleza que P, pero de menor tamaño.
• Cada uno de los P_i se puede resolver para obtener soluciones S_i.
• Con la combinación de todas las S_i 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 óptima debe ser, a su vez, secuencia óptima.

Algoritmos Probabilistas

A veces es preferible hacer una elección aleatoriamente en vez de perder el tiempo en decidir cuál 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 Carlo: 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 realiza 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

1. Que tenga éxito y encuentre la hoja del árbol (solución). Si lo único que buscamos era una solución al problema, finaliza aquí.
2. 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, para finalmente 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 dificiles de resolver que otros.

Si una funcion es computable en un tiempo polinomial depende del largo de la entrada:

                         L1=pol>

NP Completos

P= problemas que se pueden resolver en tiempo polinómico.

NP= los problemas que se pueden comprobar en tiempo polinómico

– Los NP-completos parecen intratables.

– Nadie ha sabido demostrar que los NP-completos son intratables.

 NP-Dificiles

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 Dificil si existe un algoritmo rápido para un problema, pues no se consideraría que el problema requiera inteligencia.

* Es NP-Dificil 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 tendra 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.