• Descripción

A la hora de diseñar un programa suele ser muy importante su eficiencia, es decir, que consuma la menor cantidad de recursos para llevar a cabo su cometido. Así pues nos interesa minimizar el tiempo de cálculo, el espacio de memoria para almacenar los datos, el número de mensajes que deben enviarse a través de la red, la cantidad de energía que consumida, etc.

Dos herramientas fundamentales para conseguir esta eficiencia son las estructuras de datos y los esquemas algorítmicos:

• Las estructuras de datos se centran en cómo gestionar la información: son estrategias para organizar los datos de forma que se reduzca el tiempo de acceso y manipulación, así como el espacio de almacenamiento necesario.
• Los esquemas algorítmos se centran en el proceso de cálculo: son patrones generales que describen los pasos necesarios para alcanzar una solución y que deben particularizarse para el problema concreto a resolver.

Esta asignatura presenta los conceptos sobre estructuras de datos y algorítmica necesarios para realizar actividades de investigación. En particular, la asignatura revisa conceptos fundamentales de complejidad algorítmica (coste espacial y temporal, cálculo del coste de un algoritmo, órdenes de magnitud usuales) así como conceptos básicos de estructuras de datos (tipos abstractos de datos, gestión de apuntadores y memoria, etc). A partir de esta base, la asignatura profundiza en estructuras de datos frecuentas (pilas, colas, listas, árboles, heaps, tablas de hash) y presenta una introducción a algoritmos sobre grafos (recorridos, caminos mínimos, árboles generadores, etc.).

El máster ha tenido una modificación del plan de estudios para mejorar y actualizar los contenidos de las asignaturas. Esto hace que haya algunos cambios de creditaje en asignaturas que comparten aula y / o cambios de nomenclatura. En los casos que esto ocurre no se producen cambios sustanciales en los contenidos, aunque puede que se pida alguna actividad adicional para las asignaturas de 6 créditos.

• La asignatura en el conjunto del plan de estudios

Estructuras de datos y algoritmos es una asignatura optativa del Máster Interuniversitario en Ingeniería Computacional y Matemática.

Los conocimientos adquiridos en esta asignatura serán de utilidad en el desarrollo de prácticas en otras asignaturas del Máster. En particular, se recomienda cursar esta asignatura antes de cursar Optimización combinatoria.

• Campos profesionales en que se proyecta

Los conceptos adquiridos en esta asignatura son fundamentales para desarrollar software que utilice de forma eficiente los recursos de cálculo disponibles. Por este motivo, esta asignatura es relevante para cualquier trabajo relacionado con el diseño e implementación de software, especialmente en el campo del I+D o de la matemática aplicada.

• Conocimientos previos

Esta asignatura requiere conocimientos básicos de algorítmica: conocer las primitivas básicas de programación (bucles, condicionales, etc.) y comprender algoritmos descritos en pseudocódigo. También se requiere un conocimiento previo del lenguaje de programación orientado a objectos Java suficiente para escribir, ejecutar y testear programas.

Por otro lado, los materiales centrales de la asignatura están en inglés. Por este motivo, se recomienda tener un buen nivel de comprensión lectora de inglés técnico.

• Información previa a la matrícula

Antes de cursar esta asignatura, es necesario disponer de conocimientos previos de algorítmica y programación en Java y tener un buen nivel de inglés técnico a nivel de lectura.

• Objetivos y competencias

La competencias generales del Máster que se ponen de manifiesto en esta asignatura son:

• Comprender y poder aplicar conocimientos avanzados de computación y métodos numéricos o computacionales a problemas de ingeniería.
• Aplicar los métodos matemáticos y computacionales a la resolución de problemas tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación, desarrollo e innovación.
• Diseñar, implementar y validar algoritmos utilizando las estructuras más convenientes.

Las competencias específicas de esta asignatura son:

• Conocer el concepto de tipo abstracto de datos y saber definir un tipo abstracto de datos para un problema concreto.
• Conocer los tipos abstractos de datos secuenciales (pilas, colas, listas) y sus operaciones, y saber utilizarlos para resolver problemas.
• Conocer el concepto de complejidad asintótica, saber calcularla para un algoritmo dado y ser capaz de utilizarla para comparar dos algoritmos diferentes desde el punto de vista de su eficiencia.
• Conocer diferentes algoritmos de ordenación, sus ventajas e inconvenientes y saber elegir el más apropiado en un contexto concreto.
• Conocer diferentes estrategias de búsqueda de información (hashing, árboles de búsqueda), sus ventajas e inconvenientes y saber elegir la más apropiada en un contexto concreto.
• Conocer los principales algoritmos sobre grafos, su complejidad y ser capaz de utilizarlos para resolver problemas concretos.
• Ser capaz de elegir la estructura de datos más apropiada para un problema según criterios de eficiencia y justificar argumentadamente la decisión.

• Contenidos

La asignatura se estructura en cuatro bloques temáticos:

• Consulta de los recursos de aprendizaje que dispone la asignatura

• Recursos de aprendizaje y herramientas de apoyo

El material central de la asignatura es un libro de referencia en este ámbito: "Algorithms, 4th Edition", de Robert Sedgewick y Kevin Wayne. Tanto por extensión como por profundidad, los contenidos del libro van más allá de lo que se estudiará en la asignatura y os será útil como referencia durante vuestra carrera profesional.

