MATERIA: Introducción a Ciencias de la Computación II

CLAVE: COMP-320

SEMESTRE DE UBICACION: Tercero

AREA: Ciencias de la Computación

PRE-REQUISITOS: Ninguno

OBJETIVOS: Este curso continúa con el desarrollo de las ideas fundamentales en, el diseño y desarrollo de software. Se introduce a los alumnos el concepto de tipo abstracto de datos. Ese concepto se aplica a la implementación de varias estructuras de datos, incluyendo stacks, colas y árboles binarios. Se revisan algoritmos de búsquedas y ordenamientos que utilizan estas estructuras de datos. Otros temas incluyen recursividad, el ciclo de vida del software, especificación de requisitos, e introducción a verificación de programas. También en este curso se hace una introducción superficial a los problemas de complejidad de algoritmos

TEMARIO:

1. Especificación, verificación y validació
   • Tipos de especificaciones: especificaciones operativas; especificaciones descriptivas; construcción y usos de especificaciones

   • Verificación. Metas; enfoques, pruebas, análisis; ejecución simbólica; depuración

   • Lectura de código y diseño, recorridos estructurados

2. Tipos abstractos de datos

   • Conceptos Involucrados

   • Instrumentación de TAD (ADT) en un lenguaje de alto nivel, con ejemplos

3. Estructuras de datos básicos
   • Definición de las estructuras de datos lineales. Estructuras secuenciales. Arreglos empacados

   • Uso de las estructuras de datos básicos

   • Implementaciones contiguas y ligadas; ajuste para que correspondan al problema planteado, incluyendo contraposición entre tiempo y espacio

   • Estructuras múltiples. Búsqueda, inserción y remoción de elementos. Listas circulares y bidireccionales. Listas múltiples

4. Estructuras de datos no lineales
   • Presentación de las estructuras no lineales. Árboles y estructuras arborescentes. Árboles binarios. Representación de árboles arbitrarios en base a árboles binarios

   • Listas y recolección de basura. Asignación dinámica de espacio

5. Búsquedas y Ordenamientos
   • Algoritmos de ordenamiento de orden nlogn (quicksort, heapsort, mergesort); complejidad en el tiempo y el espacio: mejor y peor casos

   • Otros algoritmos de ordenamiento (Algoritmo de Shell, de cubetas y de radicales)

   • Comparación de algoritmos

   • Funciones de dispersión y resolución de colisiones

   • Algoritmos de búsqueda y manejo de árboles balanceados: árboles B y árboles AVL

   • Algoritmos de ordenamientos externos

BIBLIOGRAFIA:

• Tucker, A.B.;Bradley, W.J.; Cupper, R.D.; Epstein, R.D.; Kelemen, C.F.,Fundamentals of Computing, II. Abstraction, Data Structures, and Large Software Systems, C+ + Edition, McGraw-Hill, 1994

• Magidin, M., Estructuras De Datos, Editorial Trillas, 1991

BIBLIOGRAFÍA COMPLEMENTARIA:

• Aho, A. V.; Hopkroft, J. E.; Ullman, J. D., Estructuras De Datos Y Algoritmos, AddisonWesley Publishing Company, 1988

• Baase, S., Computer Algorithms, Introduction to Design and Analysis, Addison-Wesley Publishing Company, 1990

• Cormen, T. H.; Leierson, C. E.; Rivest, R. L., Introduction To Algolithms, McGraw-Hili Book Company, 1990

• Biggerstaff, T. J.; Perles A. J. edited by , Software Reusabi@, Volume Ii II, ACM Press, Addison-Wesley Publishing Company, 1989

• Ghezzi, C.; Jazayeri, M.; Mandrioli, D., Fundamentals Of Software Engineedng, Prentice-Hall Inc., 1991

• Glass, R. L., Software Conflict, Essays on the Ail and Science of Software Engineen'ng, Yourdon Press Computing Series, 1991

• Gehani, N.; McGettrick, A.D. ; Editores., Software Specificatio Techniques, AddisonWesley Publishing Company, 1980

• Gries, D., Editor, Programming in the 1990's, An Introduction to the Calculation of Programs, Springer Verlag, 1990

• Dijkstra, W. E. Editor, Fonnal Development Of Programs And Proofs, Addison-Wesley Publishing Company, 1990