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

• 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 el 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 materiales de los que dispone la asignatura