Hoy voy a escribir de forma breve lo que es el diseño de algoritmos. Ya mas adelante extenderé cada parte del tema pues este tema da para mucho mas que una entrada de blog
Conceptos básicos
En principio describiremos de forma
general las técnicas para resolver algoritmos, estas no son otra
cosa que estrategias utilizadas en la resolución de problemas que,
originalmente fueron planteadas por matemáticos para su propio
campo, y como estos mismos investigadores fueron los pioneros de la
computación junto con físicos, aplicaron los mimos criterios para
resolver los algoritmos. Cabe mencionar que en su principio la
computación fue enfocada a la resolución de problemas matemáticos
orientados a asuntos bélicos como la balística y que después se
implementó el uso de las máquinas a cuestiones financieras; mismas
que convergían en la solución de números.
Estas técnicas fueron nombradas de
acuerdo al procedimiento que seguían, y las principlaes son:
- Algoritmos voraces
- Divide y vencerás
- Programación dinámica
- Vuelta atrás
- Ramificación y poda
Niveles de abstracción para la construcción de algoritmos.
La
construcción de
algoritmos
necesita de
tres niveles
de abstracción;
es decir;
son tres
los pasos
necesarios para
su construcción.
Estos son:
- Análisis
- Diseño
- Implementación
Análisis
Consiste en la
recopilación de toda la información necesaria para el algoritmo,
variables que lo rodean, el proceso que le demos a estas, y la salida
que queremos encontrar.
Es
aquí donde
los procesos
pueden
identificarse
como operaciones
que se
aplican a
las variables
del problema.
Y se
perfila el
resultado
deseado.
Diseño
Para
esta etapa
ya se
tiene
identificados y
delimitado el
problema, se
conoce las
variables
involucradas y
se sabe
el los
valores de
salida deseados;
no resueltas
sino más
bien que
debemos esperar
de estas;
con lo
cual se
comienza a
perfilar la
solución
mediante el
planteamiento de
la hipótesis,
se modela
el algoritmo
mediante la
aplicación de
estructuras
definidas para
los algoritmos
y se
comienza hacer
pruebas de
su uso
mediante las
“pruebas de
escritorio”
Implementación
En este paso ya se
comienza la programación en un lenguaje adecuado al algoritmo
basados en la solución que se tiene modelada.
Estructuras básicas de un algoritmo
En la implementación de
algoritmos se puede observar la presencia de comportamientos clásicos
y que están definidos a través de modelos previamente definidos.
Las estructuras típicas
que podemos definir son:
- Ciclos
- Contadores
- Acumuladores
- Condicionales
- Interruptores
Ciclos
Estas estructuras hacen
que el algoritmo se repita de forma iterativa en función de una
condición cumplida en un momento determinado.
Existen dos tipos de
ciclos. Los que se ejecutan “mientras que” y los que se ejecutan
“hasta que”
Mientras que:
Este realiza la
verificación de la condición antes de ejecutar una instrucción,
así es que, si se cumple la condición puede realizar su función de
otro modo salta a otro paso. Al terminar el proceso vuelve hacer la
verificación.
Hasta que
Este ciclo realiza su
propio proceso y después hace la verificación de la condición para
que este se ejecute y esta le dice si debe volver a realizar el
proceso o seguir con el algoritmo.
Ambas iteraciones tienen
en común que se debe cumplir cierta condición para realizar su
proceso.
Contadores
Esta estructura también
realiza iteraciones de las instrucciones por un momento conocido.
Esta estructura sufre incrementos o decrementos del valor asignado a
ella y se ejecutará mientras no se cumpla su condición.
Acumuladores
Estos
guardan valores
crecientes o
decrecientes a
lo largo
de la
ejecución del
algoritmo. Esto
debido a
que los
primeros y
últimos valores
así como
los intermedios
son relevantes
para la
solución o
forman parte
de ella.
Condicionales
Esta estructura tiene como
fin que se realice o no cierta parte del código de acuerdo a una
condición definida. Esto lo hace si se cumple una condición se
ejecuta una parte del código si no se ejecuta otra.
Interruptores
Estas estructuras disparan
un código o parte de uno si se cumple una condición o evento sin
hacer incrementos o decrementos, solo si se cumple o sucede una
condición.
Estrategias de diseño de algoritmos
Toda modelación de un
algoritmo debe caer o se debe diseñar por una de estas estrategias
para la resolución de un problema.
Algoritmos voraces
Estos se utilizan para la
solución de problemas de optimización, son sencillos de programar y
pueden encontrar una solución en un tiempo corto.
Divide y vencerás
Toma el problema y lo
divide en partes más pequeñas y por ende más sencillas del mismo.
La solución la encuentra haciendo una sumatoria do todas estas
partes pequeñas.
Programación dinámica
Defina sub-problemas
superpuestos y sub-estructuras optimas, buscan soluciones óptimas
del problema en su conjunto.
Vuelta atrás
Toma un valor del conjunto
de posibles soluciones posibles al problema y lo evalúa para ver si
es la solución deseada. Si se comprueba que este valor no es el
mejor regresa al punto donde tomo la variable para evaluarla y elige
el valor siguiente, Esto lo realizará hasta que encuentra un valor
satisfactorio.
Ramificación y poda
Su
estrategia es
muy similar
a vuelta
atrás, solo
que se
diferencia en
que puede
ejecutar un
conjunto de
posibles
soluciones a
la vez
y no
hacer esto
de una
en una.
De este
proceso puede
discriminar a
un conjunto
de posibles
soluciones y
descartar (poda)
los valores
que no
satisfacen al
algoritmo.
Realiza una
segunda
evaluación de
los valores
restantes y
descarta los
menos óptimos.
El proceso
se ejecuta
hasta que
se obtiene
un valor
que resuelva
el problema
y se
pueda determinar
a alguno
como el
más óptimo.
No hay comentarios:
Publicar un comentario