Para guiar el estudio del libro y focalizar los contenidos relevantes del libro dentro de la asignatura, en el aula de la asignatura podréis encontrar guías de estudio semanales de los contenidos a estudiar cada semana con consejos sobre cómo revisar el material del libro.

A modo de material complementario, en el aula de la asignatura podréis encontrar módulos didácticos UOC titulados "Diseño de estructuras de datos". Estos materiales os pueden servir como apoyo para resolver dudas que podáis tener revisando el libro de la asignatura. Sin embargo, estos materiales se centran mucho en cómo están implementadas las estructuras de datos, mientras que en esta asignatura nos centraremos más en saber cómo utilizarlas y los criterios para elegir la más apropiada.

• Bibliografía y fuentes de información

Podéis encontrar más información en las siguientes referencias complementarias:

• Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. (2001). Introduction to Algorithms. Cambridge: MIT Press.
• Skiena, S.S. (1998). The Algorithm Design Manual. Berlin: Springer-Verlag.
• Goodrich, M; Tamassia, R. (2006), Data structures and algorithms in Java (4a ed). John Wiley and Sons.
• Collins, W. J. (2011). Data structures and the Java Collections Framework (3a ed). John Wiley and Sons.

• Metodología

El estudio de la asignatura se centra en los módulos didácticos y el material complementario que se proporciona a través del campus virtual. La dedicación que se estima para esta asignatura es de 25 horas por crédito ECTS, es decir, aproximadamente unas nueve horas semanales incluyendo todas las actividades relacionadas con el estudio (lectura de materiales, participación en el foro, resolución de ejercicios, etc.).

La metodología de trabajo se basa en el estudio detallado de los materiales del libro, guiados por una guía de estudio. Estos contenidos se trabajarán de forma eminentemente práctica y aplicada dentro de la evaluación continua. En las fechas que figuran en la tabla de Actividades de Evaluación del espacio del aula de Evaluación se enviará una colección de actividades que configurarán la evaluación continua.

Es muy recomendable consultar cualquier duda al profesor de la asignatura (o  a los compañeros) a través del foro (lo más recomendable), o bien, a través del buzón personal.

El seguimiento activo de los espacios del aula  (tablones, foro, planificación) es de primordial interés, dado que habitualmente se plantean dudas, se dan respuestas y se tratan temas relacionados con la materia de estudio.

Es importante intentar realizar un trabajo constante de estudio de los contenidos dado que esta es la vía habitual de asegurar el éxito para superar la asignatura. En este sentido van las propuestas de distribución temporal de aprendizajes incluidas en este documento y las otras que se puedan dar durante el curso.

• Consulta del modelo de evaluación

• Evaluación Contínua

La evaluación continua se ha diseñado para facilitar el seguimiento de la asignatura y la asimilación progresiva de las competencias. Está estructurada en cuatro Pruebas de Evaluación Continua (PEC), una por cada bloque temático, con las siguientes características:

La nota final de la evaluación continua se determinará en función de las calificaciones parciales obtenidas, la participación del estudiante en el foro y haber demostrado un dominio suficiente en los aspectos fundamentales de la asignatura durante el semestre.

Se considera que un estudiante sigue la evaluación continua cuando hace la entrega de como mínimo el 50% de las Pruebas de Evaluación Continua (PEC) que se proponen. En esta asignatura hay 4 PEC y por lo tanto: 

• Si un estudiante no entrega ningún PEC o entrega sólo una, la nota obtenida de la evaluación continua será una N.
• Si un estudiante entrega sólo dos o tres PECs, se hará la media considerando que las PEC no entregadas tienen una D. 
• Si el estudiante entrega las cuatro PEC, se hará la media normalmente.

Las fechas de publicación de los enunciados de las pruebas y de entrega de los ejercicios se pueden consultar en el calendario de la asignatura. Tendréis que entregar cada PEC dentro de los plazos establecidos.

El seguimiento correcto de la asignatura os compromete a realizar las actividades de la evaluación continua de manera individual y según las indicaciones que pauta este Plan Docente. En caso de que no sea así, la evaluación continua se os evaluará con una D.  En concreto: en caso de extrema similitud entre algún ejercicio de PEC de dos o más estudiantes que desacredite el hecho de haberla realizado individualmente, la nota final de AC será una D para todos ellos. Por otro lado, y siempre a criterio de los Estudios, el incumplimiento de este compromiso, puede suponer que no se os permita superar ninguna otra asignatura mediante evaluación continua ni en el semestre en curso ni en los siguientes.

• Evaluación final

Esta asignatura no tiene pruebas finales: sólo puede superarse mediante la evaluación continua. La nota final de la asignatura será directamente la nota de evaluación continua.

• Feedback

Podéis dirigir vuestras dudas generales sobre la asignatura (contenidos, evaluación, etc.) al foro del aula. Si tenéis dudas más individuales, los podéis plantear en el buzón personal del consultor.

El consultor también hará un seguimiento personalizado de la evaluación continua, revisarà todas las PEC entregadas y comentará de forma cualitativa a nivel grupal y/o individual la resolución. Estos comentarios os ayudarán a progresar en vuestro aprendizaje y a adquirir el conjunto de las competencias.