Comparacion de las cuatro tecnicas de diseño de algoritmos

ALGORITMOS

LISETH PATERNINA PEREZ

ASIG.
ANALISIS DE ALGORITMOS

ING.
GUILLERMO HERNANDEZ

CORPORACION UNIVERSITARIA DEL CARIBE CECAR
INGENIERIA DE SISTEMAS
SINCELEJO
2011COMPARACION DE LAS CUATRO TECNICAS DE DISEÑO DE ALGORITMOS

A continuación se pasa a exponer 4 de las técnicas de diseño de algoritmos más conocidas: voraz, divide y vencerás, programación dinámica ybacktracking.
ALGORITMOS VORACES: es una técnica de diseño de algoritmos, que se basa principalmente en tratar de producir tipo de mejor resultado a partir de conjunto de opciones candidatas .Para ello, seva procedimiento paso a paso realizándose la mejor elección (usando una función objetivo que respeta un conjunto de restricciones ) de entre las posibles. Puede emplearse en problemas de optimización,como el conocido de la mochila, en la búsqueda de caminos mínimos sobre grafos, la planificación en el orden de la ejecución de unos programas en un computador, etc. Ejemplo. Dar un cambio utilizandoel menor número de monedas.
El funcionamiento de esta técnica sigue los siguientes pasos:
– Para cada paso en el algoritmo se elige la mejor opción, que se tiene disponible.
– Se comprueba si laopción elegida podría llevar a la solución del problema.
– Si esa opción puede llevar a la solución se elige, sino se elige la siguiente mejor opción.
– Si el conjunto de “mejores opciones” escogidases solución, se termina el algoritmo. Si no continúa. Está técnica nos brinda muchas ventajas, las soluciones “ávidas” son muy fáciles de implementar, por lo tanto fáciles de depurar, la velocidad deejecución es muy rápida además de usar muy poca memoria.

DIVIDE Y VENCERAS: La técnica divide y vencerás consiste en descomponer el problema en un conjunto de subproblemas más pequeños. Después seresuelven estos subproblemas y se combinan las soluciones para obtener la solución para el problema original.
La técnica de divide y vencerás es quizás una de las utilizadas debido a su sencillez:...