Algoritmos y Estructura de Datos

Guía de Aprendizaje – Información al estudiante

1 Datos Descriptivos

AsignaturaAlgoritmos y Estructura de Datos
MateriaProgramación
DepartamentoLSIIS
responsable
Créditos ECTS6
CarácterObligatoria
TitulaciónGrado de Ingeniería Informática
por la Universidad Politécnica de Madrid
CursoSegundo
EspecialidadNo aplica
Curso académico2012-2013
Semestre en el queAmbos (septiembre a enero y febrero a junio)
se imparte
Semestre principalSeptiembre a enero
Idioma en el queCastellano
se imparte
Página Webhttp://web3.fi.upm.es/AulaVirtual/course/view.php?id=272

2 Profesorado

NOMBRE Y APELLIDODESPACHOCorreo electrónico
Pablo Nogueira (Coord.)D-2304pnogueira@fi.upm.es
Manuel CarroD-3323mcarro@fi.upm.es
Lars-Ake FredlundD-2309lfredlund@fi.upm.es
Ricardo JiménezD-2313rjimenez@fi.upm.es
Tonghong LiD-2312tonghong@fi.upm.es
Marta PatiñoD-2313mpatino@fi.upm.es
Germán PueblaD-2305german@fi.upm.es

3 Conocimientos previos requeridos para poder seguir con normalidad la asignatura

Asignaturas superadasProgramación I y Programación II
Otros resultados deCapacidad de modelar y resolver matemáticamente
aprendizaje necesariosproblemas reales.

4 Objetivos de aprendizaje

CódigoCompetencias TransversalesNivel
CG-1/21Capacidad de resolución de problemas aplicando2
conocimientos de matemáticas, ciencias e ingeniería.
CG-2/CE45Capacidad para el aprendizaje autónomo y la actualización2
de conocimientos, y reconocimiento de su necesidad en el
área de la informática.
CG‐3/4Saber trabajar en situaciones carentes de información y2
bajo presión, teniendo nuevas ideas, siendo creativo.
CG-5Capacidad de gestión de la información.2
CG-6Capacidad de abstracción, análisis y síntesis.2
CG-7/8/9/Capacidad para trabajar dentro de un equipo,2
10/16/17organizando, planificando, tomando decisiones, negociando
y resolviendo conflictos, relacionándose, y criticando
y haciendo autocrítica.
CG19Capacidad para usar las tecnologías de la información y2
la comunicación.

LEYENDA: Nivel de adquisición 1: Bajo Nivel de adquisición 2: Medio Nivel de adquisición 3: Alto

CódigoCompetencias EspecíficasNivel
CE-6Comprender intelectualmente el papel central que tienen4
los algoritmos y las estructuras de datos, así como una
apreciación del mismo.
CE-8Poseer destrezas fundamentales de la programación que4
permitan la implementación de los algoritmos y las
estructuras de datos en el software.
CE-9Poseer las destrezas que se requieren para diseñar e4
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ódigoResultado de aprendizajeCompetenciasNivel de
asociadasadquisición
RA1Programar aplicaciones medianteCE-8, CE-94
librerías existentes de TADs.Todas las CG
RA2Resolver problemas algorítmicosCE-6, CE-84
no triviales.Todas las CG
RA3Razonar sobre la complejidadCE-6, CE-82
algorítmica.Todas las CG
RA4Razonar sobre la terminaciónCE-6, CE-82
de algoritmos y programas.Todas las CG
RA5Usar y definir estructuras de datosCE-6, CE-8,4
eficientes y adecuadas a cadaCE-9
problema.Todas las CG

5.2 Sistema de evaluación de la asignatura

5.2.1 Indicadores de logro

RefIndicadorRelación
con RA
I1Sabe elegir de entre varias opciones el TADRA5
más adecuado para resolver un problema.
I2Comprende las implicaciones prácticas de losRA3
diferentes niveles de complejidad asintótica.
I3Comprende y sabe calcular la complejidad asintóticaRA3
de algoritmos y programas.
I4Demuestra informalmente la terminación de unRA4
algoritmo o un programa.
I5Comprende el diseño de TADs relativamente avanzados.RA5
I6Es capaz de implementar TADs relativamente avanzados.RA5
I7Conoce las colecciones estándar de Java.RA1
I8Comprende y utiliza librerías de código de tamañoRA1
considerable que definen e implementan TADs avanzados.
I9Comprende y sabe aplicar algoritmos de búsquedaRA2
y de ordenación, generando código apropiado.
I10Comprende y sabe aplicar técnicas algorítmicasRA2
generando código apropiado.

