Fundamentos de programación.
Objetivos propios del área de conocimiento:
1. Aprender las estructuras de datos principales
2. Aprender la programación orientada a objetos
3. Aprender un lenguaje orientado a objetos concreto, como el C++ o el Java
4. Diseñar la estructura de datos más eficiente para un determinado problema, dados unos requisitos de coste temporal y espacial5. Aprender a diseñar y desarrollar aplicaciones software con una complejidad y dimensión elevadas
Otros objetivos:
6. Fomentar la capacidad de análisis y síntesis
7. Fomentar la comunicación oral y escrita en la propia lengua
8. Fomentar la habilidad de búsqueda e integración de información de distintas fuentes
9. Fomentar la capacidad de resolución de problemas
10. Fomentar la aplicación de los conocimientos en la práctica
11. Fomentar el trabajo en equipo
12. Fomentar la habilidad para aprender y resolver problemas de manera autónoma
13. Potenciar los hábitos de trabajo y estudio continuado
1. Especificación algebraica de tipos abstractos de datos
1.1. Concepto de tipo abstracto de datos
1.2. Especificación algebraica de TADs
1.2.1. Signaturas y álgebras
1.2.2. Especificación ecuacional
1.3. Ejemplos. Las cadenas de caracteres. Una biblioteca.
2. Estructuras de datos lineales
2.1. Introducción
2.2. Pila
2.2.1. Idea intuitiva
2.2.2. Especificación algebraica
2.2.3. Implementación estática y dinámica
2.2.4. Ejercicios
2.3. Cola
2.3.1. Idea intuitiva
2.3.2. Especificación algebraica
2.3.3. Implementación estática y dinámica
2.3.4. Ejercicios
2.4. Listas
2.4.1. Idea intuitiva
2.4.2. Listas con punto de interés. Especificación. Implementación secuencial, encadenada y co
n punteros
2.4.3. Listas ordenadas por posición. Especificación. Implementación
2.4.4. Listas ordenadas por llave. Especificación. Implementación
2.4.5. Listas ordenadas por distintos campos
2.4.6. Variantes de las listas. Listas circulares. Listas doblemente encadenadas
2.4.7. Multilistas
2.5. Ejercicios de aplicación de las ED lineales
3. Estructuras de datos funcionales
3.1. Introducción
3.2. Especificación algebraica del TAD tabla
3.3. Implementación con listas desordenadas
3.4. Implementación con listas ordenadas
3.5. Implementación con vectores
3.6. Implementación con tablas de hash
3.7. Hashing
3.7.1. Funciones de hashing
3.7.2. Posibles representaciones
4. Árboles
4.1. Definiciones y conceptos básicos
4.2. Los TADs árbol binario y árbol n-ario
4.3. Representación de árboles
4.4. Recorridos de árboles
4.5. Árboles de búsqueda
4.6. Árboles binarios con hilos
4.7. Arboles equilibrados
4.7.1. AVL
4.7.2. Árboles 2-3
4.7.3. Árboles B
4.8. Heaps
4.9. Tries
5. Grafos
5.1. Introducción
5.2. Definiciones
5.3. Especificación algebraica
5.4. Representación de grafos
5.4.1. Matrices de adyacencia
5.4.2. Listas de adyacencia
5.4.3. Multilistas de adyacencia
5.5. Algoritmos básicos sobre grafos
5.5.1. Búsqueda de caminos mínimos
5.5.2. Algoritmo de Dijkstra
5.5.3. Algoritmo de Floyd
5.5.4. Algoritmo de Warshall
5.6. Recorridos sobre grafos
5.6.1. Profundidad prioritaria
5.6.2. Anchura prioritaria
5.6.3. Ordenación topológica
5.7. Árboles de expansión minimales
5.7.1. Algoritmo de Prim
5.7.2. Algoritmo de Kruskal
6. Programación orientada a objetos
6.1. Diseño orientado a objetos
6.2. Clases y objetos en Java/C++
6.3. Herencia y interfícies
6.4. Clases de utilidad
6.5. Tratamiento de excepciones
La asignatura se imparte en tres tipos de sesiones:
- sesiones magistrales
- sesiones de resolución de ejercicios
- sesiones de laboratorio
La mayor parte de las sesiones son clases magistrales. Al final de cada tema (y al final de cada parcial), se hace una sesión de ejercicios donde se aplican de manera práctica los conocimientos adquiridos en las clases magistrales.
A medianos de curso se realizan dos sesiones guiadas de laboratorio de dos horas cada una, que están destinadas a poner en práctica el lenguaje de programación (Java/C++). En concreto, se plantea un problema y los alumnos deben hacer una aplicación software que lo resuelva. En el laboratorio, el alumno puede compilar y ejecutar el programa con la ayuda del profesor. Principalmente, las sesiones están orientadas como introducción de la práctica 1 de la asignatura.
La parte práctica de la asignatura consiste en diseñar, implementar y testear programas software para la resolución de problemas concretos. Para llevarlo a cabo, el alumno debe integrar distintos temas de la asignatura. Hay un total de dos prácticas y están pensadas para resolverse incrementalmente, con un nivel de dificultad creciente. Las prácticas potencian el trabajo en equipo, pues se realizan en grupos de tres personas.
La atención al alumnado se realiza con soporte presencial y no presencial mediante la intranet de la asignatura. En ésta, se cuelgan documentación, ejemplos de aplicaciones, enlaces de interés, se anuncian noticias en el tablero, permite el envío de e-mails a la aula, etc. Para atender a las dudas, el alumno dispone de horarios de tutoría, fórums en la intranet y el e-mail.
La evaluación de la asignatura consta de dos partes: la que entendemos como nota de teoría y la nota de prácticas. La parte teórica es evaluada con los exámenes y ejercicios de evaluación continuada (Nex) y la parte práctica mediante las prácticas que se realizan durante el curso (Nprac).
Los requisitos para aprobar la asignatura son:
Nex >= 4.5
Nprac >= 5
La nota final de la asignatura (Nasig) se calcula:
Nasig = Nex * 0.75 + Nprac * 0.25
La asignatura se aprueba si Nasig >= 5
- Cálculo de la nota de teoría:
Para valorar el trabajo continuado, el alumno se puede presentar por parciales. En caso contrario, el alumno debe examinarse de un examen de todo el curso, que se hace en Junio o en Septiembre. Si el alumno se presenta por parciales, la nota Nex es la media geométrica de los tres parciales. Si el alumno se presenta de un examen único, la nota Nex es la que se obtiene de éste examen.
También se realiza una evaluación continuada del alumno. Ésta consiste en la entrega optativa de ejercicios resueltos por el alumno. Hay aproximadamente uno o dos ejercicios propuestos por cada tema que el alumno debe resolver individualmente. En función de la calidad de los ejercicios entregados, la nota de teoría sube un máximo de un punto sobre la nota final de los exámenes.
- Cálculo de la nota de prácticas:
La nota de la práctica se calcula a partir de las dos notas prácticas que se presentan en una fecha fijada. Para valorar el trabajo continuado, si el alumno entrega la práctica fuera de la fecha fijada, la nota máxima a la que aspira es un 6.
Hay dos prácticas a realizar, las cuales se deben aprobar obligatoriamente por separado. En este caso, la nota de prácticas se calcula del siguiente modo:
Nprac = 0.25 * Prac1 + 0.75 * Prac2
Los criterios de evaluación de las prácticas son:
- El análisis y diseño del programa y las estructuras de datos
- El funcionamiento
- La calidad del software
- La calidad de la memoria
- La entrevista personal
Objetivo 1: Aprender las estructuras de datos principales
Evaluación: [A,B,C,D,F,G,H]
Objetivo 2: Aprender la programación orientada a objetos
Evaluación: [A,B,C,D,F,G,H]
Objetivo 3: Aprender un lenguaje orientado a objetos concreto, como puede ser C++ o Java
Evaluación: [A,B,C,D,F,G,H]
Objetivo 4: Diseñar la estructura de datos más eficiente para un determinado problema, dados unos requisitos de coste temporal y espacial
Evaluación: [A,B,C,D,F,G,H]
Objetivo 5: Aprender a diseñar y desarrollar aplicaciones software con una complejidad y dimensión elevadas
Evaluación: [B,D,F,G,H]
Objetivo 6: Fomentar la capacidad de análisis y síntesis
Evaluación: [A,B,C,D,F,G,H]
Objetivo 7: Fomentar la comunicación oral y escrita en la propia lengua
Evaluación: [A,B,F,G,H]
Objetivo 8: Fomentar la habilidad para buscar e integrar información de diferentes fuentes
Evaluación: [B,D,F,G,H]
Objetivo 9: Fomentar la capacidad de resolución de problemas
Evaluación: [A,B,C,D,F,G,H]
Objetivo 10: Fomentar la aplicación de los conocimientos a la práctica
Evaluación: [A,B,C,D,F,G,H]
Objetivo 11: Fomentar el trabajo en equipo
Evaluación: [B,F,G,H]
Objetivo 12: Fomentar la habilidad para aprender y resolver problemas de manera autónoma
Evaluación: [A,B,C,D]
Objetivo 13: Potenciar los hábitos de trabajo y estudio continuados
Evaluación: [A,B,C,D,F,G,H]
- Xavier Franch, Estructures de Dades. Especificació, disseny i implementació, Edicions UPC, 1993.
- Ester Bernadó, Albert Orriols, Recull d'exàmens d'estructures de dades, Enginyeria i Arquitectura La Salle, 2004.
- Ester Bernadó, Albert Orriols, Exercicis d'Estructures de Dades, Enginyeria i Arquitectura La Salle, 2004.
- Ester Bernadó, Exercicis de C++, Enginyeria i Arquitectura La Salle, 2004.
- Ester Bernadó, Exercicis de Java, Enginyeria i Arquitectura La Salle, 2004.
Horowitz, E. and Sahni, Fundamentals of Data Structures in C++, S. Computer Science Press, 1995.
Aho, Hopcroft and Ullman, Estructuras de Datos y Algoritmos, Addison-Wesley Iberoamericana, 1998.
Mark Allen Weiss, Estructuras de datos y algoritmos, Addison-Wesley Iberoamericana, 1992.
Herbert Schildt, C++: Guia de autoenseñanza, McGraw-Hill, 1995.
Bjarne Stroustrup, The C++ Programming Language (Second Edition), Addison-Wesley, 1991.
Ken Arnold, James Gosling, David Holmes, The java programming language, Addison-Wesley, 2000.
Bruce Eckel, Thinking in Java, 3rd Edition, Prentice Hall, 2002 (disponible per Internet -vegeu link-).
H. Ehrig and Mahr. Fundamentals of Algebraic Specification, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1985.
F. Escudero i J.M. Garrell, Fonaments de Programació, Bruño/EUETT, 1993.