• 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

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

• Informaciones sobre la evaluación a la UOC

La Normativa académica de la UOC dispone que el proceso de evaluación se fundamenta en el trabajo personal del estudiante y presupone la autenticidad de la autoría y la originalidad de los ejercicios realizados.

La falta de originalidad en la autoría o el mal uso de las condiciones en las que se hace la evaluación de la asignatura es una infracción que puede tener consecuencias académicas graves.

El estudiante será calificado con un suspenso (D/0) si se detecta falta de originalidad en la autoría de alguna actividad evaluable (práctica, prueba de evaluación continua (PEC) o final (PEF), o la que se defina en el plan docente), ya sea porque ha utilizado material o dispositivos no autorizados, ya sea porque ha copiado de forma textual de internet, o ha copiado de apuntes, de materiales, manuales o artículos (sin la citación correspondiente) o de otro estudiante, o por cualquier otra conducta irregular.

La calificación de suspenso (D/0) en la evaluación continua (EC) puede conllevar la obligación de hacer el examen presencial para superar la asignatura (si hay examen y si superarlo es suficiente para superar la asignatura según indique este plan docente).

Cuando esta mala conducta se produzca durante la realización de las pruebas de evaluación finales presenciales, el estudiante puede ser expulsado del aula, y el examinador hará constar todos los elementos y la información relativos al caso.

Además, esta conducta puede dar lugar a la incoación de un procedimiento disciplinario y la aplicación, si procede, de la sanción que corresponda.

La UOC habilitará los mecanismos que considere oportunos para velar por la calidad de sus titulaciones y garantizar la excelencia y la calidad de su modelo educativo.

• Consulta del modelo de evaluación