5.2.2 Evaluación sumativa

Breve descripción deMomentoLugarPeso en la
las actividades evaluablescalificación
Exámenes de teoría2 en el semestreAulas de evaluación55%
(evaluación continua)
o 1 en el semestre
(evaluación prueba final)
Ejercicios de laboratorio10 en el semestreAula informática45%

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 abarca una parte del temario de teoría. La parte evaluada por un examen no será evaluada de nuevo por los otros exámenes dentro de la convocatoria ordinaria.

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

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

    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 este sistema de evaluación deberá comunicarlo mediante escrito firmado al coordinador de la asignatura en un plazo de 15 días naturales desde el comienzo de las clases.

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 la sección *Sistema de evaluación continua de esta guía.

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ítuloApartadoIndicadores
relacionados
Bloque 1:1.1 Conceptos de programación en JavaI1 I5 I6 I7 I8
TADs secuenciales ypara la abstracción de datos.
complejidad1.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 decolas con prioridad y ordenación.
prioridades,2.2 Árboles generales y binarios.de I1 a I9
ordenación, y árboles2.3 Montículos y ordenación.de I1 a I9
Bloque 3: Algoritmos3 Algoritmos básicos,I2 I3 I4 I8 I9 I10
y ordenaciónté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 y4.2 Tablas de dispersión.de I1 a I8
árboles4.2 Funciones finitas conde 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ÍAMétodo expositivo y estudio de casos.
CLASES DE PROBLEMASEjercicios de laboratorio.
Aprendizaje basado en resolución de problemas.
PRÁCTICASEjercicios de laboratorio más extensos.
Aprendizaje basado en resolución de problemas.
TRABAJOS AUTÓNOMOSEjercicios voluntarios.
TRABAJOS EN GRUPOEjercicios de laboratorio.
TUTORÍASAtención personalizada en
teoría y laboratorio.

9 Recursos didácticos

BIBLIOGRAFÍAM. 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 WEBSitio 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).
EQUIPAMIENTOAulas 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

SemanaActividades en AulaActividades enTrabajoTrabajoActividadesOtros
Aula InformáticaIndividualen Grupode Evaluación
Semana 1Conceptos de programación en JavaEstudio teoría
(8 horas)para la abstracción de datos (2 horas)y repaso Programación II
(6 horas)
Semana 2Conceptos de programación en JavaEstudio teoría
(8 horas)para la abstracción de datos (2 horas)y repaso.
(6 horas)
Semana 3Listas enlazadas y sus algoritmosEstudio teoría
(9 horas)(2 horas)y repaso.
(7 horas)
Semana 4Listas, Complejidad de AlgoritmosLaboratorioEstudio teoría
(9 horas)(2 horas)(2 horas)y repaso laboratorio (5 horas)
Semana 5IteradoresLaboratorioEstudio teoría
(9 horas)(2 horas)(2 horas)y repaso laboratorio (5 horas)
Semana 6Comparadores. Colas con prioridadLaboratorioEstudio teoría
(10 horas)(2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 7Colas con prioridad, ordenaciónLaboratorioEstudio teoría
(10 horas)(2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 8Árboles generales y binariosRevisión para examen (7 horas)Primer examen de teoría
(10 horas)(2 horas)(1 hora)
Semana 9Montículos y ordenación (2 horas)Estudio teoría
(10 horas)técnica divide y vencerás,y repaso laboratorio (8 horas)
Semana 10Algoritmos básicos,LaboratorioEstudio teoría
(10 horas)técnica divide y vencerás,(2 horas)y repaso laboratorio (6 horas)
ordenación por mezcla (2 horas)
Semana 11Ordenación por mezcla y ordenaciónLaboratorioEstudio teoría
(10 horas)rápida (2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 12Funciones finitas yLaboratorioEstudio teoría
(10 horas)Tablas de dispersión (2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 13Tablas de dispersión y funciones finitasLaboratorioEstudio teoría
(10 horas)con dominio ordenado (2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 14Árboles binarios de búsqueda yLaboratorioEstudio teoría
(10 horas)Árboles AVL (2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 15Árboles multicamino, (2,4), (a,b) y B.Estudio teoría
(10 horas)(2 horas)y repaso laboratorio (8 horas)
Semana 16Repaso (2 horas)Estudio teoría
(10 horas)y repaso laboratorio (8 horas)
Semana deRevisió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.