Todo

FUNDAMENTOS DE COMPLEJIDAD COMPUTACIONAL.

TECNICAS DE ANALISIS Y DISEÑO DE ALGORITMOS.

Algoritmos Voraces: aquellos que se caracterizan por tomar decisiones basados en la información que tienen a primera mano, sin tener en cuenta lo que pueda pasar más adelante. Una vez que toman una decisión nunca reconsideran otras posibilidades.

Dividir y Conquistar: técnica que permite encontrar lasolución a un problema descomponiéndolo en subproblemas más pequeños y luego se unen las diferentes soluciones de cada uno de los subproblemas para conformar la solución global.

Dinámica: se utilizan estructuras como vectores, tablas, arreglos, archivos, con el fin de almacenar los resultados parciales que contribuyan a la solución final. Evita calcular dos veces la misma información. El mayornúmero de aplicaciones se encuentra en problemas que requieren optimización, ya que pueden hallar múltiples soluciones y así evaluarlas para hallar la óptima.

Vuelta Atrás: son aquellos que analizan todo el espacio de búsqueda que garantiza que pueden encontrar una solución óptima. Realiza una búsqueda exhaustiva, sistemática y organizada sobre el espacio de búsqueda del problema. En caso deno encontrar una solución a una subtarea se retrocede a la subtarea anterior y se prueba otro camino diferente.

Algoritmos paralelos: permiten la división de un problema en subproblemas de forma que se puedan ejecutar de forma simultánea en varios procesadores.

Algoritmos probabilísticos: algunos de los pasos de este tipo de algoritmos están en función de valores pseudoaleatorios.Algoritmos determinísticos: el comportamiento del algoritmo es lineal: cada paso del algoritmo tiene únicamente un paso sucesor y otro antecesor.

Algoritmos no determinísticos: el comportamiento del algoritmo tiene forma de árbol y a cada paso del algoritmo puede bifurcarse a cualquier número de pasos inmediatamente posteriores, además todas las ramas se ejecutan simultáneamente.

Metaheurísticas:encuentran soluciones aproximadas (no óptimas) a problemas basándose en un conocimiento anterior (a veces llamado experiencia) de los mismos.

Ramificación y acotación: se basa en la construcción de las soluciones al problema mediante un árbol implícito que se recorre de forma controlada encontrando las mejores soluciones.

NATURALEZA DE PROBLEMAS DE ALGORITMOS.

Los problemas algorítmicos sonclasificados de acuerdo a su naturaleza intrínseca respecto a la posibilidad y dificultad de resolverlos.

Los problemas de naturaleza algorítmica que no admiten solución por algoritmo son llamados no - computables.
Los problemas de decisión y no-computables son llamados de indecidíbles.
Los problemas para los cuales existen algoritmos de complejidad polinomial para resolverlos son llamadosde tratables.
Los problemas que admiten solución y para los cuales comprobadamente no pueden ser resueltos por algoritmos de complejidad polinomial son rotulados de intratables

Problemas que no admiten solución algorítmica: No computable, Indicidible.
Problemas que admiten solución algorítmica: Tratable, Intratable.

IMPLEMENTACION HARDWARE/SOFTWARE.

1.- Implementación de un algoritmo ensoftware o lo que es lo mismo, preparado para ejecutarse en el procesador:

El software siempre se tiene que ejecutar en el hardware de la máquina donde esté. Normalmente, siempre disponemos de un procesador de propósito general, llamado así porque está pensado para poder ejecutar cualquier algoritmo. Para ello utiliza un conjunto de instrucciones generales, como por ejemplo, "suma dosnúmeros", "guarda este dato en esta posición de memoria" o "recupera lo que hay en esta posición de memoria".

Además, para ejecutar cada instrucción, el procesador de propósito general tiene que realizar una secuencia de pasos, que son siempre los mismos (no como en la implementación en hardware).

Hay que aclarar, que en un ordenador, además del procesador, podemos ejecutar partes del software en...