Facultade de Informática de A Coruña

Saltar seleccción de idioma
Idioma actual:
Saltar o menú
Menú:

Materias - Curso académico 2009/2010

Estructura de datos e da información (EDI)

Enxeñería Técnica en Informática de Sistemas (ETIS) - Código 614311102

1º Ciclo ,1º Curso
2º Cuatrimestre, Troncal
Créditos: 6.0 (4.5T + 1.5P) Créditos ECTS: 6.0
Alumnos matriculados: 166
Linguaxe na que se imparte: castelán
Máis informaciónSoftwareExamenesHorario

Descriptores

  • Estructura de datos e algoritmo de manipulación
  • Tipos abstractos de datos

Prerequisitos

Recomendada

Conflictos

Coincidencia da data de exame

Profesores

Obxetivos

  • - Coñecer os mecanismos de abstracción e valorar o papel importante que xoga a abstracción en xeral, e a de datos en particular, como ferramenta fundamental na metodoloxía de construcción de programas.
  • - Dominar a metodoloxía de deseño de tipos de datos: abstracción, especificación e implementación. Comprensión do concepto de Tipo Abstracto de Datos.
  • - Comprender a necesidade de separación entre os niveis de especificación, implementación e uso de un tipo abstracto de datos.
  • - Coñecer, desde o punto de vista da abstracción de datos, as estructuras de datos básicas que se utilizan en programación, as suas realizacións máis comúns, os seus algoritmos de manipulación e a sua utilidade en aplicacións básicas realistas.
  • - Aprender a manexar estas estructuras de datos básicas e ser capaces de crear outras máis complexas usando as primeiras como referencia.
  • - Apreciala relevancia que ten a elección dunha estructura de datos apropiada para a resolución dun problema de programación e razoar sobre a solución en canto a eficiencia e coste. Desenrolar a habilidade para definir e analizar alternativas de representación.
  • - Implementalas estructuras estudiadas utilizando unha linguaxe de programación imperativa de alto nivel (Pascal).

Bibliografía

Bibliografía recomendada
  • Dale, N. e Lilly, S.C.. Pascal y estructuras de datos. McGraw Hill. 2Edición. 1989.
  • Wirth, N.. Algoritmos y estructuras de datos. México D.F.. Prentice-Hall Hispanoamericana. 1986.
  • Aho A.V. , Hopcroft J.E. e Ullman J.D. . structuras de datos y algoritmos.. Wilmington, Delaware. Addison-Wesley Iberoamericana. 1988.
  • Lipschutz, S.. Estructuras de datos. Naucalpan de Juárez, Edo. de México. McGraw-Hill Interamericana de México, S.A. de C.V.. 1987.
  • Cairó O. e Guardati S. Estructuras de datos. Naucalpan de Juárez, Edo. de México. McGraw-Hill Interamericana de México, S.A. de C.V.. 1993.
  • Carmona, A., Merina, R., Madrid, F.J., Romero, J.A. , Fernández, N.L. e Prieto, M.. Pascal y Estructuras de datos. Servicio Publicaciones, Universidad de Córdoba.. 1999.
  • Collado, M. , Morales, R. e Moreno, J.J. Estructuras de Datos: Realización en Pascal. Madrid. Diaz de Santos. 1987.
  • Franch, X.. Estructuras de datos. Especificación, diseño e implementación. Barcelona. Edicions UPC. 2Edición. 1996.
  • Heileman, G. L.. Estructuras de Datos, Algoritmos, y Programación Orientada a Objetos. McGraw-Hill. 1998.
  • Hernández, R., Lázaro, J.C., Dormido, R. e Ros, S.. Estructuras de datos y algoritmos. Madrid. Prentice Hall. 2001.
  • Horowitz, E. e Sahni, S.. Fundamentals of Data Structures in Pascal. Rockville, Maryland. Computer Science Press. 1990.
  • Joyanes, L. e Zahonero, I.. Estructuras de Datos: algoritmos, abstracción y objetos. Madrid. McGraw-Hill/Interamericana de España. 1998.
  • Joyanes, L., Zahonero, I. , Fernández, M. e Sánchez, L.. Estructuras de Datos: libro de problemas. Madrid. McGraw-Hill. 1999.
  • Campos, J.. Estructuras de Datos y Algoritmos. Zaragoza. Prensas Universitarias de Zaragoza, Colección Textos Docentes. 2001.
  • Liskov B. e Guttag J.. Abstraction and specification in program development. The MIT Press. 1989.
  • Peña, R.. Diseño de programas. Formalismo y abstracción. Madrid. Prentice Hall. 2Edición. 1998.
  • Standish, T.. Data structures, algorithms, and software principles. Addison-Wesley. 1994.
  • Weiss, M.. Estructuras de datos y algoritmos. Wilmington, Delaware. Addison-Wesley Iberoamericana. 1995.

Temario

