Algoritmos y Estructura de Datos
Guía de Aprendizaje – Información al estudiante
1 Datos Descriptivos
Asignatura | Algoritmos y Estructura de Datos |
Materia | Programación |
Departamento | LSIIS |
responsable | |
Créditos ECTS | 6 |
Carácter | Obligatoria |
Titulación | Grado de Ingeniería Informática |
por la Universidad Politécnica de Madrid | |
Curso | Segundo |
Especialidad | No aplica |
Curso académico | 2013-2014 |
Semestre en el que | Ambos (septiembre a enero y febrero a junio) |
se imparte | |
Semestre principal | Septiembre a enero |
Idioma en el que | Castellano |
se imparte | |
Página Web | http://web3.fi.upm.es/AulaVirtual/course/view.php?id=272 |
2 Profesorado
NOMBRE Y APELLIDO | DESPACHO | Correo electrónico |
---|---|---|
Pablo Nogueira (Coord.) | D-2304 | pnogueira@fi.upm.es |
Manuel Carro | D-3323 | mcarro@fi.upm.es |
Lars-Ake Fredlund | D-2309 | lfredlund@fi.upm.es |
Ricardo Jiménez | D-2313 | rjimenez@fi.upm.es |
Tonghong Li | D-2312 | tonghong@fi.upm.es |
Marta Patiño | D-2313 | mpatino@fi.upm.es |
Germán Puebla | D-2305 | german@fi.upm.es |
3 Conocimientos previos requeridos para poder seguir con normalidad la asignatura
Asignaturas superadas | Programación I y Programación II |
Otros resultados de | Capacidad de modelar y resolver matemáticamente |
aprendizaje necesarios | problemas reales. |
4 Objetivos de aprendizaje
Código | Competencias Transversales | Nivel |
---|---|---|
CG-1/21 | Capacidad de resolución de problemas aplicando | 2 |
conocimientos de matemáticas, ciencias e ingeniería. | ||
CG-2/CE45 | Capacidad para el aprendizaje autónomo y la actualización | 2 |
de conocimientos, y reconocimiento de su necesidad en el | ||
área de la informática. | ||
CG‐3/4 | Saber trabajar en situaciones carentes de información y | 2 |
bajo presión, teniendo nuevas ideas, siendo creativo. | ||
CG-5 | Capacidad de gestión de la información. | 2 |
CG-6 | Capacidad de abstracción, análisis y síntesis. | 2 |
CG-7/8/9/ | Capacidad para trabajar dentro de un equipo, | 2 |
10/16/17 | organizando, planificando, tomando decisiones, negociando | |
y resolviendo conflictos, relacionándose, y criticando | ||
y haciendo autocrítica. | ||
CG19 | Capacidad para usar las tecnologías de la información y | 2 |
la comunicación. |
LEYENDA: Nivel de adquisición 1: Bajo Nivel de adquisición 2: Medio Nivel de adquisición 3: Alto
Código | Competencias Específicas | Nivel |
---|---|---|
CE-6 | Comprender intelectualmente el papel central que tienen | 4 |
los algoritmos y las estructuras de datos, así como una | ||
apreciación del mismo. | ||
CE-8 | Poseer destrezas fundamentales de la programación que | 4 |
permitan la implementación de los algoritmos y las | ||
estructuras de datos en el software. | ||
CE-9 | Poseer las destrezas que se requieren para diseñar e | 4 |
implementar unidades estructurales mayores que utilizan | ||
los algoritmos y las estructuras de datos, así como las | ||
interfaces por las que se comunican estas unidades. |
LEYENDA: Nivel de adquisición 1: Conocimiento Nivel de adquisición 2: Comprensión Nivel de adquisición 3: Aplicación Nivel de adquisición 4: Análisis y síntesis
5 Resultados de aprendizaje
5.1 Resultados de aprendizaje de la asignatura
Código | Resultado de aprendizaje | Competencias | Nivel de |
---|---|---|---|
asociadas | adquisición | ||
RA1 | Programar aplicaciones mediante | CE-8, CE-9 | 4 |
librerías existentes de TADs. | Todas las CG | ||
RA2 | Resolver problemas algorítmicos | CE-6, CE-8 | 4 |
no triviales. | Todas las CG | ||
RA3 | Razonar sobre la complejidad | CE-6, CE-8 | 2 |
algorítmica. | Todas las CG | ||
RA4 | Razonar sobre la terminación | CE-6, CE-8 | 2 |
de algoritmos y programas. | Todas las CG | ||
RA5 | Usar y definir estructuras de datos | CE-6, CE-8, | 4 |
eficientes y adecuadas a cada | CE-9 | ||
problema. | Todas las CG |
5.2 Sistema de evaluación de la asignatura
5.2.1 Indicadores de logro
Ref | Indicador | Relación |
---|---|---|
con RA | ||
I1 | Sabe elegir de entre varias opciones el TAD | RA5 |
más adecuado para resolver un problema. | ||
I2 | Comprende las implicaciones prácticas de los | RA3 |
diferentes niveles de complejidad asintótica. | ||
I3 | Comprende y sabe calcular la complejidad asintótica | RA3 |
de algoritmos y programas. | ||
I4 | Demuestra informalmente la terminación de un | RA4 |
algoritmo o un programa. | ||
I5 | Comprende el diseño de TADs relativamente avanzados. | RA5 |
I6 | Es capaz de implementar TADs relativamente avanzados. | RA5 |
I7 | Conoce las colecciones estándar de Java. | RA1 |
I8 | Comprende y utiliza librerías de código de tamaño | RA1 |
considerable que definen e implementan TADs avanzados. | ||
I9 | Comprende y sabe aplicar algoritmos de búsqueda | RA2 |
y de ordenación, generando código apropiado. | ||
I10 | Comprende y sabe aplicar técnicas algorítmicas | RA2 |
generando código apropiado. |
5.2.2 Evaluación sumativa
Breve descripción de | Momento | Lugar | Peso en la |
---|---|---|---|
las actividades evaluables | calificación | ||
Exámenes de teoría | 2 en el semestre | Aulas de evaluación | 55% |
(evaluación continua) | |||
o 1 en el semestre | |||
(evaluación prueba final) | |||
Ejercicios de laboratorio | 10 en el semestre | Aula informática | 45% |
6 Criterios de calificación
6.1 Introducción
El año académico se divide en dos periodos de matriculación o semestres: primer semestre de septiembre a enero y segundo semestre de febrero a junio. Las normas de esta sección se aplican a los dos semestres.
Los criterios de evaluación de la asignatura se establecen en conformidad con la "Normativa Reguladora de los Sistemas de Evaluación" (en adelante "Normativa Reguladora") actualmente vigente en la Universidad Politécnica de Madrid para los planes de estudio adaptados al R.D. 1393/2007.
Según dicha normativa, por cada periodo de matrícula de las asignaturas (es decir, por cada semestre) se establecen dos convocatorias de evaluación:
-
Convocatoria ordinaria, que se corresponde con las actividades de
evaluación que se realizan durante el desarrollo de la asignatura en cada
semestre y, en su caso, en el periodo inmediatamente posterior a su
finalización que se fije en el calendario académico de la universidad.
Cada semestre tiene su convocatoria ordinaria a la que concurren los alumnos matriculados en el semestre.
-
Convocatoria extraordinaria, que se corresponde con las actividades de
evaluación que deben realizar aquellos estudiantes que no logren superar
la asignatura en la convocatoria ordinaria.
La convocatoria extraordinaria tiene lugar en el mes de julio y pueden concurrir a ella los alumnos que han estado matriculados en cualquiera de los semestres del año académico y no han superado la asignatura.
A continuación se detallan, para cada convocatoria, los sistemas de evaluación y las normas.
Es importante advertir que las normas pueden ser modificadas al comienzo de cada semestre en función de la disposición de recursos de la Facultad de Informática de Madrid para impartir la asignatura. Dichas modificaciones se anunciarán con toda la antelación posible en el transcurso de las clases, a través de los recursos informáticos de los que dispone la asignatura o, en su defecto, a través cualesquiera otros medios disponibles a través de la UPM y sus departamentos.
6.2 Convocatoria ordinaria
6.2.1 Sistemas de evaluación
Según el Artículo 20 de la Normativa Reguladora, en la convocatoria ordinaria el alumno puede optar únicamente por uno de los siguientes sistemas de evaluación:
- Sistema de evaluación continua.
- Sistema de evaluación mediante prueba final.
El sistema de evaluación continua será el que se aplique en general a todos los alumnos de la asignatura.
El alumno que desee seguir el sistema de evaluación mediante prueba final deberá comunicarlo mediante escrito firmado al coordinador de la asignatura en un plazo de 15 días naturales desde el comienzo de las clases. Los detalles del procedimiento y el escrito a rellenar se encuentran disponibles en en http://www.fi.upm.es/?pagina=1147
6.2.2 Sistema de evaluación continua
- Actividades evaluables
Se evalúa al alumno de forma continua a lo largo del semestre mediante las siguientes actividades:
-
Parte de teoría: 2 exámenes de teoría.
Cada examen de teoría se evalúa en una escala de 0 a 10.
Las fechas de realización y las partes del temario correspondientes a cada examen se indicarán con suficiente antelación de acuerdo a la Normativa Reguladora.
Los exámenes se realizarán en general en el horario de Actividades de Evaluación del semestre, aunque podrá recurrirse a otros horarios, como por ejemplo, el horario de actividades de laboratorio, semanas destinadas al proceso de evaluación en el calendario docente, etc.
-
Parte de laboratorio: 10 ejercicios de laboratorio.
Se realizarán en las Aulas Informáticas en el horario establecido. Cada ejercicio consiste en la resolución de problemas de programación con algoritmos y estructuras de datos.
Es obligatoria la asistencia a al menos 80% de las clases de laboratorio.
Los ejercicios de laboratorio se realizarán en grupos de 2 alumnos.
Para poder ser calificados, los ejercicios de laboratorio deben superar las pruebas del sistema de entregas de la asignatura. De no superarlas, el ejercicio se calificará como "no aceptado".
Cada ejercicio de laboratorio aceptado se evalúa en una escala de 0 a 10.
Para optar a la máxima nota, los ejercicios deben haber sido aceptados por el sistema de entrega antes de la fecha y hora límite, la cual será publicada al comienzo del semestre y será de aplicación a todos los ejercicios de laboratorio, a excepción de aquellos para los que se estipule una fecha y hora de entrega diferente en su enunciado. Los ejercicios aceptados con posterioridad tendrán una reducción en su nota del 20% por cada 24 horas posteriores a la fecha y hora límite. Llegado al 100% de penalización se puede seguir entregando el ejercicio pero la nota máxima del mismo será 0.
Los alumnos que no hayan superado la asignatura pero hayan superado en convocatorias anteriores o bien la parte de teoría o bien la parte de laboratorio no están obligados a repetir la parte superada.
-
Parte de teoría: 2 exámenes de teoría.
- Criterios de calificación
- Parte de teoría: los alumnos deben entregar todos los exámenes de teoría y la nota media de los exámenes debe ser al menos 4.5. Los alumnos que cumplan estos requisitos tendrán la parte de teoría de la asignatura superada, su nota de teoría se guardará para siguientes convocatorias, y quedarán exentos de la obligación de repetir la parte de teoría. Los alumnos con notas de teoría guardadas pueden realizar los exámenes de teoría en siguientes convocatorias, pero perderán la nota guardada.
- Parte de laboratorio: los alumnos deben asistir al 80% de las clases de laboratorio y tener aceptados todos los ejercicios de laboratorio. Los alumnos que cumplan estos requisitos tendrán la parte de laboratorio superada, su nota de laboratorio se guardará para siguientes convocatorias, y quedarán exentos de la obligación de repetir la parte de laboratorio. Los alumnos con notas de laboratorio guardadas pueden realizar los laboratorios en siguientes convocatorias, pero perderán la nota guardada.
La nota de la asignatura para la convocatoria se calcula usando la siguiente fórmula:
Nota Final = 0.55 * T + 0.45 * L
donde T es la nota media de la parte de teoría, L es la nota media de la parte de laboratorio.
El alumno habrá superado la asignatura en la convocatoria ordinaria si la Nota Final es al menos 5. En caso contrario la calificación para la convocatoria ordinaria será "suspenso". Excepcionalmente, en caso de que no se entregue ningún examen de teoría y ningún ejercicio de laboratorio durante el semestre la calificación de la asignatura para la convocatoria ordinaria será "no presentado".
En caso de verificarse plagio tanto en los exámenes de teoría o en las entregas de laboratorio, los alumnos involucrados, copiador(es) y copiado(s) anuentes, recibirán la siguiente sanción:
- Tendrán la asignatura suspensa en las siguientes convocatorias del año académico.
- Se desecharán las notas guardadas de cualquiera de las partes de la asignatura que tuvieran superadas, estando obligados a repetir la asignatura completa.
- Se solicitará a Jefatura de Estudios la apertura de su expediente académico para que conste en el mismo que han plagiado en la asignatura.
6.2.3 Sistema de evaluación mediante prueba final
El alumno que desee seguir el sistema de evaluación mediante prueba final deberá comunicarlo mediante escrito firmado al coordinador de la asignatura en un plazo de 15 días naturales desde el comienzo de las clases. Los detalles del procedimiento y el escrito a rellenar se encuentran disponibles en en http://www.fi.upm.es/?pagina=1147
En esta modalidad se evalúa a los alumnos con las mismas actividades y normas que en el sistema de evaluación continua con la única salvedad de que la parte de teoría consta de un único examen al final del semestre, el cual abarca todo el temario de la asignatura. La nota del examen debe ser al menos 4.5.
La nota de la asignatura se calcula usando la misma fórmula que para el sistema de evaluación continua, con la salvedad de que T será la nota del examen final.
6.3 Convocatoria extraordinaria
Los alumnos que no han superado la asignatura en la convocatoria ordinaria, independientemente del semestre del año académico cursado y del sistema de evaluación elegido para dicha convocatoria ordinaria, tienen la posibilidad de concurrir a la convocatoria extraordinaria del mes de julio. En esta convocatoria se evalúa la asignatura completa.
- Los alumnos con la parte de teoría no superada deben realizar y entregar un examen de teoría que abarca todo el temario de la asignatura. La nota del examen debe ser al menos 4.5.
- Los alumnos con la parte de laboratorio no superada deben realizar un ejercicio de laboratorio en el Aula Informática de temática similar a los propuestos en el semestre. El ejercicio debe ser aceptado por el sistema de entrega antes de la fecha y hora límite establecida.
La nota de la asignatura para la convocatoria extraordinaria se calcula usando la siguiente fórmula:
Nota Final = 0.55 * T + 0.45 * L
donde T es la nota del examen de teoría y L es la nota del ejercicio de laboratorio.
El alumno habrá superado la asignatura en la convocatoria extraordinaria si la Nota Final es al menos 5. En caso contrario la calificación para la convocatoria extraordinaria será "suspenso". La nota de la parte de teoría o laboratorio superada se guardará para siguientes convocatorias, quedando los alumnos exentos de la obligación de repetir dicha parte.
Excepcionalmente, en caso de que no se entregue el examen de teoría y el ejercicio de laboratorio la calificación de la asignatura para la convocatoria extraordinaria será "no presentado".
En caso de verificarse plagio se aplicará la sanción descrita en el párrafo "En caso de verificarse plagio" de la sección *Sistema de evaluación continua.
6.4 Alumnos que han cambiado de plan de estudios
Independientemente del sistema de evaluación elegido para la convocatoria ordinaria y en concordancia con lo que se ha venido haciendo en el plan de estudios de 1996, los alumnos con el proyecto o la práctica de Estructuras de Datos II aprobado y realizado en Java tienen la parte de laboratorio superada. La nota de dicha parte será la nota que hayan obtenido en el proyecto o la práctica de Estructuras de Datos II.
7 Contenidos y Actividades de Aprendizaje
Contenidos específicos
Bloque/Tema/Capítulo | Apartado | Indicadores |
---|---|---|
relacionados | ||
Bloque 1: | 1.1 Conceptos de programación en Java | I1 I5 I6 I7 I8 |
TADs secuenciales y | para la abstracción de datos. | |
complejidad | 1.2 Listas enlazadas y sus algoritmos. | I1 I5 I6 I7 I8 |
1.3 Análisis y complejidad de algoritmos. | de I2 a I4 | |
1.5 Iteradores. | de I1 a I8 | |
Bloque 2: | 2.1 Comparación, comparadores, | de I1 a I9 |
TADs con manejo de | colas con prioridad y ordenación. | |
prioridades, | 2.2 Árboles generales y binarios. | de I1 a I9 |
ordenación, y árboles | 2.3 Montículos y ordenación. | de I1 a I9 |
Bloque 3: Algoritmos | 3 Algoritmos básicos, | I2 I3 I4 I8 I9 I10 |
y ordenación | técnica divide y vencerás, | |
ordenación por mezcla y | ||
ordenación rápida. | ||
Bloque 4: | 4.1 Funciones finitas. | de I1 a I8 |
Funciones finitas y | 4.2 Tablas de dispersión. | de I1 a I8 |
árboles | 4.2 Funciones finitas con | de I1 a I8 |
dominio ordenado. | ||
4.3 Árboles binarios de búsqueda, | de I1 a I9 | |
AVL, multicamino, (2,4), (a,b) y B. |
8 Breve descripción de las modalidades organizativas y los métodos de enseñanza empleados
CLASES DE TEORÍA | Método expositivo y estudio de casos. |
CLASES DE PROBLEMAS | Ejercicios de laboratorio. |
Aprendizaje basado en resolución de problemas. | |
PRÁCTICAS | Ejercicios de laboratorio más extensos. |
Aprendizaje basado en resolución de problemas. | |
TRABAJOS AUTÓNOMOS | Ejercicios voluntarios. |
TRABAJOS EN GRUPO | Ejercicios de laboratorio. |
TUTORÍAS | Atención personalizada en |
teoría y laboratorio. |
9 Recursos didácticos
BIBLIOGRAFÍA | M. T. Goodrich y R. Tamassia, |
Data Structures and Algorithms in Java | |
International Student Version, 5ed, Wiley. | |
–——————————————————————— | |
T. Cormen, C. Leiserson, R. Rivest y C. Stein, | |
Introduction to Algorithms 2ed, MIT Press. | |
–——————————————————————— | |
P. Sestoft, Java Precisely, 2ed, MIT Press. | |
–——————————————————————— | |
M. Augenstein, Y. Langsam, A. M. Tenenbaum, | |
Data Structures Using Java, 2003, Prentice Hall | |
–——————————————————————— | |
A. Aho, J. Hopcroft, J. Ullman, | |
Data Structures and Algorithms Addison-Wesley | |
RECURSOS WEB | Sitio Moodle de la asignatura |
http://web3.fi.upm.es/AulaVirtual/course/view.php?id=272 | |
Java Language Specification, 3rd Edition, | |
http://java.sun.com/docs/books/jls. | |
Java Platform SE (incluye JCF) | |
http://download.oracle.com/javase | |
Librería del libro de la asignatura: | |
http://net3.datastructures.net/download.html (código). | |
http://net3.datastructures.net/doc5/index.html (Javadoc). | |
http://ww0.java5.datastructures.net/ (ejemplos, transparencias). | |
EQUIPAMIENTO | Aulas docentes con proyector y pizarra. Aulas informáticas con |
proyector, pizarra y ordenadores para los alumnos. | |
Compiladores y JRE de Java versión 1.6, entorno de desarrollo | |
integrado (IDE) Eclipse. |
10 Cronograma de trabajo
Semana | Actividades en Aula | Actividades en | Trabajo | Trabajo | Actividades | Otros |
---|---|---|---|---|---|---|
Aula Informática | Individual | en Grupo | de Evaluación | |||
Semana 1 | Conceptos de programación en Java | Estudio teoría | ||||
(8 horas) | para la abstracción de datos (2 horas) | y repaso Programación II | ||||
(6 horas) | ||||||
Semana 2 | Conceptos de programación en Java | Estudio teoría | ||||
(8 horas) | para la abstracción de datos (2 horas) | y repaso. | ||||
(6 horas) | ||||||
Semana 3 | Listas enlazadas y sus algoritmos | Laboratorio | Estudio teoría | |||
(9 horas) | (2 horas) | (2 horas) | y repaso. | |||
(5 horas) | ||||||
Semana 4 | Listas enlazadas, | Laboratorio | Estudio teoría | |||
(9 horas) | Complejidad de Algoritmos (2 horas) | (2 horas) | y repaso laboratorio (5 horas) | |||
Semana 5 | Listas enalzadas, Iteradores | Laboratorio | Estudio teoría | |||
(9 horas) | (2 horas) | (2 horas) | y repaso laboratorio (5 horas) | |||
Semana 6 | Comparadores. Colas con prioridad | Laboratorio | Estudio teoría | |||
(10 horas) | (2 horas) | (2 horas) | y repaso laboratorio (6 horas) | |||
Semana 7 | Colas con prioridad, ordenación | Revisión para examen (7 horas) | Primer examen de teoría | |||
(10 horas) | (2 horas) | (1 hora) | ||||
Semana 8 | Árboles generales y binarios | Estudio teroía | ||||
(10 horas) | (2 horas) | y repaso laboratorio (8 horas) | ||||
Semana 9 | Árboles generales, binarios y de búsqueda | Laboratorio | Estudio teoría | |||
(10 horas) | (2 horas) | (2 horas) | y repaso laboratorio (6 horas) | |||
Semana 10 | Montículos y ordenación | Laboratorio | Estudio teoría | |||
(10 horas) | (2 horas) | (2 horas) | y repaso laboratorio (6 horas) | |||
Semana 11 | Funciones finitas | Laboratorio | Estudio teoría | |||
(10 horas) | (2 horas) | (2 horas) | y repaso laboratorio (6 horas) | |||
Semana 12 | Funciones finitas y | Laboratorio | Estudio teoría | |||
(10 horas) | Tablas de dispersión (2 horas) | (2 horas) | y repaso laboratorio (6 horas) | |||
Semana 13 | Tablas de dispersión | Laboratorio | Estudio teoría | |||
(10 horas) | (2 horas) | (2 horas) | y repaso laboratorio (6 horas) | |||
Semana 14 | Funciones finitas con dominio ordenado | Laboratorio | Estudio teoría | |||
(10 horas) | (2 horas) | (2 horas) | y repaso laboratorio (6 horas) | |||
Semana 15 | Arboles AVL, (2,4) y B | Estudio teoría | ||||
(10 horas) | (2 horas) | y repaso laboratorio (8 horas) | ||||
Semana 16 | Revisión (2 horas) | Estudio teoría | ||||
(10 horas) | y repaso laboratorio (8 horas) | |||||
Semana de | Revisión para examen (7 horas) | Segundo examen de teoría | ||||
Examen | (1 hora) | |||||
(8-11 horas) | Examen final (3 horas) |
Nota: Para cada actividad se especifica la dedicación en horas que implica para el alumno.