Algoritmos y Estructura de Datos

Guía de Aprendizaje – Información al estudiante

1 Datos Descriptivos

AsignaturaAlgoritmos y Estructura de Datos
MateriaDesarrollo de Software
DepartamentoLSIIS
responsable
Créditos ECTS6
CarácterObligatoria
TitulaciónGrado de Matemáticas e Informática
por la Universidad Politécnica de Madrid
CursoSegundo
EspecialidadNo aplica
Curso académico2013-2014
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
CG01Capacidad de resolución de problemas aplicando2
conocimientos de matemáticas, ciencias e ingeniería.
CG05Capacidad de abstracción, análisis y síntesis.2
CG06Capacidad para trabajar dentro de un equipo,2
organizando, planificando, tomando decisiones, negociando
y resolviendo conflictos, relacionándose, y criticando
y haciendo autocrítica.
CG10Capacidad 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 EspecificasNivel
CE07Conocer los cimientos esenciales y fundacionales de la
informática, subrayando los aspectos esenciales de la3
disciplina que permanecen inalterables ante el cambio
tecnológico.
CE09Capacidad de elegir y usar los métodos analíticos y3
de modelización relevantes, y de describir una solución
de forma abstracta.
CE11Comprender intelectualmente el papel central que tienen4
los algoritmos y las estructuras de datos, así como una
apreciación del mismo.
CE13Poseer destrezas fundamentales de la programación que4
permitan la implementación de los algoritmos y las
estructuras de datos en el software.
CE14Poseer 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.
CE43Capacidad para trabajar de forma efectiva como3
individuo, organizando y planificando su propio trabajo,
de forma independiente o como miembro de un equipo.

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 medianteCE13, CE144
librerías existentes de TADs.CE43
Todas las CG
RA2Resolver problemas algorítmicosCE07, CE09,4
no trivialesCE11, CE13,
CE43
Todas las CG
RA3Razonar sobre la complejidadCE07, CE09,2
algorítmicaCE11, CE13,
CE43
Todas las CG
RA4Razonar sobre la terminaciónCE07, CE09,2
de algoritmos y programas.CE11, CE13,
CE43
Todas las CG
RA5Usar y definir estructuras de datosCE07, CE09,4
eficientes y adecuadas a cadaCE11, CE13,
problemaCE14, CE43
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 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. 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í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 algoritmosLaboratorioEstudio teoría
(9 horas)(2 horas)(2 horas)y repaso.
(5 horas)
Semana 4Listas enlazadas,LaboratorioEstudio teoría
(9 horas)Complejidad de Algoritmos (2 horas)(2 horas)y repaso laboratorio (5 horas)
Semana 5Listas enalzadas, IteradoresLaboratorioEstudio 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ónRevisión para examen (7 horas)Primer examen de teoría
(10 horas)(2 horas)(1 hora)
Semana 8Árboles generales y binariosEstudio teroía
(10 horas)(2 horas)y repaso laboratorio (8 horas)
Semana 9Árboles generales, binarios y de búsquedaLaboratorioEstudio teoría
(10 horas)(2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 10Montículos y ordenaciónLaboratorioEstudio teoría
(10 horas)(2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 11Funciones finitasLaboratorioEstudio teoría
(10 horas)(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ónLaboratorioEstudio teoría
(10 horas)(2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 14Funciones finitas con dominio ordenadoLaboratorioEstudio teoría
(10 horas)(2 horas)(2 horas)y repaso laboratorio (6 horas)
Semana 15Arboles AVL, (2,4) y BEstudio teoría
(10 horas)(2 horas)y repaso laboratorio (8 horas)
Semana 16Revisión (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.