Código: 240204 | Asignatura: ESTRUCTURAS DE DATOS | ||||
Créditos: 6 | Tipo: Obligatoria | Curso: 1 | Periodo: 2º S | ||
Departamento: Ingeniería Matemática e Informática | |||||
Profesorado: | |||||
FARIÑA FIGUEREDO, FEDERICO (Resp) [Tutorías ] | ERICE ERRECART, CARLOS [Tutorías ] | ||||
ROYO ROMEO, ALBERTO [Tutorías ] |
Esta asignatura aborda dos aspectos fundamentales para el diseño de programas de tamaño medio.
En primer lugar se presentan metodologías de diseño que permiten escribir programas de calidad (correctos, fáciles de leer y entender, flexibles, eficientes y de fácil mantenimiento). Por un lado el diseño descendente que permite resolver grandes problemas como una sucesión de programas pequeños a diferentes niveles de abstracción ('divide y vencerás'). Por otro lado el diseño modular que permite organizar los programas de modo que sean mucho a más fáciles de mantener y chequear al limitar las decisiones de cambio a pequeños módulos.
En segundo lugar, se presenta el concepto de tipo abstracto de dato (TAD) y se trabaja con algunos TADs de amplio uso (pilas, colas, listas, etc.). Los TADs son, junto con los algoritmos, la base sobre la que se construyen los programas. En esta asignatura se trabaja con las primitivas que permiten construir TADs (tablas, tuplas y punteros), se explican diferentes implementaciones de diversos TADs, se comprueba como los TADs ayudan a resolver diferentes problemas y se resuelven problemas que aparecen al usar dichos TADs.
Diseño modular, diseño descendente, tipos abstractos de datos, pilas, colas, listas, tablas de dispersión (hash)
Las competencias genéricas que un alumno debería adquirir en esta asignatura son:
Las competencias específicas que un alumno debería adquirir en esta asignatura son:
Los Resultados de Aprendizaje que se pretenden alcanzar con esta asignatura se resumen a continuación:
RA1.- Entender las primitivas que permiten construir tipos estructurados a partir de tipos básicos (tablas, tuplas, punteros).
RA2.- Comprender el concepto de tipo abstracto de dato TAD.
RA3.- Diseñar tipos de datos adecuados a los problemas que se pretende resolver.
RA4.- Resolver problemas que precisen utilizar TADs de uso extendido (pilas, colas, ...).
RA5.- Utilizar módulos que implementen TADs para programar soluciones a problemas concretos.
RA6.- Comprender técnicas de diseño de algoritmos que permitan abordar ciertos problemas usando esquemas conocidos.
RA7.- Utilizar de forma eficiente algunas estructuras de datos en el diseño de algoritmos
Los mecanismos empleados para conseguir estos resultados, así como los mecanismos para evaluar su consecución se indican a continuación
Rsultado de Aprendizaje |
Se trabaja en los temas (T-> Teoría, P->Prácticas) |
Actividad Formativa | Instrumento de Evaluación |
RA1 | T2, T3, T4, T5, P3, P4, P5, P6, P7 | Todas | Todos |
RA2 | T2, T4, T5, P2, P6, P7 | Todas | Todos |
RA3 | T2, T3, T4, T5, T6 | Todas | Todos |
RA4 | T5, T6, P6, P7 | Todas | Todos |
RA5 | P3, P6, P7 | A3, A5, A6 | Examen/trabajo práctico final |
RA6 | T1, T3, T4, P2, P3, P4 | Todas | Todos |
RA7 | T%, T6, P6, P7 | Todas | Todos |
Metodología - Actividad | Horas Presenciales | Horas no Presenciales |
A-1 Clases magistrales | 22,5 (teoría y ejemplos) | |
A-2 Preparación de presentaciones de trabajos, proyectos, etc. | 7,5 | |
A-3 Sesiones prácticas en grupos reducidos | 24,5 (prácticas de laboratorio) | |
A-4 Aprendizaje basado en problemas y/o casos en grupos reducidos | 7,5 (corrección de problemas) | |
A-5 Elaboración de trabajos y/o proyectos y escritura de memorias | 22,5 | |
A-6 Actividades de evaluación | 2,5 | |
A-7 Tutorías en grupos muy reducidos | 3 (dudas teóricas o prácticas) | |
A-8 Estudio autónomo | 22,5 | |
A-9 Programación u otros trabajos en ordenador/laboratorio | 22,5 | |
A-10 Resolución de problemas, ejercicios y otras actividades de aplicación | 15 | |
Total | 60 | 90 |
Aspecto | Criterios | Instrumento | Peso |
N1 Participación Evaluación competencias: G9, FC6, FC7 |
Asistencia a las sesiones presenciales. Intervención y aportaciones |
Control de firmas en el laboratorio. Entrega en tiempo y forma de problemas de evaluación. |
10% |
N2 Conceptos teórico/prácticos Evaluación competencias: CB2, G1, G5, G9, T1, T4, T8, FC6, FC7, FC8 |
Comprensión de los conocimientos teóricos y su aplicación a la resolución de problemas. Capacidad de análisis y síntesis. Respuesta en tiempo, forma y adecuación de contenidos. Aplicación de los conocimientos en casos prácticos. Capacidad de comunicación correcta y precisa. |
Examen final. | 40% |
N3 Conceptos prácticos Evaluación competencias: CB2, G1, G5, G9, T1, T3, T4, T8, FC6, FC7, FC8 |
Aplicación de los conocimientos de teoría al desarrollo de programas correctos con criterios de calidad exigidos a este nivel. Aplicación de los conocimientos en la práctica. Creatividad, capacidad de análisis y síntesis. Capacidad de comunicación correcta y precisa. |
Examen/trabajo práctico final. | 50% |
Cada aspecto tendrá una nota entre 0 y 10 puntos. La nota final de la asignatura (N) se obtiene atendiendo al siguiente procedimiento:
Si (N2>=4 y N3>=4) o (N2 < 4 y N3 < 4) entoces N= 0,4*N2+0,5*N3+0,1*N1
Si (N2>=4 y N3 < 4) o (N2 < 4 y N3 >= 4) entoces N = minimo(4, (N2+N3)/2)
Superarán la asignatura los estudiantes cuya nota final N sea mayor o igual que 5,0.
Siguiendo la normativa de la Universida Pública de Navarra, los alumnos que no aprueben en la convocatoria ordinaria tendrán derecho a un examen extraordinario. En dicho examen podrán recuperar las notas N2 y N3.
Programa de Teoría
Tema 1. Acciones y funciones.
1.1. Acciones y funciones (modularidad 1). 1.2. Clases de parámetros. 1.3. Declaración de acciones. 1.4.Llamadas a acciones. 1.5. Declaración de funciones. 1.6. Llamadas a funciones. 1.7. Acciones y funciones internas. 1.8 Ámbito de validez de las declaraciones.
Tema 2. Acceso secuencial: ficheros.
2.1. Introducción. 2.2. Lectura y escritura de ficheros. 2.3. Esquema de recorrido. 2.4. Esquema de búsqueda. 2.5.Composición de esquemas.
Tema 3. Diseño descendente.
3.1. Introducción. 3.2. Ejemplo 1: parejas de caracteres. 3.3. Ejemplo 2: subsecuencias. 3.4. Ventajas del diseño descendente. 3.5. Definición de tipos, tipos estructurados.
Tema 4. Diseño modular.
4.1. Conceptos elementales. 4.2. Creadores y usuarios. 4.3. Descomposición modular. 4.4.Ventajas e inconvenientes.
Tema 5. Estructuras de datos lineales.
5.0. Tipos básicos y constructores de tipos. 5.1. Tipos abstractos de datos (TADs). 5.2. Especificación de TADs. 5.3. Pilas. 5.4. Colas. 5.5. Listas.
Tema 6. Tablas de dispersión
6.1.Diccionarios y conjuntos . 6.2. Tablas dispersas. 6.3. Funciones de dispersión. 6.4. Resolución de colisiones.
Programa de Prácticas
Las prácticas se organizan en las siguinetes sesiones: (Se asume que los estudiantes ya han desarrollado 14 horas de programación en Pascal de la asignatura Informática según la ficha).
Práctica 1. Compilación bajo linux (opcional)
Práctica 2. Acciones y funciones.
Práctica 3. Ficheros.
Práctica 4. Diseño descendente.
Práctica 5. Diseño Modular.
Práctica 6. TADs (implementación estática).
Práctica 7. TADs (implementación dinámica).
Acceda a la bibliografía que el profesorado de la asignatura ha solicitado a la Biblioteca.
Para la parte teórica de la asignatura:
Para la parte práctica de la asignatura. Sobre el lenguaje de programación Pascal
Para la parte práctica de la asignatura. Sobre el sistema operativo Linux
Para la parte práctica de la asignatura. Sobre el compilador de libre distribución FreePascal.
Para la parte práctica de la asignatura. Sobre el depurador de código de libre distribución ddd.
Para la parte práctica de la asignatura. Sobre otro software gnu (de libre distribución) que pueda necesitar (gdb, editores, ...).
Las actividades A-1 y A-4 se desarrollarán en el aula de teoría que se asigne a la asignatura. Se informará mendiante el aulario virtual cuando se conozca qué aula es.
La actividad A-3 y A-7 se desarrollará en alguno de los laboratorios de informática de la UPNa. Se informará mendiante el aulario virtual cuando se conozca qué aula es.