Estructura de datos

TEMARIO

I. Diseño y análisis de algoritmos. I.1 I.2 I.3 Conceptos básicos. Diseño de algoritmos. Computabilidad y complejidad de algoritmos.

II. Tipos de datos y TAD'S. II.1 II.2 II.3 Abstracción. TAD. Especificación e implementación.

III. Recursividad. Definición y conceptos básicos. IV. Tablas. IV.1 IV.2 Estructura, representación y operaciones básicas. Transformación de clases (HASH).V. Listas. V.1 V.2 V.3 V.4 Pilas y colas. Listas lineales. Listas secuenciales. Listas encadenadas.

VI. Arboles. VI.1 VI.2 VI.3 VI.4 Estructura y representación. Operaciones básicos. Arboles equilibrios. Arboles multicaminos y binarios.

VII. Grafos. VII.1 VII.2 VII.3 Fundamento matemático. Representación. Algoritmo de manipulación.

VIII. Clasificación y búsqueda. VIII.1 VIII.2 VIII.3VIII.4 Conceptos básicos. Clasificación interna, métodos. Clasificación externa, métodos. Búsqueda.

IX. Resolución general de problemas. BACKTRAKING. PROFESOR: Miguel Angel Díaz, Despacho 2117 bloque II.

Página 2 de 106

Diseño y análisis de algoritmos

1. CONCEPTOS BASICOS.
Una posible definición de algoritmo es un conjunto de reglas que permiten obtener un resultado determinadoapartir de ciertas reglas definidas. Otra definición sería, algoritmo es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito. Ha de tener las siguientes características: Legible, correcto, modular, eficiente, estructurado, no ambiguo y a ser posible se ha de desarrollar en el menor tiempoposible. Características de un algoritmo de computador: Ser algoritmo: Tiene que consistir instrucciones claras y finitas. Ser correcto: El algoritmo ha planteado en todas sus facetas. Ser legible. Ser eficiente: Es relativa porque depende de la maquinas en la que lo ejecutemos. Existen ejemplos de algoritmos eficientes que ocupan demasiado espacio para ser aplicados sin almacenamiento secundariolento, lo cual puede anular la eficiencia. Un algoritmo eficiente pero complicado puede ser inapropiado porque posteriormente puede tener que darle mantenimiento otra persona distinta del escritor. de en una secuencia el de

resolver

problema

2. DISEÑO DE ALGORITMOS.
Fases de diseño de algoritmos. 1. Diseño: se dan las especificaciones en lenguaje natural y se crea un primer modelomatemático apropiado. La solución en esta etapa es un algoritmo expresado de manera muy informal. 2. Implementación: El programador convierte el algoritmo en código, siguiendo alguna de estas 3 metodologías. A. TOP-DOWN se alcanza el programa sustituyendo las palabras del palabras del pseudocódigo por secuencias de proposiciones cada vez mas detalladas, en un llamado refinamiento progresivo. B. BOTTON-UPparte de las herramientas mas primitivas hasta que se llega al programa.

Diseño y análisis de algoritmos

Página 3 de 106

C. TAD'S modularización dependiendo de los recursos.Tenemos unas estructuras abstractas implementadas, y una serie de conocimientos asociados a esos recursos. 3. Pruebas: Es un material que se pasa al programa para detectar posibles errores.Esto no quiere decir que eldiseño no tenga errores, puede tenerlos para otros datos.

3. COMPLEJIDAD DE ALGORITMOS.
La eficiencia de un determinado algoritmo depende de la maquina, y de otros factores externos al propio diseño. Para comparar dos algoritmos sin tener en cuenta estos factores externos se usa la complejidad. Esta es una media informativa del tiempo de ejecución de un algoritmo, y depende de varios factores:¨ Los datos de entrada del programa. Dentro de ellos, lo más importante es la cantidad, su disposición, etc. ¨ La calidad del código generado por el compilador utilizado para crear el programa. ¨ La naturaleza y rapidez de las instrucciones empleados por la máquina y la propia máquina. ¨ La propia complejidad del algoritmo base del programa. El hecho de que el tiempo de ejecución dependa de la...