Bloque Temático I: Xestión dinámica da memoria e recursividade

  • - Tema 1: Xestión dinámica da memoria: Organización da memoria dun programa. Definición de variables de tipo punteiro. Reserva e destrucción dinámica da memoria. Asignación e comparación
  • - Tema 2: Recursividade: O concepto de recursión. Principios de deseño de funcións recursivas. Exemplos de funcións recursivas. A recursión con respecto á iteración. Algoritmos recursivos de ordenación.

Bloque Temático II: Introducción ós tipos abstractos e as estructuras de datos

  • - Tema 3: Introducción ós Tipos Abstractos de Datos (TAD): A abstracción e modularidade na programación. Evolución das linguaxes imperativas. Tipos abstractos de datos (TAD).

Bloque Temático III: Estructuras de datos lineais

  • - Tema 4: Listas: Especificación informal do TAD Lista. Implementacións do TAD Lista. O TAD Lista Ordenada.
  • - Tema 5: Pilas: Especificación informal do TAD Pila. Implementacións do TAD Pila. Aplicaciónss en computación.
  • - Tema 6: Colas: Especificación informal do TAD Cola. Implementacións do TAD Cola. Colas de prioridade. Aplicacións en computación.

Bloque Temático IV: Estructuras de datos no lineais

  • - Tema 7: Árbores: Definición de árbore e terminoloxía. Árbores binarios. Variantes de Árbores Binarios: de expresións e en montículo.
  • - Tema 8: Árbores de búsqueda: Árbores binarios de búsqueda. Árbores AVL

Programa de prácticas

  • Laboratorio 0. Desenrolo de algoritmos recursivos e programación con variables dinámicas. Traballo de grupo: Elaboración de apuntes sobre Tipos Abstractos de Datos.
  • Laboratorio 1. Solución dun problema mediante o uso de listas.
  • Laboratorio 2. Solución dun problema mediante o uso de colas, pilas e/ou listas.
  • Laboratorio 3. Solución de problemas mediante o uso de árbores.

Avaliación

Baséase, fundamentalmente, na calificación dun exame final único ó término do cuatrimestre, e na nota obtida nos exercicios prácticos de laboratorio.

O exame final da asignatura será eminentemente práctico para co alumno poida demostrar que adquiriu os coñecementos necesarios de abstracción e diseño de tipos abstractos de datos e que se adestrou o suficinte como para poseer as habilidades precisas para resolver supostos prácticos que impliquen a aplicación de ditas estructuras. Este tipo de examen persigue fomentar o traballo continuado ó largo do cuatrimestre e evitar o estudio exclusivamente memorístico.

A puntuación asignada a cada unha das preguntas do exame irá consignada na proba e será necesario alcanzar una puntuación de polo menos 5 puntos sobre un total de 10 para poder aprobar, aínda que poderá compensarse ca nota do apartado de prácticas a partir de un 3,5. Ademáis, poderanse valorar outros aspectos como a participación activa na clase ou a realización dos exercicios propostos.

A nota do exame supón un 80% da nota final, un 15% corresponde á nota de prácticas, e o 5% restante á participación activa na clase. As prácticas de laboratorio, que poderán sumar ata 1,5 puntos, evaluaránse de forma continuada establecendo controles periódicos de seguimento. A valoración global das prácticas será cualitativa (non APTO, APTO-, APTO o APTO+), e permitirá compensar positivamente a nota de teoría en algúns casos. A valoración de NON APTO significa que a práctica está suspensa e polo tanto a asignatura.

Como requisitos básicos para superalas prácticas esixese:

  • - A asistencia ós alumnos de primeira matrícula, porque sin duda considerase que a experiencia práctica é fundamental para asimilalos coñecementos teóricos.
  • - A entrega das prácticas obrigatorias nas datas indicadas.
  • - A realización de todolos apartados sinalados como obrigatorios.
  • - A realización individual e a orixinalidade da mesma. As prácticas manifestamente copiadas recibirán a calificación de NON APTO, tanto o orixinal como a copia.

Cumplidos estos riquisitos, outros aspectos a considerar a hora de valoralas prácticas serán:

  • - Presentación
    • Lexibilidade do código: uso correcto de comentarios, nomes de variables, sangrado do código
    • Metodoloxía
    • Estructuración adecuada do programa mediante o uso de subprogramas e módulos
    • Uso correcto de variables globais, locais e parámetros
    • Implementación e uso correctos do/os TDA/s implicados na práctica
  • - Funcionamento
    • Eficiencia nas realizacións
    • Correcto funcionamento do programa
    • Adecuación do código ás especificacións proporcionadas
  • - Outros
    • Progresión do alumno ó largo do curso
    • Asistencia regular ás clases de prácticas

As prácticas aprobadas (calificadas con APTO ou APTO+) serán válidas durante as convocatorias ordinarias de Xuño, e extraordinarias de Setembro e Decembro do ano en curso.

Última actualización 2/03/09