Análisis y diseño de algoritmos

Un enfoque práctico

Eduardo Villegas Jaramillo, Luz Enith Guerrero Mendieta, Eduardo Villegas Jaramillo, Luz Enith Guerrero Mendieta

• Editorial: Universidad Nacional de Colombia
• Año: 2016
• ISBN del libro electrónico: 9789587757934
• Categoría: Ciencia de la computación
• Categoría: Ingeniería computacional

Esta obra es una herramienta de formación imprescindible para todos aquellos interesados en aprender a programar. Parte del análisis como una herramienta práctica para predecir y determinar la mejor manera de escribir algoritmos. Además, explica diferentes técnicas para su diseño con ejemplos en los que se plantean y solucionan diversos tipos de problemas mediante ejercicios escritos en seudocódigo e implementaciones en lenguaje C/C ++.

SEGUNDA PARTE

Diseño de algoritmos

Introducción

Desde que se diseñaron los primeros computadores se viene buscando la mejor forma de escribir programas. Al principio se hacían de forma empírica, así que cada programador tenía su propia técnica y se basaba en su propia experiencia para escribir programas.

Con el paso del tiempo se buscaron técnicas que permitieran el desarrollo de los programas de una manera sistemática, cumpliendo con reglas y principios. Apareció entonces lo que se denominó ingeniería de software, que es un conjunto de técnicas, principios y reglas que permiten analizar, diseñar y construir programas [1].

El principal problema de la ingeniería de software es que los problemas no se pueden resolver todos de la misma forma, ya que su naturaleza, características y exigencias son totalmente diferentes. Si esto no sucediera, sería relativamente sencillo desarrollar un programa que hiciera programas, lo cual solo se puede dar para resolver algunos problemas que son del mismo tipo, como sucede con las herramientas CASE (Computer Aided Software Engineering), o si se pudiera acudir a las técnicas de inteligencia computacional que están explorando esta área (programación genética) [17].

El diseño correcto, eficiente y la implementación de algoritmos para problemas del mundo real necesitan técnicas de diseño algorítmico. El modelamiento es la clave para aplicar estas técnicas, y es el arte de formular las aplicaciones en términos de problemas bien entendidos, descritos precisamente. De hecho, el modelamiento puede eliminar el diseño o implementación de algoritmos relacionando su aplicación con lo que ha sido hecho antes [13].

El objetivo de esta parte del libro es presentar las técnicas más representativas para solucionar problemas y escribir programas en el computador. No se trata de las únicas, pero sí de las principales técnicas que permitirán resolver la mayor parte de los problemas que uno puede enfrentar.

Las técnicas que se analizarán son las siguientes:

■Algoritmos voraces

■Dividir y conquistar

■Programación dinámica

■Algoritmos exhaustivos

■Algoritmos aproximados

La combinación de estas técnicas servirá para solucionar otros problemas que tal vez no puedan ser solucionados con las técnicas por separado.

5 Algoritmos voraces

Se analiza en primera instancia esta técnica por ser la más simple de aplicar y la que requiere menos conocimientos en el campo de la programación.

5.1 Definición

Se conocen también como algoritmos miopes, glotones, ávidos o avaros, y 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. Además, una vez que toman una decisión nunca reconsideran otras posibilidades, lo que ocasionalmente los lleva a caer en puntos muertos o sin salida.

Los algoritmos voraces también se caracterizan por la rapidez con la que encuentran una solución (cuando la encuentran), que casi nunca es la mejor. Normalmente son utilizados para resolver problemas en los cuales la velocidad de respuesta debe ser muy alta o el árbol de decisiones de búsqueda es muy grande, de modo que no es factible analizar todas las posibilidades.

Ejemplos típicos de problemas que se pueden resolver mediante este esquema son búsquedas en árboles o grafos, recorridos de grafos, solución de laberintos y algunos juegos, entre otros.

5.2 Forma general

La estrategia general de este tipo de algoritmos se basa en la construcción de una solución que comienza sin elementos, y cada vez que debe tomar algún tipo de decisión lo hace con la información que tiene a primera mano, para, de alguna manera, adicionar elementos y así avanzar hacia la solución total. Cada elemento o paso se adiciona al conjunto solución, y así hasta llegar a la solución completa o a un punto en el cual el algoritmo no puede seguir avanzando, lo cual indica que no encontró una solución al problema.

El esquema típico de una función para un algoritmo voraz es:

donde C es el dominio o modelo del problema, S es la solución y X es cada una de las soluciones parciales que el algoritmo encuentra.

El esquema general en lenguaje C es:

5.3 Problemas clásicos

Problema 1: devolver el cambio

Dado un conjunto de denominaciones de monedas se pretende regresar una determinada cantidad de dinero haciendo uso de la menor cantidad de monedas.

Ejemplo: dadas tres denominaciones {1, 4, 6} de monedas, si quisiéramos retornar una cantidad de 8 unidades, un algoritmo voraz en un primer paso examinaría entre las posibles denominaciones cuál lo acerca más a la solución completa. Es evidente que si consideramos cada una de las denominaciones disponibles, encontraremos que la mejor aproximación inicial es regresar una moneda de 6 unidades, de modo que solo queden por regresar 2 unidades. En un segundo paso, es evidente que regresar una moneda de una unidad nos acercará aún más a la solución definitiva. Y si repetimos nuevamente el proceso, encontraremos que con regresar otra moneda de una unidad resolveremos el problema.

El resultado final es que para regresar 8 unidades se necesitan 3 monedas, una de 6 unidades y dos de 1 unidad.

Si se analiza el problema desde un punto de vista diferente, se puede encontrar una solución que regresa la misma cantidad con un número inferior de monedas: dos de 4 unidades (solución no voraz).

El algoritmo voraz para resolver este problema parte de la base de que se tienen las denominaciones en un arreglo ordenadas en forma descendente de mayor a menor, lo cual permite una más fácil toma de decisiones.

El programa en lenguaje C queda de la siguiente manera:

donde...

Índice

• Cubierta
• Portadilla
• Página legal
• Contenido
• Lista de figuras
• Lista de tablas
• Prefacio
• Primera parte: Análisis de algoritmos
• Segunda parte: Diseño de algoritmos
• Referencias
• Índice analítico
• Página institucional
• Créditos
• Cubierta posterior