Estructuras De Datos

Algoritmos y Estructuras de Datos Unidad I Introducción a los Algoritmos y Estructuras de Datos

Ing. Alma Leticia Palacios Guerrero pág. 1 de 8

UNIDAD 1 Introducción a los Algoritmos y Estructuras de Datos

1.1 Definición de Algoritmo

Algoritmo se define como un conjunto de instrucciones que la computadora debe seguir para resolver

un problema. La palabra algoritmo se deriva de la traducción al latín del nombre Muhammad Musa Alkhawarizmi,

un matemático y astrónomo árabe que en el siglo IX escribió un tratado sobre manipulación

de números y ecuaciones.

1.1.1 Características de los Algoritmos

• Son independientes del lenguaje de programacióna utilizar.

• Sencillo, los pasos deben ser claros y bien definidos.

• Precisos, indican claramente el orden de realización paso a paso.

• Definidos, cada vez que se ejecutan con las mismas entradas se obtiene el mismo resultado.

• Finitos, tienen un número de pasos finito.

1.2 Modelo de Cascada para el desarrollo de Sistemas

La resolución de un problema con una computadora conduce a la escritura de un programa y a su

ejecución en la misma. Aunque el proceso de diseñar programas es un proceso creativo, los pasos a

seguir se establecen en varios modelos para el desarrollo de sistemas uno de ellos es el modelo de

cascada. Este se define como el proceso que se sigue para diseñar, construir, entregar y hacer

evolucionar el software, desde la concepción de una idea hasta la entrega y el retiro del sistema1.

Paso 1: Análisis del problema. Esta fase requiere una

clara definición, donde se contemple exactamente lo que

debe hacer el programa y el resultado o solución

deseada.. Para poder definir bien un problema es

conveniente responder a las preguntas: ¿Qué cantidad y

tipo de datos de entrada se requieren?, ¿Qué cantidad y

tipo de salidas se desean? ¿Qué método(s) produce(n) la

salida deseada?

Paso 2. Diseño del Algoritmo. En esta etapa se define

cómo hace el programa la tarea solicitada, es decir, se

define el algoritmo.

Paso 3. Codificación. Se traduce el algoritmo en un

lenguaje de programación apropiado.

Paso 4. Compilación y Ejecución. El proceso de

compilación consiste en pasar el programa de código

fuente a un código ejecutable. La ejecución es “correr” el

programa generado en el proceso de compilación.

Paso 5. Depuración. Se ejecuta el programa con datos

de prueba para detectar y corregir errores en tiempo de

ejecución.

Paso 6. Documentación. Interna: Comentarios dentro del

programa. Externa: Manuales del programador, del

usuario, de instalación, etc.

Paso 7. Entrega y Mantenimiento

1 http://www.biblioteca.co.cr/pdf/unidad12-4.pdf

Codificación

Análisis del Problema

Diseño del algoritmo

Documentación

Depuración

Compilación y Ejecución

Entrega y Mantenimiento

Algoritmos y Estructuras de Datos Unidad I Introducción a los Algoritmos y Estructuras de Datos

Ing. Alma Leticia Palacios Guerrero pág. 2 de 8

1.3 Estrategias para la solución de problemas

Cuando se trata de resolver un problema, pueden presentarse varias estrategias para solucionarlo2. Las

técnicas o estrategias más comunes son:

Estrategias de solución directa

• Algoritmos de Solución Forzada: Un algoritmo de este tipo resuelve el problema de la forma

mas simple, obvia o directa. Como resultado es posible que el algoritmo haga mas trabajo

que una solucióm más sofisticada. Por otra parte, las soluciones forzadas son más fáciles de

implementar y por eso algunas veces resultan más eficientes.

• Algoritmos Codiciosos: Se caracterizan las decisiones que toman se basan en que la

busqueda del menor costo en esa parte del problema, pero no toman en cuenta el resto de la

solución y en ocasiones no generan soluciones óptimas.

Estrategias de Vuelta Atrás

• Un algoritmo de vuelta atrás, sistemáticamente considera todos los posibles resultados para

cada decisión. En este sentido, los algoritmos vuelta atrás son como las soluciones forzadas.

Sin embargo, los algoritmos vuelta atrás se distinguen por la forma en que exploran todas las

