Técnicas de diseños de algoritmos

Técnicas de Diseños de Algoritmos
a) Divide y Vencerás

b) Algoritmos Voraces

c) Algoritmos de Vuelta Atrás

d) Programación Dinámica

e) Ramificación y Poda

Índice

Técnicas de Diseños de Algoritmos…………………………………………...…3

Algoritmo divide y vencerás ……………………………………………………....3
Diseño e implementación……………………………………………………..3
Recursión………………………………………………………………….……5
Pilaexplícita………………………………………………………………..…..5
Tamaño de la pila……………………………………………………...………5
Eficiencia del algoritmo…………………………………………………..……5
Acceso a memoria……………………………………………………..………5
Desventaja………………………………………………………………….…..5
Ejemplo: Multiplicación de enteros grandes……………………………...…6

Vuelta Atrás……………………………………………………………………...…….8
Concepto…………………………………………………………………....…..8
Algoritmo deBacktracking…………………………………………………….8
Enfoque………………………………………………………………………….9
Diseño e implementación……………………………………………………...9
Ejemplo: Problema del laberinto……………………………………………..10

Algoritmo voraz……………………………………………………………………....10
Esquema………………………………………………………………………..11
Elementos de los que consta la técnica……………………………………..11
Funcionamiento………………………………………………………………...11
Ejemplo: Algoritmo de Dijkstra………………………………………………..12
Algoritmo…………………………………………………………………….…..12Complejidad……………………………………………………………………..12
Pseudocódigo…………………………………………………………………..13
Implementación…………………………………………………………….…..13
Programación dinámica………………………………………………………..15
Empleos………………………………………………………………………....16
Ramificación y poda…………………………………………………………………18
Descripción General………………………………………………………..…..18
Pseudocódigo…………………………………………………………………..19
SubdivisiónEfectiva……………………………………………………………19
Estrategias de Poda…………………………………………………………....20
Estrategias de Ramificación…………………………………………………..20
Ramificación y Poda "Relajado"……………………………………………....21
Ramificación y Corte…………………………………………………………...21
Ejemplo: Sudoku ramificación y poda…………………………………..……22

Técnicas de Diseños de Algoritmos

El diseño del algoritmo de un problema que tiene solución algorítmica, requiere de la aplicación de técnicas de diseño de algoritmos.

Laformulación de muchos algoritmos para problemas complejos basan su solución en técnicas conocidas de Diseño de Algoritmos.

Algoritmo divide y vencerás

En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solucióndel problema principal se construye con las soluciones encontradas.

En las ciencias de la computación, el término divide y vencerás (DYV) hace referencia a uno de los más importantes paradigmas de diseño algorítmico. El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser losuficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original.

Esta técnica es la base de los algoritmos eficientes para casi cualquier tipo de problema como, por ejemplo, algoritmos de ordenamiento (quicksort, mergesort, entre muchos otros), multiplicar números grandes(Karatsuba), análisis sintácticos (análisis sintáctico top-down) y la transformada discreta de Fourier.

El nombre divide y vencerás también se aplica a veces a algoritmos que reducen cada problema a un único subproblema, como la búsqueda binaria para encontrar un elemento en una lista ordenada (o su equivalente en computación numérica, el algoritmo de bisección para búsqueda de raíces).

Estosalgoritmos pueden ser implementados más eficientemente que los algoritmos generales de “divide y vencerás”; en particular, si es usando una serie de recursiones que lo convierten en simples bucles. Bajo esta amplia definición, sin embargo, cada algoritmo que usa recursión o bucles puede ser tomado como un...