Prefacio - Uniandes
PrefacioEste libro está dirigido a estudiantes de ingeniería de sistemas, con conocimientos básicos de programaciónen algún lenguaje de alto nivel, de preferencia C. En la Universidad de los Andes está planteado como el textodel tercer curso del ciclo de formación básica en informática, y supone que el estudiante maneja con ciertahabilidad los conceptos básicos de la programación de computadores.El objetivo del libro es servir como guía para un curso en diseño y manejo de estructuras de datos en C. Alfinal, el estudiante será capaz de diseñar las estructuras de datos, en memoria principal, más adecuadas paraun problema específico, y desarrollar los algoritmos para el manejo de éstas. El libro utiliza metodologías deTipos Abstractos de Datos y soporta todo el proceso de diseño en sólidas bases teóricas. Brinda al estudianteherramientas para la evaluación de soluciones, como la complejidad de algoritmos, de manera que cuentecon criterios concretos de decisión. El libro no se queda en consideraciones teóricas, sino que muestra ladimensión práctica de las metodologías de diseño propuestas y la manera de aplicarlas para mejorar lacalidad del software obtenido.El lenguaje escogido para el libro es C, dada su enorme difusión en el medio informático, su eficiencia, suestandarización y porque ha sido seleccionado como el lenguaje de base por muchas universidades delmundo. Además, el contenido del libro se ajusta muy bien para ser utilizado en desarrollo de software en C .Cada algoritmo que trae el libro tiene una especificación formal, una explicación de su funcionamiento y elcálculo de su complejidad. Todos los programas del libro han sido desarrollados y probados en ANSI C, sobrediferentes plataformas computacionales.En cada capítulo, el estudiante encuentra un conjunto de ejemplos y ejercicios propuestos, tanto a nivel dediseño como a nivel de implementación. Esto permite al estudiante ver la aplicación de las metodologíaspropuestas en problemas reales y practicar para obtener destreza en su utilización. Los ejercicios estánorganizados por temas y clasificados por nivel de complejidad. En cada capítulo se dan algunas referenciasbibliográficas a través de las cuales es posible profundizar en los temas allí tratados. Cada capítulo presentaun tipo de estructura de datos, un TAD que la administra y ejemplos de la parte algorítmica.El libro viene apoyado por un disquete, que incluye la implementación y los programas de prueba de todos losalgoritmos que son presentados en la parte teórica, lo mismo que la solución de algunos de los ejerciciospropuestos. Esto permite al estudiante ver el funcionamiento de cada una de las rutinas planteadas, lo mismoque reutilizar el software para el desarrollo de sus propios proyectos. Existe también una guía completa delprofesor, en la cual se hacen varias recomendaciones metodológicas para la presentación en clase delmaterial, lo mismo que la solución de otros de los ejercicios propuestos a lo largo del libro.Este libro es el producto de más de 8 años de trabajo en la Universidad de los Andes, en el curso Estructurasde Datos. Materiales previos han sido utilizados por más de 3000 estudiantes en ésta y otras universidadesdel país.En el capítulo 0 se presentan algunos conceptos básicos de programación y las nociones elementales deanálisis de algoritmos. En el capítulo 1 se dan las pautas generales de la metodología de diseño de-i-
estructuras de datos. Su utilización se ilustra a lo largo de todo el libro a través del estudio de casos. Loscapítulos 2 y 3 presentan las estructuras lineales de datos, tales como listas, pilas y colas. Los capítulos 4 y 5estudian las estructuras recursivas de datos como los árboles binarios y los árboles n-arios. El capítulo 6 haceun estudio de estructuras de datos no lineales, como grafos dirigidos. Por último, el capítulo 7 trata el tema deestructuras de acceso directo, en particular, tablas de hashing.Al interior del libro se utilizan las siguientes convenciones: Algoritmo implementado en el disquete¹Ejercicio medianamente complejo¹¹Ejercicio con alto grado de dificultad:Ejercicio de programación Marca de final de ejemplotimes, sin tildeNombre de rutinas en el textonegrillaDefinición de un nuevo conceptoitálicaPalabra en inglés que, por razones de claridad, no hasido traducida al españolQuiero agradecer los comentarios sobre las versiones preliminares del libro, que recibí de parte de lassiguientes personas: Mario Daniel Ramírez (Instituto Tecnológico de Costa Rica), Javier Cañas (UniversidadFederico Santa María - Chile), Claudia Jiménez (Universidad de los Andes - Bogotá), Roberto Ojeda(Universidad Nacional de Colombia - Bogotá), Yadran Eterovic (Pontificia Universidad Católica de Chile),Silvia Takahashi (Universidad de los Andes - Bogotá), Diego Andrade (Pontificia Universidad Católica delEcuador), Jorge Elías Morales (Fundación Universitaria San Martín - Bogotá), Carlos Figueira (UniversidadSimón Bolivar - Venezuela), Ariel Ortiz Ramírez (Instituto Tecnológico de Monterrey - México), John A.Atkinson (Universidad Federico Santa María - Chile), Demetrio Ovalle (Universidad Nacional de Colombia Medellín), Hernán Dario Toro (Universidad EAFIT - Medellín), Emilio Insfran (Universidad Católica deAsunción - Paraguay) y Gustavo Rossi (Universidad de La Plata - Argentina).Por último, quiero agradecer de una manera muy especial a mi colega y amigo Alejandro Quintero, con quiencomenzamos hace casi 9 años este proyecto, y sin cuyo apoyo habría sido imposible llevarlo a cabo.J.V.Enero de 1996- ii -
A Vicky,por lo que ella significa para mí.- iii -
ContenidoCAPITULO 0 - CONCEPTOS BÁSICOS0.1. Diseño y documentación de algoritmos . 10.1.1. Los conceptos de estado y aserción . 10.1.2. La especificación de un programa . 4Ejercicios propuestos . 60.1.3. Dividir y conquistar . 70.1.4. Consideración de casos . 80.1.5. Ciclos e invariantes . 9Ejercicios propuestos . 130.2. Recursión . 140.2.1. Conceptos básicos . 140.2.2. Estructura de una rutina recursiva . 160.2.3. Metodología de desarrollo . 17Ejercicios propuestos . 180.3. Análisis de algoritmos . 190.3.1. Definición del problema . 190.3.2. Tiempo de ejecución de un algoritmo . 200.3.3. El concepto de complejidad . 230.3.4. Aritmética en notación O . 250.3.5. Ejemplos . 260.3.6. Complejidad en espacio . 310.3.7. Selección de un algoritmo . 310.3.8. Complejidad de rutinas recursivas . 32Ejercicios propuestos . 35CAPITULO 1 - DISEÑO DE SOFTWARE Y TIPOS ABSTRACTOS1.1. Ingeniería de software . 391.1.1. Ciclo de vida del software . 391.1.2. Software de alta calidad . 401.1.3. Arquitectura del software . 411.1.4. Reutilización de software: genericidad . 431.2. Tipos abstractos de datos . 431.2.1. Motivación y definiciones . 431.2.2. Representación de un objeto abstracto . 431.2.3. El invariante de un TAD . 451.2.4. Especificación de un TAD . 461.2.5. Clasificación de las operaciones . 491.2.6. Manejo de error . 511.2.7. Metodología de diseño de TAD . 531.2.8. Uso de TAD en solución de problemas . 561.2.9. Genericidad: TAD paramétricos . 57Ejercicios propuestos . 581.3. Diseño de estructuras de datos . 601.3.1. Relación objeto abstracto - estructuras de datos . 601.3.2. Consideraciones básicas . 611.3.3. Representación de longitud variable . 641.3.4. Manejo de información redundante . 64-v -
ContenidoDiseño y Manejo de Estructuras de Datos en C1.3.5. Representaciones compactas vs. exhaustivas . 651.3.6. Ordenamiento físico vs. lógico . 651.3.7. Representación implícita vs. explícita . 661.3.8. Incorporación de restricciones del problema . 661.3.9. Estructuras de datos para el TAD Matriz . 671.3.10. Un TAD como estructura de datos . 701.3.11. Esquema de persistencia . 72Ejercicios propuestos . 731.4. Implementación de las operaciones de un TAD . 781.4.1. Esquema de implementación en C . 781.4.2. Documentación . 821.4.3. Implementación de la genericidad . 831.4.4. Probador interactivo de un TAD . 83CAPITULO 2 - ESTRUCTURAS LINEALES: LISTAS2.1. Definiciones y conceptos básicos . 852.2. El TAD Lista . 872.3. Ejemplos de utilización del TAD . 892.4. Otras operaciones interesantes . 94Ejercicios propuestos . 972.5. Esquema de persistencia . 992.6. Algunas implementaciones del TAD Lista . 1002.6.1. Estructura doblemente encadenada . 1002.6.2. Vectores . 1032.6.3. Encadenamiento sencillo con centinela . 1052.6.4. Encadenamiento sencillo con encabezado . 1092.6.5. Representación a nivel de bits . 1102.6.6. Representación compacta de elementos repetidos . 1102.6.7. Multirrepresentación . 1112.6.8. Tabla comparativa . 111Ejercicios propuestos . 1122.7. El TAD Lista ordenada . 1152.8. Implementación del TAD Lista ordenada . 1162.8.1. Sobre el TAD Lista . 1162.8.2. Estructura sencillamente encadenada . 118Ejercicios propuestos . 119CAPITULO 3 - ESTRUCTURAS LINEALES: PILAS Y COLAS3.1. Pilas: definiciones y conceptos básicos . 1253.2. El TAD Pila . 1263.3. Ejemplos de utilización del TAD Pila . 127Ejercicios propuestos . 1313.4. Implementación del TAD Pila . 1323.4.1. Listas . 1323.4.2. Vectores . 1333.4.3. Estructura sencillamente encadenada . 134Ejercicios propuestos . 1363.5. Colas: definiciones y conceptos básicos . 1363.6. El TAD Cola . 137-vi -
Diseño y Manejo de Estructuras de Datos en CContenido3.7. Ejemplos de utilización del TAD Cola . 138Ejercicios propuestos . 1393.8. Implementación del TAD Cola . 1403.8.1. Listas . 1403.8.2. Vectores circulares . 1413.8.3. Estructura sencillamente encadenada . 143Ejercicios propuestos . 1453.9. El TAD Cola de prioridad . 1453.10. Implementación del TAD Cola de prioridad . 147Ejercicios propuestos . 1483.11. El TAD Ronda . 150Ejercicios propuestos . 1513.12. El TAD Bicola . 151Ejercicios propuestos . 152CAPITULO 4 - ESTRUCTURAS RECURSIVAS: ARBOLES BINARIOS4.1. Definiciones y conceptos básicos . 1554.2. El TAD Arbin: analizadoras para árboles binarios . 1594.3. Ejemplos de utilización del TAD Arbin . 160Ejercicios Propuestos . 1634.4. Recorrido de árboles binarios . 1654.4.1. Algoritmo de recorrido por niveles . 1674.4.2. Algoritmo iterativo de recorrido de árboles . 1684.4.3. Reconstrucción de un árbol a partir de sus recorridos . 170Ejercicios propuestos . 1714.5. Algorítmica de manejo de árboles . 172Ejercicios propuestos . 1804.6. Implementación de árboles binarios . 1814.6.1. Árboles sencillamente encadenados . 1814.6.2. Árboles con encadenamiento al padre . 1844.6.3. Árboles enhebrados por la derecha . 1854.6.4. Cursores . 1874.6.5. Representación secuencial . 1904.7. Destrucción y persistencia de árboles binarios . 1934.7.1. Persistencia con cursores . 1944.7.2. Persistencia con representación secuencial . 1954.7.3. Destructora del TAD Arbin . 197Ejercicios propuestos . 1984.8. El TAD árbol binario ordenado . 2014.8.1. Proceso de búsqueda . 2044.8.2. Proceso de inserción . 2044.8.3. Proceso de eliminación . 206Ejercicios propuestos . 2094.9. Árboles binarios ordenados balanceados . 2104.9.1. El TAD AVL . 2114.9.2. Estructuras de datos . 2124.9.3. Algoritmo de inserción . 2134.9.4. Algoritmo de eliminación . 220Ejercicios propuestos . 2224.10. El TAD árbol de sintaxis . 2234.10.1. Expresiones aritméticas en infijo . 2234.10.2. Árboles de sintaxis . 224- vii -
ContenidoDiseño y Manejo de Estructuras de Datos en C4.10.3. La tabla de símbolos . 2244.10.4. El TAD Arsin . 225Ejercicios propuestos . 228CAPITULO 5 - ESTRUCTURAS RECURSIVAS: ARBOLES N-ARIOS5.1. Motivación . 2315.2. Definiciones y conceptos básicos . 2325.3. El TAD ArbolN: analizadoras . 2335.4. Ejemplos de utilización . 235Ejercicios propuestos . 2395.5. Implementación del TAD ArbolN. . 2425.5.1. Vector de apuntadores . 2425.5.2. Hijo izquierdo - hermano derecho . 2445.5.3. Vectores dinámicos . 2465.5.4. Lista de hijos . 2475.5.5. Representaciones implícitas . 2495.6. El TAD ArbolN: algunas modificadoras y destructoras . 2505.6.1. Implementación sobre vector de apuntadores . 2525.6.2. Implementación sobre apuntadores . 2535.6.3. Implementación sobre vectores dinámicos . 2545.6.4. Implementación sobre lista de hijos . 255Ejercicios propuestos . 2565.7. El TAD Arbol1-2-3: un árbol triario ordenado . 257Ejercicios propuestos . 2615.8. El TAD Arbol2-3: un árbol triario ordenado balanceado . 2625.8.1. Definiciones y conceptos básicos . 2625.8.2. Especificación del TAD . .2655.8.3. Estructuras de datos . 2665.8.4. Algoritmo de inserción . 2665.8.5. Algoritmo de eliminación . 274Ejercicios propuestos . 2835.9. El TAD Trie: conjunto de palabras . 284Ejercicios propuestos . 2875.10. El TAD Cuadtree: representación de imágenes . 288Ejercicios propuestos . 2935.11. El TAD Árbol AND-O
capítulos 2 y 3 presentan las estructuras lineales de datos, tales como listas, pilas y colas. Los capítulos 4 y 5 estudian las estructuras recursivas de datos como los árboles binarios y los árboles n-arios. El capítulo 6 hace un estudio de estructuras de datos no lineales, como grafos dirigidos. Por último, el capítulo 7 trata el tema de
OFFICE 365 UNIANDES Cada cuenta de Office 365 UNIANDES tiene varias aplicaciones dentro de la misma como los son Outlook institucional, Microsoft TEAMS, Microsoft STREAM, entre otras, las mismas que serán utilizadas dentro de sus actividades académicas además de beneficios adicionales como licencias de Microsoft Office y Windows 2
Diecisiete fábulas del rey león Jean Muzi 3 Prefacio y fábulas Desarrollo En el prefacio del libro se mencionan las características del león que se conocerá en los relatos. Léaselo a los niños y coméntelo con ellos. Escriba en el pizarrón los adjetivos dados al león que se mencionan en el prefacio (miedoso, bur-lado, cobarde .
R. Swinburne Clymer, M.D. Prefacio por Dr. Allan F. Odell Publicado por LA CONFEDERACIÓN DE INICIADOS Beverly Hall, Quakertown, Pa. PREFACIO El autor del presente volumen fue bien conocido por el público lector de dos generaciones atrás. Vivió y escribió en una época de tensión y presión mental; en los días de la
LA PROBABILIDAD EN EL CURRÍCULO DE SECUNDARIA . Uno de los cinco núcleos temáticos de la materia de matemáticas de Educación Secundaria es el Tratamiento de la Información Estadística y del Azar. El Decreto 148/2002, de 14 de mayo, propone comenzar con una revisión de términos usados
el autor puede elegir distintos caminos para su sustentación. Así pues, dado que se trata del tramo más extenso del cuerpo del texto, y el que mayor diversidad y profundidad de los temas presenta, los párrafos de desarrollo pueden ser variados. A continuación, encontrarás seis formas de construir un párrafo de desarrollo: Conector de
lado, incapacita a aquellpersonasas que reinciden y, por el otro, disuade a los criminales de cometer un nuevo delito al aumentar la probabilidad de ser capturados. Si un individuo sabe que s
Owen of the Illinois Institute of Design asserts that “design is the creation process through which we employ tools and language to invent artifacts and institutions. As society has evolved, so has our ability to design.”16 He further describes the design pro
Anaesthetic Machine Anatomy O 2 flow-meter N 2 O flow-meter Link 22. Clinical Skills: 27 28 Vaporisers: This is situated on the back bar of the anaesthetic machine downstream of the flowmeter It contains the volatile liquid anaesthetic agent (e.g. isoflurane, sevoflurane). Gas is passed from the flowmeter through the vaporiser. The gas picks up vapour from the vaporiser to deliver to the .