posibles soluciones; en ocasiones estos algoritmos encuentrar que una búsqueda exhaustiva

es innecesaria y por lo tanto pueden tener una mejor ejecución.

Estrategias arriba-abajo

• Algoritmos divide y vencerás. Para resolver un problema, este se subdivide en uno o más

subproblemas cada uno de los cuales es similar al problema dado. Cada uno de los

subproblemas se soluciona en forma independiente y al final las soluciones de todos los

subproblemas se combinan para obtener la solución general del problema completo.

Estrategias abajo-arriba

• Programación Dinámica: Para resolver un problema se resuelven una serie de

subproblemas. La serie de subproblemas es planeada cuidadosamente de tal forma que

cada solución subsecuente se obtiene mediante la combinación de las soluciones de uno o

más subproblemas que ya han sido resueltos. Todos las soluciones intermedias se

mantienen en una tabla para evitar la duplicidad de esfuerzos.

Estrategias Probabilísticas:

• En los algoritmos probabilísticos existe un elemento de aleatoridad en la forma en que el

algoritmo soluciona el problema, se dice que estos métodos son el último recurso debido a

que se usan cuando no hay otra técnica conocida que se pueda aplicar. Los métodos

probabilísticos se usan cuando el espacio de soluciones es tan grande que una búsqueda

exhaustiva no seria factible.

Algoritmos y Estructuras de Datos Unidad I Introducción a los Algoritmos y Estructuras de Datos

Ing. Alma Leticia Palacios Guerrero pág. 3 de 8

1.4 Definición de Estructura de Datos.

En el desarrollo de programas, existe una fase previa a la escritura del programa, esta es el diseño del

algoritmo que conducirá a la solución del problema, en esta fase también deberá considerarse la

estructura de datos que se va a utilizar. El término estructura de datos se refiere a la forma en que la

información esta organizada dentro de un programa. La correcta organización de datos puede conducir a

algoritmos más simples y más eficientes.

Estructura de datos: Conjunto de variables agrupadas y organizadas de cierta forma para representar

un comportamiento.

1.4.1 Clasificación de las estructuras de datos

Las estructuras de datos según su tamaño en memoria, se clasifican en:

Estructuras de datos estáticas: Son aquellas cuyo tamaño en memoria es fijo, por ejemplo, los

arreglos.

Estructuras de datos dinámicas: Son las estructuras que permiten variar su tamaño en memoria de

acuerdo a las necesidades del ambiente, por ejemplo, listas enlazadas.

1.3.1 Abstracción

Desde el desarrollo de la informática los programadores han luchado con el problema de la complejidad

inherente al software, una de las herramientas utilizadas para resolverlo es la abstracción. Esta se

puede definir como la consideración aislada de las cualidades esenciales de un objeto. En otro términos

la abstracción es la capacidad para encapsular y aislar la información del diseño y ejecución.

1.4. Tipo Abstracto de Datos (TAD)

Un tipo abstracto de datos es un modelo (estructura) con un número de operaciones que afectan a ese

modelo. Un TAD es un tipo de datos definido por el programador que se puede manipular de un modo

similar a los tipos de datos definidos por el sistema.

1.4.1 Desarrollo de la Abstracción

Al inicio de la informática los programadores introducían la información y datos a través de interruptores,

los mnemónicos eran abstracciones diseñadas para ayudar a recordar secuencias de bits, luego, esto

mnemónicos se agruparon en macroinstrucciones pasando así al siguiente nivel de abstracción: los

lenguajes de alto nivel. Los inicios de la abstracción se dieron al surgir lenguajes como FORTRAN,

COBOL y ALGOL60, los cuales suministraban tipos de datos simples; sin embargo, estos datos no

siempre se ajustaban al tipo requerido para resolver el problema y no podian sufrir cambios.

Posteriormente surgen lenguajes como Pascal, Simula-67 y ALGOL68 en los que existian más tipos de

datos y que permitian al programador crear construcciones (arreglos, registros). Con el tiempo

aparecieron otros lenguajes de programación con mayor nivel de abstracción que permitieron al

programador la creación de estructuras de datos. Hacia 1974, John Guttag propone el concepto de tipo

abstracto

...