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 2014-2015
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
Adriana Toni D-2310 atoni@fi.upm.es
Tonghong Li D-2312 tonghong@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 9 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:

  1. 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.

  2. 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:

  1. Sistema de evaluación continua.
  2. 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:

    1. 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.

    2. Parte de laboratorio: 9 ejercicios de laboratorio, no obligatorios.

      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.

      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 se publicará en la "Guía de Laboratorio" correspondiente. 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.

      Al comienzo de la sesión teórica posterior a cada sesión de laboratorio se comentará una solución correcta al mismo.

    Los alumnos que no hayan superado la asignatura pero hayan superado en convocatorias anteriores la parte de teoría no están obligados a repetir la parte superada. La nota obtenida en laboratorio se guardará igualmente para posteriores convocatorias.

  • 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: la nota de laboratorio obtenida por el alumno se guardará para siguientes convocatorias. 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, 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 pueden realizar un ejercicio de laboratorio en el Aula Informática de temática similar a los propuestos en el semestre. En caso de tener una nota de laboratorio guardada, obtenida en una convocatoria anterior, la perderán. 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 superada o la obtenida en laboratorio se guardarán para siguientes convocatorias.

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 Análisis y complejidad de algoritmos. de I2 a I4
1.2 Listas enlazadas y sus algoritmos. I1 I5 I6 I7 I8
1.2 Conjuntos e Implementaciones. I1 I5 I6 I7 I8
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, binarios y binarios de búsqueda. 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 AVL, de I1 a I9
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 (4 horas) y repaso Programación II
(4 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 Conjuntos, 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 binarios 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.